Optimal Rates for Zero-Order Convex Optimization: The Power of Two Function Evaluations
Optimal Rates for Zero-Order Convex Optimization: The Power of Two Function Evaluations
复制标题
DOI：
10.1109/tit.2015.2409256
复制
发表时间：
2013-12
影响因子：
2.5
通讯作者：
John C. Duchi;Michael I. Jordan;M. Wainwright;Andre Wibisono
中科院分区：
文献类型：
--
作者：
John C. Duchi;Michael I. Jordan;M. Wainwright;Andre Wibisono
我们考虑的随机和非随机凸优化问题，只使用函数值，而不是梯度的导数免费算法。专注于收敛速度的非渐近界，我们表明，如果对函数值是可用的，算法的d-维优化，使用梯度估计的基础上随机扰动遭受的因素，最多的收敛速度超过传统的随机梯度方法。我们建立了这样的结果，光滑和非光滑的情况下，锐化以前的分析，提出了一个更坏的尺寸依赖，并将我们的结果的情况下，多个（m ≥ 2）的评估。我们补充我们的算法开发与信息理论的下限上的极大极小收敛速度的这样的问题，建立我们可实现的结果的锐利度恒定（有时对数）的因素。
We consider derivative-free algorithms for stochastic and nonstochastic convex optimization problems that use only function values rather than gradients. Focusing on nonasymptotic bounds on convergence rates, we show that if pairs of function values are available, algorithms for d-dimensional optimization that use gradient estimates based on random perturbations suffer a factor of at most √d in convergence rate over traditional stochastic gradient methods. We establish such results for both smooth and nonsmooth cases, sharpening previous analyses that suggested a worse dimension dependence, and extend our results to the case of multiple (m ≥ 2) evaluations. We complement our algorithmic development with information-theoretic lower bounds on the minimax convergence rate of such problems, establishing the sharpness of our achievable results up to constant (sometimes logarithmic) factors.