We study the ℓ1 regularized least squares optimization problem in a separable Hilbert space. We show that the iterative soft-thresholding algorithm (ISTA) converges linearly, without making any assumption on the linear operator into play or on the problem. The result is obtained combining two key concepts: the notion of extended support, a finite set containing the support, and the notion of conditioning over finite-dimensional sets. We prove that ISTA identifies the solution extended support after a finite number of iterations, and we derive linear convergence from the conditioning property, which is always satisfied for ℓ1 regularized least squares problems. Our analysis extends to the entire class of thresholding gradient algorithms, for which we provide a conceptually new proof of strong convergence, as well as convergence rates.
Mots-clés : Forward–Backward method, support identification, conditioning, convergence rates
@article{COCV_2020__26_1_A28_0,
author = {Garrigos, Guillaume and Rosasco, Lorenzo and Villa, Silvia},
title = {Thresholding gradient methods in {Hilbert} spaces: support identification and linear convergence},
journal = {ESAIM: Control, Optimisation and Calculus of Variations},
publisher = {EDP-Sciences},
volume = {26},
year = {2020},
doi = {10.1051/cocv/2019011},
mrnumber = {4077680},
zbl = {07198291},
language = {en},
url = {http://www.numdam.org/articles/10.1051/cocv/2019011/}
}
TY - JOUR AU - Garrigos, Guillaume AU - Rosasco, Lorenzo AU - Villa, Silvia TI - Thresholding gradient methods in Hilbert spaces: support identification and linear convergence JO - ESAIM: Control, Optimisation and Calculus of Variations PY - 2020 VL - 26 PB - EDP-Sciences UR - http://www.numdam.org/articles/10.1051/cocv/2019011/ DO - 10.1051/cocv/2019011 LA - en ID - COCV_2020__26_1_A28_0 ER -
%0 Journal Article %A Garrigos, Guillaume %A Rosasco, Lorenzo %A Villa, Silvia %T Thresholding gradient methods in Hilbert spaces: support identification and linear convergence %J ESAIM: Control, Optimisation and Calculus of Variations %D 2020 %V 26 %I EDP-Sciences %U http://www.numdam.org/articles/10.1051/cocv/2019011/ %R 10.1051/cocv/2019011 %G en %F COCV_2020__26_1_A28_0
Garrigos, Guillaume; Rosasco, Lorenzo; Villa, Silvia. Thresholding gradient methods in Hilbert spaces: support identification and linear convergence. ESAIM: Control, Optimisation and Calculus of Variations, Tome 26 (2020), article no. 28. doi : 10.1051/cocv/2019011. http://www.numdam.org/articles/10.1051/cocv/2019011/
[1] and , On the convergence of the proximal algorithm for nonsmooth functions involving analytic features. Math. Program. Ser. B 116 (2009) 5–16. | DOI | MR | Zbl
[2] , and , Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward-backward splitting, and regularized Gauss-Seidel methods. Math. Program. 137 (2013) 91–129. | DOI | MR | Zbl
[3] , and , Maximal Solutions of Sparse Analysis Regularization. Preprint (2017). | arXiv | MR
[4] and , Convex Analysis and Monotone Operator Theory, CMS Books in Mathematics, 2nd edn. Springer, Berlin (2017). | MR | Zbl
[5] and , A family of functional inequalities: Lojasiewicz inequalities and displacement convex functions. J. Funct. Anal. 275 (2018) 1650–1673. | DOI | MR | Zbl
[6] , , and , From error bounds to the complexity of first-order descent methods for convex functions. Math. Programm. 165 (2017) 471–507. | DOI | MR | Zbl
[7] and , Partially finite convex programming, part I: Quasi relative interiors and duality theory. Math. Programm. 57 (1992) 15–48. | DOI | MR | Zbl
[8] and , Linear convergence of iterative soft-thresholding. J. Fourier Anal. Appl. 14 (2008) 813–837. | DOI | MR | Zbl
[9] and , Proximal thresholding algorithm for minimization over orthonormal bases. SIAM J. Optim. 18 (2007) 1351–1376. | DOI | MR | Zbl
[10] , and , Consistency of regularized learning schemes in Banach spaces. Math. Programm. published online 2017-03-25.
[11] , and , An iterative thresholding algorithm for linear inverse problems with a sparsity constraint. Commun. Pure Appl. Math. 57 (2004) 1413–1457. | DOI | MR | Zbl
[12] and , Convergence rate analysis of several splitting schemes, in Splitting Methods in Communication, Imaging, Science, and Engineering. Springer International Publishing, Switzerland (2016) 115–163. | DOI | MR
[13] , and , Elastic-net regularization in learning theory. J. Complexity 25 (2009) 201–230. | DOI | MR | Zbl
[14] , , and , Sparse support recovery with non-smooth loss functions, in Advances in Neural Information Processing Systems (2016) 4269–4277.
[15] , A necessary and sufficient condition for exact recovery by minimization. Comptes Rendus Mathématique 350 (2011) 117–120. | DOI | MR | Zbl
[16] and , Error bounds, quadratic growth, and linear convergence of proximal methods. Math. Oper. Res. (2018) published online. | MR | Zbl
[17] and , Sparse spikes super-resolution on thin grids I: the LASSO. Inverse Probl. 33 (2017) 055008. | DOI | Zbl
[18] , and , Sensitivity analysis for Mirror-Stratifiable convex functions. Preprint (2017). | arXiv | MR
[19] , and , Splitting methods with variable metric for Kurdyka-Łojasiewicz functions and general convergence rates. J. Optim. Theory Appl. 165 (2015) 874–900. | DOI | MR | Zbl
[20] , and , Convergence of the Forward-Backward algorithm: beyond the worst case with the help of geometry. Preprint (2017). | arXiv | MR
[21] , and , Fixed-point continuation for ℓ1-minimization: methodology and convergence. SIAM J. Optim. 19 (2008) 1107–1130. | DOI | MR | Zbl
[22] and , Identifying active constraints via partial smoothness and prox-regularity. J. Convex Anal. 11 (2004) 251–266. | MR | Zbl
[23] and , Convex Analysis and Minimization Algorithms I: Fundamentals. Springer Science & Business Media, Berlin (1993). | MR
[24] , Stability of the iteration method for non expansive mappings. Serdica Math. J. 22 (1996) 331–340. | Zbl
[25] , Global error bounds for piecewise convex polynomials. Math. Programm. 137 (2013) 37–64. | DOI | MR | Zbl
[26] , and , Local linear convergence of Forward–Backward under partial smoothness, in Advances in Neural Information Processing Systems (2014) 1970–1978.
[27] , and , Activity identification and local linear convergence of Forward-Backward-type methods. SIAM J. Optim. 27 (2017) 408–437. | DOI | MR | Zbl
[28] , , , and , Solving structured sparsity regularization with proximal methods, in Machine Learning and Knowledge Discovery in Databases, edited by , , , , ECML PKDD 2010. Vol 6322 of Lecture Notes in Computer Science. Springer, Berlin, Heidelberg (2010). | DOI
[29] , and , Linear convergence of first order methods for non-strongly convex optimization. Math. Programm. 175 (2018) 69–107. | DOI | MR | Zbl
[30] , and , “Active-set complexity” of proximal gradient: how long does it take to find the sparsity pattern?. Preprint (2017). | arXiv | MR
[31] , Convex Optimization in Normed Spaces: Theory, Methods and Examples. Springer Science & Buisness Media, Switzerland (2015). | DOI | MR | Zbl
[32] and , Evolution equations for maximal monotone operators: asymptotic analysis in continuous and discrete time. J. Convex Anal. 17 (2010) 1113–1163. | MR | Zbl
[33] , Convex Analysis, Vol. 28 of Princeton Mathematical Series. Princeton University Press, Princeton, NJ (1970). | MR | Zbl
[34] , Convex Analysis in General Vector Spaces. World Scientific, NJ (2002). | DOI | MR | Zbl
[35] and , Regularization and variable selection via the elastic net. J. R. Stat. Soc. Ser. B 67 (2005) 301–320. | DOI | MR | Zbl
Cité par Sources :
