From Low Probability to High Confidence in Stochastic Convex Optimization
From Low Probability to High Confidence in Stochastic Convex Optimization
复制标题
DOI：
--
复制
发表时间：
2019-07
期刊：
影响因子：
--
通讯作者：
Damek Davis;D. Drusvyatskiy;Lin Xiao;Junyu Zhang
中科院分区：
文献类型：
--
作者：
Damek Davis;D. Drusvyatskiy;Lin Xiao;Junyu Zhang
随机凸优化的标准结果对算法为生成一个期望函数值较小的点所需的样本数量进行了界定。更细致的高概率保证很少见，并且通常要么依赖于“轻尾”噪声假设，要么表现出更差的样本复杂度。在这项工作中，我们表明，对于强凸问题的一大类随机优化算法，可以用高置信界进行扩充，其额外成本在置信水平上仅是对数级的，在条件数上是多项对数级的。我们提出的方法称为proxBoost，它很基础，建立在两个众所周知的要素之上：稳健的距离估计和近端点方法。我们讨论了它对流式（在线）算法和基于经验风险最小化的离线算法的影响。
Standard results in stochastic convex optimization bound the number of samples that an algorithm needs to generate a point with small function value in expectation. More nuanced high probability guarantees are rare, and typically either rely on "light-tail" noise assumptions or exhibit worse sample complexity. In this work, we show that a wide class of stochastic optimization algorithms for strongly convex problems can be augmented with high confidence bounds at an overhead cost that is only logarithmic in the confidence level and polylogarithmic in the condition number. The procedure we propose, called proxBoost, is elementary and builds on two well-known ingredients: robust distance estimation and the proximal point method. We discuss consequences for both streaming (online) algorithms and offline algorithms based on empirical risk minimization.