research-article

Nearly-Linear Time Positive LP Solver with Faster Convergence Rate

Authors:

Zeyuan Allen-Zhu,

Lorenzo OrecchiaAuthors Info & Claims

STOC '15: Proceedings of the forty-seventh annual ACM symposium on Theory of Computing

Pages 229 - 236

https://doi.org/10.1145/2746539.2746573

Published: 14 June 2015 Publication History

Abstract

Positive linear programs (LP), also known as packing and covering linear programs, are an important class of problems that bridges computer science, operation research, and optimization. Efficient algorithms for solving such LPs have received significant attention in the past 20 years [2, 3, 4, 6, 7, 9, 11, 15, 16, 18, 19, 21, 24, 25, 26, 29, 30]. Unfortunately, all known nearly-linear time algorithms for producing (1+ε)-approximate solutions to positive LPs have a running time dependence that is at least proportional to ε^-2. This is also known as an O(1/√T) convergence rate and is particularly poor in many applications. In this paper, we leverage insights from optimization theory to break this longstanding barrier. Our algorithms solve the packing LP in time ~O(N ε^-1) and the covering LP in time ~O(N ε^-1.5). At high level, they can be described as linear couplings of several first-order descent steps. This is the first application of our linear coupling technique (see [1]) to problems that are not amenable to blackbox applications known iterative algorithms in convex optimization. Our work also introduces a sequence of new techniques, including the stochastic and the non-symmetric execution of gradient truncation operations, which may be of independent interest.

References

[1]

Z. Allen-Zhu and L. Orecchia. Linear coupling: An ultimate unification of gradient and mirror descent. ArXiv e-prints, abs/1407.1537, July 2014.

[2]

Z. Allen-Zhu and L. 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 26th ACM-SIAM Symposium on Discrete Algorithms, SODA '15, 2015.

Digital Library

[3]

S. Arora, E. Hazan, and S. Kale. The Multiplicative Weights Update Method: a Meta-Algorithm and Applications. Theory of Computing, 8:121--164, 2012.

[4]

B. Awerbuch and R. Khandekar. Stateless distributed gradient descent for positive linear programs. Proceedings of the fourtieth annual ACM symposium on Theory of computing - STOC 08, page 691, 2008.

Digital Library

[5]

B. Awerbuch, R. Khandekar, and S. Rao. Distributed algorithms for multicommodity flow problems via approximate steepest descent framework. ACM Transactions on Algorithms, 9(1):1--14, Dec. 2012.

Digital Library

[6]

Y. Bartal, J. W. Byers, and D. Raz. Global optimization using local information with applications to flow control. In Proceedings 38th Annual Symposium on Foundations of Computer Science, pages 303--312. IEEE Comput. Soc, 1997.

Digital Library

[7]

Y. Bartal, J. W. Byers, and D. Raz. Fast, Distributed Approximation Algorithms for Positive Linear Programming with Applications to Flow Control. SIAM Journal on Computing, 33(6):1261--1279, Jan. 2004.

Digital Library

[8]

A. Ben-Tal and A. Nemirovski. Lectures on Modern Convex Optimization. Society for Industrial and Applied Mathematics, Jan. 2013.

[9]

D. Bienstock and G. Iyengar. Faster approximation algorithms for packing and covering problems. Technical report, 2004. Preliminary version published in STOC '04.

[10]

J. Byers and G. Nasser. Utility-based decision-making in wireless sensor networks. In Mobile and Ad Hoc Networking and Computing, 2000. MobiHOC. 2000 First Annual Workshop on, pages 143--144. IEEE, 2000.

Digital Library

[11]

F. A. Chudak and V. Eleutério. Improved Approximation Schemes for Linear Programming Relaxations of Combinatorial Optimization Problems. In Proceedings of the 11th International IPCO Conference on Integer Programming and Combinatorial Optimization, pages 81--96, 2005.

Digital Library

[12]

R. Duan and S. Pettie. Linear-Time Approximation for Maximum Weight Matching. Journal of the ACM, 61(1):1--23, Jan. 2014.

Digital Library

[13]

O. Fercoq and P. Richtárik. Accelerated, Parallel and Proximal Coordinate Descent. ArXiv e-prints, abs/1312.5799:25, Dec. 2013.

[14]

L. K. Fleischer. Approximating Fractional Multicommodity Flow Independent of the Number of Commodities. SIAM Journal on Discrete Mathematics, 13(4):505--520, Jan. 2000.

Digital Library

[15]

