arXiv CSopen access

Stable Movement for Nondual Lipschitz Convex Optimization: Efficiency and Nearly Optimal Oracle Rates

Stable Movement for Nondual Lipschitz Convex Optimization: Efficiency and Nearly Optimal Oracle Rates David Martı́nez-Rubio

[email protected]

IMDEA Software Institute, Madrid, Spain

arXiv:2609.20701v1 [math.OC] 17 Sep 2026

Cristóbal Guzmán

[email protected] Institute for Mathematical and Computational Engineering, Faculty of Mathematics and School of Engineering, Pontificia Universidad Católica de Chile, Santiago, Chile

Abstract 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, e p,q (GR/T 1/p−(1/q−1/2)+ ) after T oracle where 1 ≤ p, q ≤ ∞. For p < q, we obtain error O 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 e 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 RB dp , we introduce a novel notion of stable center whose movement e p,q (RT 1−1/p+(1/q−1/2)+ ) in the ℓq -norm after T steps, which we show is is bounded by O 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.

1. Introduction Lipschitz convex optimization is a classical and highly influential problem. Foundational algorithmic developments in this area include cutting-plane (NY83; Kha79), subgradient (Sho85), proximal (Mar70), and mirror descent methods (NY83). Each of these developments has played a key role in areas including theoretical computer science (GLS93), signal processing (BT09), and machine learning (BCN18), among others. In this work, we minimize a convex Lipschitz function on RB dp using a local first-order oracle, and the norm for measuring Lipschitzness need not agree with the domain norm: we measure Lipschitzness in the ℓq norm; here 1 ≤ p, q ≤ ∞. In this context, Guzmán [Guz15b] asked for the high-dimensional minimax complexity of this problem, as well as its Hölder-smooth analogues (Guz15b; GN15). The classical case p ≥ q or p ≥ 2 was already understood up to logarithmic factors, since mirror descent algorithms are known to be near . Most non-local notation in this work links to its definition, using this code; for example, G links to its definition as the Lipschitz constant in ∥·∥q for the optimization problem we consider in this work. © D. Martı́nez-Rubio & C. Guzmán.

Martı́nez-Rubio Guzmán

optimal in those regimes1 . The open regime is p < min{q, 2}, where the feasible set is much smaller than the ball suggested by the regularity norm. At the nonsmooth endpoint with p < q, the predicted high-dimensional rate is:   GR e   , Θ (1) 1 1 1 − − p q 2 + T e where (·)+ = max{0, ·}. For (p, q) = (1, 2), this is Θ(GR/T ). The rate is faster than the previously known bounds with efficient algorithms, which were given √ by mirror descent, where the fastest known rate in the most benign geometries is O(1/ T ). Martı́nez-Rubio et al. [MBG+26] showed these oracle rates were attainable albeit with an information theoretical analysis that yielded an algorithm with exponential runtime; see also the references therein. The positive results in the aforementioned paper motivated the present work. An independent work (Ouy26) appeared on arXiv as we prepared the writing of our results. The work studies the specific case of quadratics when (p, q) = (1, 2), linked to the smooth end of the open problem in (Guz15b). It contains an idea that we had also used, about splitting coordinates into a head (their absolute value is large enough) and a tail (the rest), which we analyze more generally. (see Lemma 8). Our solution involves the chasing nested convex sets problem (BBE+20; ABC+19; Sel20). It consists of an online game where at each round an adversary selects a convex set K t and a player selects a point in it z t ∈ K t , while the sets are nested K t+1 ⊆ K t ⊆ · · · ⊆ K 0 and the initial point z 0 ∈ K 0 is fixed. The aim usually to compare the movement cost PTis −1 of the player in some norm after T rounds, t=0 ∥z t − z t+1 ∥, relative to the movement of an offline strategy that knows K T inPadvance. For our purposes, we will actually look −1 ∥z t − z t+1 ∥ in absolute terms. For instance, at solely bounding the movement cost Tt=0 Bubeck et al. [BKL+20] show that for ℓ -norm, one can provide a strategy with movement 2 p bounded by O(ω(K 0 ) d log(T /ω(K 0 ))), where ω(K 0 ) is the mean width of K 0 and d is e the dimension, which results in O(1) movement in the unit ℓ1 ball. Previous studies focused mainly on cases where T ≫ d. In this work, we introduce new selectors that obtain improved and nearly dimension-independent movement bounds when T ≤ d, which is crucial for our high-dimensional problem. Our optimization algorithm is inspired by the two-level bundle method of Lemaréchal, Nemirovskii, and Nesterov [LNN95], but we make a direct connection to the problem of chasing nested convex bodies and reduce the optimization problem to it. The idea is simple and elegant. After t queries (xi )i≤t and oracle answers (f (xi ), g i ) where g i ∈ ∂f (xi ), let mt (x) = max{f (xi ) + ⟨g i , x − xi ⟩},

ℓt ≤ min mt (x),

i≤t

x∈Q

U t = min f (xi ). i≤t

Here ℓt is a certified lower bound maintained by Algorithm 1. Convexity gives ℓt ≤ minx f (x) ≤ U t . We run the algorithm in phases. Freeze the gap Γ = U − ℓ and two levels 1. The case p ≥ 2 when p < q was also stated as an open question (Guz15b). However, the lower bound is attained by an instance of mirror descent. Indeed, notice that Gq -Lipschitz function in ℓq is also Gq -Lipschitz in ℓp . In fact the best Lipschitz constant Gp in the ℓp geometry can be Gp ≪ Gq . Hence, for p ≥ 2, running mirror descent over RB dp and using the ℓp geometry gives a rate of O(RGp /T 1/p ), which is no larger than the requested rate O(RGq /T 1/p ).

2

Stable Movement for Nondual Lipschitz Convex Optimization

h− = ℓ+Γ/4 < h+ = ℓ+3Γ/4, and query a stable selector z t ∈ K t := {x ∈ Q : mt (x) ≤ h− }. If f (z t ) ≤ h+ , the upper bound improves by a constant fraction. Otherwise the new tangent at (x) = f (z t ) + ⟨g t , x − z t ⟩ gives K t+1 = K t ∩ {at ≤ h− }. Since ∥g t ∥q∗ ≤ G, this retained halfspace is at ℓq -distance at least (h+ − h− )/G = Γ/(2G) from z t . Thus every such deep cut forces movement of the selector, P unless the new body is empty; see Figure 1. An upper bound on the total movement Tt=1 ∥z t − z t+1 ∥q after T steps coming from the chasing convex bodies problem along with the fact that the movement is lower bounded by T · Γ/(2G) gives a maximum number of steps until the certified lower bound increases by at least Γ/8 or we have f (z t ) ≤ h+ . Either way, we decrease the gap by a constant factor and continue to the next phase. Since certifying emptyness of a set can be computationally challenging, in the actual algorithm, we can in fact stop before seeing an empty sublevel set, if we can certify that an estimate for the minimum of the current bundle increased enough with respect to the previous one, cf. Line 7 of Algorithm 1. a2

f (z 2 )

a0 h+

h−

≥ Γ/(2G)

K3 a1

old K2 z2

Figure 1: A one-dimensional section of a step where the function value is no less than h+ (null step). The old model max{a0 , a1 } lies below h− at z 2 (that is, z 2 ∈ K 2 ), whereas the new tangent satisfies a2 (z 2 ) = f (z 2 ) > h+ . Adding a2 reduces the (h− )-sublevel to the thick black segment (K 3 ⊂ K 2 ), separated from z 2 by at least Γ/(2G) as the subgradient norm is no larger than G. Recall that Γ is the duality gap at the beginning of a phase.

Contributions.

The paper has three modular pieces.

1. For chasing nested convex subsets of B dp , with movement measured in the ℓq -norm, we prove that the optimal movement for the chasing nested convexbodies problem over  1− 1 + 1 − 1   e p,q T p q 2 + for p < q in T requests, up to logarithmic factors in d and T , is Θ the high-dimensional regime T ≤ d. 2. We reduce Lipschitz convex optimization to nested convex-body chasing in Proposition 5, where we still get the optimization rate even if we allow for computing inexact versions of stable selectors, cf. Lemma 6. 3

Martı́nez-Rubio Guzmán

3. We compute a selector that succeeds with high probability and runs in polynomial time for our case in Algorithm 1 with sets consisting of B dp intersected with halfspaces. Combined with the reduction gives our main result (Theorem 3): an efficient algorithm attaining the rates of (MBG+26) and resolving the nonsmooth ℓp /ℓq case of the COLT 2015 open question (Guz15b) efficiently.2 Every implemented query is feasible. Our polynomial-time optimization guarantees use the real-arithmetic and sampling model in Theorem 12. 1.1. Online learning and online-to-batch In online learning with convex functions, the mirror descent algorithm updates the current point using a subgradient of the observed loss and a Bregman penalty for moving away from that point (NY83; BT03). With a suitable regularizer, it achieves nearly minimax regret for a broad class of convex online learning problems (SST11). This universality does not imply that ordinary regret bounds recover every optimal rate for minimizing one fixed convex function. The obstruction is already one-dimensional. It concerns reductions through ordinary cumulative regret uniformly over adversarial linear losses; it does not rule out every online-inspired construction. Indeed, the classical Rademacher lower bound already applies to the one-coordinate linear losses ℓt (x) = Gεt x1 on RB dp , where the signs εt are independent and uniform on {−1, 1}, independently of the learner’s randomness. For every possibly randomized learner choosing xt , ordinary cumulative regret satisfies RegT :=

T X t=1

ℓt (xt ) − min

u∈RB dp

T X

ERegT ≥ GR E

ℓt (u),

t=1

T X

√ εt = Ω(GR T );

t=1

see, for example, Abernethy et al. [AAB+09, Section 7.1] and Cesa-Bianchi and Lugosi [CL06]. Consequently, a standard adversarial-regret bound followed by the ordinary online√ to-batch conversion cannot certify o(GR/ T ). We note that the worst-case complexity of mirror descent for optimization does not necessarily have to follow that of the worst-case example in the adversarial case along with online-to-batch conversion, but this argument √ provides some evidence that the algorithm may not be able to improve over O(1/ T ) under the general assumptions considered in this work. We also note that precisely√the open regimes in (1) are the ones where the convergence would be faster than O(1/ T ), e including the fastest rate of O(1/T ) when p = 1, q ≥ 2. This classical barrier allows adversarial losses that need not be affine tangent lower bounds of one fixed convex objective. Our method exploits this additional consistency: all cuts accumulate into a single lower model. 1.2. Nested convex-body chasing and absolute movement Fix a norm ∥·∥ on Rd . In convex-body chasing, theP player starts at x0 , sees a convex request K t , and then chooses xt ∈ K t , paying movement Tt=1 ∥xt − xt−1 ∥. After T iterations, the 2. Note that the lower bounds in the open question are only applicable to deterministic algorithms (Guz15a; Guz15b), while our efficient algorithm is randomized. However, the analogous lower bounds also hold against randomized algorithms, using the same constructions and by following arguments from (BGP17), as we show in Appendix G.

