论文标题
快速随机的复合材料最小化和并行的加速弗兰克 - 沃尔夫算法
Fast Stochastic Composite Minimization and an Accelerated Frank-Wolfe Algorithm under Parallelization
论文作者
论文摘要
我们考虑最小化两个凸函数的总和的问题。其中一个功能具有LIPSCHITZ连续梯度，可以通过随机甲壳访问，而另一个则可以“简单”。我们提供Bregman型算法，在功能值中加速收敛到包含最小值的球。该球的半径取决于问题依赖性常数，包括随机甲骨文的方差。我们进一步表明，这种算法的设置自然会导致Frank-Wolfe在并行化下达到加速度的变体。更确切地说，当最大程度地减少有界域上的平稳凸功能时，我们表明，只有仅通过访问原始功能的$ tilde {o}（1/ \sqrtε）$迭代才能在$ \ tilde {o}中实现$ε$原始缝隙（预期），仅通过访问原始函数的梯度和$ o（1/ ^ $ o o（1/ c）的范围。我们说明了合成数值实验的这种快速收敛性。
We consider the problem of minimizing the sum of two convex functions. One of those functions has Lipschitz-continuous gradients, and can be accessed via stochastic oracles, whereas the other is "simple". We provide a Bregman-type algorithm with accelerated convergence in function values to a ball containing the minimum. The radius of this ball depends on problem-dependent constants, including the variance of the stochastic oracle. We further show that this algorithmic setup naturally leads to a variant of Frank-Wolfe achieving acceleration under parallelization. More precisely, when minimizing a smooth convex function on a bounded domain, we show that one can achieve an $ε$ primal-dual gap (in expectation) in $\tilde{O}(1/ \sqrtε)$ iterations, by only accessing gradients of the original function and a linear maximization oracle with $O(1/\sqrtε)$ computing units in parallel. We illustrate this fast convergence on synthetic numerical experiments.
