Randomized sketch descent methods for non-separable linearly constrained optimization
Randomized sketch descent methods for non-separable linearly constrained optimization
复制标题
用于不可分离线性约束优化的随机草图下降法
DOI：
10.1093/imanum/draa018
复制
发表时间：
2020
影响因子：
2.1
通讯作者：
Takáč, Martin
中科院分区：
文献类型：
--
作者：
Necoara, Ion;Takáč, Martin
本文研究了具有多个线性耦合约束的大规模光滑优化问题。由于约束的不可分离性，不能保证任意的随机草图。因此，我们首先调查的必要条件和充分条件的草图采样有明确的算法。基于这些采样条件，我们开发了新的草图下降方法来解决一般光滑线性约束问题，特别是随机草图下降（RSD）和加速随机草图下降（A-RSD）方法。据我们所知，这是第一次收敛性分析RSD算法的多个不可分的线性约束优化问题。对于一般情况下，当目标函数是光滑的和非凸的，我们证明了非加速变量的次线性率在期望的适当的最优性措施。在光滑凸的情况下，我们推导出这两种算法，非加速和A-RSD，次线性收敛速度的目标函数的预期值。此外，如果目标函数满足强凸型条件，这两种算法的线性收敛的期望。在特殊情况下，复杂性的界限是已知的一些特定的草图算法，如坐标下降法的优化问题与一个单一的线性耦合约束，我们的理论恢复最知名的界限。最后，我们提出了几个数值例子来说明我们的新算法的性能。
In this paper we consider large-scale smooth optimization problems with multiple linear coupled constraints. Due to the non-separability of the constraints, arbitrary random sketching would not be guaranteed to work. Thus, we first investigate necessary and sufficient conditions for the sketch sampling to have well-defined algorithms. Based on these sampling conditions we develop new sketch descent methods for solving general smooth linearly constrained problems, in particular, random sketch descent (RSD) and accelerated random sketch descent (A-RSD) methods. To our knowledge, this is the first convergence analysis of RSD algorithms for optimization problems with multiple non-separable linear constraints. For the general case, when the objective function is smooth and non-convex, we prove for the non-accelerated variant sublinear rate in expectation for an appropriate optimality measure. In the smooth convex case, we derive for both algorithms, non-accelerated and A-RSD, sublinear convergence rates in the expected values of the objective function. Additionally, if the objective function satisfies a strong convexity type condition, both algorithms converge linearly in expectation. In special cases, where complexity bounds are known for some particular sketching algorithms, such as coordinate descent methods for optimization problems with a single linear coupled constraint, our theory recovers the best known bounds. Finally, we present several numerical examples to illustrate the performances of our new algorithms.
登录
查看更多内容
通过随机子空间下降进行预测市场的收敛分析
DOI：
--
发表时间：
2015
期刊：
Neural Information Processing Systems
影响因子：
--
作者：
Rafael M. Frongillo;Mark D. Reid
通讯作者：
Mark D. Reid
DOI：
10.1137/130949993
发表时间：
2013-12
期刊：
SIAM J. Optim.
影响因子：
--
作者：
Olivier Fercoq;Peter Richtárik
通讯作者：
Olivier Fercoq;Peter Richtárik
影响因子：
6.8
作者：
H. Ishii;R. Tempo;E. Bai
通讯作者：
H. Ishii;R. Tempo;E. Bai
DOI：
--
发表时间：
2017-01
期刊：
--
影响因子：
--
作者：
Stephen Tu;S. Venkataraman;Ashia C. Wilson;Alex Gittens;Michael I. Jordan;B. Recht
通讯作者：
Stephen Tu;S. Venkataraman;Ashia C. Wilson;Alex Gittens;Michael I. Jordan;B. Recht