SOURCE-LINKED INTELLIGENCE

The First-Order Oracle Complexity of Lipschitz Convex Optimization in Nondual Settings

arXiv · AI, language, vision and robotics · article · Sep 17, 2026 · UTC

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

Read original source ↗ Open in workspace

recordType

paper

region

Global