First-Order Oracle Complexity of Lipschitz Convex Optimization over ℓ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 ℓp-ball for objectives that are Lipschitz with respect to the ℓ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. Their rates match prior lower bounds up to logarithmic factors, including an Õ(1/T) rate for convex Euclidean-Lipschitz optimization over the ℓ1-ball, improving the classical O(1/√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 above and below via the sequential fat-shattering dimension, with a characterization for the ℓp/ℓq setting. The analysis applies broadly to convex, centrally symmetric feasible sets and subgradient sets satisfying a minimax theorem, advancing a foundational question of Sridharan. As a geometric corollary, the paper provides quantitative extensions of Wendel's theorem on expected distances from sample convex hulls to their means for bounded general 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

Abstract

We study first-order black-box convex optimization over an ℓp-ball for objectives Lipschitz in the ℓ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 ℓ1-ball, improving on the O(1/√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. We bound the value of this game above and below in terms of a combinatorial online learning quantity — the sequential fat-shattering dimension — and characterize it for the ℓp/ℓq setting.

Key Contributions

Affirmative resolution of the nonsmooth COLT open question (Guz15b): smaller feasible-set geometry (p < q) does improve convex optimization convergence rates.
Rates matching lower bounds up to logarithmic factors, including Õ(1/T) for Euclidean-Lipschitz convex optimization over the ℓ1-ball versus the classical O(1/√T).
New online learning game whose comparator uses the maximum of affine losses observed so far, bounded via the sequential fat-shattering dimension.
Generality: results hold when the feasible set X and possible subgradient set H are convex, centrally symmetric, and satisfy a certain minimax theorem, advancing a foundational problem posed by Sridharan [Sri12, Section 10.1.2, Q3].
Banach geometry corollary: expected distance estimates from sample convex hulls to their means under several geometries — a quantitative version of Wendel's theorem (Wen62) for bounded general (not necessarily centrally symmetric) distributions.

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