Linear Convergence of Random Dual Coordinate Descent on Nonpolyhedral Convex Problems

References

• [1] Bauschke H, Borwein J (1996) On projection algorithms for solving convex feasibility problems. SIAM Rev. 38(3):367–426.Crossref, Google Scholar
• [2] Beck A, Teboulle M (2003) Convergence rate analysis and error bounds for projection algorithms in convex feasibility problems. Optim. Methods Software 18(4):377–394.Crossref, Google Scholar
• [3] Bhattacharyya C, Grate LR, Jordan MI, El Ghaoui L, Mian S (2004) Robust sparse hyperplane classifiers: Application to uncertain molecular profiling data. J. Comput. Biol. 11(6):1073–1089.Crossref, Google Scholar
• [4] Blatt D, Hero A (2006) Energy based sensor network source localization via projection onto convex sets. IEEE Trans. Signal Processing 54(9):3614–3619.Crossref, Google Scholar
• [5] Boyle JP, Dykstra RL (1986) A method for finding projections onto the intersection of convex sets in Hilbert spaces. Dykstra R, Robertson T, Wright FT, eds. Advances in Order Restricted Statistical Interference. Lecture Notes in Statistics, Vol. 37 (Springer, New York), 28–47.Crossref, Google Scholar
• [6] Choi H, Baraniuk R (2004) Multiple wavelet basis image denoising using Besov ball projections. IEEE Signal Processing Lett. 11(9):717–720.Crossref, Google Scholar
• [7] Combettes PL, Pesquet JC (2011) Proximal splitting methods in signal processing. Bauschke H, Burachik R, Combettes P, Elser V, Luke D, Wolkowicz H, eds. Fixed-Point Algorithms for Inverse Problems in Science and Engineering (Springer, New York), 185–212.Crossref, Google Scholar
• [8] Deutsch F, Hundal H (1994) The rate of convergence of Dykstra’s cyclic projections algorithm: The polyhedral case. Numerical Functional Anal. Optim. 15(5–6):537–565.Crossref, Google Scholar
• [9] Fercoq O, Qu Z (2020) Restarting the accelerated coordinate descent method with a rough strong convexity estimate. Comput. Optim. Appl. 75(1):63–91.Crossref, Google Scholar
• [10] Fercoq O, Richtarik P (2015) Accelerated, parallel and proximal coordinate descent. SIAM J. Optim. 25(4):1997–2023.Crossref, Google Scholar
• [11] Friberg H (2016) CBLIB 2014: A benchmark library for conic mixed-integer and continuous optimization. Math. Programming Comput. 8(2):191–214.Crossref, Google Scholar
• [12] Gidel G, Pedregosa F, Lacoste-Julien S (2018) Frank–Wolfe splitting via augmented Lagrangian method. Proc. 21st Internat. Conf. Artificial Intelligence Statist. Proceedings of Machine Learning Research, vol. 84 (MLResearch Press).Google Scholar
• [13] Goberna MA, Martinez-Legaz JE, Todorov MI (2010) On Motzkin decomposable sets and functions. J. Math. Anal. Appl. 372(2):525–537.Crossref, Google Scholar
• [14] Gu J, Stark H, Yang Y (2004) Wide-band smart antenna design using vector space projection methods. IEEE Trans. Antennas Propagation 52(12):3228–3236.Crossref, Google Scholar
• [15] Herman G, Chen W (2008) A fast algorithm for solving a linear feasibility problem with application to intensity-modulated radiation therapy. Linear Algebra Appl. 428(5–6):1207–1217.Crossref, Google Scholar
• [16] Hoffman AJ (1952) On approximate solutions of systems of linear inequalities. J. Res. Natl. Bureau Standards 49(4):174–176.Crossref, Google Scholar
• [17] Iusem A, Pierro AR (1990) On the convergence properties of Hildreth’s quadratic programming algorithm. Math. Programming 47:37–51.Crossref, Google Scholar
• [18] Li H, Lin Z (2018) On the complexity analysis of the primal solutions for the accelerated randomized dual coordinate ascent. Preprint, submitted July 1, https://arxiv.org/abs/1807.00261.Google Scholar
• [19] Liew A, Yan H, Law N (2005) POCS-based blocking artifacts suppression using a smoothness constraint set with explicit region modeling. IEEE Trans. Circuits Systems Video Tech. 15(6):795–800.Crossref, Google Scholar
• [20] Lu Z, Xiao L (2015) On the complexity analysis of randomized block-coordinate descent methods. Math. Programming 152(1–2):615–642.Crossref, Google Scholar
• [21] Necoara I, Clipici D (2016) Parallel random coordinate descent methods for composite minimization: Convergence analysis and error bounds. SIAM J. Optim. 26(1):197–226.Crossref, Google Scholar
• [22] Necoara I, Nedelcu V (2014) Rate analysis of inexact dual first order methods: Application to dual decomposition. IEEE Trans. Automatic Control 59(5):1232–1243.Crossref, Google Scholar
• [23] Necoara I, Nedelcu V (2015) On linear convergence of a distributed dual gradient algorithm for linearly constrained separable convex problems. Automatica J. IFAC 55(5):209–216.Crossref, Google Scholar
• [24] Necoara I, Nesterov Y, Glineur F (2019) Linear convergence of first order methods for non-strongly convex optimization. Math. Programming 175(1):69–107.Crossref, Google Scholar
• [25] Necoara I, Patrascu A, Richtarik P (2019) Randomized projection methods for convex feasibility problems: Conditioning and convergence rates. SIAM J. Optim. 29(4):2814–2852.Crossref, Google Scholar
• [26] Nedich A (2011) Random algorithms for convex minimization problems. Math. Programming 129(2):225–253.Crossref, Google Scholar
• [27] Nesterov Y (2004) Introductory Lectures on Convex Optimization: A Basic Course (Kluwer, Boston).Crossref, Google Scholar
• [28] Nesterov Y (2012) Efficiency of coordinate descent methods on huge-scale optimization problems. SIAM J. Optim. 22(2):341–362.Crossref, Google Scholar
• [29] Pang CJ (2017) Nonasymptotic and asymptotic linear convergence of an almost cyclic SHQP Dykstra’s algorithm for polyhedral problems. Preprint, submitted July 10, https://arxiv.org/abs/1707.03081.Google Scholar
• [30] Pang CJ (2019) Dykstra’s splitting and an approximate proximal point algorithm for minimizing the sum of convex functions. J. Optim. Theory Appl. 182:1019–1049.Crossref, Google Scholar
• [31] Patrascu A, Necoara I (2018) Nonasymptotic convergence of stochastic proximal point algorithms for constrained convex optimization. J. Machine Learn. Res. 18(198):1–42.Google Scholar
• [32] Qu Z, Richtarik P, Takac M, Fercoq O (2016) SDNA: Stochastic dual Newton ascent for empirical risk minimization. Proc. 33rd Internat. Conf. Machine Learn. Proceedings of Machine Learning Research, vol. 48 (MLResearch Press), 1823–1832.Google Scholar
• [33] Raj A, Bach F (2021) Explicit regularization of stochastic gradient methods through duality. Proc. 24th Internat. Conf. Artificial Intelligence Statist. Proceedings of Machine Learning Research, vol. 130 (MLResearch Press), 1882–1890.Google Scholar
• [34] Richtarik P, Takac M (2014) Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function. Math. Programming 144:1–38.Crossref, Google Scholar
• [35] Rockafellar TR (1970) Convex Analysis (Princeton University Press, Princeton, NJ).Crossref, Google Scholar
• [36] Samsonov A, Kholmovski E, Parker D, Johnson C (2004) POCSENSE: POCS-based reconstruction for sensitivity encoded magnetic resonance imaging. Magnetic Resonance Medicine 52(6):1397–1406.Crossref, Google Scholar
• [37] Sharma G (2000) Set theoretic estimation for problems in subtractive color. Color Res. Appl. 25:333–348.Crossref, Google Scholar
• [38] Stark H, Yang Y (1998) Vector Space Projections: A Numerical Approach to Signal and Image Processing, Neural Nets and Optics (Wiley-Interscience, Hoboken, NJ).Google Scholar
• [39] Tibshirani R (2017) Dykstra’s algorithm, ADMM, and coordinate descent: Connections, insights, and extensions. Proc. 31st Internat. Conf. Neural Inform. Processing Systems (Curran Associates, Red Hook, NY), 517–528.Google Scholar