We study the problem of minimizing a strongly convex, smooth function when we
have noisy estimates of its gradient. We propose a novel multistage accelerated
algorithm that is universally optimal in the sense that it achieves the optimal
rate both in the deterministic and stochastic case and operates without
knowledge of noise characteristics. The algorithm consists of stages that use a
stochastic version of Nesterov's method with a specific restart and parameters
selected to achieve the fastest reduction in the bias-variance terms in the
convergence rate bounds.

研究如何在存在梯度估计噪声的情况下，通过使用多阶段加速算法，探讨最小化强凸光滑函数的问题，并通过采用特定的重启和参数选择，实现在确定性和随机情况下的最佳速率，以及在不知道噪声特性的情况下操作。

一种普适最优的多阶段加速随机梯度方法

A Universally Optimal Multistage Accelerated Stochastic Gradient Method

We introduce a generic scheme for accelerating first-order optimization
methods in the sense of Nesterov, which builds upon a new analysis of the
accelerated proximal point algorithm. Our approach consists of minimizing a
convex objective by approximately solving a sequence of well-chosen auxiliary
problems, leading to faster convergence. This strategy applies to a large class
of algorithms, including gradient descent, block coordinate descent, SAG, SAGA,
SDCA, SVRG, Finito/MISO, and their proximal variants. For all of these methods,
we provide acceleration and explicit support for non-strongly convex
objectives. In addition to theoretical speed-up, we also show that acceleration
is useful in practice, especially for ill-conditioned problems where we measure
significant improvements.

本研究引入了一种通用方案，利用对加速邻域点算法的新分析，加快一阶优化方法。通过近似解决一系列精心选择的辅助问题来最小化凸目标，从而实现更快的收敛速度，为包括梯度下降、块坐标下降、SAG、SAGA、SDCA、SVRG、Finito/MISO 及其邻域点变体在内的大类算法提供加速和明确的非强凸目标支持，加速在实践中证明对病态问题尤其有用。

一种用于一阶优化的通用催化剂

A Universal Catalyst for First-Order Optimization

The problem of joint feature selection across a group of related tasks has
applications in many areas including biomedical informatics and computer
vision. We consider the l2,1-norm regularized regression model for joint
feature selection from multiple tasks, which can be derived in the
probabilistic framework by assuming a suitable prior from the exponential
family. One appealing feature of the l2,1-norm regularization is that it
encourages multiple predictors to share similar sparsity patterns. However, the
resulting optimization problem is challenging to solve due to the
non-smoothness of the l2,1-norm regularization. In this paper, we propose to
accelerate the computation by reformulating it as two equivalent smooth convex
optimization problems which are then solved via the Nesterov's method-an
optimal first-order black-box method for smooth convex optimization. A key
building block in solving the reformulations is the Euclidean projection. We
show that the Euclidean projection for the first reformulation can be
analytically computed, while the Euclidean projection for the second one can be
computed in linear time. Empirical evaluations on several data sets verify the
efficiency of the proposed algorithms.

本文提出了两种等价的平滑凸优化问题，并使用 Nesterov's 方法来加速计算。我们还展示了 Euclidean Projection 的解析和线性计算方法，并在多个数据集上验​​证了该算法的有效性。