4

Stable Movement for Nondual Lipschitz Convex Optimization

competitive benchmark is the minimum of the same normed path length over all yt ∈ K t with y0 = x0 , where the offline path may use the entire request sequence in advance. An algorithm is C-competitive if its movement is at most C times this clairvoyant optimum. This problem was introduced by Friedman and Linial [FL93]. For the nested problem, where K t ⊂ K t−1 for all t, Bansal et al. [BBE+20] first proved a finite dimension-dependent competitive ratio, quantitatively 6d (d!)2 . Argue et al. [ABC+19] improved this to O(d log d) in every normed space, nearly matching √ the Ω(d) lower bound d in ℓ∞ . In Euclidean space, Bubeck et al. [BKL+20] obtained O( d log d) and showed that the memoryless rule which follows the Steiner point has the horizon-sensitive bound √ O(min{d, d log T }), where T is the number of requests. The Steiner point is a classical selector belonging to the requested body; its support-function representation makes it stable under Hausdorff perturbations, and it was known to have the optimal Euclidean HausdorffLipschitz constant and the property that the Steiner point of a Minkowski sum is the sum of the Steiner points. Building on this idea, Sellke [Sel20] introduced a functional Steiner point and a corresponding potential, extending the approach to non-nested convex-body chasing. They obtained competitive ratio d for convex bodies √ and d + 1 for convex functions in an arbitrary d-dimensional normed space, with an O( d log T ) Euclidean refinement. The classical Ω(d) lower bound in ℓd∞ establishes optimality when T ≥ d. For our high-dimensional optimization results, we study the regime T ≤ d. Our reduction for optimization, Proposition 5, requires an absolute movement bound, regardless of the offline comparator’s √ cost. This distinction matters even for short horizons: Proposition 1 gives ratio at least T /2 for Euclidean movement in B dp , 1 ≤ p ≤ 2, in high dimension d ≥ T , whereas the movement can be of lower order. In fact in Theorem √ 2, we show for our regimes of interest p < min{q, 2} a movement bound that is lower than T and it is as e small as O(1) when p = 1 and q ≥ 2. We note that for the same norm ∥·∥ used to charge movement, if we have B ∥·∥ = {x : ∥x∥ ≤ 1}, then up to universal constants, an F (d, T )-competitive nested-chasing algorithm is equivalent to an algorithm whose movement is O(F (d, T )r) whenever K 1 ⊆ x0 + rB ∥·∥ . Equivalently, one may require this movement bound only until the first time that K t is contained in a translate of (r/2)B ∥·∥ (ABC+19, Claim 1.4). However, our case is different. The requests lie in RB dp , but movement is measured in ℓq , which need not match the containing geometry. And we seek an absolute movement bound for our optimization algorithms. We start by showing some lower bounds on competitive ratio and movement bounds, that illustrate this phenomenon. Proposition 1 (Movement and competitive ratio lower bounds in ℓq ) [↓] Fix 1 ≤ p ≤ q ≤ ∞, T ≥ 1, d ≥ 2T , and R > 0. Starting from x0 = 0, an adaptive adversary can generate nonempty compact convex requests RB dp = K 0 ⊇ K 1 ⊇ · · · ⊇ K T that force every possibly randomized online selector to incur ℓq movement T X R ∥xt − xt−1 ∥q ≥ √ T 1−1/p+(1/q−1/2)+ , 2 t=1

while the offline optimum in ℓq is at most RT 1/q−1/p , so the competitive ratio is at least T 1−1/ max{q,2} = T 1−1/q+(1/q−1/2)+ . 5

Martı́nez-Rubio Guzmán

For p < q, the movement lower bound in Proposition 1 matches the power of T in our movement upper bounds of Theorem 2, up to logarithmic factors. The classical Steiner point has been used as an important selector for chasing convex bodies, and it consists of averages of support points over directions. Our proposed selector, in (14), instead averages minimizers of a different regularized objective. The regularization allows movement bounds adapted to RB dp , the q-norm and the horizon T , avoiding the poly(d) dependence in the classical selectors like the Steiner point when T ≤ d. For 2 ≤ p < q, we note that a simple selector based on minimizing the ℓp -norm (see (10)) provides movement bounds matching the lower bound of the previous proposition. The intuition behind it is in connection to why mirror descent works: a uniformly convex potential function trades-off movement with the potential. Similarly for the original algorithm in Lemaréchal, Nemirovskii, and Nesterov [LNN95] for p = q = 2. However, it √ seems this technique is only able to achieve O( T ) movement at best. For p < 2, our novel center in (14) gives the smaller power required by the domain and movement norms, see Theorem 9.

2. Setting and main results We write ei for the i-th standard basis vector. The ambient space is Rd . The parameters p, q ∈ [1, ∞] specify the domain and regularity norms, respectively; the domain is Q = RB dp . We write f for the convex objective and f ⋆ = minx∈Q f (x) for its constrained minimum. For r ∈ [1, ∞], we use the convention 1/∞ P = 0 and let r∗ be its conjugate exponent, so that 1/rP + 1/r∗ = 1. Let the norm ∥x∥r = ( i |xi |r )1/r for finite r, and ∥x∥∞ = maxi |xi |; ⟨x, y⟩ = i xi yi . Write n o B dr = x ∈ Rd : ∥x∥r ≤ 1 ,

and B dr (a, R) = a + RB dr . We use 1A for the indicator of an event A and distr (x, S) = inf y∈S ∥x − y∥r , with inf ∅ = ∞. We write P and E for probability and expectation. A first-order oracle for a convex G-Lipschitz function in ℓq returns f (x) and a subgradient g ∈ ∂f (x) with ∥g∥q∗ ≤ G; thus f (y) ≥ f (x) + ⟨g, y − x⟩ for every y ∈ Q. Throughout, e p,q additionally omits factors Op,q allows constants depending on fixed norm parameters; O polynomial in logarithms of d, T , and of the inverse failure probability δ ∈ (0, 1) and target error ε > 0. Similarly for Ω(·) and Θ(·) notations. Unless indicated otherwise, Z ∼ N (0, I d ) is a standard Gaussian vector, where I d is the identity matrix. Formally, the nested convex body chasing in RB dp is the following problem. For a horizon T , nonempty compact convex requests arrive in a nested sequence RB dp ⊇ K 0 ⊇ K 1 ⊇ · · · ⊇ K T , and a selector chooses P −1z t ∈ K t for every 0 ≤ t ≤ T . We measure its performance by the total ℓq -movement Tt=0 ∥z t+1 − z t ∥q and seek bounds that hold uniformly over every such sequence. Our main results are summarized in the following two theorems. Theorem 2 (Movement over RB dp ) [↓] Fix 1 ≤ p < q ≤ ∞, let T ≥ 2, and fix a confidence parameter δ ∈ (0, 1). There is a deterministic selector which, for every nested sequence in RB dp , satisfies     T −1 X 1− p1 + 1q − 21 e + ∥z t+1 − z t ∥q = Op,q RT . (2) t=0

6

Stable Movement for Nondual Lipschitz Convex Optimization

A Monte Carlo approximation achieves the same movement bound with high probability, which we can implement in polynomial time for nested requests generated by Algorithm 1. The exact selectors are the Gaussian center in (14) for p < min{q, 2} and the energy selector in (15) for 2 ≤ p < q. For p < min{q, 2} and bodies generated by Algorithm 1, Theorem 12 gives polynomial-time feasible approximations. The following matches the high-dimensional lower bounds of Guzmán [Guz15b]; see also (Guz15a). The match is up to logarithmic factors. The computational time is polynomial in the real-arithmetic model where arithmetic, comparisons, rational powers, logarithms, and independent scalar standard Gaussian draws have unit cost. The degree can depend on p and q, cf. Theorem 12. Theorem 3 (Nonsmooth ℓp /ℓq optimization) [↓] Fix 1 ≤ p < min{q, 2} with q ≤ ∞. Let f : Rd → R be convex and G-Lipschitz in ∥·∥q , T ≥ 2, and fix δ ∈ (0, 1). There is a polynomial-time algorithm in the real-arithmetic model, using at most T first-order queries returning a feasible point x bT such that with probability at least 1 − δ   GR e f (b xT ) − min f (x) = Op,q . (3) x∈RB dp T 1/p−(1/q−1/2)+ As mentioned in the introduction, the remaining cases, p ≥ q and 2 ≤ p < q, are already solved optimally up to logarithmic factors by mirror descent (NY83; NN85). For p ≥ q, e p,q (GRd1/q−1/p /T 1/ max{2,q} ) if we the q-radius of RB dp is at most Rd1/q−1/p , giving error O use mirror descent on the ℓq geometry. For 2 ≤ p < q, G-Lipschitzness in ℓq implies Ge p,q (GR/T 1/p ). The Lipschitzness in ℓp , so mirror descent in the ℓp geometry gives error O rest of the paper therefore focuses mostly on p < min{q, 2}, which in particular implies q > 1.

3. The modular two-level bundle algorithm After queries xi with subgradients g i , define the bundle model mt (x) := max {f (xi ) + ⟨g i , x − xi ⟩} . i≤t

(4)

Convexity gives mt ≤ f on Q = RB dp . Hence ℓt ≤ min mt (x) ≤ f ⋆ ,

U t := min f (xi ) ≥ f ⋆ . i≤t

x∈Q

Here ℓt is the certified lower bound maintained by Algorithm 1. Both bounds are monotonic in the useful directions. The algorithm retains ℓ until the stopping test in line 7 certifies an improvement. The algorithm proceeds in phases. During each phase it keeps two fixed levels between the current lower and upper bounds and queries a selector on a nested sequence of model sublevel sets. The phase ends when either bound improves by a constant fraction of the current gap, after which the levels and the selector are restarted. At the start of a phase, freeze Γ = U − ℓ,

1 h− = ℓ + Γ, 4 7

3 h+ = ℓ + Γ. 4

(5)

Martı́nez-Rubio Guzmán

Algorithm 1 Stable Movement Bundle Method Input: Q = RB dp , first-order oracle O for f , target ε, selector C, initial point x0 ∈ Q. 1: (f (x0 ), g) ← O(x0 ); initialize m(x) = f (x0 ) + ⟨g, x − x0 ⟩, U ← f (x0 ), xbest ← x0 , and ℓ ← f (x0 ) − 2GR. 2: while U − ℓ > ε do 3: Γ ← U − ℓ; h− ← ℓ + Γ/4; h+ ← ℓ + 3Γ/4; ℓ0 ← ℓ. 4: loop 5: K ← {x ∈ Q : m(x) ≤ h− }. 6: Get a, b ∈ R, y ∈ Q such that a ≤ minx∈Q m(x) ≤ m(y) ≤ b, and b − a ≤ Γ/32. 7: if a ≥ ℓ0 + Γ/8 then ℓ ← max{ℓ, a}; break endif. 8: z ← C(K) and (f (z), g) ← O(z). 9: if f (z) < U then xbest ← z endif ; U ← min{U , f (z)}. 10: m(x) ← max{m(x), f (z) + ⟨g, x − z⟩}. 11: if f (z) ≤ h+ then retain ℓ; break endif. 12: end loop 13: end while 14: return xbest .

