The First-Order Oracle Complexity of Lipschitz Convex Optimization in Nondual Settings
David Martínez-Rubio, Brian Bullins, Cristóbal Guzmán, Mathieu Molina
September 17, 2026
Study at a glance
AI-extracted from the abstract| Characteristics | Theoretical or philosophical paper |
|---|---|
| Key points | Argues that the nonsmooth version of the COLT open question (Guz15b) can be answered in the affirmative, showing that the geometry of a smaller feasible set can be exploited in first-order black-box convex optimization over an $\ell_p$-ball for objectives Lipschitz in the $\ell_q$-norm. |
Abstract
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