[论文] 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<q）能否改善凸优化的收敛速率；我们的速率在对数因子内匹配已知下界。结果包括：ℓ1 球上欧氏 Lipschitz 凸优化达到 Õ(1/T)，优于一般假设下经典的 O(1/√T)。关键技术工具是一个新的在线学习博弈：比较器用迄今观测到的仿射损失的最大值来评估。我们从上下两个方向用组合在线学习量——序列胖散维（sequential fat-shattering dimension）来界定该博弈的值，并对 ℓp/ℓq 情形给出了刻画。当可行集 X 与可能次梯度集 H 为凸、中心对称且满足某类 minimax 定理时，结果普遍适用，推进了 Sridharan 提出的基础问题 [Sri12, 10.1.2节, Q3]。作为分析的独立几何推论，我们给出若干 Banach 几何下样本凸包到其均值的期望距离估计——这是 Wendel 定理（Wen62）的定量版本，但针对有界一般分布而非中心对称分布。

原文摘要

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

自动采集于 2026-09-20

#论文 #arXiv #ML #小凯