The lower level defines the body to be chased; the upper level decides whether a query is a serious step. A query at z is a serious step if f (z) ≤ h+ , and a null step otherwise. Both add the returned affine lower bound to the bundle. A serious step ends the phase; a null step continues it unless the stopping test in line 7 certifies a lower-bound improvement of at least Γ/8. The fractions 1/4 and 3/4 are chosen only for simplicity; any fixed constants 0 < β < α < 1 also work. In the algorithm, O(x) = (f (x), g) is a first-order oracle, C(K) ∈ K is the chosen selector, and xbest stores a queried point attaining U . Lemma 4 (A null step is a deep cut) [↓] During a phase of Algorithm 1, with gap Γ and levels h− , h+ from (5), suppose the query at z returns g and f (z) > h+ . If g ̸= 0, then
f (z) − h− Γ distq z, {x : f (z) + ⟨g, x − z⟩ ≤ h− } = ≥ . ∥g∥q∗ 2G If the next body is nonempty, a null step forces the next center to move by at least Γ/(2G). Comparing this charge with the selector’s total movement bound limits the number of null steps in each phase. Proposition 5 (Movement-to-optimization reduction) [↓] Let p < q and 0 < ρ ≤ 1, and suppose an algorithm for chasing nested convex sets in RB dp , with movement measured in ℓq , satisfies, for every N , N −1 X

e RN 1−ρ . ∥z t+1 − z t ∥q = O

t=0

8

(6)

Stable Movement for Nondual Lipschitz Convex Optimization

Then, for every ε > 0, Algorithm 1 obtains certified error at most ε using the following number of first-order calls  1/ρ ! GR e 1+ T =O . (7) ε We now show that we can achieve the same oracle complexity if we have a good approximation to a sequence with the movement in (6). The optimization problem allows for errors that are absorbed without degrading the order of the optimization convergence, which helps providing a polynomial computational complexity. We show such a result in the following lemma. Lemma 6 (Oracle complexity under approximate centers) [↓] Let p < q and 0 < ρ ≤ 1. Within every phase of Algorithm 1, with fixed gap Γ and queried bodies K 0 ⊇ · · · ⊇ K N , suppose that (6) holds for reference centers z t ∈ K t and that the selector provides zbt ∈ K t satisfying Γ ∥b z t − z t ∥q ≤ , 0 ≤ t ≤ N. (8) 16G Then Algorithm 1 with selector sequence (b z t )t has oracle complexity (7). In the sequel, we show our movement bounds and efficient implementation in order to obtain an optimization algorithm via Algorithm 1.

4. Warm-up: the Steiner point in B d1 For a compact convex set K, its support function is defined as hK (θ) := supx∈K ⟨θ, x⟩, for θ ∈ Sd−1 . Here Sd−1 = {θ : ∥θ∥2 = 1} and µ is its uniform probability measure. The Steiner point is Z h i st(K) = d hK (θ)θ dµ(θ) = EZ∼N (0,I d ) argmax ⟨Z, x⟩ ∈ K, (9) Sd−1

x∈K

where feasibility holds because this is an average of points in K. The identity follows from the divergence theorem, see (PY89). We also define the mean-width of a compact set K as the average length of its one-dimensional projections: Z
ω(K) = hK (θ) + hK (−θ) dµ(θ). Sd−1

The following is an immediate consequence of the result in (BKL+20). Fact 7 (Steiner Euclidean movement) There is C > 0 such that for every T ≥ 1 and every nested sequence of convex bodies B d2 ⊇ K 0 ⊇ K 1 ⊇ · · · ⊇ K T ̸= ∅, s

T −1 X t=0

 2eT ∥st(K t+1 ) − st(K t )∥2 ≤ Cω(K 0 ) d log . ω(K 0 ) 9



Martı́nez-Rubio Guzmán

For an ℓp ball, duality gives ω(B dp ) = 2Eθ∼µ ∥θ∥p∗ . In particular, ω(B d1 ) = 2Eθ∼µ ∥θ∥∞ = p ∗ Θ( log(2d)/d), whereas, for every fixed 1 < p < 2, ω(B dp ) = Θp (d1/p −1/2 ). Since ω(K 0 ) ≤ e ω(B dp ) for K 0 ⊆ B dp , the width-sensitive term gives O(1) movement for p = 1, which in combination with Proposition 5 gives a rate that is optimal up to logarithmic factors. For fixed p not trivially close to 1, however, it gives a polynomial-in-dimension dependence, which is too large and suboptimal when T ≤ d, where the optimal movement is e p (T 1−1/p ); see Theorem 2 and Proposition 1 for Euclidean movement. Θ The expectation identity in (9) also gives a Monte Carlo implementation. With N samples per body, draw independent Z j , solve the linear optimization problems vj ∈ argmaxx∈K ⟨Z j , x⟩, and query the average N

1 X sbN (K) := vj . N j=1

Every query is in K. Hilbert-space concentration (the ℓ2 case of the argument in Proposition 11) gives the simultaneous error along a planned path, with probability at least 1 − δ, for sampling tolerance E > 0: ∥b sN (K t ) − st(K t )∥2 ≤ E,

0 ≤ t ≤ T.

