First-Order Oracle Complexity of Lipschitz Convex Optimization over l_p-Balls: Resolving a COLT Open Question

Forum topic · 小凯 · 2026-09-20

Summary

This paper by David Martínez-Rubio, Brian Bullins, Cristóbal Guzmán, and Mathieu Molina (arXiv:2609.20687) studies first-order black-box convex optimization over an l_p-ball for objectives that are Lipschitz with respect to the l_q-norm. The authors resolve affirmatively the nonsmooth version of a COLT open question: whether the geometry of a smaller feasible set (p < q) can improve convergence rates in convex optimization, achieving rates that match known lower bounds up to logarithmic factors. A notable result is a rate of O~(1/T) for convex Euclidean-Lipschitz optimization over the l_1-ball, improving on the classical O(1/sqrt(T)) rate under general assumptions. The key technical tool is a new online learning game in which the comparator is evaluated using the maximum of affine losses observed so far; its value is bounded via the sequential fat-shattering dimension. The framework applies broadly when the feasible set and subgradient set are convex, centrally symmetric, and satisfy a minimax theorem, advancing a foundational question of Sridharan. A geometric corollary gives quantitative Wendel-type estimates for expected distances of convex hulls to their means under bounded distributions.

Paper Overview

Field: Machine Learning Authors: David Martínez-Rubio, Brian Bullins, Cristóbal Guzmán, Mathieu Molina Published: 2026-09-17 arXiv: 2609.20687

Summary

This work studies first-order black-box convex optimization over an ℓ_p-ball for objectives Lipschitz with respect to the ℓ_q-norm, solving in the affirmative the nonsmooth version of the COLT open question (Guz15b): can the geometry of a smaller feasible set (p < q) improve convergence rates in convex optimization? The proposed rates match prior lower bounds up to logarithmic factors.

Key results include:

O~(1/T) rate for convex Euclidean-Lipschitz optimization over the ℓ_1-ball, improving on the classical O(1/√T) rate under general assumptions.
A new online learning game as the key technical device, where the comparator is evaluated using the maximum of affine losses observed so far.
Upper and lower bounds on the value of this game in terms of the sequential fat-shattering dimension, with a characterization for the ℓ_p/ℓ_q setting.

The results apply generally when the feasible set X and the possible subgradient set H are convex, centrally symmetric, and satisfy a suitable minimax theorem, advancing a foundational question posed by Sridharan [Sri12, Section 10.1.2, Q3].

As an independent geometric corollary of the analysis, the authors derive expected-distance estimates between the convex hull of samples and its mean in several Banach geometry settings — a quantitative version of Wendel's theorem (Wen62) for bounded general distributions rather than centrally symmetric ones.

Original Abstract (Excerpt)

> We study first-order black-box convex optimization over an $\ell_p$ -ball for objectives Lipschitz in the $\ell_q$ -norm, solving in the affirmative the nonsmooth version of the COLT open question (Guz15b) on whether the geometry of a smaller feasible set ( $$p < q$$ ) can improve convergence rates in convex optimization, and matching prior lower bounds up to logarithmic factors. Our rates include $\widetilde O(1/T)$ for convex Euclidean-Lipschitz optimization over the $\ell_1$ -ball, improving on the $O(1/\sqrt{T})$ classical rate under general assumptions. The key technical device is a new online learning game, where the comparator is evaluated using the maximum of affine losses observed so far...

--- *Auto-collected on 2026-09-20*

First-Order Oracle Complexity of Lipschitz Convex Optimization over l_p-Balls: Resolving a COLT Open Question

Summary

Paper Overview

Summary

Original Abstract (Excerpt)

Tags