The First-Order Oracle Complexity of Lipschitz Convex Optimization in Nondual Settings
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 Õ(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, which we characterize for the ℓp / ℓq case. Our results generally apply when the feasible set X and the set of possible subgradients H are convex, centrally symmetric, and admit a type of minmax theorem, advancing on a fundamental question by Sridharan [Sri12, Section 10.1.2, Q3]. As a geometric consequence of our analysis, of independent interest, we obtain estimates for the expected distance of a convex hull of samples to their mean in several Banach geometries, a version of the celebrated Wendel's theorem (Wen62), but quantitative and for bounded general distributions as opposed to centrally symmetric ones.
Related
- Stable Movement for Nondual Lipschitz Convex Optimization: Efficiency and Nearly Optimal Oracle Rates
- Near-Optimal Acceleration for Smooth ℓp / ℓq Nondual Convex First-Order Oracle Optimization
- Optimal Deterministic First-Order Oracle Complexity for Nonconvex-Concave Minimax Optimization
- Descending Everest with First-Order Oracles: Oracle Complexity of Convex Optimization under (L0,L1)-Smoothness
- Minimax Oracle Call Complexity, Rounds and Admissible Noise in Zeroth-Order Optimization of Highly Smooth Functions
BibTeX
@misc{martinezrubio2026firstorder,
title = {{The First-Order Oracle Complexity of Lipschitz Convex Optimization in Nondual Settings}},
author = {David Martínez-Rubio and Brian Bullins and Cristóbal Guzmán and Mathieu Molina},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.20687},
eprint = {2609.20687},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.20687},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - The First-Order Oracle Complexity of Lipschitz Convex Optimization in Nondual Settings
AU - David Martínez-Rubio
AU - Brian Bullins
AU - Cristóbal Guzmán
AU - Mathieu Molina
PY - 2026
DA - 2026/09/17
PB - arXiv
DO - 10.48550/arxiv.2609.20687
UR - https://arxiv.org/abs/2609.20687
AB - 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 Õ(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, which we characterize for the ℓ_p / ℓ_q case. Our results generally apply when the feasible set X and the set of possible subgradients H are convex, centrally symmetric, and admit a type of minmax theorem, advancing on a fundamental question by Sridharan [Sri12, Section 10.1.2, Q3]. As a geometric consequence of our analysis, of independent interest, we obtain estimates for the expected distance of a convex hull of samples to their mean in several Banach geometries, a version of the celebrated Wendel's theorem (Wen62), but quantitative and for bounded general distributions as opposed to centrally symmetric ones.
ER -