LIPIcs.ICALP.2016.50.pdf
- Filesize: 0.52 MB
- 13 pages
Document
Unified Acceleration Method for Packing and Covering Problems via Diameter Reduction
Authors
-
Part of:
Volume:
43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Colloquium on Automata, Languages, and Programming (ICALP) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2016-08-23
Cite AsGet BibTex
Di Wang, Satish Rao, and Michael W. Mahoney. Unified Acceleration Method for Packing and Covering Problems via Diameter Reduction. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 50:1-50:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.ICALP.2016.50
https://doi.org/10.4230/LIPIcs.ICALP.2016.50
Abstract
In a series of recent breakthroughs, Allen-Zhu and Orecchia [Allen-Zhu/Orecchia, STOC 2015; Allen-Zhu/Orecchia, SODA 2015] leveraged insights from the linear coupling method [Allen-Zhu/Oreccia, arXiv 2014], which is a first-order optimization scheme, to provide improved algorithms for packing and covering linear programs. The result in [Allen-Zhu/Orecchia, STOC 2015] is particularly interesting, as the algorithm for packing LP achieves both width-independence and Nesterov-like acceleration, which was not known to be possible before. Somewhat surprisingly, however, while the dependence of the convergence rate on the error parameter epsilon for packing problems was improved to O(1/epsilon), which corresponds to what accelerated gradient methods are designed to achieve, the dependence for covering problems was only improved to O(1/epsilon^{1.5}), and even that required a different more complicated algorithm, rather than from Nesterov-like acceleration. Given the primal-dual connection between packing and covering problems and since previous algorithms for these very related problems have led to the same epsilon dependence, this discrepancy is surprising, and it leaves open the question of the exact role that the linear coupling is playing in coordinating the complementary gradient and mirror descent step of the algorithm. In this paper, we clarify these issues, illustrating that the linear coupling method can lead to improved O(1/epsilon) dependence for both packing and covering problems in a unified manner, i.e., with the same algorithm and almost identical analysis. Our main technical result is a novel dimension lifting method that reduces the coordinate-wise diameters of the feasible region for covering LPs, which is the key structural property to enable the same Nesterov-like acceleration as in the case of packing LPs. The technique is of independent interest and that may be useful in applying the accelerated linear coupling method to other combinatorial problems.
Keywords
- Convex optimization
- Accelerated gradient descent
- Linear program
- Approximation algorithm
- Packing and covering
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Zeyuan Allen-Zhu and Lorenzo Orecchia. Nearly-linear time positive LP solver with faster convergence rate. In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC'15, pages 229-236, 2015. Newer version available at URL: http://arxiv.org/abs/1411.1124.
-
Zeyuan Allen-Zhu and Lorenzo Orecchia. Using optimization to break the epsilon barrier: A faster and simpler width-independent algorithm for solving positive linear programs in parallel. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA'15, pages 1439-1456, 2015.
- Sanjeev Arora, Elad Hazan, and Satyen Kale. The multiplicative weights update method: a meta-algorithm and applications. Theory of Computing, 8(6):121-164, 2012. URL: http://dx.doi.org/10.4086/toc.2012.v008a006.
- Baruch Awerbuch and Rohit Khandekar. Stateless distributed gradient descent for positive linear programs. In Proceedings of the 40th Annual ACM Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008, pages 691-700, 2008. URL: http://dx.doi.org/10.1145/1374376.1374476.
- Lisa Fleischer. A fast approximation scheme for fractional covering problems with variable upper bounds. In Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2004, New Orleans, Louisiana, USA, January 11-14, 2004, pages 1001-1010, 2004. URL: http://dl.acm.org/citation.cfm?id=982792.982942.
- Christos Koufogiannakis and Neal E. Young. A nearly linear-time PTAS for explicit fractional packing and covering linear programs. Algorithmica, 70(4):648-674, 2014. URL: http://dx.doi.org/10.1007/s00453-013-9771-6.
- Michael Luby and Noam Nisan. A parallel approximation algorithm for positive linear programming. In Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, May 16-18, 1993, San Diego, CA, USA, pages 448-457, 1993. URL: http://dx.doi.org/10.1145/167088.167211.
- Arkadi Nemirovski. Prox-method with rate of convergence O(1/t) for variational inequalities with Lipschitz continuous monotone operators and smooth convex-concave saddle point problems. SIAM Journal on Optimization, 15(1):229-251, 2004. URL: http://dx.doi.org/10.1137/S1052623403425629.
- Yurii Nesterov. Smooth minimization of non-smooth functions. Math. Program., 103(1):127-152, 2005. URL: http://dx.doi.org/10.1007/s10107-004-0552-5.
- Yurii Nesterov. Efficiency of coordinate descent methods on huge-scale optimization problems. SIAM Journal on Optimization, 22(2):341-362, 2012. URL: http://dx.doi.org/10.1137/100802001.
- Serge A. Plotkin, David B. Shmoys, and Éva Tardos. Fast approximation algorithms for fractional packing and covering problems. In 32nd Annual Symposium on Foundations of Computer Science, San Juan, Puerto Rico, 1-4 October 1991, pages 495-504, 1991. URL: http://dx.doi.org/10.1109/SFCS.1991.185411.
- James Renegar. Efficient first-order methods for linear programming and semidefinite programming. CoRR, abs/1409.5832, 2014. URL: http://arxiv.org/abs/1409.5832.
- Neal E. Young. Sequential and parallel algorithms for mixed packing and covering. In 42nd Annual Symposium on Foundations of Computer Science, FOCS 2001, 14-17 October 2001, Las Vegas, Nevada, USA, pages 538-546, 2001. URL: http://dx.doi.org/10.1109/SFCS.2001.959930.
- Neal E. Young. Nearly linear-time approximation schemes for mixed packing/covering and facility-location linear programs. CoRR, abs/1407.3015, 2014. URL: http://arxiv.org/abs/1407.3015.
- Zeyuan Allen Zhu and Lorenzo Orecchia. Linear coupling: An ultimate unification of gradient and mirror descent. CoRR, abs/1407.1537, 2014. URL: http://arxiv.org/abs/1407.1537.