论文标题
黑盒非平滑问题的一阶光滑优化的功能
The Power of First-Order Smooth Optimization for Black-Box Non-Smooth Problems
论文作者
论文摘要
在过去的十年中，已对黑框凸优化的无梯度/零阶方法进行了广泛的研究，主要关注Oracle调用复杂性。在本文中，除了甲骨文的复杂性外，我们还专注于迭代复杂性，并提出了一种通用方法，该方法基于最佳的一阶方法，允许以黑色盒子时尚新的零阶算法获得非平滑凸凸优化问题。我们的方法不仅会导致最佳的甲骨文复杂性，而且还允许获得类似于一阶方法的迭代复杂性，这又允许利用并行计算来加速我们的算法的收敛性。我们还详细介绍了随机优化问题，鞍点问题和分布式优化的扩展。
Gradient-free/zeroth-order methods for black-box convex optimization have been extensively studied in the last decade with the main focus on oracle calls complexity. In this paper, besides the oracle complexity, we focus also on iteration complexity, and propose a generic approach that, based on optimal first-order methods, allows to obtain in a black-box fashion new zeroth-order algorithms for non-smooth convex optimization problems. Our approach not only leads to optimal oracle complexity, but also allows to obtain iteration complexity similar to first-order methods, which, in turn, allows to exploit parallel computations to accelerate the convergence of our algorithms. We also elaborate on extensions for stochastic optimization problems, saddle-point problems, and distributed optimization.
