Black-Box Acceleration of Monotone Convex Program Solvers

References

• Agrawal A, Klein P, Ravi R (1995) When trees collide: An approximation algorithm for the generalized Steiner problem on networks. SIAM J. Comput. 24(3):440–456.Crossref, Google Scholar
• Agrawal S, Devanur NR (2015) Fast algorithms for online stochastic convex programming. SODA’15 Proc. 26th Annu. ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 1405–1424.Google Scholar
• Agrawal S, Wang Z, Ye Y (2014) A dynamic near-optimal algorithm for online linear programming. Oper. Res. 62(4):876–890.Link, Google Scholar
• Allen-Zhu Z, Orecchia L (2015) Using optimization to break the epsilon barrier: A faster and simpler width-independent algorithm for solving positive linear programs in parallel. SODA’15 Proc. 26th Annu. ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 1439–1456.Google Scholar
• Andersen ED, Andersen KD (2000) The Mosek interior point optimizer for linear programming: An implementation of the homogeneous algorithm. Frenk H, Roos K, Terlaky T, Zhang S, eds. High Performance Optimization, Applied Optimization, vol. 33 (Springer US, Boston), 197–232.Crossref, Google Scholar
• Balakrishnan A, Magnanti TL, Wong RT (1989) A dual-ascent procedure for large-scale uncapacitated network design. Oper. Res. 37(5):716–740.Link, Google Scholar
• Bar-Yehuda R, Even S (1981) A linear-time approximation algorithm for the weighted vertex cover problem. J. Algorithms 2(2):198–203.Crossref, Google Scholar
• Barnhart C, Cohn A, Johnson E, Klabjan D, Nemhauser G, Vance P (2002) Airline crew scheduling. Hall RW, ed. Handbook in Transportation Science, International Series in Operations Research & Management Science, vol. 56 (Springer, Boston), 517–560.Google Scholar
• Barnhart C, Johnson EL, Nemhauser GL, Savelsberg MWP, Vance P (2000) Branch-and-price: Column generation for solving huge integer programs. Oper. Res. 48(3):318–326.Link, Google Scholar
• Bartal Y, Byers JW, Raz D (2004) Fast distributed approximation algorithms for positive linear programming with applications to flow control. SIAM J. Comput. 33(6):1261–1279.Crossref, Google Scholar
• Bertsimas D, Vohra R (1998) Rounding algorithms for covering problems. Math. Program. 80(1):63–89.Crossref, Google Scholar
• Borsos Z, Mutny M, Krause A (2020) Coresets via bilevel optimization for continual learning and streaming. Adv. Neural Inform. Processing Systems 33:34.Google Scholar
• Borsos Z, Mutny M, Tagliasacchi M, Krause A (2021) Data summarization via bilevel optimization. Preprint, submitted September 26, https://arxiv.org/abs/2109.12534.Google Scholar
• Boyd S, Vandenberghe L (2004) Convex Optimization (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• Boyd S, Parikh N, Chu E, Peleato B, Eckstein J (2011) Distributed optimization and statistical learning via the alternating direction method of multipliers. Foundations Trends Machine Learning 3(1):1–122.Crossref, Google Scholar
• Buchbinder N, Naor J (2009) The design of competitive online algorithms via a primal-dual approach. Foundations Trends Theor. Comput. Sci. 3(2-3):93–263.Crossref, Google Scholar
• Byers J, Nasser G (2000) Utility-based decision-making in wireless sensor networks. First Annu. Workshop Mobile Ad Hoc Networking Comput. Mobihoc (IEEE, Piscataway, NJ), 143–144.Crossref, Google Scholar
• Cevher V, Becker S, Schmidt M (2014) Convex optimization for big data: Scalable, randomized, and parallel algorithms for big data analytics. IEEE Signal Processing Magazine 31(5):32–43.Crossref, Google Scholar
• Chi Y, Lu YM, Chen Y (2019) Nonconvex optimization meets low-rank matrix factorization: An overview. IEEE Trans. Signal Processing 67(20):5239–5269.Crossref, Google Scholar
• Chowdhury A, London P, Avron H, Drineas P (2020) Faster randomized infeasible interior point methods for tall/wide linear programs. Adv. Neural Inform. Processing Systems 33:8704–8715.Google Scholar
• Desaulniers G, Desrosiers J, Solomon M (2005) Column Generation (Springer, New York).Crossref, Google Scholar
• Devanur NR, Hayes TP (2009) The adwords problem: Online keyword matching with budgeted bidders under random permutations. EC’09 Proc. 10th ACM Conf. Electronic Commerce (Association for Computing Machinery, New York), 71–78.Google Scholar
• Diamond S, Boyd S (2016) CVXPY: A Python-embedded modeling language for convex optimization. J. Machine Learning Res. 17(83):1–5.Google Scholar
• Domahidi A, Chu E, Boyd S (2013) ECOS: An SOCP solver for embedded systems. 2013 Eur. Control Conf. ECC (IEEE, Piscataway, NJ), 3071–3076.Google Scholar
• Donoho DL (2006) Compressed sensing. IEEE Trans. Inform. Theory 52:1289–1306.Crossref, Google Scholar
• Donoho DL, Tanner J (2005) Sparse nonnegative solution of underdetermined linear equations by linear programming. Proc. Natl. Acad. Sci. USA 102(27):9446–9451.Crossref, Google Scholar
• Erlenkotter D (1978) A dual-based procedure for uncapacitated facility location. Oper. Res. 26(6):992–1009.Link, Google Scholar
• Esser E, Zhang X, Chan T (2010) A general framework for a class of first order primal-dual algorithms for convex optimization in imaging science. SIAM J. Imaging Sci. 3(4):1015–1046.Crossref, Google Scholar
• Gabay D, Mercier B (1976) A dual algorithm for the solution of nonlinear variational problems via finite element approximations. Comput. Math. Appl. 2(1):17–40.Crossref, Google Scholar
• Gilmore P, Gomory R (1963) A linear programming approach to the cutting-stock problem. Oper. Res. 11(6):863–888.Link, Google Scholar
• Goemans MX, Williamson DP (1995) A general approximation technique for constrained forest problems. SIAM J. Comput. 24(2):296–317.Crossref, Google Scholar
• Gopalakrishnan B, Johnson E (2005) Airline crew scheduling: State-of-the-art. Ann. Oper. Res. 140:305–337.Crossref, Google Scholar
• Gupta A, Molinaro M (2016) How the experts algorithm can help solve LPs online. Math. Oper. Res. 41(4):1404–1431.Link, Google Scholar
• Ho-Nguyen N, Kilinc-Karzan F (2018) Online first-order framework for robust convex optimization. Oper. Res. 66(6):1670–1692.Link, Google Scholar
• Jalali A (2020) Persistent reductions in regularized loss minimization for variable selection. Preprint, submitted November 30, https://arxiv.org/abs/2011.14549.Google Scholar
• Johansson M, Sternad M (2005) Resource allocation under uncertainty using the maximum entropy principle. IEEE Trans. Inform. Theory 51(12):4103–4117.Crossref, Google Scholar
• Kesselheim T, Tönnis A, Radke K, Vöcking B (2014) Primal beats dual on online packing LPs in the random-order model. STOC’14 Proc. 46th Annu. ACM Sympos. Theory Comput. (Association for Computing Machinery, New York), 303–312.Google Scholar
• Kumar S, Ying J, de Miranda Cardoso JV, Palomar D (2019) Structured graph learning via Laplacian spectral constraints. Adv. Neural Inform. Processing Systems 32. https://papers.nips.cc/paper/2019/hash/90cc440b1b8caa520c562ac4e4bbcb51-Abstract.html.Google Scholar
• Kyng R, Wang D, Zhang P (2020) Packing LPs are hard to solve accurately, assuming linear equations are hard. Proc. 14th Annu. ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 279–296.Google Scholar
• Leskovec J, Krevl A (2014) SNAP Datasets: Stanford large network data set collection. Accessed January 20, 2020, http://snap.stanford.edu/data.Google Scholar
• London P, Chen N, Vardi S, Wierman A (2017) Distributed optimization via local computation algorithms. ACM SIGMETRICS Performance Evaluation Rev. 45(2):30–32.Crossref, Google Scholar
• London P, Vardi S, Wierman A (2019) Logarithmic communication for distributed optimization in multi-agent systems. Proc. ACM Measurement Anal. Comput. Systems 3(3):1–29.Google Scholar
• London P, Vardi S, Wierman A, Yi H (2018) A parallelizable acceleration framework for packing linear programs. McIlraith SA, Weinberger KQ, eds. AAAI’18/IAAI’18/EAAI’18 Proc. 32nd AAAI Conf. Artificial Intelligence 30th Innovative Appl. Artificial Intelligence Conf. Eighth AAAI Sympos. Ed. Adv. Artificial Intelligence (AAAI Press, Palo Alto, CA), 3706–3713.Crossref, Google Scholar
• Luby M, Nisan N (1993) A parallel approximation algorithm for positive linear programming. STOC’93 Proc. 25th Annu. ACM Sympos. Theory Comput. (Association for Computing Machinery, New York), 448–457.Google Scholar
• Mansour Y, Rubinstein A, Vardi S, Xie N (2012) Converting online algorithms to local computation algorithms. Czumaj A, Mehlhorn K, Pitts A, Wattenhofer R, eds. ICALP 2012 Automata Languages Program., Lecture Notes in Computer Science, vol. 7391 (Springer, Berlin), 653–664.Google Scholar
• Martino AD, Martino DD (2018) An introduction to the maximum entropy approach and its application to inference problems in biology. Heliyon. 4(4): e00596.Crossref, Google Scholar
• Mohan K, London P, Fazel M, Witten D, Lee SI (2014) Node-based learning of multiple Gaussian graphical models. J. Machine Learning Res. 15:445–488.Google Scholar
• Molinaro M, Ravi R (2013) The geometry of online packing linear programs. Math. Oper. Res. 39(1):46–59.Link, Google Scholar
• Nair V, Bartunov S, Gimeno F, von Glehn I, Lichocki P, Lobov I, O’Donoghue B, et al. (2020) Solving mixed integer programs using neural networks. Preprint, submitted December 23, https://arxiv.org/abs/2012.13349.Google Scholar
• Nedić A, Olshevsky A, Rabbat MG (2018) Network topology and communication-computation tradeoffs in decentralized optimization. Proc. IEEE 106(5):953–976.Crossref, Google Scholar
• Nemhauser GL (2012) Column generation for linear and integer programming. Documenta Math. Extra Volume ISMP:65–73.Google Scholar
• Nesterov Y (2005) Smooth minimization of non-smooth functions. Math. Program. 103(1):127–152.Crossref, Google Scholar
• O’Donoghue B, Chu E, Parikh N, Boyd S (2016) Conic optimization via operator splitting and homogeneous self-dual embedding. J. Optim. Theory Appl. 169:1042–1068.Crossref, Google Scholar
• Orlik P, Terao H (1992) Arrangements of Hyperplanes, Grundlehren der Mathematischen Wissenschaften, vol. 300 (Springer-Verlag, Berlin).Google Scholar
• Pesnea P, Sadykov R, Vanderbeck F (2012) Feasibility pump heuristics for column generation approaches. Klasing R, ed. Experimental Algorithms SEA 2012, Lecture Notes in Computer Science, vol. 7276 (Springer, Berlin), 332–343.Crossref, Google Scholar
• Plotkin SA, Shmoys DB, Tardos E (1995) Fast approximation algorithms for fractional packing and covering problems. Math. Oper. Res. 20(2):257–301.Link, Google Scholar
• Ravikumar P, Agarwal A, Wainwright MJ (2010) Message passing for graph-structured linear programs: Proximal methods and rounding schemes. J. Machine Learning Res. 11:1043–1080.Google Scholar
• Recht B, Fazel M, Parrilo PA (2010) Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization. SIAM Rev. 52(3):471–501.Crossref, Google Scholar
• Richert D, Cortés J (2015) Robust distributed linear programming. IEEE Trans. Automatic Control. 60(10):2567–2582.Crossref, Google Scholar
• Riquelme C, Johari R, Zhang B (2017) Online active linear regression via thresholding. AAAI’17 Proc. 31st AAAI Conf. Artificial Intelligence (AAAI Press, Palo Alto, CA), 2506–2512.Google Scholar
• Sadykov R, Vanderbeck F (2013) Column generation for extended formulations. EURO J. Comput. Optim. 1(1–2):81–115.Crossref, Google Scholar
• Sanghavi S, Malioutov D, Willsky AS (2008) Linear programming analysis of loopy belief propagation for weighted matching. Platt JC, Koller D, Singer Y, Rowels ST, eds. NIPS’07 Proc. 20th Internat. Conf. Neural Inform. Processing Systems (Curran Associates, Red Hook, NY), 1273–1280.Google Scholar
• Shi Y, Zhang J, O’Donoghue B, Letaief KB (2015) Large-scale convex optimization for dense wireless cooperative networks. IEEE Trans. Signal Processing 63(18):4729–4743.Crossref, Google Scholar
• Shim Jh, Kong K, Kang SJ (2021) Core-set sampling for efficient neural architecture search. Proc. of ICML.Google Scholar
• Sridhar S, Wright SJ, Ré C, Liu J, Bittorf V, Zhang C (2013) An approximate, efficient LP solver for LP rounding. Burges CJC, Bottou L, Welling M, Ghahramani Z, Weinberger KQ, eds. NIPS’13 Proc. 26th Internat. Conf. Neural Inform. Processing Systems, vol. 2 (Curran Associates, Red Hook, NY), 2895–2903.Google Scholar
• Sturm JF (1999) Using Sedumi 1.02, a Matlab toolbox for optimization over symmetric cones. Optim. Methods Software 1(1–4):625–653.Crossref, Google Scholar
• Sun L, Fan Z, Fu X, Huang Y, Ding X, Paisley J (2019) A deep information sharing network for multi-contrast compressed sensing MRI reconstruction. IEEE Trans. Image Processing 28(12):6141–6153.Crossref, Google Scholar
• Taskar B, Chatalbashev V, Koller D (2004) Learning associative Markov networks. ICML’04 Proc. 21st Internat. Conf. Machine Learning (Association for Computing Machinery, New York), 102–112.Google Scholar
• Toh KC, Todd MJ, Tutuncu RH (1999) SDPT3—a MATLAB software package for semidefinite programming, version 1.3. Optim. Methods Software 11(1–4):625–581.Crossref, Google Scholar
• Trevisan L (1998) Parallel approximation algorithms by positive linear programming. Algorithmica 21(1):72–88.Crossref, Google Scholar
• Tukan M, Maalouf A, Feldman D (2020) Coresets for near-convex functions. Adv. Neural Inform. Processing Systems 34:997–1009.Google Scholar
• van der Vaart A, Wellner J (1996) Weak Convergence and Empirical Processes with Applications to Statistics, Springer Series in Statistics (Springer-Verlag, New York).Crossref, Google Scholar
• Vera A, Banerjee S (2021) The Bayesian prophet: A low-regret framework for online decision making. Management Sci. 67(3):1368–1391.Link, Google Scholar
• Woodruff DP (2014) Sketching as a tool for numerical linear algebra. Foundations Trends Theor. Comput. Sci. 10(1–2):1–157.Crossref, Google Scholar
• Yarmish G, Slyke R (2009) A distributed, scalable simplex method. J. Supercomputing 49(3):373–381.Crossref, Google Scholar
• Young NE (2001) Sequential and parallel algorithms for mixed packing and covering. Proc. 42nd IEEE Sympos. Foundations Comput. Sci. (IEEE, Piscataway, NJ), 538–546.Google Scholar
• Zurel E, Nisan N (2001) An efficient approximate allocation algorithm for combinatorial auctions. EC’01 Proc. 3rd ACM Conf. Electronic Commerce (ACM, New York), 125–136.Google Scholar