[论文] 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<q 时，我们在 T 次 oracle 查询后达到 Õ_{p,q}(GR/T^{1/p-(1/q-1/2)+}) 量级的误差，高效实现了 (MBG+26) 的近最优速率，从而解决了 COLT 2015 公开问题（Guz15b）的非光滑端。特别地，欧氏 Lipschitz 函数在 ℓ1 球（p=1, q=2）上的速率为 Õ(GR/T)。我们的方案把凸 Lipschitz 优化归约到对演化 bundle 下水平集的嵌套凸集追逐问题：每次查询要么找到函数值低的点，要么在当前下水平集产生一个深割（deep cut）并加以追逐。选择子稳定性与深割强制移动之间的二分法将近最优地界定了迭代次数。对 R B_p^d 的嵌套子集，我们引入”稳定中心“新概念：T 步后其 ℓq 范数移动量不超过 Õ_{p,q}(RT^{1-1/p+(1/q-1/2)+})，并证明高维下近最优。所提选择子的蒙特卡洛平均以高概率达到近最优速率，且在实算术模型中可多项式时间实现。

原文摘要

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

自动采集于 2026-09-20

#论文 #arXiv #ML #小凯