There is a recent interest on first-order methods for linear programming (LP). In this paper,we propose a stochastic algorithm using variance reduction and restarts for solving sharp primal-dual problems such as LP. We show that the proposed stochastic method exhibits a linear convergence rate for solving sharp instances with a high probability. In addition, we propose an efficient coordinate-based stochastic oracle for unconstrained bilinear problems, which has $\mathcal O(1)$ per iteration cost and improves the complexity of the existing deterministic and stochastic algorithms. Finally, we show that the obtained linear convergence rate is nearly optimal (upto $\log$ terms) for a wide class of stochastic primal dual methods.


翻译:最近有人对线性编程的第一阶方法(LP)感兴趣。在本文中,我们提出使用差异减少和重新启动的随机算法来解决尖锐的原始和双重问题(如LP)。我们表明,拟议的随机方法显示了一种线性趋同率,以极有可能的方式解决尖锐的事例。此外,我们建议对未受约束的双线性问题采用一种高效的基于协调的随机拼凑法,即每迭代费用为$\mathcal O(1)美元,提高现有确定性和随机性算法的复杂性。最后,我们表明,获得的线性趋同率对于一系列广泛的随机性初线性双轨方法来说几乎是最佳的(最高为$\log$ )。

0
下载
关闭预览

相关内容

专知会员服务
28+阅读 · 2020年11月4日
《DeepGCNs: Making GCNs Go as Deep as CNNs》
专知会员服务
30+阅读 · 2019年10月17日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
已删除
将门创投
12+阅读 · 2017年10月13日
Arxiv
5+阅读 · 2017年12月14日
VIP会员
相关VIP内容
专知会员服务
28+阅读 · 2020年11月4日
《DeepGCNs: Making GCNs Go as Deep as CNNs》
专知会员服务
30+阅读 · 2019年10月17日
相关资讯
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
已删除
将门创投
12+阅读 · 2017年10月13日
Top
微信扫码咨询专知VIP会员