We study efficient algorithms for realizing the first-order oracle complexity of optimization of
G-Lipschitz convex functions with respect to the
ℓq-norm over an
ℓp-ball of radius
R, where
1≤p,q≤∞. For
p<q, we obtain error
Op,q(GR/T1/p−(1/q−1/2)+) after
T oracle queries, efficiently realizing the nearly optimal rates of (MBG+26), thereby resolving the nonsmooth end of the COLT 2015 open problem (Guz15b). In particular, the rate is
O(GR/T) for Euclidean Lipschitzness over an
ℓ1-ball of radius
R (
p=1,q=2). Our solution consists of reducing convex Lipschitz optimization to the chasing nested convex sets problem in sublevel sets of an evolving bundle (LNN95; BBE+20): at each query we either find a point with low function value or we produce a deep cut in the current sublevel of the bundle, that we chase. The dichotomy between stability of selectors and forced movement by deep cuts bounds the number of iterations of the algorithm near optimally. For nested subsets of
RBpd, we introduce a novel notion of stable center whose movement is bounded by
Op,q(RT1−1/p+(1/q−1/2)+) in the
ℓq-norm after
T steps, which we show is nearly optimal in high dimensions. A Monte Carlo average of the proposed selector achieves near-optimal rates with high probability and can be implemented in polynomial time for our optimization algorithm in the real-arithmetic model.