研究凸优化在非对偶设置下的第一阶oracle复杂度
The First-Order Oracle Complexity of Lipschitz Convex Optimization in Nondual Settings
这篇论文研究的是凸优化理论，对于数学和计算机科学领域的研究者来说，如果他们关注优化算法的理论基础，可能会觉得这篇论文很有价值。
本文研究了在非对偶设置下，对于目标函数在ℓ_q范数下Lipschitz的凸优化问题，在ℓ_p-球上的第一阶黑盒优化，解决了COLT开放问题（Guz15b）的不可微版本，即当可行集更小时（p<q）是否可以改善收敛速率。其速率包括凸欧几里得-Lipschitz优化在ℓ_1-球上的\(\widetilde O(1/T)\)，优于经典速率\(O(1/\sqrt{T})\)。关键的技术装置是一个新的在线学习游戏，其中比较器使用迄今为止观察到的仿射损失的极大值进行评估。我们通过一个组合在线学习量——顺序脂肪碎裂维度——来界定了该游戏的值，并对其在ℓ_p/ℓ_q情况下的特征进行了刻画。我们的结果一般适用于可行集X和可能的次梯度集H是凸、中心对称且具有某种minmax定理的情况，推进了Sridharan [Sri12, Section 10.1.2, Q3]提出的根本性问题。作为几何分析的一个独立结果，我们获得了凸包样本到其均值的期望距离在几个Banach几何中的估计，这是Wendel定理（Wen62）的一个版本，但定量且适用于有界的一般分布，而非中心对称分布。
The First-Order Oracle Complexity of Lipschitz Convex Optimization in Nondual Settings
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 quantity: the sequential fat-shattering dimension, which we characterize for the $\ell_p / \ell_q$ case. Our results generally apply when the feasible set $X$ and the set of possible subgradients $H$ are convex, centrally symmetric, and admit a type of minmax theorem, advancing on a fundamental question by Sridharan [Sri12, Section 10.1.2, Q3]. As a geometric consequence of our analysis, of independent interest, we obtain estimates for the expected distance of a convex hull of samples to their mean in several Banach geometries, a version of the celebrated Wendel's theorem (Wen62), but quantitative and for bounded general distributions as opposed to centrally symmetric ones.