[论文] Stable Movement for Nondual Lipschitz Convex Optimization: Efficiency ...

论文概要

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

中文摘要

我们研究在半径 R 的 ℓp 球上、关于 ℓq 范数为 G-Lipschitz 的凸函数优化问题的一阶 oracle 复杂度高效算法，其中 1≤p,q≤∞。当 p

原文摘要

We study efficient algorithms for realizing the first-order oracle complexity of optimization of \(G\)-Lipschitz convex functions with respect to the \(\ell_{q}\)-norm over an \(\ell_{p}\)-ball of radius \(R\), where \(1\leq p,q\leq \infty\). For \(p<q\), we obtain error \(\widetilde{O}_{p,q}(GR/T^{1/p-(1/q-1/2)_{+}})\) after \(T\) oracle queries, efficiently realizing the nearly optimal rates of (MBG+26), thereby resolving the nonsmooth end of the COLT 2015 open problem (Guz15b). In particular, the rate is \(\widetilde{O}(GR/T)\) for Euclidean Lipschitzness over an \(\ell_1\)-ball of radius \(R\) (\(p=1,q=2\)). Our solution consists of reducing convex Lipschitz optimization to the chasing nested convex sets problem in sublevel sets of an evolving bundle (LNN95; BBE+20): at each query we either find a point with ...

#论文 #arXiv #ML #小凯