N. Garg and J. Könemann. Faster and Simpler Algorithms for Multicommodity Flow and Other Fractional Packing Problems. SIAM Journal on Computing, 37(2):630--652, Jan. 2007.

Digital Library

[16]

M. D. Grigoriadis and L. G. Khachiyan. A sublinear-time randomized approximation algorithm for matrix games. Operations Research Letters, 18:53--58, 1995.

Digital Library

[17]

P. Klein and N. Young. On the number of iterations for dantzig-wolfe optimization and packing-covering approximation algorithms. In G. Cornuéjols, R. E. Burkard, and G. J. Woeginger, editors, Integer Programming and Combinatorial Optimization, volume 1610 of Lecture Notes in Computer Science, pages 320--327. Springer Berlin Heidelberg, 1999.

Digital Library

[18]

C. Koufogiannakis and N. E. Young. A Nearly Linear-Time PTAS for Explicit Fractional Packing and Covering Linear Programs. Algorithmica, pages 494--506, Mar. 2013. Previously appeared in FOCS '07.

Digital Library

[19]

M. Luby and N. Nisan. A parallel approximation algorithm for positive linear programming. In Proceedings of the twenty-fifth annual ACM symposium on Theory of computing - STOC '93, pages 448--457, New York, New York, USA, 1993. ACM Press.

Digital Library

[20]

A. Madry. Faster approximation schemes for fractional multicommodity flow problems via dynamic graph algorithms. In Proceedings of the 42nd ACM symposium on Theory of computing - STOC '10, page 121, New York, New York, USA, 2010. ACM Press.

Digital Library

[21]

A. 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, Jan. 2004.

Digital Library

[22]

Y. Nesterov. A method of solving a convex programming problem with convergence rate O(1/k2). In Doklady AN SSSR (translated as Soviet Mathematics Doklady), volume 269, pages 543--547, 1983.

[23]

Y. Nesterov. Introductory Lectures on Convex Programming Volume: A Basic course, volume I. Kluwer Academic Publishers, 2004.

Digital Library

[24]

Y. Nesterov. Smooth minimization of non-smooth functions. Mathematical Programming, 103(1):127--152, Dec. 2005.

Digital Library

[25]

Y. Nesterov. Rounding of convex sets and efficient gradient methods for linear programming problems. Optimisation Methods and Software, 23(1):109--128, 2008.

Digital Library

[26]

S. A. Plotkin, D. B. Shmoys, and E. Tardos. Fast Approximation Algorithms for Fractional Packing and Covering Problems. Mathematics of Operations Research, 20(2):257--301, May 1995.

Digital Library

[27]

S. Shalev-Shwartz and A. Tewari. Stochastic methods for l1-regularized loss minimization. Journal of Machine Learning Research, 12:1865--1892, 2011.

Digital Library

[28]

L. Trevisan. Parallel Approximation Algorithms by Positive Linear Programming. Algorithmica, 21(1):72--88, May 1998.

[29]

