A Single-Phase, Proximal Path-Following Framework

References

• Andersen MS, Dahl J, Liu Z, Vandenberghe L (2011) Interior-point methods for large-scale cone programming. Sra S, Nowozin S, Wright SJ, eds. Optimization for Machine Learning (MIT Press, Cambridge, MA), 55–83.Google Scholar
• Baldassarre L, Bhan N, Cevher V, Kyrillidis A, Satpathi S (2016) Group-sparse model selection: Hardness and relaxations. IEEE Trans. Inform. Theory 62(11):6508–6534.Crossref, Google Scholar
• Bauschke HH, Combettes P (2011) Convex Analysis and Monotone Operators Theory in Hilbert Spaces (Springer, Cham, Switzerland).Crossref, Google Scholar
• Beck A, Teboulle M (2009) A fast iterative shrinkage-thresholding agorithm for linear inverse problems. SIAM J. Imaging Sci. 2(1):183–202.Crossref, Google Scholar
• Becker S, Candès EJ, Grant M (2011) Templates for convex cone problems with applications to sparse signal recovery. Math. Programming Comput. 3(3):165–218.Crossref, Google Scholar
• Ben-Tal A, Nemirovski A (2001) Lectures on Modern Convex Optimization: Analysis Algorithms, and Engineering Applications, MPS/SIAM Series on Optimization, Vol. 3 (SIAM, Philadelphia).Crossref, 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 Learn. 3(1):1–122.Crossref, Google Scholar
• Cai J-F, Candès E, Shen Z (2010) A singular value thresholding algorithm for matrix completion. SIAM J. Optim. 20(4):1956–1982.Crossref, Google Scholar
• Candès E, Eldar Y, Strohmer T, Voroninski V (2013) Phase retrieval via matrix completion. SIAM J. Imaging Sci. 6(1):199–225.Crossref, Google Scholar
• Combettes P, Pesquet J-C (2011) Signal recovery by proximal forward-backward splitting. Bauschke HH, Burachik RS, Combettes PL, Elser V, Luke DR, Wolkowicz H, eds. Fixed-Point Algorithms for Inverse Problems in Science and Engineering (Springer, New York), 185–212.Crossref, Google Scholar
• Fercoq O, Qu Z (2016) Restarting accelerated gradient methods with a rough strong convexity estimate. Working paper, Université Paris-Saclay, Paris. https://arxiv.org/abs/1609.07358.Google Scholar
• Freund RM (1991) Theoretical efficiency of a shifted-barrier-function algorithm for linear programming. Linear Algebra Appl. 152(July):19–41.Crossref, Google Scholar
• Friedlander MP, Goh G (2017) Efficient evaluation of scaled proximal operators. Electronic Trans. Numerical Anal. 46:1–22.Google Scholar
• Frieze A, Jerrum M (1997) Improved approximation algorithms for max-k-cut and max bisection. Algorithmica 18(1):67–81.Crossref, Google Scholar
• Frostig R, Ge R, Kakade S, Sidford A (2015) Competing with the empirical risk minimizer in a single pass. Conf. Learn. Theory, 728–763.Google Scholar
• Gondzio J (2012) Interior point methods 25 years later. Eur. J. Oper. Res. 218(3):587–601.Crossref, Google Scholar
• Gramfort A, Kowalski M (2009) Improving M/EEG source localization with an inter-condition sparse prior. IEEE Internat. Sympos. Biomedical Imaging (IEEE, Piscataway, NJ), 141–144.Google Scholar
• Grant M, Boyd S, Ye Y (2006) Disciplined convex programming. Liberti L, Maculan N, eds. Global Optimization: From Theory to Implementation, Nonconvex Optimization and Its Applications (Springer, New York), 155–210.Crossref, Google Scholar
• Jaganathan K, Oymak S, Hassibi B (2017) Sparse phase retrieval: Uniqueness guarantees and recovery algorithms. IEEE Trans. Signal Processing 65(9):2402–2410.Crossref, Google Scholar
• Jalali A, Srebro N (2012) Clustering using max-norm constrained optimization. Proc. Internat. Conf. Machine Learning (ICML 2012) (Edinburgh, UK), 1–17.Google Scholar
• Jenatton R, Audibert J-Y, Bach F (2011) Structured variable selection with sparsity-inducing norms. J. Machine Learn. Res. 12:2777–2824.Google Scholar
• Jenatton R, Gramfort A, Michel V, Obozinski G, Bach F, Thirion B (2011) Multi-scale mining of FMRI data with hierarchical structured sparsity. IEEE Internat. Workshop Pattern Recognition NeuroImaging (IEEE Computer Society, Los Alamitos, CA), 69–72.Crossref, Google Scholar
• Kyrillidis A, Mahabadi RK, Dinh QT, Cevher V (2014) Scalable sparse covariance estimation via self-concordance. Proc. 28th AAAI Conf. Artificial Intelligence (Association for the Advancement of Artificial Intelligence, Menlo Park, CA), 1946–1952.Google Scholar
• Kyrillidis A, Baldassarre L, El Halabi M, Tran-Dinh Q, Cevher V (2015) Structured sparsity: Discrete and convex approaches. Boche H, Caire G, Calderbank R, März M, Kutyniok G, Mathar R, eds. Compressed Sensing and Its Applications (Springer, Cham, Switzerland), 341–387.Crossref, Google Scholar
• Lewis A, Sendov H (2001) Self-concordant barriers for hyperbolic means. Math. Programming 91(1):1–10.Crossref, Google Scholar
• Liu Z, Vandenberghe L (2009) Interior-point method for nuclear norm approximation with application to system identification. SIAM J. Matrix Anal. Appl. 31(3):1235–1256.Crossref, Google Scholar
• Löefberg J (2004) YALMIP: A toolbox for modeling and optimization in MATLAB. 2004 IEEE International Conference on Robotics and Automation (New Orleans, LA), 284–289.Google Scholar
• Millane R (1990) Phase retrieval in crystallography and optics. J. Optical Soc. Amer. A 7(3):394–411.Crossref, Google Scholar
• MOSEK (2015) The MOSEK Optimization Toolbox for MATLAB Manual, Version 7.1 (Revision 28) (MOSEK ApS, Copenhagen, Denmark).Google Scholar
• Nemirovski A (2001) Lectures on Modern Convex Optimization (SIAM, Philadelphia).Google Scholar
• Nemirovski A, Shapiro A (2006) Convex approximations of chance constrained programs. SIAM J. Optim. 17(4):969–996.Crossref, Google Scholar
• Nemirovski A, Todd MJ (2008) Interior-point methods for optimization. Acta Numerica 17(1):191–234.Crossref, Google Scholar
• Nesterov Y (2004) Introductory Lectures on Convex Optimization: A Basic Course Applied Optimization, Vol. 87 (Kluwer Academic Publishers, Boston).Crossref, Google Scholar
• Nesterov Y (2006) Constructing self-concordant barriers for convex cones. CORE Discussion Paper 2006/30, Catholic University of Louvain, Louvain-la-Neuve, Belgium.Google Scholar
• Nesterov Y (2011) Barrier subgradient method. Math. Programming Ser. B 127(1):31–56.Crossref, Google Scholar
• Nesterov Y (2013) Gradient methods for minimizing composite objective function. Math. Programming 140(1):125–161.Crossref, Google Scholar
• Nesterov Y, Nemirovski A (1994) Interior-Point Polynomial Algorithms in Convex Programming (SIAM, Philadelphia).Crossref, Google Scholar
• Nesterov Y, Nemirovski A (1992) Conic formulation of a convex programming problem and duality. Optim. Methods Software 1(2):95–115.Crossref, Google Scholar
• Nesterov Y, Todd MJ (1997) Self-scaled barriers and interior-point methods for convex programming. Math. Oper. Res. 22(1):1–42.Link, Google Scholar
• O’Donoghue B, Candès E (2015) Adaptive restart for accelerated gradient schemes. Foundations Comput. Math. 15(3):715–732.Crossref, Google Scholar
• Parikh N, Boyd S (2013) Proximal algorithms. Foundations Trends Optim. 1(3):123–231.Google Scholar
• Rapaport F, Barillot E, Vert JP (2008) Classification of array CGH data using fused SVM. Bioinformatics 24(13):i375–i382.Crossref, Google Scholar
• Renegar J (2001) A Mathematical View of Interior-Point Methods in Convex Optimization, MPS/SIAM Series on Optimization, Vol. 2 (SIAM, Philadelphia).Crossref, Google Scholar
• Rockafellar RT (1970) Convex Analysis, Princeton Mathematics Series, Vol. 28 (Princeton University Press, Princeton, NJ).Crossref, Google Scholar
• Roos C, Terlaky T, Vial J-P (2006) Interior Point Methods for Linear Optimization (Springer Science, Heidelberg, Germany).Google Scholar
• Sturm F (1999) Using SeDuMi 1.02: A Matlab toolbox for optimization over symmetric cones. Optim. Methods Software 11(1–4):625–653.Crossref, Google Scholar
• Su W, Boyd S, Candès E (2014) A differential equation for modeling Nesterov’s accelerated gradient method: Theory and insights. Ghahramani Z, Welling M, Cortes C, Lawrence ND, Weinberger KQ, eds. Advances in Neural Information Processing Systems, Vol. 2 (MIT Press, Cambridge, MA), 2510–2518.Google Scholar
• Subramanian A, Tamayo P, Mootha VK, Mukherjee S, Ebert BL, Gillette MA, Paulovich A, Pomeroy SL, Golub TR, Lander ES (2005) Gene set enrichment analysis: A knowledge-based approach for interpreting genome-wide expression profiles. Proc. Natl. Acad. Sci. USA 102(43):15545–15550.Crossref, Google Scholar
• Toh K-Ch, Todd MJ, Tütüncü RH (2010) On the implementation and usage of SDPT3—A MATLAB software package for semidefinite-quadratic-linear programming, version 4.0. Technical report, NUS Singapore, Singapore.Google Scholar
• Tran-Dinh Q, Kyrillidis A, Cevher V (2013) A proximal Newton framework for composite minimization: Graph learning without Cholesky decompositions and matrix inversions. Proc. 30th Internat. Conf. Machine Learn., 271–279.Google Scholar
• Tran-Dinh Q, Kyrillidis A, Cevher V (2014) An inexact proximal path-following algorithm for constrained convex minimization. SIAM J. Optim. 24(4):1718–1745.Crossref, Google Scholar
• Tran-Dinh Q, Kyrillidis A, Cevher V (2015) Composite self-concordant minimization. J. Machine Learn. Res. 16(1):374–416.Google Scholar
• Tütüncü RH, Toh KC, Todd MJ (2003) Solving semidefinite-quadratic-linear programs using SDPT3. Math. Programming 95(2):189–217.Crossref, Google Scholar
• Vanderbei R, Liu H, Wang L, Lin K (2013) Optimization for compressed sensing: The simplex method and Kronecker sparsification. Working paper, Princeton University, Princeton, NJ. https://arxiv.org/abs/1312.4426v1.Google Scholar
• Wright SJ (1997) Primal-Dual Interior-Point Methods (SIAM, Philadelphia).Crossref, Google Scholar
• Zhou H, Sehl ME, Sinsheimer JS, Lange K (2010) Association screening of common and rare genetic variants by penalized regression. Bioinformatics 26(19):2375–2382.Crossref, Google Scholar