{"id":"arxiv/2609.20687","url":"https://arxiv.org/abs/2609.20687","tags":["math.OC","cs.LG"],"score":0,"title":"The First-Order Oracle Complexity of Lipschitz Convex Optimization in Nondual Settings","domain":"math.OC","source":"arxiv","authors":["David Martínez-Rubio","Brian Bullins","Cristóbal Guzmán","Mathieu Molina"],"reviews":0,"subject":"math.OC","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-17","reactions":{}}