The First-Order Oracle Complexity of Lipschitz Convex Optimization in Nondual Settings
David Martínez-Rubio, Brian Bullins, Cristóbal Guzmán, Mathieu Molina
math.OC · cs.LG
Quick verdict
Solves the nonsmooth COLT'15 nondual open question with Õ(1/T) on ℓ1-ball via max-regret+sfat; near-matching bounds, but algorithm is exponential-time.
Summary
This theory paper resolves the nonsmooth version of a COLT 2015 open question by Guzmán on first-order convex optimization in nondual settings, where the feasible set is the ℓp-ball but objectives are Lipschitz in the ℓq-norm with p<q. The authors establish the minimax rate Õ(T^{-(1/p-(1/q-1/2)_+)}) for p≤q, matching known lower bounds up to logarithmic factors; notably, Euclidean-Lipschitz convex optimization over the ℓ1-ball achieves Õ(1/T), improving the classical O(1/√T). The proof introduces 'max-regret', an online learning game whose comparator is T times the maximum of past losses rather than their sum. A reduction chain connects the max-regret minimax value to convex-hull approximation of distribution means and to the sequential fat-shattering dimension of the induced linear class, which the authors characterize for ℓp/ℓq up to log factors, yielding two-sided bounds. General results hold when the feasible set and subgradient set are convex, centrally symmetric, and admit a minmax theorem, partially answering Sridharan's question; infinite-dimensional instances (Sobolev, Lipschitz, ℓp-basis) and quantitative Wendel-type convex-hull bounds follow. Main limitations: the near-optimal strategy is only existential — realized via dynamic programming in time exponential in T and d — with efficient algorithms deferred to future work, and all rates hold up to logarithmic factors.
Review complete
Assessment at a glance
3
risk flags identified
● high 0
● medium 2
● low 1
5 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 1≤p≤q≤∞ with d≥T, first-order convex optimization over B^d_p with ℓq-Lipschitz objectives has minimax error Õ_{p,q}(T^{-(1/p-(1/q-1/2)_+)}), matching known lower bounds up to log factors and resolving the nonsmooth case of Guzmán's COLT 2015 open question.
- Convex Euclidean-Lipschitz optimization over the ℓ1-ball admits Õ(1/T) error, a polynomial improvement over the classical O(1/√T) subgradient rate under general assumptions.
- The minimax value of the new max-regret game is characterized up to log factors by the sequential fat-shattering dimension of the associated linear class in any symmetric convex setting admitting a minmax theorem (Theorem 10), partially answering Sridharan's question.
- sfat_α and fat_α agree up to logarithmic factors for linear classes between ℓp- and ℓq*-balls (Theorem 12), with explicit two-regime profiles depending on p<q or p≥q and the d vs T cutoff.
- Expected distance from the convex hull of T iid samples to their mean admits matching upper/lower bounds in the (p,q) case (Theorem 7, Corollary 8), decaying at most as fast as 1/T for benign geometries — a quantitative Wendel-type result for general bounded distributions.
Strengths
Resolves a decade-old open problem with matching rates
The nonsmooth case of Guzmán's COLT 2015 open question (Guz15b) is settled: for p≤q, T≤d the rate Õ_{p,q}(T^{-(1/p-(1/q-1/2)_+)}) (Corollary 11 via Theorem 10) matches the prior lower bounds up to log factors, with the ℓ1/Euclidean case reaching Õ(1/T) versus the classical O(1/√T).
Conceptually new online learning device
Max-regret (eq. 1), where the comparator is T×max of past losses, is proven compatible with convex optimization via a three-line Jensen argument (Lemma 4) and a triplex-style minimax reduction (Proposition 5); it circumvents the Ω(T^{-1/2}) standard-regret barrier (RST15a Prop 9, CDL25) and connects to bundle methods (Kelley 1960 onward), claimed the first with a worst-case oracle-rate advantage.
Two-sided bridge from optimization to sequential complexity
Independent-interest geometric corollaries
Transparent disclosure of AI-assisted proofs
Weaknesses
No computationally efficient algorithm
All results up to logarithmic factors
Long external-dependency proof chain, partially AI-generated
Lower-bound novelty is partial
Full Review Report
$1.99 · one-timeUnlock the complete preliminary analysis Evolve produced for this paper.
Report preview
Scope & Claims
This is a pure theory paper on the minimax first-order oracle complexity of nonsmooth convex optimization in **nondual geometries**: minimize a G_q-Lipschitz convex function over the ℓp-ball B^d_p with p<q (flagship case (p,q)=(1,2)). The claims are all theorem-backed in the extracted text:
1. For p≤q and T≤d, the minimax error is Õ_{p,q}(T^{-(1/p-(1/q-1/2)_+)}) (Corollary 11, via Theorem 10 and Lemma 4), matching the lower bounds of Guz15a/Guz15b up to logarithmic factors and resolving the nonsmooth case of the COLT 2015 open problem. The polynomial improvement over mirror descent's O(T^{-1/max{q,2}}) occurs exactly when p<min{q,2}; the abstract's ℓ1/Euclidean headline is the s=1 endpoint, Õ(1/T) vs O(1/√T).
2. A general two-sided characterization: if sfat_α(L_{X,H}) = eΘ((Λ_{X,H}/α)^r), then V^max_{X,H,T}/T = eΘ(Λ_{X,H}T^{-1/r}) (Theorem 10, eq. (10)) — valid whenever X, H are convex, centrally symmetric, and a minmax theorem applies (Assumption 3, justified via Sion for compact/reflexive regimes).
3. sfat and fat agree up to log factors for the ℓp/ℓq* linear class (Theorem 12), in both the p<q and p≥q regimes and the d vs T cutoff, using known fat profiles (eq. (11)-(12), MS04, MPR05).
4. Quantitative Wendel-type bounds on the expected distance from the convex hull of T iid samples to their mean (Theorem 7, Corollary 8), matching in the (p,q) case, with a coupon-collector lower bound c·log T/T (Proposition 9) proving 1/T is the fastest possible decay — and a sharp 1D example (atoms at −1 and 1/T) showing exponential decay fails for general distributions.
5. Infinite-dimensional instances (Props 13–15): Sobolev H^s gives E=T^{-(1/2+s/m)} reaching 1/T at critical smoothness s=m/2; 1-Lipschitz functions on [0,1]^m give T^{-1/m} (1/T in 1D); ℓp coefficient balls (1<p<2) give T^{-1/p}.
The remaining sections cover Methodology Assessment, Statistical Evidence, Results & Reproducibility, Limitations & Risks, and Verdict & Recommendations.
- All 5 strengths & 4 weaknesses, analyzed in detail
- 3 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 does 'nondual setting' mean in convex optimization, and why does it matter?
Usually, minimizing over a set bounded in a norm pairs it with gradients bounded in the dual norm (e.g., ℓp-ball with ℓp*-bounded gradients), where mirror descent is provably optimal. A nondual setting mismatches them — e.g., the ℓ1-ball with Euclidean-bounded (Lipschitz) gradients. This paper shows the smaller feasible ball genuinely helps when p<q: the optimal first-order rate improves polynomially over the dual-geometry rate, answering a COLT 2015 open question in the nonsmooth case.
Does this paper provide a practical algorithm?
No. The near-optimal rates are established through a minimax (existence) argument. The optimal strategy can be realized only by dynamic programming with runtime exponential in the horizon T and dimension d, and the authors explicitly leave polynomial-time algorithms to future work. The contribution is information-theoretic, not yet computationally practical.
What improvement does the paper give on the ℓ1-ball?
For convex objectives that are Lipschitz in the Euclidean norm, restricted to the ℓ1-ball (or subsets of it), the paper achieves error Õ(1/T) after T first-order oracle queries in the high-dimensional regime d≥T, improving the classical O(1/√T) subgradient rate — a polynomial speedup, valid up to logarithmic factors.
What is 'max-regret' in this paper?
A new performance metric for online learning: instead of comparing cumulative loss to the best fixed action's cumulative loss (standard regret), max-regret compares the sum of the learner's losses to T times the maximum single loss of the best fixed action. It preserves the convex-optimization interpretation via averaging, is always at most standard regret, and escapes the Ω(T^{-1/2}) regret lower-bound barrier; its value is characterized by the sequential fat-shattering dimension.
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.
- Text extraction truncated several parts (part of Section 4.1 including the full Theorem 12 statement, Section 5 opening, parts of Appendices A and D); judgments rest on the visible statements and appendix proofs.
- Proof correctness was not independently re-verified line-by-line; the log-factor bookkeeping in Theorem 12's p<q, p<2 case cannot be fully checked from the extracted text.
- No figures, hyperlinked notation, or supplementary material were verifiable; review is based on arXiv v1 (Sep 2026).
- Related-work completeness against the 2015-2026 nondual-complexity literature could not be audited offline.
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.