论文标题
Oracle复杂性分离凸优化
Oracle Complexity Separation in Convex Optimization
论文作者
论文摘要
许多凸优化问题已经将目标函数构成了作为具有不同类型的甲壳（完整梯度，坐标衍生物，随机梯度）的功能和不同评估复杂性的功能的总和。在强凸情况下，这些功能也具有不同的条件数，最终定义了一阶方法的迭代复杂性以及实现给定准确性所需的甲骨文调用数量。在本文中，以更昂贵的Oracle呼吁更昂贵的甲骨文的愿望，我们考虑最小化两个功能的总和，并提出一个通用算法框架，以分离总和中每个组件的甲骨文复杂性。作为一个具体示例，对于$μ$ - strongly凸出问题$ \ min_ {x \ in \ mathbb {r}^n} H（x） $ o（\ sqrt {l_h/μ}）$ h $和$ o（\ sqrt {l_g/μ}）$一阶甲骨文呼叫$ g $的一阶甲骨文调用。我们的一般框架还涵盖了强烈凸目标的设置，坐标衍生物Oracle给出$ G $时的设置，以及$ G $具有有限和的结构时的设置，可以通过随机梯度Oracle获得。在后两种情况下，我们分别获得了具有Oracle复杂性分离的加速随机坐标下降和加速差异方法。
Many convex optimization problems have structured objective function written as a sum of functions with different types of oracles (full gradient, coordinate derivative, stochastic gradient) and different evaluation complexity of these oracles. In the strongly convex case these functions also have different condition numbers, which eventually define the iteration complexity of first-order methods and the number of oracle calls required to achieve given accuracy. Motivated by the desire to call more expensive oracle less number of times, in this paper we consider minimization of a sum of two functions and propose a generic algorithmic framework to separate oracle complexities for each component in the sum. As a specific example, for the $μ$-strongly convex problem $\min_{x\in \mathbb{R}^n} h(x) + g(x)$ with $L_h$-smooth function $h$ and $L_g$-smooth function $g$, a special case of our algorithm requires, up to a logarithmic factor, $O(\sqrt{L_h/μ})$ first-order oracle calls for $h$ and $O(\sqrt{L_g/μ})$ first-order oracle calls for $g$. Our general framework covers also the setting of strongly convex objectives, the setting when $g$ is given by coordinate derivative oracle, and the setting when $g$ has a finite-sum structure and is available through stochastic gradient oracle. In the latter two cases we obtain respectively accelerated random coordinate descent and accelerated variance reduction methods with oracle complexity separation.
