First-Order Oracle Complexity of Lipschitz Convex Optimization
The First-Order Oracle Complexity of Lipschitz Convex Optimization in Nondual Settings
This paper provides a theoretical analysis of optimization algorithms, which is valuable for researchers and developers working on machine learning and optimization problems.
This academic paper addresses the complexity of first-order black-box convex optimization over an ℓ_p-ball for objectives Lipschitz in the ℓ_q-norm.
It solves a COLT open question regarding whether the geometry of a smaller feasible set can improve convergence rates, matching prior lower bounds up to logarithmic factors.
The study includes rates like \(\widetilde O(1/T)\) for convex Euclidean-Lipschitz optimization over the ℓ_1-ball, improving on the classical \(O(1/\sqrt{T})\) rate.
A key technical device is a new online learning game involving affine losses.The results apply to convex, centrally symmetric sets and advance on a fundamental question by Sridharan.
As a geometric consequence, the paper obtains estimates for the expected distance of a convex hull of samples to their mean in several Banach geometries, a quantitative version of Wendel's theorem.
The First-Order Oracle Complexity of Lipschitz Convex Optimization in Nondual Settings
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. 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 $\ell_p / \ell_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.
This report is categorized under AITOP's "Papers" desk, focusing on US frontier AI labs and Silicon Valley technology leaders. Within our cross-regional analytical framework, it directly maps to AI developer toolchains, coding agents, and engineering workflows. Key entities and technical topics under continuous tracking include convex optimization, first-order methods, Lipschitz convex optimization, online learning.
Source attribution: curated from arXiv cs.LG (@David Martínez-Rubio, Brian Bullins, Cristóbal Guzmán, Mathieu Molina).