[论文] The First-Order Oracle Complexity of Lipschitz Convex Optimization in ...

论文概要

研究领域: ML 作者: David Martínez-Rubio, Brian Bullins, Cristóbal Guzmán, Mathieu Molina 发布时间: 2026-09-17 arXiv: 2609.20687

中文摘要

我们研究 ℓp 球上目标函数关于 ℓq 范数为 Lipschitz 的一阶黑盒凸优化，肯定性地解决了 COLT 公开问题（Guz15b）的非光滑版本：更小的可行集几何（p

原文摘要

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 quanti...

#论文 #arXiv #ML #小凯