N. E. Young. Sequential and parallel algorithms for mixed packing and covering. In 42nd Annual IEEE Symposium on Foundations of Computer Science (FOCS'01), pages 538--546. IEEE Comput. Soc, 2001.

Digital Library

[30]

N. E. Young. Nearly linear-time approximation schemes for mixed packing/covering and facility-location linear programs. ArXiv e-prints, abs/1407.3015, July 2014.

[31]

E. Zurel and N. Nisan. An efficient approximate allocation algorithm for combinatorial auctions. In Proceedings of the 3rd ACM conference on Electronic Commerce, pages 125--136. ACM, 2001.

Digital Library

Cited By

Blanchet JJambulapati AKent CSidford A(2024)Towards optimal running times for optimal transportOperations Research Letters10.1016/j.orl.2023.11.00752:COnline publication date: 16-May-2024
https://dl.acm.org/doi/10.1016/j.orl.2023.11.007
Chekuri CQuanrud KChan T(2019)On approximating (sparse) covering integer programsProceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3310435.3310532(1596-1615)Online publication date: 6-Jan-2019
https://dl.acm.org/doi/10.5555/3310435.3310532
Sun RYe Y(2019)Worst-case complexity of cyclic coordinate descent: $$O(n^2)$$ O ( n 2 ) gap with randomized versionMathematical Programming10.1007/s10107-019-01437-5Online publication date: 11-Oct-2019
https://doi.org/10.1007/s10107-019-01437-5
Show More Cited By

Index Terms

Nearly-Linear Time Positive LP Solver with Faster Convergence Rate

Recommendations

Nearly linear-time packing and covering LP solvers

Packing and covering linear programs (PC-LP s) form an important class of linear programs (LPs) across computer science, operations research, and optimization. Luby and Nisan (in: STOC, ACM Press, New York, 1993) constructed an iterative algorithm for ...
A Variant of the Vavasis-Ye Layered-Step Interior-Point Algorithm for Linear Programming

In this paper we present a variant of Vavasis and Ye's layered-step path-following primal-dual interior-point algorithm for linear programming. Our algorithm is a predictor--corrector-type algorithm which uses from time to time the layered least squares ...
Newton-KKT interior-point methods for indefinite quadratic programming

Two interior-point algorithms are proposed and analyzed, for the (local) solution of (possibly) indefinite quadratic programming problems. They are of the Newton-KKT variety in that (much like in the case of primal-dual algorithms for linear programming)...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC '15: Proceedings of the forty-seventh annual ACM symposium on Theory of Computing

June 2015

916 pages

ISBN:9781450335362

DOI:10.1145/2746539

General Chair:
Rocco Servedio
Columbia University
,
Program Chair:
Ronitt Rubinfeld
MIT and Tel Aviv University

Copyright © 2015 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 14 June 2015

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Conference

STOC '15

Sponsor:

SIGACT

STOC '15: Symposium on Theory of Computing

June 14 - 17, 2015

Oregon, Portland, USA

Acceptance Rates

STOC '15 Paper Acceptance Rate 93 of 347 submissions, 27%;

Overall Acceptance Rate 716 of 2,233 submissions, 32%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

13
Total Citations
View Citations
488
Total Downloads

Downloads (Last 12 months)33
Downloads (Last 6 weeks)15

Reflects downloads up to 13 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Blanchet JJambulapati AKent CSidford A(2024)Towards optimal running times for optimal transportOperations Research Letters10.1016/j.orl.2023.11.00752:COnline publication date: 16-May-2024
https://dl.acm.org/doi/10.1016/j.orl.2023.11.007
Chekuri CQuanrud KChan T(2019)On approximating (sparse) covering integer programsProceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3310435.3310532(1596-1615)Online publication date: 6-Jan-2019
https://dl.acm.org/doi/10.5555/3310435.3310532
Sun RYe Y(2019)Worst-case complexity of cyclic coordinate descent: $$O(n^2)$$ O ( n 2 ) gap with randomized versionMathematical Programming10.1007/s10107-019-01437-5Online publication date: 11-Oct-2019
https://doi.org/10.1007/s10107-019-01437-5
Elbassioni KMakino KNajy W(2019)A Multiplicative Weight Updates Algorithm for Packing and Covering Semi-infinite Linear ProgramsAlgorithmica10.1007/s00453-018-00539-481:6(2377-2429)Online publication date: 1-Jun-2019
https://dl.acm.org/doi/10.1007/s00453-018-00539-4
Chekuri CQuanrud KCzumaj A(2018)Randomized MWU for positive LPsProceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3174304.3175292(358-377)Online publication date: 7-Jan-2018
https://dl.acm.org/doi/10.5555/3174304.3175292
Allen-Zhu Z(2017)KatyushaThe Journal of Machine Learning Research10.5555/3122009.324207818:1(8194-8244)Online publication date: 1-Jan-2017
https://dl.acm.org/doi/10.5555/3122009.3242078
Chekuri CQuanrud KKlein P(2017)Near-linear time approximation schemes for some implicit fractional packing problemsProceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3039686.3039737(801-820)Online publication date: 16-Jan-2017
https://dl.acm.org/doi/10.5555/3039686.3039737
Elbassioni KDumitrescu A(2017)Computational Geometry Column 66ACM SIGACT News10.1145/3173127.317313848:4(57-74)Online publication date: 13-Dec-2017
https://dl.acm.org/doi/10.1145/3173127.3173138
Allen-Zhu ZHatami HMcKenzie PKing V(2017)Katyusha: the first direct acceleration of stochastic gradient methodsProceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing10.1145/3055399.3055448(1200-1205)Online publication date: 19-Jun-2017
https://dl.acm.org/doi/10.1145/3055399.3055448
Allen-Zhu ZLi YOliveira RWigderson A(2017)Much Faster Algorithms for Matrix Scaling2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS.2017.87(890-901)Online publication date: Oct-2017
https://doi.org/10.1109/FOCS.2017.87
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents