Near-Optimal Acceleration for Smooth $\ell_p$ / $\ell_q$ Nondual Convex First-Order Oracle Optimization
David Martínez-Rubio, David Martínez-Rubio, Brian Bullins, Brian Bullins, Cristóbal Guzmán, Cristóbal Guzmán, Mathieu Molina, Mathieu Molina
math.OC · cs.LG
Quick verdict
Claims near-optimal rates for ℓp/ℓq Hölder-smooth convex optimization, solving Guzmán's 2015 open problem; selector machinery is in a companion paper.
Summary
This theory paper resolves the COLT 2015 open problem of Guzmán: the oracle complexity of convex optimization over an ℓp ball when smoothness is measured in a different ℓq norm. For objectives with (L, κ−1)-Hölder-continuous gradients (1<κ≤2) over RB_p^d, the authors prove that when T≤d and p<min{q,2}, a polynomial-time first-order method achieves error Õ_{κ,p,q}(LR^κ/T^{κ(1+1/p−(1/q−1/2)+)−1}), matching the Guzmán–Nemirovski lower bounds up to logarithmic factors; at (p,q)=(1,2) this yields Õ(LR^κ/T^{2κ−1}), including cubic T^{-3} decay for smooth objectives. The mechanism couples a movement bound for selectors chasing nested convex bodies (imported from the companion paper Martínez-Rubio–Guzmán 2026) with Hölder descent, balancing guaranteed descent against cut depth via a power-mean/harmonic-mean inequality; constrained feasibility is recovered through an inexact-gradient Moreau envelope with certified bundle solves. Appendices A–F supply proofs, including a randomized selector implementation and certified numerical solves. Limitations are explicit: the manuscript is a self-declared unpolished draft; the central selector primitive and its implementation live in the companion paper; guarantees are restricted to T≤d; computation is analyzed in a strong real-arithmetic model; and there are no experiments.
Review complete
Assessment at a glance
4
risk flags identified
● high 1
● medium 2
● low 1
4 strengths · 4 weaknesses · 5 author questions
AI text signal = Binoculars zero-shot detector score over 20 sampled passages (Fast-DetectGPT co-reported) — absence does not prove human authorship, and a flag does not imply misconduct.
Levels reflect verification complexity — not a quality score. Evolve never rates your paper.
Key claims under review
- For T <= d and p < min{q,2} (or p = q <= 2), a polynomial-time first-order method returns a feasible point on RB_p^d with error O-tilde_{k,p,q}(L R^kappa / T^{kappa(1+1/p-(1/q-1/2)_+)-1}) after T oracle calls, with probability at least 1 - delta (Theorem 1).
- Combined with classical accelerated methods for 2 <= p < q, these upper bounds match the Guzman-Nemirovski lower bounds up to logarithmic factors, resolving Guzman's COLT 2015 open problem.
- At (p,q)=(1,2) the rate is O-tilde(L R^kappa / T^{2kappa-1}), including O-tilde(L R^2 / T^3) for smooth (kappa = 2) objectives.
- Any feasible selector with movement O-tilde(R N^{1-rho}) on nested convex bodies yields an accelerated method with exponent kappa - 1 + kappa*rho (Theorem 4), robust to budgeted descent and cut errors.
- The full algorithm, including inner bundle solves, line search and numerical certificates, needs at most O-tilde((L R^kappa / epsilon)^{1/alpha}) first-order calls with alpha = kappa - 1 + kappa*rho (Eq. 26) plus polynomial additional work.
Strengths
Resolves a decade-old open problem with exactly matching exponents
Theorem 1's exponent kappa(1+1/p-(1/q-1/2)_+)-1 reproduces the Guz15 lower-bound powers kappa(3/2+1/p-1/q)-1 (q<2) and kappa(1+1/p)-1 (q>=2) exactly (Section 8), giving matching upper bounds up to logs; at (p,q)=(1,2) this yields the advertised O-tilde(L R^2/T^3) cubic decay in the smooth case.
Clean conceptual reduction with geometric intuition
Theorem 4 converts any selector with movement O-tilde(R N^{1-rho}) into an optimizer with rate exponent kappa-1+kappa*rho; Section 2's harmonic-vs-power-mean inequality (Eq. 5) explains why acceleration emerges, echoing the Allen-Zhu-Orecchia coupling intuition the authors credit.
Unusually careful inexactness bookkeeping
Complete self-contained proof chain for the coupling
Weaknesses
Core primitive external to the paper
Self-declared unpolished draft with AI-drafted proofs
Partial coverage of the problem's regime
Idealized computational model and no experiments
Full Review Report
$1.99 · one-timeUnlock the complete preliminary analysis Evolve produced for this paper.
Report preview
Scope & Claims
The paper attacks Guzmán's COLT 2015 open problem (Guz15): determine the minimax first-order oracle complexity of minimizing a convex function over the ℓp ball RB_p^d when its gradients are (L, κ−1)-Hölder continuous in a different ℓq norm, 1<κ≤2. The headline result (Theorem 1) states that for T≤d and either p<min{q,2} or p=q≤2, a polynomial-time method returns x̂∈RB_p^d with f(x̂)−f* ≤ Õ_{κ,p,q}(LR^κ/T^{κ(1+1/p−(1/q−1/2)+)−1}) with probability ≥1−δ. At (p,q)=(1,2) this is Õ(LR^κ/T^{2κ−1}), including Õ(LR²/T³) for κ=2 — versus the classical O(T^{-2}). Section 8 checks the exponent against the Guz15/GN15 lower-bound powers: κ(3/2+1/p−1/q)−1 for q<2 and κ(1+1/p)−1 for q≥2; the algebra agrees, and combined with classical p-geometry methods for 2≤p<q (invoked by citation) the authors claim full resolution up to logarithmic factors.
The remaining sections cover Methodology Assessment, Statistical Evidence, Results & Reproducibility, Limitations & Risks, and Verdict & Recommendations.
- All 4 strengths & 4 weaknesses, analyzed in detail
- 4 risk flags with severity, section & reviewer questions
- Methods & statistical evidence assessment
- 5 questions a peer reviewer would ask
- Full six-dimension evaluation report & recommendations
One-time purchase · this paper only
One-time purchase, this paper only. AI-generated preliminary analysis — not peer review.
Frequently asked questions
What problem does this paper solve?
It resolves Guzman's COLT 2015 open problem: the first-order oracle complexity of minimizing a convex function over an l_p ball when smoothness (Holder continuity of the gradient, parameter kappa between 1 and 2) is measured in a different l_q norm. The paper's upper bounds match the known Guzman-Nemirovski lower bounds up to logarithmic factors.
How much faster is the method at (p,q)=(1,2)?
The rate is O-tilde(L R^kappa / T^(2kappa-1)). For smooth functions (kappa=2) this is O-tilde(L R^2 / T^3), a cubic decay in the number T of gradient queries, versus the classical O(T^-2) of accelerated gradient methods - a genuinely faster order enabled by the l1-ball/l2-smoothness mismatch.
Does the guarantee hold for any number of iterations T?
No. The main theorem is stated for T <= d (the high-dimensional regime) with confidence parameter delta. The O-tilde notation hides polylogarithmic factors but, by the authors' explicit convention, never hides polynomial dependence on the dimension d.
Is there code or an implementation available?
No. This is a theory paper: it provides pseudocode (Algorithm 1) and explicit parameter recipes analyzed in an idealized real-arithmetic model. The core movement-selector subroutine is implemented in a companion paper (Martinez-Rubio and Guzman, 2026), which is not included here.
About this review
This is an AI-generated preliminary review by Evolve.Pub, produced from the openly available text of the paper. It is not peer review and does not represent the authors' views. The canonical record of the paper is at the publisher link above.
- The companion paper MG26 (selector existence and polynomial-time implementation) was not available for inspection; the movement bound in Section 2 and all of Proposition 14 are accepted as cited.
- Figure 1 is only partially reconstructible from the extracted text; it illustrates the nonsmooth warm-up and does not affect any proof.
- The authors label the manuscript an unpolished draft; cross-referenced equations (Eqs. 17, 25-27) were checked only for internal consistency within the extracted text, not against a typeset version.
- No empirical section exists in the paper, so this review evaluates theory only.
Go deeper on this paper
Wrote a paper? Stress-test it before reviewers do.
Upload your manuscript for the same structured scrutiny — reasoning, statistics, evidence, figures, and reproducibility.