for 0 < E ≤ 1, if we use N = O(E −2 log((T + 1)/δ)) samples per body when K t ⊆ B d1 . For the bundle application with Q = B d1 , q = 2, and 0 < ε < G, each body is the unit ℓ1 -ball intersected with stored affine halfspaces, so each sampled support point is obtained by a polynomial-size linear program. In the exact-subproblem model, the uniform sampling tolerance E = ε/(32G) satisfies the accuracy needed to keep the optimization rate, cf. Lemma 6, since every active phase has gap Γ > ε and Esol = 0. Combining e Fact 7 and Lemma 6 gives a planned budget of T = O(G/ε) first-order queries. With fresh samples at each query and total failure probability δ, the sample bound above requires N = 2 ) support-point solves per center, hence O((G/ε) 3 ) sampled linear programs in e e O((G/ε) total; the model-minimum computations add only O(T ) linear programs. Here the omitted factors are logarithmic in d, G/ε, and 1/δ. Thus, when G = 1, tolerance E = Θ(ε) suffices e −3 ) linear-program solves used, for a and the running time is dominated by that of the O(ε guarantee with success probability at least 1 − δ.

5. The general movement construction Now we construct a different stable selector in (14) in order to obtain near-optimal optimization convergence in all geometries in high dimensions. We first use the threshold decomposition in the following lemma. Large coordinates form an ℓ1 head while the remaining coordinates form a small tail in the movement norm. Lemma 8 (Head-tail containment) [↓] Let T ≥ 1, 1 ≤ p ≤ s ≤ ∞, τ = T −1/p , and x ∈ RB dp . Let ui = xi 1{|xi |>Rτ } , and v = x − u. One has ∥u∥1 ≤ R1 := RT 1−1/p ,

∥v∥s ≤ Rs := RT 1/s−1/p 10

and

RB dp ⊆ R1 B d1 + Rs B ds .

Stable Movement for Nondual Lipschitz Convex Optimization

Now assume 1 ≤ p < min{2, q} and set r = min{2, q},

Ld = ⌈log(2d + 2)⌉ ,

s=1+

1 . Ld

(10)

The ceiling and the shift inside the logarithm only avoid the degeneracy at d = 1 and make s rational. Thus 1 < s ≤ 2 and p < r ≤ 2. For a nonempty compact convex set K ⊆ RB dp , we use the lift Lp,q,T (K) = {(u, v) : u + v ∈ K, ∥u∥1 ≤ R1 , ∥v∥r ≤ Rr } . Define µ=

R2r = T 2/r−2 , R12

η=

R2r R √ = √ T 2/r−1/p−1 , R1 Ld Ld

(11)

(12)

and, for g ∈ Rd , let  (uK (g), v K (g)) =

argmin (u,v)∈Lp,q,T (K)

 µ 1 2 2 F g (u, v) := ∥v∥r + ∥u∥s − η⟨g, u⟩ 2 2

(13)

The lift is nonempty by Lemma 8, and the objective F g is strongly convex by Fact 15. Define the deterministic selector: Cp,q,T (K) = EZ∼N (0,I d ) [uK (Z) + v K (Z)].

(14)

Every sampled point lies in K, so the center lies in K as well. In the following, we show this selector is stable and later we show that we can approximate with high probability without sacrificing the order of this movement. Theorem 9 (Unified Gaussian movement for p < 2) [↓] Let 1 ≤ p < min{2, q}, r = min{q, 2} and consider (14). Every nested sequence in RB dp satisfies T −1 X

    1− p1 + 1q − 21 e + . ∥Cp,q,T (K t+1 ) − Cp,q,T (K t )∥q = Op,q RT

t=0

The objective in (13) handles both q < 2 and q ≥ 2. The function ∥u∥2s /2 has range at most R12 /2 on the head and is Ω(1/Ld )-strongly convex with respect to ∥·∥1 by Fact 16. Consequently, we control the total ℓ1 head movement with the value-budget bound in Lemma 17 in Appendix D. Gaussian integration by parts controls the same head increments in ℓ2 , while ∥v∥2r /2 controls the tail directly, see Appendix D. If q ≥ 2, monotonicity ∥·∥q ≤ ∥·∥2 finishes the head estimate. If q < 2, one interpolates the ℓ1 and ℓ2 estimates. In both cases, R1 T

1/r−1/2

√ = Rr T = RT

1− p1 +



1 − 12 q

 +

,

which gives the common power of T in Theorem 9. Approximating every center to ℓq error at most Ectr increases total movement by at most 2T Ectr , see Proposition 11. A Monte Carlo computation can realize such approximation with high probability, see Theorem 12. 11

Martı́nez-Rubio Guzmán

5.1. The p-energy center for 2 ≤ p < q We include this section for completeness since the movement bound was not known, to the best of our knowledge. But we recall that for optimization purposes, the case p ≥ 2 can be solved optimally using mirror descent algorithms. We will use Φp (x) = ∥x∥pp /p. For every nonempty compact convex set K, define its p-energy center by Cp (K) ∈ argmin Φp (x). (15) x∈K

Proposition 10 (p-energy center movement) [↓] Let 2 ≤ p < q ≤ ∞, Φp (x) = ∥x∥pp /p, and let RB dp ⊇ K 0 ⊇ K 1 ⊇ · · · ⊇ K T be nonempty compact convex nested sets. Let (z t )Tt=0 be defined by z t = Cp (K t ) in (15) Then T −1 X

∥z t+1 − z t ∥q = Op (RT 1−1/p ).

(16)

t=0

5.2. Feasible randomized implementation Let 1 ≤ p < min{2, q}, r = min{q, 2}, T ≥ 1, 0 < E ≤ R, and 0 < δ < 1. Let K 0 ⊇ · · · ⊇ K T be nonempty compact convex subsets of RB dp , possibly chosen adaptively. Given a numerical-solver tolerance Esol ≥ 0, choose the number of samples per body so that    T +1 r∗ 2 N ≥ Cr (R/E) + (R/E) log , (17) δ where Cr > 0 depends only on r. After K t is known, draw N fresh independent standard Gaussian vectors Z t,1 , . . . , Z t,N and let Y t,j = uK t (Z t,j ) + v K t (Z t,j ),

1 ≤ j ≤ N,

using the definitions in (13). Compute feasible numerical approximations and define the randomized selector zbt by Yb t,j ∈ K t ,

Yb t,j − Y t,j

q

≤ Esol , 1 ≤ j ≤ N ,

N

1 Xb zbt = Y t,j , N

0 ≤ t ≤ T.

j=1

Convexity of K t ensures zbt ∈ K t for every realization. Proposition 11 (Movement of the feasible randomized selector) [↓] In the setting above, choose R − 1 +( 1 − 1 ) E = Esol = T p q 2 + . 4 Then, with probability at least 1 − δ, T −1 X

  1 1 1 e p,q RT 1− p +( q − 2 )+ . ∥b z t+1 − zbt ∥q = O

t=0

12

(18)

Stable Movement for Nondual Lipschitz Convex Optimization

In a bundle phase with gap Γ from (5), the sampling and solver errors must satisfy E + Esol ≤ Γ/(16G).

(19)

This is the center tolerance required by Lemma 6. Since every active phase has Γ > ε, the tolerances in (19) and (32) and the sample count in (17) have polynomial dependence on inverse target accuracy for fixed p, q. Fresh samples are drawn after K t is known. Conditionally on the past, the body is fixed; a union bound therefore remains valid against an adaptive oracle. For the next theorem, we assume access to a local first-order oracle for f and a realarithmetic model in which arithmetic, comparisons, rational powers, logarithms, and independent scalar standard Gaussian draws have unit cost. Theorem 12 (Polynomial-time implementation) [↓] Fix 1 ≤ p < min{2, q}, q ∈ (1, ∞] and ε, δ ∈ (0, 1). Let f : Rd → R be convex and G-Lipschitz in ∥·∥q . There is a ran
e p,q 1 + (GR/ε)1/(1/p−(1/q−1/2)+ ) first-order domized implementation of Algorithm 1 using O oracle calls and polyp,q (d, 1 + GR/ε, log(1/δ)) additional real operations for minimization over RB dp . All queries and the output xbest belong to RB dp . With probability at least 1 − δ, it returns a certificate ℓ ≤ f ⋆ ≤ f (xbest ) ≤ ℓ + ε. The polynomial implementation comes from approximating the solution of the convex program by the ellipsoid algorithm, and the polynomial degree and constants depend only on p, q. We did not attempt to optimize the polynomial in the implementation and just used the ellipsoid method for simplicity in order to provide a polynomial-time algorithm. The complexity of our ellipsoid method depends critically on inner and outer balls for the feasible domain. Our proof certifies quantifiable bounds on the queried bodies. Subproblem implementation. The body K is an ℓp ball intersected with stored affine halfspaces, so it has an explicit separation oracle. The lower bound minQ m is a convex epigraph problem. A planned phase horizon is found by doubling until the phase-length bound in (20) would be violated; that contradiction forces the phase to terminate. The Monte Carlo construction preceding Proposition 11 uses the phase tolerance in (19) and remain feasible by convexity. Algorithm 1 uses certified model-minimum bounds and the stopping test in line 7. Proposition 5 analyzes selectors with a movement bound, and Lemma 6 allows approximate centers. For p < min{2, q}, the convex subproblems can be solved in polynomial time by Theorem 12.

6. Discussion This work provides the first polynomial-time guarantee with nearly optimal oracle complexity for Lipschitz convex optimization in the ℓp /ℓq setting when p < min{q, 2}, answering positively the nonsmooth end of a question raised in (Guz15b). This result also shows that the minimax rates established in (MBG+26) can be efficiently attained for ℓp /ℓq settings. Attaining these rates requires genuinely new techniques, particularly departing from the regret minimization approaches that seem to be unable to leverage the additional structure of the feasible domain in nondual optimization settings. 13

Martı́nez-Rubio Guzmán

We believe our reduction from chasing convex sets to convex optimization to be of independent interest and we hope for this newly found connection to convex optimization to be fruitful. We also initiated the study of movement bounds in the high-dimensional setting where the number of steps T is no larger than the dimension d, a setting that is scarcely the focus of study in online algorithms. For fully resolving the open question in (Guz15b) the oracle complexity of the entire spectrum of Hölder-smooth settings should be considered. This extension will be addressed in a forthcoming work under preparation.

14

Stable Movement for Nondual Lipschitz Convex Optimization

Acknowledgements David Martı́nez-Rubio was funded by grant La Caixa Junior Leader Fellowship 2025. He thanks OpenAI for free access to their models. Cristóbal Guzmán was partially funded by ANID FONDECYT 1251029 grant, and ANID Basal FB210017 National Center for Artificial Intelligence CENIA. This work was elaborated in combination with ChatGPT/Codex versions 5.5 and 5.6 (the newest models when we worked on the main results), that helped in a few places after a highly interactive workflow. Most of the main ideas were from the authors (adapting the bundle method from (LNN95), connection to chasing nested convex bodies along with deep cuts, studying low dimensional movement bounds, head and tail decomposition,...), while AI was used to accelerate computations, to quickly close fruitless directions, doing checks and elaboration of some proofs. In particular, an initial version of the Gaussian movement analysis was fully done by AI. The authors checked and rewrote the proofs that were automated, simplifying the presentation and making the main ideas more transparent. In particular, they are solely responsible for the contents of this manuscript.

References [AAB+09]

Jacob Abernethy, Alekh Agarwal, Peter L. Bartlett, and Alexander Rakhlin. A Stochastic View of Optimal Regret through Minimax Duality. 2009 (cit. on p. 4).

[ABC+19]

C. J. Argue, Sébastien Bubeck, Michael B. Cohen, Anupam Gupta, and Yin Tat Lee. A Nearly-Linear Bound for Chasing Nested Convex Bodies. In: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms. 2019, pp. 117–122 (cit. on pp. 2, 5).

[BBE+20]

Nikhil Bansal, Martin Böhm, Marek Eliáš, Grigorios Koumoutsos, and Seeun William Umboh. Nested Convex Bodies are Chaseable. In: Algorithmica 82.6 (2020), pp. 1640–1653 (cit. on pp. 1, 2, 5).

[BCL94]

Keith Ball, Eric A. Carlen, and Elliott H. Lieb. Sharp Uniform Convexity and Smoothness Inequalities for Trace Norms. In: Inventiones Mathematicae 115.1 (1994), pp. 463–482 (cit. on p. 18).

[BCN18]

Léon Bottou, Frank E Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning. In: SIAM review 60.2 (2018), pp. 223–311 (cit. on p. 1).

[Bec17]

Amir Beck. First-Order Methods in Optimization. Philadelphia, PA: Society for Industrial and Applied Mathematics, 2017 (cit. on p. 18).

[BGP17]

Gábor Braun, Cristóbal Guzmán, and Sebastian Pokutta. Lower Bounds on the Oracle Complexity of Nonsmooth Convex Optimization via Information Theory. In: IEEE Transactions on Information Theory 63.7 (2017), pp. 4709– 4724 (cit. on pp. 4, 30–32).

[BKL+20]

Sébastien Bubeck, Bo’az Klartag, Yin Tat Lee, Yuanzhi Li, and Mark Sellke. Chasing Nested Convex Bodies Nearly Optimally. In: Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms. 2020, pp. 1496–1508 (cit. on pp. 2, 5, 9). 15

Martı́nez-Rubio Guzmán

[BT03]

Amir Beck and Marc Teboulle. Mirror descent and nonlinear projected subgradient methods for convex optimization. In: Oper. Res. Lett. 31.3 (May 2003), pp. 167–175. issn: 0167-6377 (cit. on p. 4).

[BT09]

Amir Beck and Marc Teboulle. A fast iterative shrinkage-thresholding algorithm for linear inverse problems. In: SIAM Journal on Imaging Sciences 2.1 (2009), pp. 183–202 (cit. on p. 1).

[CL06]

Nicolò Cesa-Bianchi and Gábor Lugosi. Prediction, Learning, and Games. Cambridge University Press, 2006 (cit. on p. 4).

[Cla36]

James A. Clarkson. Uniformly Convex Spaces. In: Transactions of the American Mathematical Society 40.3 (1936), pp. 396–414 (cit. on p. 18).

[FL93]

Joel Friedman and Nathan Linial. On Convex Body Chasing. In: Discrete & Computational Geometry 9.3 (1993), pp. 293–321 (cit. on p. 5).

[GLS93]

Martin Grötschel, László Lovász, and Alexander Schrijver. Geometric Algorithms and Combinatorial Optimization. 2nd ed. Springer, 1993 (cit. on pp. 1, 27).

[GN15]

Cristóbal Guzmán and Arkadi Nemirovski. On Lower Complexity Bounds for Large-Scale Smooth Convex Optimization. In: Journal of Complexity 31.1 (2015), pp. 1–14 (cit. on p. 1).

[Guz15a]

Cristóbal Guzmán. “Information, Complexity and Structure in Convex Optimization”. PhD dissertation. Georgia Institute of Technology, 2015 (cit. on pp. 4, 7, 30).

[Guz15b]

Cristóbal Guzmán. Open Problem: The Oracle Complexity of Smooth Convex Optimization in Nonstandard Settings. In: Proceedings of the 28th Conference on Learning Theory. Vol. 40. Proceedings of Machine Learning Research. PMLR, 2015, pp. 1761–1763 (cit. on pp. 1, 2, 4, 7, 13, 14, 30).

[Kha79]

Leonid Genrikhovich Khachiyan. A polynomial algorithm in linear programming. In: Doklady Akademii Nauk. Vol. 244. 5. Russian Academy of Sciences. 1979, pp. 1093–1096 (cit. on p. 1).

[LNN95]

Claude Lemaréchal, Arkadii Nemirovskii, and Yurii E. Nesterov. New variants of bundle methods. In: Math. Program. 69 (1995), pp. 111–147 (cit. on pp. 1, 2, 6, 15).

[LT91]

Michel Ledoux and Michel Talagrand. Probability in Banach Spaces: Isoperimetry and Processes. Berlin: Springer, 1991 (cit. on p. 25).

[Mar70]

Bernard Martinet. Régularisation d’inéquations variationnelles par approximations successives. In: Revue Française d’Informatique et de Recherche Opérationnelle 4.R3 (1970), pp. 154–158 (cit. on p. 1).

[MBG+26]

David Martı́nez-Rubio, Brian Bullins, Cristóbal Guzmán, and Mathieu Molina. “The First-Order Oracle Complexity of Lipschitz Convex Optimization in Nondual Settings”. Manuscript. 2026 (cit. on pp. 1, 2, 4, 13, 30).

16

Stable Movement for Nondual Lipschitz Convex Optimization

[McD89]

Colin McDiarmid. On the Method of Bounded Differences. In: Surveys in Combinatorics, 1989. Ed. by Johannes Siemons. Cambridge University Press, 1989, pp. 148–188 (cit. on p. 26).

[MS04]

Shahar Mendelson and Gideon Schechtman. The Shattering Dimension of Sets of Linear Functionals. In: The Annals of Probability 32.3A (2004), pp. 1746– 1770 (cit. on pp. 30, 31).

[Nes18]

Yurii Nesterov. Lectures on Convex Optimization. 2nd. Vol. 137. Springer Optimization and Its Applications. Springer, 2018. isbn: 978-3-319-91578-4 (cit. on p. 18).

[NN85]

Arkadii S. Nemirovskii and Yurii E. Nesterov. Optimal Methods of Smooth Convex Optimization. In: USSR Computational Mathematics and Mathematical Physics 25.2 (1985), pp. 21–30 (cit. on p. 7).

[NY83]

Arkadi S. Nemirovski and David B. Yudin. Problem Complexity and Method Efficiency in Optimization. New York: Wiley, 1983 (cit. on pp. 1, 4, 7).

[Ouy26]

Yuyuan Ouyang. An O(1/T 3 ) Algorithm for Minimizing Convex Quadratic Functions over the L1 Ball . 2026 (cit. on p. 2).

[PY89]

Krzysztof Przeslawski and David Thomas Yost. Continuity Properties of Selectors and Michael’s Theorem. In: Michigan Mathematical Journal 36.1 (1989), pp. 113–134 (cit. on p. 9).

[Sel20]

Mark Sellke. Chasing Convex Bodies Optimally. In: Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms. 2020, pp. 1509–1518 (cit. on pp. 2, 5).

[Sho85]

Naun Zuselevich Shor. The Subgradient Method. In: Minimization Methods for Non-Differentiable Functions. Berlin, Heidelberg: Springer Berlin Heidelberg, 1985, pp. 22–47. isbn: 978-3-642-82118-9 (cit. on p. 1).

[SS12]

Nathan Srebro and Karthik Sridharan. On Convex Optimization, Fat Shattering and Learning. 2012 (cit. on p. 30).

[SST11]

Nathan Srebro, Karthik Sridharan, and Ambuj Tewari. On the Universality of Online Mirror Descent. In: Advances in Neural Information Processing Systems. Vol. 24. 2011 (cit. on p. 4).

[Zal02]

C. Zalinescu. Convex Analysis in General Vector Spaces. G - Reference,Information and Interdisciplinary Subjects Series. World Scientific, 2002. isbn: 9789812380678 (cit. on p. 18).

Appendix A. Facts About Strongly/Uniformly Convex Functions Here we summarize some classical facts about strongly convex and uniformly convex functions used in the proofs. Definition 13 Let (E, ∥ · ∥) be a normed space, K ⊆ E a closed convex set, and µ ≥ 0, 2 ≤ r < ∞. We say that Φ : K → R is (µ, r)-uniformly convex if for all 0 ≤ λ ≤ 1 and 17

Martı́nez-Rubio Guzmán

x, y ∈ K:

µ Φ (1 − λ)x + λy ≤ (1 − λ)Φ(x) + λΦ(y) − λ(1 − λ) λr−1 + (1 − λ)r−1 ∥y − x∥r . r We say that a function is µ-strongly convex if it is (µ, 2)-uniformly convex. A useful alternative characterization is as follows. The next result is a particular case of (Zal02, Corollary 3.5.11). Proposition 14 Let Φ : E → R be differentiable. Then Φ is (µ, r)-uniformly convex if and only if for all y, x ∈ E µ DΦ (y, x) ≥ ∥y − x∥r , r where DΦ (y, x) := Φ(y) − Φ(x) − ⟨∇Φ(x), y − x⟩ is the Bregman divergence. We summarize the uniform convexity properties of ℓdp = (Rd , ∥·∥p ) spaces, for 1 ≤ p < ∞. These results are classical in Analysis (Cla36; BCL94). Fact 15 1. If 1 < p ≤ 2, then the function Φp (x) := 21 ∥x∥2p is (p − 1)-strongly convex (see e.g. (Bec17, Example 5.28)). 2. If 2 < p < +∞, then the function Φp (x) = p1 ∥x∥pp is (22−p , p)-uniformly convex (see e.g., (Nes18, Lemma 4.2.3)). While the extreme cases p = 1, ∞ are not included above, the case p = 1 is known to have strongly convex functions with moderate growth. We provide the details below for completeness. Fact 16 (Near-strong convexity of ℓ1 -norm) Let s and Ld be as in (10). Then x 7→ 2 1 −2 2 ∥x∥s is e /Ld -strongly convex with respect to ∥·∥1 ; more precisely, D 1 ∥·∥2 (u′ , u) ≥ 2

s

s−1 ′ e−2 ′ 2 2 u −u s ≥ u − u 1. 2 2Ld

Moreover, 0 ≤ 21 ∥u∥2s ≤ R12 /2 whenever ∥u∥1 ≤ R1 . Proof By Fact 15, for any 1 < s ≤ 2, the squared ℓs norm is (s − 1)-strongly convex with respect to ∥·∥s . Since s − 1 = 1/Ld and   2(s − 1) 2/s−2 d = exp − log d ≥ e−2 , s we have (s − 1)d2/s−2 ≥ e−2 /Ld . Combining this with the norm comparison ∥x∥s ≥ d1/s−1 ∥x∥1 proves the second inequality. The range bound follows from ∥u∥s ≤ ∥u∥1 ≤ R1 .

18

Stable Movement for Nondual Lipschitz Convex Optimization

Appendix B. Movement lower bounds Proof of Proposition 1. We use signed coordinate cuts for q ≥ 2 and dense orthogonal directions for q < 2. In each case the final request contains an explicit point y. The offline player may move from 0 to y on the first request and stay there, so its cost is at most ∥y∥q . The case q ≥ 2. Let a = RT −1/p . After observing xt−1 , choose σt ∈ {−1, 1} so that σt xt−1,t ≤ 0, and reveal t \ d K t = RB p ∩ {x : σs xs ≥ a}. s=1

The point y = a satisfies

PT

s=1 σs es belongs to every request and has ∥y∥p = R.

Each transition

∥xt − xt−1 ∥q ≥ σt (xt,t − xt−1,t ) ≥ a. Thus the online movement is at least aT = RT 1−1/p . Every point of K T has its first T coordinates of absolute value at least a, so the offline optimum is exactly ∥y∥q = aT 1/q = RT 1/q−1/p , with T 1/∞ = 1. The competitive ratio is therefore at least T 1−1/q . The case p ≤ q < 2. Let n = 2⌈log2 T ⌉ , so T ≤ n < 2T and n ≤ d. We use normalized Hadamard vectors h1 , . . . , hT ∈ Rd : they are orthonormal, supported on √ the first n −1/2 1/2−1/p coordinates, and each of those coordinates equals ±n . Let a = Rn / T . After observing xt−1 , choose σt ∈ {−1, 1} with σt ⟨ht , xt−1 ⟩ ≤ 0, and reveal K t = RB dp ∩

t \

{x : σs ⟨hs , x⟩ ≥ a}.

s=1

√ P For y = a Ts=1 σs hs , orthonormality gives σs ⟨hs , y⟩ = a and ∥y∥2 = a T . Since y is supported on n coordinates and p ≤ 2, ∥y∥p ≤ n1/p−1/2 ∥y∥2 = R. Thus every request is nonempty. Moreover, ∥ht ∥q∗ = n1/2−1/q , also when q = 1. Hölder’s inequality and the choice of σt imply a ≤ σt ⟨ht , xt − xt−1 ⟩ ≤ n1/2−1/q ∥xt − xt−1 ∥q . Summing the transitions yields T X √ R ∥xt − xt−1 ∥q ≥ R T n1/q−1/p ≥ √ T 1/2+1/q−1/p . 2 t=1

On the other hand, the offline cost incurred by y is at most ∥y∥q ≤ Rn1/q−1/p ≤ RT 1/q−1/p . √ Comparing the two bounds before replacing n by T yields competitive ratio at least T . Both constructions depend only on previously observed points, so all inequalities hold for every realization of a randomized selector.

19

Martı́nez-Rubio Guzmán

Appendix C. Proof of the movement-to-optimization reduction Proof of Lemma 4. The halfspace is {x : f (z) + ⟨g, x − z⟩ ≤ h− }. If g = 0, then f (z) > h− makes the halfspace empty, so the claim is immediate. Suppose g ̸= 0. Let x ∈ {w : f (z) + ⟨g, w − z⟩ ≤ h− }. Note that 2 3 1 Γ = h+ − h− < f (z) − h− ≤ ⟨g, z − x⟩ ≤ ∥g∥q∗ ∥z − x∥q ≤ G∥z − x∥, 2 where the first equality uses the phase levels in (5), 1 uses the fact that f (z) > h+ , 2 uses that x lies on the halfspace defined above, and 3 uses Hölder’s inequality. Since x is arbitrary, we have proved the result. Proof of Proposition 5. Fix a target accuracy ε > 0. Consider a phase whose certified gap is Γ. If N consecutive null cuts leave the bodies nonempty, Lemma 4 and the assumed upper bound on movement give  1/ρ ! N −1 X Γ GR 1−ρ e e N . (20) ≤ ∥z t+1 − z t ∥q = O(RN ) =⇒ N = O 2G Γ t=0

The terminal query, either a serious step or a null step followed by a successful stopping test in line 7, adds at most one call; the test itself needs no first-order call. If the test fails, its certificate gives m(y) ≤ a + Γ/32 < ℓ0 + 5Γ/32 < h− , so every queried body is nonempty. It remains to verify that the certified gap contracts after the phase. Let ℓ and U denote the bounds at the start of the phase. If a serious step terminates the phase, then the updated bounds satisfy U new ≤ h+ = ℓ + 3Γ/4 and ℓnew ≥ ℓ, so U new − ℓnew ≤ 3Γ/4. If instead the stopping test in line 7 succeeds, then ℓnew = max{ℓ, a} ≥ ℓ+Γ/8, while U = ℓ+Γ, and hence, since U new ≤ U , U new − ℓnew ≤ 7Γ/8. The update is certified because a ≤ minQ m ≤ f ⋆ . Thus every phase contracts the certified gap by a factor of at most 7/8. A phase with 1/ρ ) calls, including its terminal query. The initialization e gap Γ therefore uses O((GR/Γ) ℓ = f (x0 ) − 2GR is certified because f is G-Lipschitz in ℓq and Q has ℓq diameter at most 2R when p < q. Thus Γ0 = 2GR. If ε ≥ 2GR, the initial certificate already gives the result. Otherwise, run Algorithm 1 with target ε. Every active phase has Γ > ε, and there are at most O(log(2GR/ε)) phases. Summing their costs and absorbing this logarithm into the 1/ρ ) oracle calls. At termination, U − ℓ ≤ ε and U is the value e notation gives O((GR/ε) e O(·) of the best queried point, so the returned point has error at most ε. Only transitions within a phase enter the null-step count. The first center of each phase adds one query. If global query movement is also recorded, transitions between phases cost at most 2R each in ℓq , adding O(R log(2GR/ε)) in total. Proof of Lemma 6. most 2GR. Every subsequent lower-bound update uses a ≤ minQ m ≤ f ⋆ , while U remains the best observed value. On the lower-bound branch, the new gap is at most 7Γ/8. On a serious step it is at most 3Γ/4, even without updating ℓ. If the stopping test in line 7 of Algorithm 1 fails, the certificate in 6 of Algorithm 1 gives m(y) ≤ b ≤ a + Γ/32 < ℓ0 + 5Γ/32 = h− − 3Γ/32, 20

Stable Movement for Nondual Lipschitz Convex Optimization

concluding that m(y) ≤ min m(x) + Γ/32,

m(y) < h− − 3Γ/32.

x∈Q

(21)

In particular, K is nonempty with a strict model-level margin. The sets remain nested during the phase. For N null transitions between queried centers, the actual movement is at least N Γ/(2G). For the queried points zbt and reference centers z t , set Ectr = max0≤t≤N ∥b zt − z t ∥q ≤ Γ/(16G). The triangle inequality then gives X NΓ ≤ ∥z t+1 − z t ∥q + 2N Ectr , 2G t<N

X 3N Γ ≤ ∥z t+1 − z t ∥q . 8G t<N

The reference-center movement bound in (6) therefore gives the phase-length estimate in (20), up to constants. To sum the per-phase bound in (20), let Γ0 , . . . , ΓJ−1 > ε be the active phase gaps. Since Γk+1 ≤ (7/8)Γk , J−1 X k=0

GR Γk

1/ρ

 ≤

GR ε

1/ρ J−1 X (GR/ε)1/ρ (7/8)j/ρ ≤ . 1 − (7/8)1/ρ j=0

The J = O(1 + log(1 + 2GR/ε)) terminal and initial-center calls are absorbed by the logarithmic factors, giving the oracle bound in Proposition 5. are O(R log N ) and are absorbed since 0 < ρ ≤ 1.

Appendix D. Geometry and value budgets for the general center Proof of Lemma 8. If p = ∞, then s = ∞, u = 0, and v = x, so the claims hold. Assume henceforth that p < ∞. For a head coordinate, |xi | > Rτ and 1 − p ≤ 0, hence |xi | = |xi |p |xi |1−p ≤ (Rτ )1−p |xi |p . For a tail coordinate and finite s ≥ p, |xi |s = |xi |p |xi |s−p ≤ (Rτ )s−p |xi |p . Since

p p −1/p , summation gives i |xi | ≤ R and τ = T

P

∥u∥1 ≤ Rτ 1−p = RT 1−1/p ,

∥v∥s ≤ Rτ 1−p/s = RT 1/s−1/p .

These are exactly R1 and Rs . For s = ∞, the tail bound follows directly from ∥v∥∞ ≤ Rτ = RT −1/p .

21

Martı́nez-Rubio Guzmán

D.1. Proof of the unified low-p movement bound For the program in (13), abbreviate ut (g) = uK t (g),

v t (g) = v K t (g),

mt (g) = F g (ut (g), v t (g)).

(22)

The increment in the optimal value is ∆t (g) = mt+1 (g) − mt (g).

(23)

Lemma 17 (Unified charge and value budget) For nested bodies K 0 ⊇ · · · ⊇ K T in RB dp , use the sample optimizers and value increments in (22) and (23), with parameters from (10) and (12). There is a universal constant c > 0 such that, for every g ∈ Rd , T −1

T −1

T −1

t=0

t=0

t=0

X r−1 X cµ X ∥v t+1 (g) − v t (g)∥2r + ∥ut+1 (g) − ut (g)∥21 ≤ ∆t (g) ≤ R2r + 2ηR1 ∥g∥∞ . 2 Ld Moreover, E

T −1 X

 ∆t (Z) ≤ E

t=0

T −1 X

!2 1/2 ∆t (Z)



≤ CR2r .

t=0

Proof Write wt = (ut (g), v t (g)). The Bregman divergence of F g is the sum of the divergences of its two squared norm terms; the linear perturbation contributes nothing. The lower and upper bounds follow from the single chain T −1

T −1

r−1 X cµ X ∥v t+1 (g) − v t (g)∥2r + ∥ut+1 (g) − ut (g)∥21 2 Ld t=0

t=0

1 ≤

T −1 X

−1 2 TX DF g (wt+1 , wt ) ≤ ∆t (g) = F g (wT ) − F g (w0 )

t=0

3 ≤

t=0

sup

F g (w) −

w∈Lp,q,T (K 0 )

inf w∈Lp,q,T (K 0 )

F g (w)

4 R2 µR2 1 ≤ r + + 2ηR1 ∥g∥∞ = R2r + 2ηR1 ∥g∥∞ . 2 2 Here 1 uses item 1 in Fact 15 and Fact 16. For 2 , the Bregman identity expresses ∆t (g) as DF g (wt+1 , wt ) + ⟨∇F g (wt ), wt+1 − wt ⟩; nestedness gives wt+1 ∈ Lp,q,T (K t+1 ) ⊆ Lp,q,T (K t ), so first-order optimality of wt gives ⟨∇F g (wt ), wt+1 − wt ⟩ ≥ 0. The inequality 3 uses w0 , wT ∈ Lp,q,T (K 0 ). Finally, 4 uses 0 ≤ ∥v∥r ≤ Rr , 0 ≤ ∥u∥s ≤ R1 , and |⟨g, u⟩| ≤ R1 ∥g∥∞ ; the last identity uses µR12 = R2r . The same first-order argument before summing gives ∆t (g) ≥ DF g (wt+1 , wt ) ≥ 0 for every t < T . This proves the first part. Finally,  !2 1/2 T −1 T −1 1/2 2 1 2  X X E ∆t (Z) ≤ E ∆t (Z)  ≤ 2(R2r )2 + 2(2ηR1 )2 E∥Z∥2∞ ≤ CR2r . t=0

t=0

22

Stable Movement for Nondual Lipschitz Convex Optimization

Here 1 follows from the Jensen inequality, and 2 uses the above derivation, nonnegativity of ∆t and Young’s inequality, and 3 uses the Gaussian maximum estimate E∥Z∥2∞ ≤ c log d, together with (12). Proof of Theorem 9. Let ūt = Eut (Z) and v̄ t = Ev t (Z). We first bound the tail and the head in the two norms used at the final interpolation step. Tail movement. give T −1 X t=0

Cauchy-Schwarz, Jensen’s inequality for the squared norm, and Lemma 17

v v u u T −1 T −1 u u 2T X X √ 2 t ∥v̄ t+1 − v̄ t ∥r ≤ T E ∥v t+1 (Z) − v t (Z)∥r ≤ t E ∆t (Z) ≤ Cr Rr T . (24) r−1 t=0

Head movement in ℓ1 . in Lemma 17, give

t=0

Cauchy–Schwarz and Jensen, applied as in (24) to the head term

v u −1 u T Ld TX p t ∆t (Z) ≤ CR1 T Ld . ∥ūt+1 − ūt ∥1 ≤ E cµ

T −1 X t=0

(25)

t=0

Here µ = R2r /R12 by (12). Head movement in ℓ2 . In (13), the only dependence of F g on g is the linear term −η⟨g, u⟩. For the optimal value mt in (22), uniqueness of the sample optimizer and Danskin’s theorem give ∇mt (g) = −ηut (g). Since ∥ut (g)∥2 ≤ R1 , each mt is ηR1 -Lipschitz. Thus ∆t is Lipschitz, and Gaussian integration by parts applies coordinatewise, yielding 1 1 ūt+1 − ūt = E[ut+1 (Z) − ut (Z)] = − E[∇∆t (Z)] = − E[Z∆t (Z)]. η η

(26)

Let bt = E[Z∆t (Z)] and take the deterministic unit vector at = bt /∥bt ∥2 when bt ̸= 0, and any deterministic Euclidean unit vector when bt = 0. Since every ∆t is nonnegative, T −1 X

" T −1 ! # 1 1 X ∥ūt+1 − ūt ∥2 ≤ E ∆t (Z) max |⟨Z, at ⟩| t<T η t=0 t=0  !2 1/2  1/2 T −1 2 1 X 2   ≤ E ∆t (Z) E max |⟨Z, at ⟩| t<T η

(27)

t=0

3 R2 p p ≤ C r log(2T ) = CR1 Ld log(2T ). η Here 1 uses (26) and the choice of at . The inequality 2 is Cauchy-Schwarz. The inq equality 3 uses Lemma 17 and the Gaussian maximum estimate p C log(2T ). 23

E maxt<T |⟨Z, at ⟩|2 ≤

Martı́nez-Rubio Guzmán

Common conversion to ℓq .

Let θq =

log∥x∥pp





2 q − 1 + . If q < 2, by the convexity of p 7→ θ

1−θq

∥x∥q ≤ ∥x∥1q ∥x∥2

.

If q ≥ 2, then θq = 0 and use norm monotonicity to conclude that ∥x∥q ≤ ∥x∥2 . Applying Hölder’s inequality and using (25) and (27) gives !θq T −1 !1−θq T −1 T −1 X X X ∥ūt+1 − ūt ∥q ≤ ∥ūt+1 − ūt ∥1 ∥ūt+1 − ūt ∥2 t=0

t=0

t=0

≤ Cq R1 T 1/r−1/2 θ

p Ld (log(2T ))1−1/r ,

(28)

1−θ

where we used that 2q = 1r − 12 and 2 q = 1 − 1r . Finally, q ≥ r implies ∥v̄ t+1 − v̄ t ∥q ≤ ∥v̄ t+1 − v̄ t ∥r . Combining (24) and (28) with √ R r T = R1 T

1/r−1/2

= RT

  1− p1 + 1q − 12

+

gives T −1 X

∥Cp,q,T (K t+1 ) − Cp,q,T (K t )∥q ≤ Cq RT

  1− p1 + 1q − 12

+

h

1+

i p Ld (log(2T ))1−1/r .

t=0

This proves the theorem. D.2. Proof of the energy and implementation statements Proof of Proposition 10. We will first prove a “Bregman-movement” bound for the p-energy selector; more precisely, T −1 X

DΦp (z t+1 , z t ) ≤

t=0

Rp . p

(29)

We will then transfer this Bregman-movement bound into an ℓq -movement bound to conclude. Since z t+1 ∈ K t+1 ⊆ K t , first-order optimality conditions for (15) yields ⟨∇Φp (z t ), z t+1 − z t ⟩ ≥ 0. Therefore DΦp (z t+1 , z t ) = Φp (z t+1 ) − Φp (z t ) − ⟨∇Φp (z t ), z t+1 − z t ⟩ ≤ Φp (z t+1 ) − Φp (z t ). Summing this inequality over t < T yields T −1 X

DΦp (z t+1 , z t ) ≤ Φp (z T ) − Φp (z 0 )

t=0

≤ Φp (z T ) ≤

24

Rp , p

Stable Movement for Nondual Lipschitz Convex Optimization

which proves (29). Next, by Proposition 14 and Fact 15 (using item 1 when p = 2 and item 2 when p > 2), 2−p we get DΦp (y, x) ≥ 2 p ∥y − x∥pp . Combining this bound with (29) we get T −1

22−p X Rp ∥z t+1 − z t ∥pp ≤ . p p t=0

Thus

T −1 X

∥z t+1 − z t ∥pp ≤ 2p−2 Rp .

(30)

t=0

Since q ≥ p, ∥z∥q ≤ ∥z∥p . Hence Hölder’s inequality and (30) provide the following estimate, T −1 X

T −1 X

t=0

t=0

∥z t+1 − z t ∥q ≤

∥z t+1 − z t ∥p

≤ T 1−1/p 1−2/p

≤2

!1/p

T −1 X

∥z t+1 − z t ∥pp

t=0 1−1/p

RT

.

Proof of Proposition 11. Fix a round t and condition on the history before its samples are drawn. Write K = K t , Y j = Y t,j , and Yb j = Yb t,j . The body K is now fixed and the fresh samples are independent. Let C = Cp,q,T (K) = E[uK (Z) + v K (Z)] and define the exact empirical average N X b N (K) = 1 C Y j. N j=1

We first bound this average’s error, then transfer the bound to numerical samples and sum the movement errors on one simultaneous success event. b N (K) ∈ K. Exact empirical average. Every Y j belongs to the convex set K, so C d Moreover, K ⊆ RB p and p < r, hence ∥Y j ∥r ≤ ∥Y j ∥p ≤ R. Let σ1 , . . . , σN be independent Rademacher signs, independent of the samples. We follow the standard symmetrization argument followed by the type-r inequality for ℓr ,  1/r N N 1 2 2 2 X X ∗ b N (K) − C ≤ E E σj Y j ≤ ∥Y j ∥rr  ≤ 2RN −1/r . E C N N r j=1

j=1

r

Here 1 is the symmetrization inequality and 2 is the Rademacher type inequality; see Ledoux and Talagrand [LT91] for both facts. For completeness, the second step follows coordinatewise from  r/2 r r N d N d N N 1 X 2 X X X X X 2   Eσ yj,i ≤ ∥yj ∥rr . σj yj = Eσ σj yj,i ≤ j=1

r

i=1

i=1

j=1

25

j=1

j=1

Martı́nez-Rubio Guzmán

Here 1 is the upper Khintchine inequality, which holds for all r ∈ (0, ∞) with an rdependent constant and here the constant is one since r ≤ 2. Step 2 uses r ≤ 2 and norm monotonicity, ∥a∥2 ≤ ∥a∥r , applied to each coordinate sequence a = (yj,i )N j=1 . Replacing one sample Y j by Y ′j changes the norm of the centered empirical average by at most 2R 1 Y j − Y ′j r ≤ . N N The bounded-differences inequality of McDiarmid [McD89] therefore gives, conditionally on the history, with probability at least 1 − δ/(T + 1), r 2R 2 log((T + 1)/δ) b C N (K) − C ≤ 1/r∗ + R . (31) N r N The sample-size condition in (17) makes the two terms on the right each at most E/2 after enlarging Cr . Since q ≥ r, norm monotonicity gives the claimed ℓq bound. Numerical solutions.

If Yb j ∈ K and Yb j − Y j

q

b N (K) − C and, on the single-round success event C

≤ Esol , convexity preserves feasibility q

≤ E from (31) and the sample-size

condition (17), N

N

1 Xb Yj −C N j=1

b N (K) − C ≤ C

q

q

+

1 X b Y j − Y j ≤ E + Esol . N q j=1

We next explain how an objective tolerance ensures the assumed samplewise error. Fix g, let w = (u, v) be the exact optimizer in (13), and let w b = (b u, vb) be feasible with F g (w) b − F g (w) ≤ ζ. Then 1 2 cµ r−1 ζ ≥ DF g (w, b w) + ⟨∇F g (w), w b − w⟩ ≥ DF g (w, b w) ≥ ∥b u − u∥21 + ∥b v − v∥2r . Ld 2 The inequality 1 is first-order optimality of w over the convex lift. For 2 , Fact 16 gives the head term, and Fact 15 gives the tail term. Thus, if we take   µ 2 ζ ≤ cEsol min ,r − 1 , (32) Ld then since q ≥ r, we have s ∥(b u + vb) − (u + v)∥q ≤ ∥b u − u∥1 + ∥b v − v∥r ≤

Ld ζ + cµ

r

2ζ ≤ Esol . r−1

Path error. Each of the T +1 conditional failure probabilities is at most δ/(T +1). Taking expectations over the histories and applying a union bound gives simultaneous success with probability at least 1 − δ, even for adaptively chosen bodies. On this event, every queried average is within E + Esol of z t = Cp,q,T (K t ). 26

Stable Movement for Nondual Lipschitz Convex Optimization

More generally, write Ectr = max0≤t≤T ∥b z t − z t ∥q . The triangle inequality gives the deterministic path-error bound T −1 X

T −1  X

t=0

t=0 T −1 X

∥b z t+1 − zbt ∥q ≤ ≤

∥z t+1 − z t ∥q + ∥b z t+1 − z t+1 ∥q + ∥b z t − z t ∥q

 (33)

∥z t+1 − z t ∥q + 2T Ectr .

t=0

On the simultaneous success event, Ectr ≤ E + Esol . For the choices in the proposition, Ectr ≤

R − p1 +( 1q − 12 )+ . T 2

Substituting this bound into (33) and using the exact-center movement bound in Theorem 9 proves (18).

Appendix E. Polynomial implementation Proof of Theorem 12. Rescaling to f (Rx)/(GR) with tolerance ε/(GR) lets us assume G = R = 1. Replace irrational finite exponents by rational p′ ≤ p and q ′ ≥ q sufficiently close that norm comparisons and complexity bounds change only by absolute factors; keep q = ∞ unchanged. Choose p′ so that B dp′ ⊆ B dp ⊆ (1 + ε/4)B dp′ : solving on the inner ball to accuracy ε/2 and subtracting ε/4 from its lower certificate preserves feasibility and ε-accuracy for the original problem. Absorb these constants and relabel the rational parameters below. We first construct the model-minimum certificate on the original ball, then use its strict model-level marginto exhibit interior balls for the queried sets and lifts. All subproblem objectives and constraints use only explicit norm functions and stored oracle cuts; solving them requires no additional calls to the first-order oracle of f . The model-minimum certificate. The original domain has explicit inner and outer balls: d−1/2 B d2 ⊆ Q = B dp ⊆ d1/2 B d2 . The model m is convex and 1-Lipschitz in ℓq , since each stored cut has normal of ℓq∗ norm at most one. Its value and a subgradient are computed by finding an active affine cut. Norm evaluation supplies a strong separation oracle for Q. The separation-based ellipsoid method therefore produces a feasible y and certified bounds a ≤ minQ m ≤ m(y) ≤ b with b − a ≤ Γ/32 in polynomial time; see (GLS93, Chapter 4) and the objective-level argument below. This constructs line 6 of Algorithm 1 without an assumption on the geometry of any model sublevel set. Interior balls for model sublevel sets We first note that, at every inner loop, the proof of Lemma 6 supplies y ∈ Q with m(y) < h− − 3Γ/32 by (21). Set α = Γ/64 and c = (1 − α)y. The initialization and valid certificate updates give 0 < Γ ≤ 2, so 0 < α < 1. Since ∥y∥q ≤ ∥y∥p ≤ 1, ∥c∥p ≤ 1 − α,

m(c) ≤ m(y) + α < h− − 5α. 27

Martı́nez-Rubio Guzmán

For any displacement h, ∥h∥p , ∥h∥q ≤ c+

√ d∥h∥2 . Consequently,

√ Γ √ B d2 ⊆ K = {x ∈ Q : m(x) ≤ h− } ⊆ c + 2 dB d2 . 128 d

Every model sublevel set is therefore full-dimensional, with a known interior point and inverse-polynomial inner radius because Γ > ε. Interior balls for the lifts. Let r = min{q, 2} and let T be the current selector horizon. Let y be as in line 6 of Algorithm 1. Apply the explicit decomposition in Lemma 8 to it: y = u + v, ∥u∥1 ≤ R1 , and ∥v∥r ≤ Rr . The pair ((1 − α)u, (1 − α)v) has respective norm slacks αR1 and αRr , and its sum is c. It follows that ((1 − α)u, (1 − α)v) +

α min{1, R1 , Rr } 2d √ B 2 ⊆ Lp,q,T (K). 4 d

Indeed, a product-space displacement √ (h, k) of norm at most the displayed radius changes either component norm by at most d∥(h, k)∥2 and changes the sum in either ℓp or ℓq by √ at most 2d∥(h, k)∥2 . These changes are smaller than the component slacks and the slacks at c. Moreover, T −1 ≤ Rr ≤ 1 and 1 ≤ R1 ≤ T . Thus the q displayed radius is at least √ Γ/(256 dT ), and an outer radius about its center is at most 2 R12 + R2r ≤ 4T . The lift is full-dimensional with explicit polynomial geometric bounds. Feasible inexact convex solves. Both K and its lift have strong separation oracles obtained by checking their norm constraints and stored affine inequalities. The objective F g in (13) is convex. Its values and subgradients use polynomially many of the permitted arithmetic and rational-power operations. On the enclosing ball, its Euclidean Lipschitz bound is polynomial in d, the horizon, and 1 + ∥g∥∞ . For completeness, suppose a convex objective H with Euclidean Lipschitz bound LH is minimized over a convex set S ⊆ Rn with a strong separation oracle and known balls c + aB n2 ⊆ S ⊆ c + bB n2 . For a minimizer w, the point wλ = (1 − λ)w + λc has a ball of radius λa in S. Given objective tolerance ξ > 0, choose λ = min{1/2, ξ/[8(LH + 1)b]}. Then H(wλ ) ≤ minS H + ξ/8, and the ball about wλ of radius min{λa/2, ξ/[8(LH + 1)]} consists of feasible points with objective value at most minS H +ξ/4. An ellipsoid feasibility test at objective level v therefore either returns a feasible point of value at most v, or, after the corresponding volume bound is reached, certifies minS H > v − ξ/4. Bisection using these valid lower and upper bounds yields a feasible point and a certified interval of width ξ in polynomial time. Subtracting H(c) bounds the initial objective interval by 2LH b. The explicit inner and outer radii above make this argument polynomial in the dimension, horizon, and inverse accuracy. For a Gaussian sample, apply this procedure to F g with the objective tolerance in (32). Strong convexity then gives the required ℓq error Esol from the exact sample, while preserving feasibility. For fixed norm parameters, the inverse of this sufficient objective tolerance is polynomial in the horizon and prescribed inverse center accuracy. 28

Stable Movement for Nondual Lipschitz Convex Optimization

Sampling, stopping, and total cost. Choose a deterministic planned query budget from the oracle bound in Lemma 6, with ρ = 1/p − (1/q − 1/2)+ and the movement bound in Theorem 9. Terminate and return the current best feasible point if that budget is exhausted. Use E = Esol = ε/64 at every center. On simultaneous sampling success these errors satisfy (19) throughout, since Γ > ε. The concentration argument in Proposition 11, with failure probability allocated across all center queries, uses polynomially many samples for fixed p, q. Denote their deterministic total budget by M . For the untruncated independent Gaussian draws,   p P max ∥Z j ∥∞ > 2 log(4dM/δ) ≤ δ/2. 1≤j≤M

If a draw exceeds this threshold, return the current best feasible point before solving its sample problem. Otherwise all sampled objectives have polynomial Lipschitz bounds. Allocate the remaining δ/2 to center estimation failures. Fresh sampling makes each estimate valid conditionally on the preceding history, so a union bound gives joint success with probability at least 1 − δ. On that event, Lemma 6 guarantees certified error at most ε within the planned oracle budget. All computed query points and both early-return rules preserve feasibility. The planned horizon, sample count, and inverse objective tolerances are polynomial in d, ε−1 , and log(1/δ) for fixed norm parameters. The preceding convex solves therefore give the claimed total arithmetic bound on every run, while the accuracy guarantee holds on the joint success event.

Appendix F. Proofs of the main theorems Proof of Theorem 2. For p < 2, the exact Gaussian center in (14) is feasible and satisfies (2) deterministically by Theorem 9. For 2 ≤ p < q, use the energy center: Proposition 10 gives the same bound, since (1/q − 1/2)+ = 0. For the Monte Carlo approximation when p < 2, apply Proposition 11 with E = Esol = (R/4)T −1/p+(1/q−1/2)+ . It preserves feasibility and gives (2) with probability at least 1 − δ. For p ≥ 2, the energy center already gives the guarantee with probability one, without sampling. It remains to justify the computational claim. For p < 2, it is exactly Theorem 12. For 2 ≤ p < q, the energy center minimizes the convex function ∥x∥pp /p over a body represented by the ball and the stored affine cuts. The separation-oracle argument in the proof of Theorem 12 computes a feasible point within O(RT −1/p ) in ℓq of that center in polynomial time. The resulting path differs in total movement by at most O(RT 1−1/p ), so (2) is preserved. Proof of Theorem 3. Normalize G = R = 1 and set ρ = 1/p − (1/q − 1/2)+ . Theorem 9 e p,q (1 + ε−1/ρ ) oracle gives the reference-center movement bound, and Lemma 6 yields O calls whenever the center errors satisfy (19). Theorem 12 supplies feasible approximations meeting these tolerances jointly with probability at least 1 − δ, with polynomial additional e p,q (T −ρ ) so that the planned oracle budget is at most T (if the target cost. Choose ε = O exceeds one, one feasible query suffices up to constants), and return the best queried point if that budget is exhausted. Every output is feasible; on the success event its error is at most ε. Rescaling gives (3).

29

Martı́nez-Rubio Guzmán

Appendix G. Lower complexity bounds for randomized convex optimization algorithms We discuss now the claim of near optimality for our randomized algorithms. Note that the oracle lower bounds of the open problem in (Guz15a; Guz15b) apply exclusively to deterministic algorithms, such as the one for our deterministic selector with the full expectation. We hereby extend those lower bounds to work against randomized algorithms, following the approach in (BGP17). We also leverage a general lower bound strategy pioneered by Srebro and Sridharan [SS12]. For the result we only discuss the high-level ideas, and refer to the original references for further details. Let (E, ⟨·, ·⟩) be a finite-dimensional space. For X , G ⊆ E convex and centrally-symmetric, consider the class of linear functionals L(X , G) := {g 7→ ⟨g, x⟩, x ∈ X }, as well as the class of convex Lipschitz functions F(X , G) := {f : E → R : f is convex and its subgradients lie in G}. We also recall the notion of fat-shattering dimension of linear functionals. Definition 18 A set g1 , . . . , gK ∈ G is α-shattered by L(X , G) if there exist r1 , . . . , rK ∈ R such that for every s ∈ {+1, −1}K there exists xs ∈ X such that for all i ∈ [K], si (⟨gi , xs ⟩ − ri ) > α/2. We define fatα (L(X , G)) as the largest value of K such that there is a set g1 , . . . , gK ∈ G that is α-shattered by L(X , G). Theorem 19 [↓] Let X , G ⊆ E be centrally symmetric, ε > 0, β ∈ [0, 1), and K ≤ fat2ε (L(X , G)). There exists a probability distribution ν over F(X , G) for which any randomized algorithm A making T queries to a local oracle (here T is a random variable) and providing x b ∈ X with h i x) − min f (x) > ε ≤ β Pf ∼ν,A f (b x∈X

must satisfy (1 − β)K − 1 . 2 In particular, for nontrivial failure probability, 0 ≤ β ≤ 1/2, we have that Ef ∼ν,A [T ] = Ω(K). Ef ∼ν,A [T ] ≥

For the case of X = B dp and G = B dq , it is known that for 1 ≤ p, q ≤ ∞ (the rates can be extracted from (MS04; Guz15a); see (MBG+26) for further information)    − 1 11 1   p < q, min α p −( q − 2 )+ , d , d   fatα (Lp,q ) ≍p,q (34)  max{q,2}   , d , p ≥ q, (p, q) ̸= (1, 1). min d1/q−1/p /α 30

Stable Movement for Nondual Lipschitz Convex Optimization

At (p, q) = (1, 1), the results of Mendelson and Schechtman [MS04, Lemma 4.5, Theorem 4.9, and proof of Theorem 3.4] give the bounds: min{α−2 , d} ≲ fatα (Ld1,∞ ) ≲ min{Lα α−2 , d},

0 < α ≤ 1.

(35)

Plugging these bounds in the previous theorem, we obtain the following result. Corollary 20 Let ε > 0, 1 ≤ p, q ≤ ∞, and d ≳ ε− max{2,p}+δ (for arbitrary but fixed δ > 0). Then the oracle complexity of optimization over the RB dp with objectives in F(RB dp , LB dq ) with randomized algorithms is lower bounded by  1 GR  1/p−(1/q−1/2)  +  , p < q,  ε T ≳p,q  (36) max{q,2} 1/q−1/p  d GR   , p ≥ q. ε This lower bound when reversed in terms of accuracy matches the upper bound obtained in Theorem 3, in the regime of interest p < min{2, q}. Proof of Theorem 19. Let g1 , . . . , gK ∈ G be a set that is (2ε)-shattered by L(X , G) with thresholds r1 , . . . , rK . For s ∈ {−1, +1}K , let xs ∈ X be the corresponding witness, from Definition 18. Hence γ := min min si (⟨gi , xs ⟩ − ri ) > ε. (37) s∈{−1,+1}K i∈[K]

Let η = γ−ε 4 and c = η − γ. Our instances will be uniformly drawn from the following family of objectives: n o fs,∆ (w) = max c, max −si (⟨gi , w⟩ − ri − ∆i ) , s ∈ {−1, +1}K , ∆ ∈ [−η, η]K . (38) i∈[K]

In particular ν is the law of fS,∆ when S ∼ Unif({−1, +1}K ), ∆ ∼ Unif([−η, η]K ) independently. Packing property. We first show that solving the optimization problem on an instance determines the string parameter s (a.k.a. the packing property (BGP17)). We note that by (37) the shattering witness xs satisfies −si (⟨gi , xs ⟩ − ri − ∆i ) ≤ η − γ = c. In particular, minx∈X fs,∆ (x) = c. Let now x̂ be a ε-optimal solution to the minimization of fs,∆ . Then fs,∆ (x̂) ≤ c + ε = −3η. In particular 0 < 2η ≤ 3η + si ∆i ≤ −fs,∆ (b x) + si ∆i ≤ si (⟨gi , x b⟩ − ri ). Here the second inequality uses ε-optimality, and the last one uses the definition of fs,∆ . We conclude that si = sgn(⟨gi , x b⟩ − ri ) ∀i ∈ [K], i.e., x b determines s uniquely. 31

Martı́nez-Rubio Guzmán

String-guessing oracle emulation. We perform now a string guessing-oracle emulation, following (BGP17). This corresponds to emulating the answer given by a single-coordinate oracle (that is, an oracle for piecewise-affine functions that provides answers whose subgradient coincide with that of an affine piece), by an oracle that only provides the values of the some coordinates of s. Fix the realization ∆ = δ and reveal it to the algorithm. Let x ∈ X be an arbitrary query, and consider the scores bi = ⟨gi , x⟩ − ri − δ i

(∀i ∈ [K]),

and select a deterministic ordering σ ∈ SK (the permutation group) such that |bσ(1) | ≥ . . . ≥ |bσ(K) |. Query the string-guessing oracle with tj = sgn(bσ(j) ), using a fixed convention when bσ(j) = 0. Let k be the first index in [K] such that tk ̸= sσ(k) , then −sσ(k) bσ(k) = |bσ(k) |, while every later coordinate j ≥ k is such that −sσ(j) bσ(j) ≤ −sσ(k) bσ(k) . Hence, the oracle returning (−sσ(k) bσ(k) , −sσ(k) gσ(k) ) is a valid single-coordinate first-order oracle answer in this case. If the answer by the string-guessing oracle is equal, then the entire string is known and one can compute a single-coordinate first-order oracle answer directly. Hence, the string-guessing oracle provides an emulation of a single-coordinate first-order oracle. Conclusion and lower bound for arbitrary oracles. By the packing property, every ε-optimal output by the algorithm identifies the random string S. The emulation above, together with Proposition III.3 and Lemma III.5 from (BGP17), gives the stated expectedquery lower bound for the preceding first-order oracle, even when ∆ is revealed. To extend it to an arbitrary local oracle, consider the maximal local oracle from (BGP17, Definition VI.1), from which every local oracle can be emulated (BGP17, Lemma VI.2). Because the offsets are independent and continuously distributed, conditionally on every transcript the offsets of affine pieces not yet exposed remain absolutely continuous. Consequently, at the next adaptive query, two previously unseen pieces have zero probability of ties. On the complementary event, which has probability one, the maximal-oracle answer can be reconstructed from the preceding transcript and the string-guessing answer. This is precisely the unpredictability argument of (BGP17, Lemma VI.4). Therefore the same lower bound holds for the maximal oracle, and hence for every local oracle. Averaging over ∆ proves the theorem.

32