An Accelerated Method for Derivative-Free Smooth Stochastic Convex Optimization
针对仅能通过含噪观测获取函数值的无约束光滑凸优化问题，提出加速和无加速两种无导数算法，并分析其复杂度，其中加速算法的复杂度仅比基于梯度的加速算法多一个√n因子。
We consider an unconstrained problem of minimizing a smooth convex function which is only available through noisy observations of its values, the noise consisting of two parts. Similar to stochastic optimization problems, the first part is of stochastic nature. The second part is additive noise of unknown nature but bounded in absolute value. In the two-point feedback setting, i.e., when pairs of function values are available, we propose an accelerated derivative-free algorithm together with its complexity analysis. The complexity bound of our derivative-free algorithm is only by a factor of $\sqrt{n}$ larger than the bound for accelerated gradient-based algorithms, where $n$ is the dimension of the decision variable. We also propose a nonaccelerated derivative-free algorithm with a complexity bound similar to the stochastic gradient--based algorithm; that is, our bound does not have any dimension-dependent factor except logarithmic. Notably, if the difference between the starting point and the solution is a sparse vector, for both our algorithms, we obtain a better complexity bound if the algorithm uses an 1-norm proximal setup rather than the Euclidean proximal setup, which is a standard choice for unconstrained problems.