Near-Optimal Acceleration for Smooth ℓp /ℓq Nondual Convex First-Order Oracle Optimization David Martı́nez-Rubio
IMDEA Software Institute, Madrid, Spain
Brian Bullins*
Purdue University, West Lafayette, IN, USA
arXiv:2609.21880v1 [math.OC] 18 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
Mathieu Molina*
Tel Aviv University, Israel
Abstract We study the optimization of convex objectives with (L, κ − 1)-Hölder-continuous gradients in ℓq over RBpd , 1 < κ ≤ 2. Martı́nez-Rubio and Guzmán [MG26] provides selectors with a movement bound for the problem of chasing high-dimensional convex nested sets for every p < q and generally reduces Lipschitz convex optimization to bounds on the movement of selectors. We couple that movement with Hölder descent yielding a polynomial-runtime first-order method whose feasible output, in the high-dimensional regime T ≤ d and for p < min{q, 2}, has error LRκ eκ,p,q O , T κ(1+1/p−(1/q−1/2)+ )−1 after T queries to a first-order oracle, solving the COLT 2015 open problem of Guzmán κ e [Guz15], up to logarithmic factors. At (p, q) = (1, 2), the rate is O(LR /T 2κ−1 ), including 2 3 e O(LR /T ) cubic decay in the smooth case.
1. Introduction and result The open problem of Guz15 asks for the minimax risk of black-box convex optimization when the domain is an ℓp ball but smoothness is measured in a different ℓq norm. The mismatch matters most for p < min{q, 2}: the feasible set is smaller than the natural ℓq ball, yet classical accelerated methods use only ℓp or ℓq geometry and do not match known lower bounds. For instance at (p, q) = (1, 2) and Lipschitz gradient smoothness, the classical rate is O(T −2 ) while the lower bound predicts O(T −3 ). The nonsmooth endpoint of this question was solved in (MG26) by reducing a level bundle method to movement of nested convex bodies in high dimensions. This paper shows that the same movement primitive also supplies the missing acceleration for every 1 < κ ≤ 2. . This draft is not yet in the form in which we would have liked to share it. In light of recent developments, we have nevertheless decided to make it available now. We plan to polish and revise this work shortly. *. Authors marked with an asterisk are listed alphabetically. © D. Martı́nez-Rubio, B. Bullins, C. Guzmán & M. Molina.
Martı́nez-Rubio Bullins Guzmán Molina
The mechanism is not an ordinary acceleration wrapper. A descent step contributes to a reduction in function value in the form of a positive power of the gradient norm, while a not-small-enough evaluation produces a deep cut in the bundle sublevel set and forces movement inversely proportional to that norm. The means inequalities balances the two effects, yielding acceleration, after a coupling of the movement selector and the descent point. More generally, our reduction takes as input a feasible selector with the required movement bound and inherits polynomial running time when that selector is computable in polynomial time on the generated bodies. Martı́nez-Rubio and Guzmán [MG26] supplies the selectors and their implementation. The contribution here is the conversion of movement into Hölder acceleration, including the coupling that preserves feasibility for constrained optimization. If the problem is unconstrained and a global minimizer x∗ is known to satisfy ∥x∗ ∥p ≤ R, we can provide a simple analysis of an algorithm that runs the movement selector on the auxiliary body RBpd , while descent steps and the final output are allowed to fall outside and returns a point outside it. For the full solution, we want to return a feasible point, and we would not assume there is a zero gradient in the set. After presenting our solution in the simplified setting, the second half of the paper constructs a solution based on approximating a Moreau envelope which, up to handling errors, reduces the problem to the previous case. 1.1. Setting ∗ ∗ We use 1/∞ = 0. For 1 ≤ r ≤ ∞, the conjugate Pd exponent r satisfies 1/r + 1/r = 1, and d d Br = {x ∈ R : ∥x∥r ≤ 1}. We write ⟨u, v⟩ = i=1 ui vi for the standard inner product. Assume ∥∇f (v) − ∇f (u)∥q∗ ≤ L∥v − u∥κ−1 , 1 < κ ≤ 2. (1) q
Integrating the gradient on a segment gives f (v) ≤ f (u) + ⟨∇f (u), v − u⟩ +
L ∥v − u∥κq . κ
(2)
.
(3)
For p < q, define the movement exponent 1 ρp,q := − p
1 1 − q 2
+
eκ,p,q omits constants depending on fixed regularity and norm parameters and Throughout, O factors polynomial in logarithms of d, T , the confidence level, and the requested numerical accuracy; it never omits a polynomial in d. Theorem 1 (Nondual Hölder accelerated optimization) [↓] Let R, L > 0, let Q = RBpd , let 1 ≤ p, q ≤ ∞, and let f be convex and differentiable on a neighborhood of Q, satisfying (1) for some 1 < κ ≤ 2. Fix δ ∈ (0, 1). For T ≤ d, and either p < min{q, 2} or p = q ≤ 2, there is a polynomial-time algorithm in the real-arithmetic model, making at most T first-order oracle queries and returning x bT ∈ Q with probability at least 1 − δ such that LRκ e , (4) f (b xT ) − min f (u) ≤ Oκ,p,q u∈Q T κ(1+1/p−(1/q−1/2)+ )−1 2
Near-Optimal Smooth Nondual Convex Optimization
Polynomial running time is understood in the real-arithmetic model of Section 9, with the selector implementation verified in Proposition 14, with fixed regularity and norm parameters. We note that there is also a deterministic algorithm if we use the deterministic stable selectors in MG26. We do not claim efficiency for that deterministic algorithm but we note that MG26 showed lower bounds of essentially the same order against randomized algorithms in comparison to the ones in the open question (Guz15) for the Lipschitz problem. The rate above, along with the observation that for 2 ≤ p < q one can run the classical modified Nesterov method in the p-geometry (GN15, Section 4.1.B) to match the lower bounds in Guzmán and Nemirovski [GN15] up to log factors, solves the COLT 2015 open problem (Guz15). The randomized implementation attains the same upper bound; we do not infer a randomized lower bound from the deterministic one. Related optimization methods. The diagonal p = q smooth rates go back to classical work (NN85), while universal methods cover unknown Hölder regularity (Nes15). Our algorithm draws on level and bundle methods (LNN95) as realized by (MG26). The new point is the coupling to the nonstandard movement geometry and the feasible envelope construction. 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) for the smooth case (κ = 2).
2. Warm-up: power descent versus harmonic movement In order to understand the solution, it is convenient to understand how the non-smooth rate of (MG26) is achieved. For intuition, we include Figure 1, borrowed from the paper. 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, z2 ∈ K2 ), whereas the new tangent satisfies a2 (z 2 ) = f (z 2 ) > h+ . Adding a2 reduces the (h− )-sublevel to the thick black segment (K3 ⊂ K2 ), 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.
3
Martı́nez-Rubio Bullins Guzmán Molina
Non-smooth solution from (MG26)
Before query t ≥ 1, let
mt (x) = max {f (xi ) + ⟨g i , x − xi ⟩},
ℓt = min mt (x),
0≤i<t
x∈Q
U t = min f (xi ). 0≤i<t
Convexity gives ℓt ≤ minx∈Q f (x) ≤ U t . We run the algorithm in phases. Freeze the phase scale Γ = (U − ℓ)/2 and two levels h− = ℓ + Γ/2 < h+ = ℓ + 3Γ/2, and query a stable selector xt = 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− }. This retained halfspace is at ℓq -distance at least (h+ −h− )/∥g t ∥q∗ = Γ/∥g t ∥q∗ from z t . Thus every such deep cut forces movement of the selector, unless the new P body is empty; see Figure 1. An upper bound on the total movement Tt=1 ∥zt − zt+1 ∥q after T steps coming from the chasing convex bodies problem along with the fact that the movement is lower bounded by T · Γ/G gives a maximum number of steps until we see an empty sublevel set (so the lower bound increases to at least h− ) or we have f (zt ) ≤ h+ . Either way, we decrease the gap by a constant factor and continue to the next phase. Hölder-smooth warm-up In this warm-up, suppose the function is convex and Hölder smooth globally but its global minimum is in RBpd while we initialized at 0, and we allow descent points yt and the points xt that we use to query the first-order oracle to be outside of RBpd while we have a stable selector zt ∈ RBpd . We assume being able to perform exact segment function value minimization in this warm-up, for simplicity. The algorithm has some similarities to the nonsmooth solution: we run the bundle method, except that within a phase, we query at xt ∈ argminx∈[yt ,zt ] f (x) receiving f (xt ) and gt = ∇f (xt ), then descend to yt+1 from xt optimizing the unconstrained upper bound (2) on the function that Hölder smoothness gives while zt is the proposed stable selector. By optimality, the first-order oracle query at xt also either has function value at most h+ or it produces a deep cut separating zt from the next sublevel set. Line search gives f (xt ) ≤ f (yt ) and ⟨gt , zt − xt ⟩ ≥ 0: descent improves the old value, and the tangent at (u) = f (xt )+⟨gt , u − xt ⟩ satisfies at (zt ) ≥ f (xt ). For the smooth method, replace the fixed levels by the moving target below. If descent guarantees decrease Dt , set Ut+1 = f (xt ) − Dt , add at to the bundle, and lower all cuts’ target to Ut+1 − Γ, with phase scale Γ. Convexity preserves all points of RBpd below this target level; the bodies stay nested. Thus the same gradient gives decrease Dt and forces selector movement at least (Γ + Dt )/∥gt ∥q∗ , unless the next body is empty. In particular, the deep cut at xt is also a deep cut for zt and we force movement similarly as if we had queried at zt instead. For p < q, Martı́nez-Rubio and Guzmán [MG26] provides, for every nonempty nested sequence RBpd ⊇ K0 ⊇ · · · ⊇ KN , a selector zt ∈ Kt satisfying X ep,q RN 1−ρp,q , ∥zt+1 − zt ∥q = O t<N
where ρp,q is defined in (3). Let g be a gradient and G = ∥g∥q∗ . Choose a support vector vq (g), i.e. such that ∥vq (g)∥q = 1 and ⟨g, vq (g)⟩ = G. Minimizing the Hölder upper model along −vq (g) gives the step length and guaranteed decrease in function value Dκ (G), where a = (G/L)1/(κ−1) ,
Dκ (G) :=
κ − 1 −1/(κ−1) mκ κ L G , for mκ = . κ κ−1 4
Near-Optimal Smooth Nondual Convex Optimization
Thus gradient descent controls the mκ -power mean of the gradient norms. If Gt = 0, the queried point is a global minimizer and we stop. Otherwise, a tangent cut with level violation Γ and subgradient norm Gt has depth Γ/Gt . Hence a purely movementbased estimate controls X 1 Γ , Gt t<N
or equivalently the harmonic mean of the subgradient norms. The inequality between the harmonic mean and the mκ -power mean is !1/mκ 1 X mκ N P ≤ Gt . (5) N t<N 1/Gt t<N
If one phase has scale Γ, the concatenated guaranteed descent is at most U0 − f ⋆ ≤ U0 − ℓ0 = 2Γ. For N nonterminal transitions in this phase, descent gives N −1 X
κ Gm ≲κ L1/(κ−1) Γ, t
t=0
whereas movement gives Γ
N −1 X t=0
1 e RN 1−ρ . =O Gt
Substituting these estimates into (5) and using mκ = κ/(κ − 1) yields LRκ κ−1+κρ e . N = Oκ Γ This is the desired exponent that yields optimality up to log factors. The line search makes both estimates simultaneously valid; the later envelope construction preserves this tradeoff using quadratic descent and phase tuning, with controlled numerical errors and feasible queries. To sum up, we know from previous work that we have certain movement bound 1−ρ ) with using some stable selectors z . We keep descent points y from doing e O(RN t t classical in the unconstrained problem, and we select the point xt where we will do the first-order oracle query as the minimizer of f on [yt , zt ] (or an approximation with controlled errors). Optimality of the line search creates a deep cut over zt in the nested convex bodies subproblem, while ensuring f (xt ) ≤ f (yt ). This is reminiscent of linear coupling and other accelerated regimes combining mirror descent and descent steps. Smaller gradient norms Gt strengthen the guaranteed cut depth Γ/Gt , while larger norms strengthen the guaranteed descent. The means inequality balances those two phenomena. The use of this inequality is reminiscent of the intuitive explanation in Allen-Zhu and Orecchia [AO14, Thought Experiment, p. 4] (that inspired the idea of this paper) and, in hindsight, of the use of the reverse Hölder inequality in higher-order acceleration (CHJ+22; ABJ+24; CGM24). We note that convergence rates depending on the harmonic mean of the gradient norms is an identified phenomenon, see (Lev17; Ora23). Our work provides an intuitive geometric explanation to this phenomenon in the form of our realized moment bound. 5
Martı́nez-Rubio Bullins Guzmán Molina
3. Algorithm at a glance The method runs in phases. Each inner bundle call builds a tangent model, and the outer level method retains its certified aggregate cut. The maximum of the retained aggregate cuts forms a model m ≤ f on Q. Minimizing m gives a certified lower bound, while a retained feasible point gives an upper bound. Each phase fixes a fraction of this certified gap, forms a corresponding model sublevel set, and queries the movement selector inside that set. The coupled-step module then returns a feasible upper witness and a new valid affine cut. Algorithm 1 Feasible Hölder movement-coupled level method Input: Feasible set Q = RBpd ; first-order oracle; Hölder parameters (κ, L); accuracy ε; movement selector C; query budget J from (26). Input: Feasible envelope step Step; initial feasible upper witness y, upper certificate U ≥ f (y), and max-affine model m ≤ f on Q. Output: A feasible witness; its certified gap is at most ε on simultaneous selector success. 1: Count every first-order call, including initialization and inner line-search calls. Before call J + 1, return the retained y. 2: ℓ ← minu∈Q m(u). 3: while U − ℓ > ε do 4: Γ ← (U − ℓ)/2 and U start ← U . 5: Choose the planned length NΓ by (25); set the envelope coefficient AΓ , bundle tolerance τ Γ , and line-search tolerance η Γ by (17). 6: Restart the horizon-dependent selector C for NΓ transitions (NΓ + 1 selector points); set n ← 0. 7: while U > U start − Γ/4 do 8: K ← {u ∈ Q : m(u) ≤ U − Γ}. 9: if K = ∅ then 10: break. 11: end if 12: If n = NΓ + 1, return y; otherwise set n ← n + 1. 13: z ← C(K); if it signals failure, return y. 14: (y, U, a, G, η, ξ) ← Step(y, U, z, Γ; AΓ , τ Γ , η Γ ). ⋄ valid cut a ≤ f , cut-normal norm G, errors η, ξ 15: m(u) ← max{m(u), a(u)} for u ∈ Q. 16: end while 17: ℓ ← minu∈Q m(u). 18: end while 19: return y b ← y. The step Step(y, U, z, Γ; A, τ , η) uses the bracketed envelope line search of Lemma 10: at each trial center it calls the certified proximal bundle solver of Proposition 9, then returns the feasible upper witness and aggregate cut described in Lemma 11. The step retains the old witness whenever it retains the old upper certificate. The displayed pseudocode uses exact model solves; Proposition 13 specifies the certified numerical replacements for its solves and emptiness tests. The query guard applies inside every subroutine; an interrupted 6
Near-Optimal Smooth Nondual Convex Optimization
call retains the previous witness. The selector uses the bounded-work implementation of Martı́nez-Rubio and Guzmán [MG26], as specified in Section 9. The certified gap guarantee holds with probability at least 1−δ. Thus the upper certificate U , phase scale Γ, cut-normal norm G, descent inexactness η, and cut inexactness ξ are the only quantities passed from the analytic module to the movement argument.
4. The abstract coupled phase Maintain a max-affine bundle model mt ≤ f on Q, a lower certificate ℓt = minQ mt , a feasible upper witness yt , and an upper certificate Ut ≥ f (yt ). A phase begins with scale Γ = (U0 − ℓ0 )/2. Its body is Kt = {u ∈ Q : mt (u) ≤ Ut − Γ} . The bodies are nested because mt increases and Ut decreases. The coupled step allows two geometrically different errors. The descent error η t is vertical slack in the upper-bound decrease: it is the amount lost from the ideal decrease D(Gt ) for a specified nonnegative descent profile D. The cut error ξt is vertical slack in the separation at zt : for cut normal gt , it makes the retained halfspace shallower by ξt /∥gt ∥s∗ . Thus η t spends the phase’s progress budget, whereas ξt spends its cut depth. An implementation obtains descent and cuts with some errors ξt η t , and we show that the rate of convergence is robust to it. Definition 2 (Coupled step with qualified errors) Fix a descent profile D : [0, ∞) → [0, ∞). At center zt ∈ Kt , a coupled step returns an upper certificate Ut+1 ≤ Ut , a valid affine cut at (u) = bt + ⟨gt , u⟩, cut-normal norm Gt = ∥gt ∥s∗ , descent inexactness η t ≥ 0, and cut inexactness ξt ≥ 0, such that Ut+1 ≤ Ut − D(Gt ) + η t ,
(6)
at (zt ) − (Ut+1 − Γ) ≥ Γ + D(Gt ) − ξt .
(7)
The movement norm is ℓs and the cut normal is measured in ℓs∗ . Lemma 3 (Cut depth and inverse normal norm) [↓] Let Gt be the cut-normal norm and ξt the cut inexactness from Definition 2. If ξt ≤ Γ/2 and the next body is nonempty, then Γ ∥zt+1 − zt ∥s ≥ . 2Gt Note that if Gt = 0, we can stop the algorithm, so zero never occurs in an inverse-norm sum. Theorem 4 (Movement-to-optimization reduction)P[↓] Let 1 < κ ≤ 2 and ρ > 0. −1 1−ρ ). e Suppose a selector for nested convex sets in RBpd satisfies N t=0 ∥zt+1 − zt ∥s = O(RN Consider the level updates of Algorithm 1, using coupled steps as in Definition 2 with profile D = Dκ , with a budget of T ≥ 1 coupled steps in place of the accuracy and first-order-call stopping rules. Stop earlier only if the certified gap vanishes. Assume that, in each phase of 7
Martı́nez-Rubio Bullins Guzmán Molina
P −1 scale Γ, the errors satisfy N t=0 η t ≤ Γ/16 and 0 ≤ ξt ≤ Γ/2 for every nonterminal prefix of length N . From an initial certified gap O(LRκ ), the retained upper witness after at most T coupled steps has optimization error at most eκ O
LRκ
T κ−1+κρ
.
5. Module I: a global minimizer lies in the auxiliary ball Assume in this section that f : Rd → R and that a global minimizer x∗ satisfies x∗ ∈ Q. Thus ∇f (x∗ ) = 0, and a value at an infeasible point is still a valid upper bound on f (x∗ ). Given a current upper witness y and movement center z, minimize f on the segment [y, z]: x ∈ argmin f (w),
g = ∇f (x),
w∈[y,z]
G = ∥g∥q∗ .
Set y + = x − (G/L)1/(κ−1) vq (g),
U + = f (x) − Dκ (G),
(8)
and use the tangent a(u) = f (x) + ⟨g, u − x⟩. Lemma 5 (Exact ambient coupling) [↓] Let U be the current upper certificate, G the gradient norm in (8), and Γ the phase scale. Then f (y + ) ≤ U + ≤ U − Dκ (G),
a(z) − (U + − Γ) ≥ Γ + Dκ (G).
Thus the ambient module satisfies Definition 2 with D = Dκ and zero descent and cut errors. Theorem 6 (Ambient rate with exact line search) [↓] Let p < min{q, 2}, let f : Rd → R be convex and differentiable and satisfy (1), and suppose a global minimizer obeys ∥x∗ ∥p ≤ R. Use RBpd only for the bundle lower model and the movement selector, and grant the segment-minimization oracle used in (8). Then after T coupled outer steps the ambient module returns a point yT ∈ Rd , not necessarily in RBpd , with
∗
eκ,p,q f (yT ) − f (x ) ≤ O
LRκ T κ(1+ρp,q )−1
.
The theorem explains the cleanest use of an externally supplied radius bound. The auxiliary ball restricts the comparator and makes movement finite; it does not restrict the descent path or output. This argument is valid only when the optimization problem itself is unconstrained. An approximate one-dimensional search can replace the ideal oracle by assigning its value and sign errors to the budgets in Definition 2; the feasible construction below gives the fully specified polynomial algorithm used in the main theorem. 8
Near-Optimal Smooth Nondual Convex Optimization
6. Why constrained feasibility requires a new module For minQ f , the point y + in (8) can be infeasible, and the constrained minimizer can have nonzero gradient. Projecting y + back to Q does not preserve either the Hölder decrease or the tangent-cut alignment. A direct κ-power proximal envelope suggests the same descent profile, but we do not establish the required linear-time proximal-solve bound for that construction. We instead use the “inexact gradient trick” at the current phase accuracy, a classical technique from Devolder, Glineur, and Nesterov [DGN14]. For a tolerance ω > 0, define (2−κ)/κ 2−κ L2/κ ω −(2−κ)/κ , 1 < κ < 2, 2κ Hω := (9) L, κ = 2. Lemma 7 (Inexact gradient trick) [↓] For every u, v ∈ Q, f (v) ≤ f (u) + ⟨∇f (u), v − u⟩ +
Hω ∥v − u∥2q + ω. 2
For the feasible construction, use s = min{q, 2}. For a center c ∈ Q and coefficient A > 0, define the quadratic envelope A 2 := MA (c) min f (u) + ∥u − c∥s . u∈Q 2 Let Js (w) = ∇(∥w∥2s /2) denote the duality map. Definition 8 (Certified envelope evaluation) At center c, a bundle call with tolerance τ returns a convex max-affine model m ≤ f and points x, y ∈ Q such that A 2 (10) x ∈ argmin m(u) + ∥u − c∥s , 2 u∈Q A A f (y) + ∥y − c∥2s ≤ m(x) + ∥x − c∥2s + τ . (11) 2 2 The aggregate residual and cut are g = AJs (c − x),
a(v) = m(x) + ⟨g, v − x⟩.
(12)
Proposition 9 (Certified bundle solve) [↓] Let 1 < s ≤ 2, let Q ⊆ RBsd be compact and convex, and let f be convex and differentiable on a neighborhood of Q. Fix c ∈ Q, A, τ > 0, and 0 < ω ≤ τ /2. Suppose that f (v) ≤ f (u) + ⟨∇f (u), v − u⟩ +
Hω ∥v − u∥2s + ω 2
Set µ = A(s − 1). Repeating (10) yields (11) using Hω Hω R 2 O 1+ log 2 + µ τ first-order calls. 9
(u, v ∈ Q).
(13)
Martı́nez-Rubio Bullins Guzmán Molina
Exact model solves are used above. We note that Proposition 13 gives the same order of calls with certified approximate solves when Hω /µ = Os (1). The proof contracts the global model gap directly. At the coefficient used below, Hω /µ = Os (1), so this nonaccelerated inner solver already has logarithmic oracle cost.
7. The feasible envelope coupling Let y old be the current feasible upper witness and z the movement center. We evaluate the envelope along cλ = y old + λ(z − y old ), 0 ≤ λ ≤ 1. At each queried cλ , compute the certified residual gλ and the scalar D E ψλ = gλ , z − y old . Lemma 10 (Certified envelope line search) [↓] Using envelope evaluations with bundle tolerance τ , sign bisection returns a center c ∈ [y old , z] and certified residual g such that MA (c) ≤ MA (y old ) + η + τ , ⟨g, z − c⟩ ≥ 0. The number of envelope evaluations is O(log(2 + AR2 /η)). By Lemma 11, the envelope-value bound preserves telescoping descent up to budgeted errors, while ⟨g, z − c⟩ ≥ 0 keeps the cut deep at z. Only selector centers enter the movement sum, not line-search trials. The nested-body movement bound therefore still applies. Lemma 11 (Feasible descent and cut) [↓] Let U be the old feasible upper certificate, let Γ be the phase scale, and let (x, y, m) be the bundle certificate at the line-search center c. Put G = ∥g∥s∗ . The aggregate affine function in (12) satisfies a ≤ f on Q, and the new feasible upper certificate U + = min{U, f (y)} obeys G2 + Cs (η + τ ), 4A G2 a(z) − (U + − Γ) ≥ Γ + − Cs (η + τ ). 2A U+ ≤ U −
(14) (15)
Its witness is y old if U ≤ f (y), and y otherwise. The cut is retained in both cases. Here g is an aggregate residual, not necessarily a subgradient of f . It is a τ -subgradient of MA by (22). This is Definition 2 with D(G) = G2 /(4A) and errors Cs (η + τ ). Its numerical version 2 in Proposition 13 uses D(G) the P 2= G /(8A). Before upper progress terminates the phase, P descent inequality gives Gt ≲ AΓ. The cut inequality and movement give Γ 1/Gt = 1−ρ ). Hölder with exponents 3 and 3/2 yields the quadratic phase bound e O(RN AR2 1+2ρ e . (16) N = Os Γ 10
Near-Optimal Smooth Nondual Convex Optimization
Choose planned phase length NΓ and parameters Γ , τ Γ ≍ ηΓ ≍ NΓ
2/κ
AΓ ≍s L
NΓ Γ
(2−κ)/κ .
(17)
Substitution in (16) gives eκ,s NΓκ−1+κρ = O
LRκ Γ
.
(18)
Thus the feasible quadratic module has exactly the Hölder exponent found in the ambient warm-up. Theorem 12 (Feasible movement-coupled rate for p < min{q, 2}) [↓] Let 1 ≤ p < min{q, 2} and 1 < q ≤ ∞, let Q = RBpd , and let f be convex and differentiable on a neighborhood of Q, satisfying (1). Use s = q when q ≤ 2 and s = 2 when q ≥ 2. Let ρp,q be the movement exponent in (3), let Ut denote the feasible upper certificates, and let τ Γ , η Γ be the bundle and line-search tolerances in (17). For a first-order budget T ≥ 1 and confidence parameter δ ∈ (0, 1), run Algorithm 1 with initialization from Lemma 16 and the target accuracy and query budget from (27), or use its small-budget fallback. This returns x bT ∈ RBpd , with f ⋆ = minu∈Q f (u), satisfying
⋆
eκ,p,q f (b xT ) − f ≤ O
LRκ T κ(1+ρp,q )−1
.
The bound holds with probability at least 1 − δ, using at most T first-order calls, including initialization and all inner bundle and line-search calls.
8. Regime assembly and comparison with lower bounds The feasible theorem is assembled as follows. 1. If p < q ≤ 2, use s = q in the envelope and the p/q movement selector from the companion paper. 2. If p < 2 ≤ q, norm comparison gives ∥∇f (v) − ∇f (u)∥2 ≤ ∥∇f (v) − ∇f (u)∥q∗ ≤ L∥v − u∥κ−1 . 2 Use the Euclidean envelope and the p/2 movement selector. Its exponent is ρp,2 = 1/p, which is the required q ≥ 2 exponent. For p < min{q, 2}, the powers reported by Guzmán [Guz15], based on the lower-bound framework of Guzmán and Nemirovski [GN15], are 1 3 1 1 + − − 1 (q < 2), κ 1+ − 1 (q ≥ 2). κ 2 p q p These agree with Theorem 1. 11
Martı́nez-Rubio Bullins Guzmán Molina
9. Implementation and scope 1−ρ ) e The reduction assumes a selector that returns feasible centers with movement O(RN on the generated nested bodies. A bounded-work implementation on these bodies, with the stated movement bound conditionally on the preceding history, is supplied by Proposition 14, making use of the selector’s implementation in Martı́nez-Rubio and Guzmán [MG26, Theorem 9, Proposition 11, and Appendix E]. We work in the real-arithmetic model: arithmetic, comparisons, logarithms, rational powers, powers with the fixed norm and regularity exponents, and independent scalar standard Gaussian draws have unit cost. Exact first-order calls are counted separately. For fixed κ, p, q, the additional work is polynomial in d, 1 + LRκ /ε, log(1/δ), and log(2 + ∥∇f (0)∥s∗ /(LRκ−1 )) in the new branch. The last dependence comes only from solving the inner tangent models; the first-order bound is independent of affine terms in f . The convex-solve and sampling bounds in Proposition 14, together with the hard budgets in Algorithm 1, bound the work on every run.
Acknowledgments Cristóbal Guzmán was partially funded by ANID FONDECYT 1251029 grant, and ANID Basal FB210017 National Center for Artificial Intelligence CENIA. David Martı́nez-Rubio was funded by grant La Caixa Junior Leader Fellowship 2025. He thanks OpenAI for free access to their models. Mathieu Molina received funding from the European Research Council (ERC) under the European Union’s Horizon Europe program (grant agreement No. 101170373), as a postdoctoral fellow at Tel Aviv University. This work was elaborated in combination with ChatGPT/Codex. After providing the initial ideas (the contents of the warm-up Section 2 along with pointing to using the Moreau envelope analysis, which can absorb errors, plus treating Hölder smooth functions as inexact smooth functions), ChatGPT 5.6 (the newest model when we elaborated the results) was able to craft the details of the proof. This draft is not in the form we would have liked to share it and the authors will shortly improve its writing quality, organization of ideas and overall presentation.
12
Near-Optimal Smooth Nondual Convex Optimization
Appendix A. Proof of the abstract phase theorem Proof of Lemma 3. The new body lies in the halfspace Ht = {u : at (u) ≤ Ut+1 − Γ} . If Gt = 0, the coupled cut is constant and its retained halfspace is empty. Suppose Gt > 0. A displacement w from zt into Ht must satisfy ⟨gt , w⟩ ≤ −[at (zt ) − (Ut+1 − Γ)]. Hölder’s inequality gives ∥w∥s ≥ [at (zt ) − (Ut+1 − Γ)]/Gt . Equality is attained by a suitably scaled negative unit ℓs direction on which gt attains its dual norm. Therefore the distance from the current center is dists (zt , Ht ) =
at (zt ) − (Ut+1 − Γ) 1 Γ − ξt 2 Γ . ≥ ≥ Gt Gt 2Gt
Here 1 uses the coupled cut (7) and D ≥ 0, and 2 uses ξt ≤ Γ/2. Since zt+1 belongs to the new body, its movement is at least this distance. Proof of Theorem 4. Fix a phase of scale Γ and a nonterminal prefix of length N . We first bound N and then sum the phase costs. Recall that Ut is the upper certificate and Gt the cut-normal norm. Here the descent profile is Dκ . As long as upper progress has not terminated the phase, U0 − UN < Γ/4. Summing (6) and using the descent error budget gives X κ Gm ≤ Cκ L1/(κ−1) Γ. (19) t t<N
P Unpack the assumed soft movement bound as t<N ∥zt+1 − zt ∥s ≤ CRΛ(d, N )N 1−ρ , where Λ is nondecreasing and polylogarithmic. The inverse-normal-norm lemma and this movement bound give ΓX 1 ≤ RΛ(d, N )N 1−ρ . (20) 2 Gt t<N
Apply Hölder in the form N=
X
mκ /(mκ +1) κ 1/(mκ +1) (Gm (G−1 t ) t )
t<N
!1/(mκ +1) ≤
X
κ Gm t
t<N
X 1 t<N
!mκ /(mκ +1)
Gt
.
Substituting (19) and (20), raising to mκ + 1, and then raising to κ − 1 yields N κ−1+κρ ≤ Cκ
LRκ Λ(d, N )κ . Γ
It remains to verify gap contraction. If upper progress occurs, the upper certificate drops by Γ/4 = (U0 − ℓ0 )/8, while the lower certificate does not decrease; the new gap is at most 7(U0 − ℓ0 )/8. If the body {m ≤ U − Γ} is empty, then ℓ = minQ m ≥ U − Γ, so the new gap is at most Γ = (U0 − ℓ0 )/2. The bounds on phase costs grow geometrically 13
Martı́nez-Rubio Bullins Guzmán Molina
as the gap shrinks and are therefore dominated by the final phase, including at most one terminal step per phase. Starting from a certified gap O(LRκ ) and inverting the resulting eκ (LRκ /T κ−1+κρ ) bound on the total number T of coupled steps gives optimization error O for the retained upper witness.
Appendix B. The ambient module Proof of Lemma 5. Exact minimization on [y, z] gives f (x) ≤ f (y),
⟨g, z − x⟩ ≥ 0.
(21)
Let a = (G/L)1/(κ−1) . By (2) and the norming-vector identity, f (x − avq (g)) ≤ f (x) − aG +
L κ κ − 1 −1/(κ−1) κ/(κ−1) a = f (x) − L G = U +. κ κ
Thus f (y + ) ≤ U + . The first sign in (21) gives U + ≤ U − Dκ (G). Because x∗ is a global minimizer, U + ≥ f (y + ) ≥ f (x∗ ), so this is a valid upper certificate. For the tangent cut, 1 a(z) − (U + − Γ) = ⟨g, z − x⟩ + Dκ (G) + Γ ≥ Γ + Dκ (G). Here 1 uses the second sign in (21). Proof of Theorem 6. Apply Lemma 5 and Theorem 4 with the imported movement exponent ρp,q . To initialize, query at 0. Since ∇f (x∗ ) = 0, (1) gives ∥∇f (0)∥q∗ ≤ L∥x∗ ∥κ−1 ≤ LRκ−1 . q The tangent range over RBpd is at most a constant times R∥∇f (0)∥p∗ ≤ LRκ , where p < q. Hence the initial certified gap is O(LRκ ). Geometric phases give the claimed rate. Nothing in the proof requires the upper witness to lie in the auxiliary ball.
Appendix C. Inexact gradient trick and the certified bundle solve Proof of Lemma 7. It suffices to prove, for every t ≥ 0, L κ Hω 2 t ≤ t + ω. κ 2 For 1 < κ < 2, the maximum of the left side minus Ht2 /2 occurs at t = (L/H)1/(2−κ) and equals κ/(2−κ) 2−κ L L . 2κ H The definition of Hω makes this value equal to ω. Combining the scalar inequality with (2) proves the claim. At κ = 2, it is the usual descent lemma. 14
Near-Optimal Smooth Nondual Convex Optimization
Proof of Proposition 9. We bound the gap between the best evaluated proximal objective and the global model minimum. Put h(u) = A∥u − c∥2s /2 and F = f + h. Query at c and let m0 be its affine tangent. For j ≥ 0, solve xj ∈ argmin{mj (u) + h(u)},
ℓj = mj (xj ) + h(xj ),
u∈Q
query at xj , and retain Vj = min0≤i≤j F (xi ) with a corresponding witness. Stop when Ej := Vj − ℓj ≤ τ ; otherwise add the tangent at xj to form mj+1 . Strong convexity and mj+1 ≥ mj give µ ∥xj+1 − xj ∥2s ≤ ℓj+1 − ℓj =: bj . 2 The new model contains the tangent at xj , so Ej+1 ≤ F (xj+1 ) − ℓj+1 1 Hω ≤ ∥xj+1 − xj ∥2s + ω 2 Hω bj + ω. ≤ µ Here 1 uses the assumed quadratic upper model. Since Vj+1 ≤ Vj , we have bj ≤ Ej −Ej+1 . With a = Hω /µ, this proves j a ω a Ej+1 ≤ Ej + , Ej ≤ ω + E0 . 1+a 1+a 1+a The initial tangent at c gives E0 = f (x0 ) − m0 (x0 ) ≤ 2Hω R2 + ω. Thus Ej ≤ τ within (13). The retained model and witness satisfy (10) and (11). All minima are over the original Q, so the stopping certificate is global. For 1 < s ≤ 2, ∥·∥2s /2 is σs -strongly convex with σs = s − 1. Taking ω = τ /8 and A ≥ Cs Hω makes Hω /[A(s − 1)] = Os (1), as required for logarithmic oracle cost.
Appendix D. Envelope line search and feasible coupling Proof of Lemma 10. Fix one certificate (x, y, m) at a queried center c and define its lower envelope A 2 M (v) = min m(u) + ∥u − v∥s . u∈Q 2 Because m ≤ f , M (v) ≤ MA (v) for all v. At c, the bundle gap gives MA (c) ≤ f (y) +
A ∥y − c∥2s ≤ M (c) + τ . 2
Danskin’s theorem (Dan67) gives g = AJs (c−x) ∈ ∂M (c). Combining the three facts yields the certified τ -subgradient inequality MA (v) ≥ MA (c) + ⟨g, v − c⟩ − τ , 15
v ∈ Q.
(22)
Martı́nez-Rubio Bullins Guzmán Molina
Write d = z − y old , cλ = y old + λd, and ψλ = ⟨gλ , d⟩. If ψ0 ≥ 0, return c0 . If ψ0 < 0, query 1; when ψ1 ≤ 0, apply (22) at c1 with v = c0 to get MA (c1 ) ≤ MA (c0 ) + τ , and return c1 . It remains to treat ψ0 < 0 < ψ1 . Bisect while maintaining endpoints λ− , λ+ with ψλ− ≤ 0 ≤ ψλ+ , and stop when λ+ − λ− ≤ η/Gls , where Gls = 4AR2 . The envelope is Gls -Lipschitz on this segment: comparison with the prox minimizer at the other center gives MA (c′ ) − MA (c) ≤ 2AR c′ − c s . The τ -subgradient inequality at the left endpoint, evaluated at c0 , gives MA (cλ− ) ≤ MA (c0 ) + τ . Therefore MA (cλ+ ) ≤ MA (c0 ) + τ + η. Finally, gλ+ , z − cλ+ = (1 − λ+ )ψλ+ ≥ 0. The initial bracket has length one, so the number of evaluations is O(log(2 + AR2 /η)). Proof of Lemma 11. Let dx = ∥c − x∥s ,
dy = ∥c − y∥s ,
G = ∥g∥s∗ = Adx .
Optimality in (10) supplies gm ∈ ∂m(x) with g − gm ∈ NQ (x). Hence, for every v ∈ Q, m(v) ≥ m(x) + ⟨gm , v − x⟩ ≥ m(x) + ⟨g, v − x⟩ = a(v). Thus a ≤ m ≤ f . The model prox objective is Aσs -strongly convex. Since m(y) ≤ f (y), the bundle gap implies Aσs ∥y − x∥2s ≤ τ . 2 The triangle inequality therefore gives 2τ 1 . d2y ≥ d2x − 2 Aσs The line search gives MA (c) ≤ MA (y f (y old ) ≤ U , the upper certificate obeys
old ) + η + τ and ⟨g, z − c⟩ ≥ 0.
(23) Since MA (y old ) ≤
A 2 d 2 y A ≤ U + η + 2τ − d2y 2 2 1 G ≤ U− + Cs (η + τ ). 4A
f (y) ≤ MA (c) + τ −
Here 1 uses (23). Taking the minimum with the old upper value proves (14). For the cut, the bundle gap also gives m(x) − f (y) ≥
A 2 (d − d2x ) − τ . 2 y
16
Near-Optimal Smooth Nondual Convex Optimization
Consequently, A 2 (d − d2x ) + Γ − τ 2 y A = ⟨g, z − c⟩ + (d2x + d2y ) + Γ − τ 2 G2 ≥Γ+ − Cs (η + τ ). 2A
a(z) − (f (y) − Γ) ≥ ⟨g, z − x⟩ +
Replacing f (y) by the no-larger U + only deepens the cut. This proves (15).
Appendix E. Certified numerical solves and cuts Proposition 13 (Certified numerical coupling) [↓] Let 1 < s ≤ 2, Q = RBpd ⊆ RBsd , and A ≥ Cs Hτ /8 . Fix η, τ > 0 and 0 < ν ≤ min{τ , AR2 }. Certified approximate model solves and the sign search of Lemma 10 produce a feasible witness y + , certificate U + ≥ f (y + ), and a valid affine cut b a ≤ f such that G2 + Cs (η + τ + ν), 8A G2 − Cs (η + τ + ν), b a(z) − (U + − Γ) ≥ Γ + 4A U+ ≤ U −
where G is the cut-normal norm in ℓs∗ . The number of first-order calls is Os (log(2 + AR2 /τ ) log(2 + AR2 /η)). For outer tests, compute a certified interval [Lm , Vm ] of width Γ/16 for minQ m, and terminate the phase if Lm ≥ U − 5Γ/4. Keeping the largest certified lower bound preserves a gap contraction of at most 7/8 per phase. Proof of Proposition 13. Put h(u) = A∥u − c∥2s /2 and µ = A(s − 1). For each tangent model mj , compute a feasible x ej and lower bound lj with mj (e xj ) + h(e xj ) ≤ lj + ζ. Write ℓj = minQ (mj + h), so lj ≤ ℓj , retain Vj = mini≤j (f + h)(e xi ), and stop when Vj − lj ≤ τ . Otherwise add the tangent at x ej . For the exact model minimizer xj , strong convexity gives ∥e xj − xj ∥2s ≤ 2ζ/µ,
∥e xj+1 − x ej ∥2s ≤ 4(ℓj+1 − ℓj + 2ζ)/µ.
The second bound compares both points to xj . Set Ej = Vj − ℓj , ω = τ /8, and a = 2Hω /µ. The inexact gradient trick at the last tangent and Vj+1 ≤ Vj give Ej+1 ≤ a(ℓj+1 − ℓj ) + (2a + 1)ζ + ω ≤ a(Ej − Ej+1 ) + (2a + 1)ζ + ω. For ζ ≤ τ /[16(1 + a)], this contracts to at most τ /4. Since E0 ≤ 2Hω R2 + ω + ζ and Vj − lj ≤ Ej + ζ, it takes Os (log(2 + AR2 /τ )) calls to certify (11) relative to the exact model minimum; the point computed is x e, while the exact minimizer x is used only in the analysis below. At termination, let x be the exact model minimizer and compute g = AJs (c − x e) in the stated real-arithmetic model. The duality map satisfies ∥Js (w) − Js (w′ )∥s∗ ≤ 17
Martı́nez-Rubio Bullins Guzmán Molina
Cs R2−s ∥w − w′ ∥s−1 on 2RBsd ; this follows from its coordinate formula and the (s − 1)s Hölder continuity of t 7→ |t|s−2 t. For g ◦ = AJs (c − x), choose ( 2/(s−1) ) ν ν τ µ , Eg = ζ ≤ min , ν, . 16(1 + a) 2 4Cs AR3−s 4R Then ∥g − g ◦ ∥s∗ ≤ Eg . The exact cut a◦ (v) = m(x) + ⟨g ◦ , v − x⟩ is valid, while the model gap and convexity of h give 0 ≤ m(e x) − m(x) − ⟨g ◦ , x e − x⟩ ≤ ζ. Thus the computable cut b a(v) = m(e x) + ⟨g, v − x e⟩ − ζ − 2REg satisfies a◦ (v) − ζ − 4REg ≤ b a(v) ≤ a◦ (v) ≤ f (v)
(v ∈ Q).
(24)
By (22), g is a (τ + 2REg )-subgradient of MA on Q. The proof of Lemma 10 therefore applies with that error, giving MA (c) ≤ MA (y old ) + η + τ + 2REg and ⟨g, z − c⟩ ≥ 0 in O(log(2+AR2 /η)) trials. Consequently ⟨g ◦ , z − c⟩ ≥ −2REg . Apply the proof of Lemma 11 to g ◦ , then use (24) and ∥g ◦ ∥2s∗ ≥ G2 /2 − Eg2 . Since Eg2 /A ≤ ν/16, this gives the stated descent and cut bounds. Retain the witness corresponding to U + = min{U, f (y)}. For the outer test, let Vm = m(vm ) with vm ∈ Q. If Lm ≥ U − 5Γ/4, the new gap is at most 5Γ/4, which is 5/8 of the starting gap. Otherwise m(vm ) < U − 19Γ/16, leaving slack 3Γ/16 in every model cut of K = {m ≤ U −Γ}. Upper progress still contracts the gap by 7/8. To apply the companion’s implementation, normalize R = L = 1 and let B be the largest norm of the stored cut normals. Here B ≤ 2 max A. With θ = min{1/2, Γ/[32(1 + B)]}, θ (1 − θ)vm + √ B2d ⊆ K. 2 d This follows from the cut slack and ∥vm ∥p ≤ 1. The phase parameters give inversepolynomial radii and objective tolerances for fixed κ, s. The transfer to the companion’s sample problems is proved in Proposition 14. Inner tangent slopes are bounded by ∥∇f (0)∥s∗ + 1 in normalized units, giving the logarithmic dependence stated in Section 9.
Proposition 14 (Feasible selector implementation) Let 1 ≤ p < min{q, 2} and s = min{q, 2}. The numerical version of Algorithm 1, initialized by Lemma 16, admits feasible ep,s (RN 1−ρp,q ) in phase k ≥ 0, conditionally on randomized selectors with ℓs -movement O Γ its initial history, with probability at least 1 − δ k . Their implementation uses no additional first-order calls. For 0 < ε ≤ LRκ , allocating δ k = δ/[2(k + 1)2 ] gives simultaneous success with probability at least 1 − δ and the additional-work bound in Section 9 on every run. On a sampling cutoff, return the retained feasible upper witness. Proof Normalize R = L = 1 by replacing f with f (R ·)/(LRκ ). Fix a phase and write N = NΓ , ρ = ρp,q . Apply MG26, Proposition 11 with their (q, T ) = (s, N ), sampling and solver errors E = Esol = N −ρ /4, and failure probability δ k /2. Use exactly their sample count (17), objective tolerance (32), and feasible empirical average. These give exact feasibility and, by their path-error estimate (33) and Theorem 9, the stated movement bound. Their conditional concentration argument already covers adaptive bodies and fresh 18
Near-Optimal Smooth Nondual Convex Optimization
samples; shorter phases can be padded by their last body. Our coupling is evaluated at the computed feasible center itself, so no additional cut error is needed. We check only the geometric input to the companion’s Appendix E. The preced√ ing proof supplies an interior ball of radius θ/(2 d) in each queried Kt , where θ = min{1/2, Γ/[32(1 + B)]} and the stored cut normals satisfy B ≤ 2 max A. Shrinking the head-tail decomposition of√vm by 1 − θ, exactly as there, gives an interior ball in its lift of radius θ min{1, R1 , Rs }/(4 d), with R1 = N 1−1/p and Rs = N 1/s−1/p ; an outer radius is at most 4N . Norm constraints and stored cuts supply the same separation oracles without queries to f . Hence the certified feasible solves of Appendix E apply to our aggregate cuts. The fixed powers are permitted directly in our model, without rational-exponent approximation. Also use the Gaussian cutoff in Appendix E with planned draw budget (N + 1)M , where M is the sample count above, and phase failure parameter δ k . It costs probability at most δ k /2 and bounds the work of every sample solve. Since Γ > ε/2 in active phases, our planned horizons and AΓ make all inverse radii, inverse tolerances, and sample counts polynomial in the parameters of Section 9. The query guard bounds the number of stored cuts and center calls by J, and phase contraction bounds the number of phases. Model and tangent solves use the same certified procedure on Q, with the logarithmic affine-term P dependence established above. Thus work is bounded on every run, and k≥0 δ k ≤ δ gives simultaneous success. Rescaling restores R, L.
Appendix F. Phase tuning, initialization, and final assembly Lemma 15 (Quadratic phase and fixed point) Consider N nonterminal transitions in one phase with fixed A, Γ > 0, nonempty bodies K0 , . . . , KN ⊆ RBpd , and U0 − UN < Γ/4. PN −1 1−ρ ). Let G be the aggregate e Suppose the selector satisfies t t=0 ∥zt+1 − zt ∥s = O(RN residual norms. Assume the cumulative contribution of the line-search, bundle, and numerical errors is a sufficiently small multiple of Γ, and each cut error is at most Γ/2. Then AR2 1+2ρ e N = Os . Γ At the planned horizon N = NΓ , with the parameters in (17), this is equivalent, up to constants and logs, to (18). P Proof Before upper progress, sum (14) to obtain t<N G2t ≤ CAΓ. The weaker constants in Proposition 13 give the same estimate.PThe cut depth from (15), after absorbing its error, and the unpacked movement bound t<N ∥zt+1 − zt ∥s ≤ CRΛ(d, N )N 1−ρ give ΓX 1 ≤ RΛ(d, N )N 1−ρ . 2 Gt t<N
Hölder with exponents 3 and 3/2 gives !1/3 N≤
X
G2t
t<N
X 1 t<N
19
Gt
!2/3 .
Martı́nez-Rubio Bullins Guzmán Molina
Substitution proves the quadratic phase inequality. To test the planned horizon, set N = NΓ and use A ≍ L2/κ (N/Γ)(2−κ)/κ . The phase inequality becomes N 1+2ρ−(2−κ)/κ ≲ L2/κ R2 Γ−2/κ . Raising to κ/2 yields
LRκ , Γ with the movement logarithms restored as in (18). N κ−1+κρ ≲
To specify the horizon in Algorithm 1, fix Λ(d, N ) = 1 + log(2d + 2) log(2N ). The selector estimates in MG26, including their feasible approximations on the success event, give movement at most Cp,s RΛ(d, N )N 1−ρ over N transitions. Fix the constants in (17) as in the proof below, and a constant Cκ,p,s large enough for the preceding phase bound. The computable horizon rule is LRκ j j κ−1+κρ j κ NΓ = min 2 : j ∈ Z≥0 , (2 ) > Cκ,p,s Λ(d, 2 ) . (25) Γ Thus NΓ counts transitions, and a phase uses at most NΓ + 1 selector points. Lemma 16 (Affine-invariant initialization) One certified envelope call at c = 0 with A0 ≍ LRκ−2 ,
τ 0 ≍ LRκ
produces a feasible upper witness and a valid affine lower cut whose certified gap over Q is Oκ,s (LRκ ), independently of any affine term in f . Proof Let (x0 , y0 , m0 ) be the bundle certificate and g0 = A0 Js (−x0 ). The bundle gap and ∥x0 ∥s ≤ R give A0 R 2 f (y0 ) − m0 (x0 ) ≤ + τ 0. 2 Moreover ∥g0 ∥s∗ ≤ A0 R. The aggregate cut a0 (v) = m0 (x0 ) + ⟨g0 , v − x0 ⟩ therefore satisfies 5 f (y0 ) − min a0 (v) ≤ A0 R2 + τ 0 = O(LRκ ). v∈Q 2 The bound on the initial tangent gap in Proposition 9 is independent of an affine term in f , so the first-order call bound is affine-invariant as well. With numerical solves, the buffered cut and a lower-bound tolerance O(LRκ ) add only O(LRκ ) to this initial gap. Proof of Theorem 12. For randomized selectors, assign phase k ≥ 0 failure probability δ k = δ/[2(k + 1)2 ], using Proposition 14, including its Gaussian cutoff. Condition on simultaneous selector success. Fresh samples make each phase P guarantee valid conditionally on the past, so this event has probability at least 1 − k≥0 δ k ≥ 1 − δ. Initialize with Lemma 16. At a phase of scale Γ, set τ Γ , η Γ to a sufficiently small constant times Γ/NΓ and choose AΓ as in (17). Then the cumulative errors in (14) and (15) are small enough for Lemma 15. Choose NΓ by (25). If a phase contained NΓ nonterminal transitions, Lemma 15 20
Near-Optimal Smooth Nondual Convex Optimization
would give the opposite inequality, a contradiction. Thus the phase terminates earlier; one final empty-body step changes the count by at most one. Take ω = τ Γ /8 and a sufficiently large AΓ ≍κ,s Hω . By Propositions 9 and 13, every envelope call is logarithmic in 2+AR2 /τ Γ . For numerical solves, take ν Γ = 21 min{τ Γ , AΓ R2 } and use the early lower-bound test in Proposition 13; its contraction factor 5/8 is also at most 7/8. The line search is logarithmic as well. Put α = κ − 1 + κρ > 0. To reach error ε, every active phase has Γ > ε/2. Reading the gaps backwards from the final active phase bounds the oracle costs by a geometric series with ratio (7/8)1/α , up to logarithms. Including initialization, choose the deterministic first-order budget l m J(ε, δ) = Cκ,p,q 1 + (LRκ /ε)1/α [1 + log(2d) + log(2 + LRκ /ε) + log(2/δ)]8 , (26) α = κ − 1 + κρ. Here the fixed constant covers all the preceding bounds. The logarithmic power 8 suffices: ρ > 1/2 gives κ/α ≤ 2, so the horizon rule costs at most four logarithmic powers, the inner solves and line search add two, and geometric phase summation preserves this order. In eκ,p,q (1 + (LRκ /ε)1/α ). On simultaneous success, the certified gap particular, J(ε, δ) = O reaches ε within this budget, and each phase uses at most NΓ + 1 selector calls. On every run, the guards in Algorithm 1 enforce these budgets and retain a feasible output. Only within-phase edges are charged to movement; restarting the selector introduces no charged edge between phases. For a prescribed first-order budget T ≥ 1, set εT = min LRκ 2−j : j ∈ Z≥0 , J(LRκ 2−j , δ) ≤ T , J = J(εT , δ). (27) If this set is nonempty, run Algorithm 1 with accuracy εT . Minimality gives J(εT /2, δ) > T , while J(εT , δ) ≤ T bounds log(2 + LRκ /εT ) by Oκ,p,q (log(2 + T )). Hence εT = eκ,p,q (LRκ /T α ). If the set is empty, use one query at 0 and minimize its tangent over O Q. This gives error at most LRκ /κ; since then T < J(LRκ , δ), the same rate holds after increasing its logarithmic factor. Every retained upper witness is feasible and matches its upper certificate. Proof of Theorem 1. If p < q ≤ 2, use Theorem 12 with s = q. If p < 2 ≤ q, use the same theorem with s = 2 and the p/2 movement selector. These two cases cover p < min{q, 2} and give (4). For p = q ≤ 2, the classical universal accelerated method eκ,p (LRκ /T 3κ/2−1 ), including the logarithmic loss (Nes15) in the p-geometry gives error O at p = q = 1. For this endpoint, take r = 1 + 1/ log(2d + 2) and the prox function u 7→ e2 ∥u∥2r /[2(r − 1)], which is 1-strongly convex in ℓ1 and has range O(R2 log(2d)) on Q. Since κ(1 + 1/p − (1/p − 1/2)+ ) − 1 = 3κ/2 − 1 for p ≤ 2, this is also (4).
21
Martı́nez-Rubio Bullins Guzmán Molina
References [ABJ+24]
Deeksha Adil, Brian Bullins, Arun Jambulapati, and Aaron Sidford. Convex Optimization with p-Norm Oracles. 2024 (cit. on p. 5).
[AO14]
Zeyuan Allen-Zhu and Lorenzo Orecchia. Linear Coupling: An Ultimate Unification of Gradient and Mirror Descent. 2014 (cit. on p. 5).
[CGM24]
Juan Pablo Contreras, Cristóbal Guzmán, and David Martı́nez-Rubio. NonEuclidean High-Order Smooth Convex Optimization. 2024 (cit. on p. 5).
[CHJ+22]
Yair Carmon, Danielle Hausler, Arun Jambulapati, Yujia Jin, and Aaron Sidford. Optimal and Adaptive Monteiro–Svaiter Acceleration. 2022 (cit. on p. 5).
[Dan67]
John M. Danskin. The Theory of Max-Min and Its Application to Weapons Allocation Problems. Vol. 5. Econometrics and Operations Research. Berlin, Heidelberg: Springer, 1967 (cit. on p. 15).
[DGN14]
Olivier Devolder, François Glineur, and Yurii Nesterov. First-order methods of smooth convex optimization with inexact oracle. In: Mathematical Programming 146.1 (2014), pp. 37–75 (cit. on p. 9).
[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 pp. 3, 11).
[Guz15]
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, 3, 11).
[Lev17]
Kfir Y. Levy. Online to Offline Conversions, Universality and Adaptive Minibatch Sizes. In: Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA. Ed. by Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. N. Vishwanathan, and Roman Garnett. 2017, pp. 1613–1622 (cit. on p. 5).
[LNN95]
Claude Lemaréchal, Arkadii Nemirovskii, and Yurii Nesterov. New Variants of Bundle Methods. In: Mathematical Programming 69 (July 1995), pp. 111–147 (cit. on p. 3).
[MG26]
David Martı́nez-Rubio and Cristóbal Guzmán. Stable Movement for Nondual Lipschitz Convex Optimization: Efficiency and Nearly Optimal Oracle Rates. 2026 (cit. on pp. 1–4, 7, 12, 18, 20).
[Nes15]
Yurii Nesterov. Universal Gradient Methods for Convex Optimization Problems. In: Mathematical Programming 152.1–2 (2015), pp. 381–404 (cit. on pp. 3, 21).
[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. 3).
22
Near-Optimal Smooth Nondual Convex Optimization
[Ora23]
Francesco Orabona. Normalized gradients for all. In: arXiv preprint arXiv:2308.05621 (2023) (cit. on p. 5).
[Ouy26]
Yuyuan Ouyang. An O(1/T 3 ) Algorithm for Minimizing Convex Quadratic Functions over the L1 Ball . 2026 (cit. on p. 3).
23