, Combining inequalities (B.14) to (B.19) we get that, for all i ?
, Noisy matrix decomposition via convex relaxation: Optimal rates in high dimensions, The Annals of Statistics, vol.40, issue.2, pp.1171-1197, 2012.
, Living on the edge: Phase transitions in convex programs with random data. Information and Inference: A, Journal of the IMA, vol.3, issue.3, pp.224-294, 2014.
, Convex multi-task feature learning, Machine Learning, vol.73, pp.243-272, 2008.
, Sparse prediction with the k-support norm, Advances in Neural Information Processing Systems, vol.25, pp.1466-1474, 2012.
URL : https://hal.archives-ouvertes.fr/hal-00858954
, Learning with submodular functions: A convex optimization perspective. Foundations and Trends in Machine Learning, vol.6, pp.145-373, 2013.
URL : https://hal.archives-ouvertes.fr/hal-00645271
, Duality between subgradient and conditional gradient methods, SIAM Journal on Optimization, vol.25, issue.1, pp.115-129, 2015.
URL : https://hal.archives-ouvertes.fr/hal-00757696
, Optimization with sparsityinducing penalties. Foundation and Trends in Machine Learning, vol.1, pp.1-106, 2012.
URL : https://hal.archives-ouvertes.fr/hal-00613125
, Optimization with sparsityinducing penalties. Foundations and Trends® in Machine Learning, vol.4, pp.1-106, 2012.
URL : https://hal.archives-ouvertes.fr/hal-00613125
, On the equivalence between herding and conditional gradient algorithms, 2012.
URL : https://hal.archives-ouvertes.fr/hal-00681128
, Convex sparse matrix factorizations, 2008.
URL : https://hal.archives-ouvertes.fr/hal-00345747
, Model selection through sparse maximum likelihood estimation for multivariate gaussian or binary data, Journal of Machine learning research, vol.9, pp.485-516, 2008.
, Nonlinear programming, 1999.
, Convex optimization algorithms, 2015.
, A lasso for hierarchical interactions, The Annals of Statistics, vol.41, issue.3, pp.1111-1141, 2013.
, Convex analysis and nonlinear optimization, 2006.
, Convex Optimization, 2004.
, A generalized conditional gradient method and its connection to an iterative shrinkage method, Computational Optimization and Applications, vol.42, issue.2, pp.173-193, 2009.
, Simple bounds for recovering low-complexity models, Mathematical Programming, pp.577-589, 2013.
, Robust principal component analysis, Journal of the ACM (JACM), vol.58, issue.3, p.11, 2011.
, Exact matrix completion via convex optimization, Foundations of Computational mathematics, vol.9, issue.6, p.717, 2009.
, Inferring large graphs using 1 -penalized likelihood, Statistics and Computing, vol.28, issue.4, pp.905-921, 2018.
URL : https://hal.archives-ouvertes.fr/hal-01602560
, Latent variable graphical model selection via convex optimization, Communication, Control, and Computing (Allerton), 2010 48th Annual Allerton Conference on, pp.1610-1613, 2010.
DOI : 10.1109/allerton.2010.5707106
URL : https://authors.library.caltech.edu/34693/1/cpw_lgm_preprint10.pdf
, The convex geometry of linear inverse problems, Foundations of Computational mathematics, vol.12, issue.6, pp.805-849, 2012.
, Rank-sparsity incoherence for matrix decomposition, SIAM Journal on Optimization, vol.21, issue.2, pp.572-596, 2011.
DOI : 10.1137/090761793
URL : https://authors.library.caltech.edu/34747/1/cspw_slr_siopt11.pdf
, Approximating discrete probability distributions with dependence trees, IEEE transactions on Information Theory, vol.14, issue.3, pp.462-467, 1968.
DOI : 10.1109/tit.1968.1054142
URL : http://www.cs.iastate.edu/~honavar/chou-liu.pdf
, Compressed sensing and best k-term approximation, Journal of the American mathematical society, vol.22, issue.1, pp.211-231, 2009.
DOI : 10.1090/s0894-0347-08-00610-3
URL : http://www.igpm.rwth-aachen.de/Download/reports/pdf/IGPM260.pdf
, Proximal splitting methods in signal processing, Fixed-point algorithms for inverse problems in science and engineering, pp.185-212, 2011.
DOI : 10.1007/978-1-4419-9569-8_10
URL : https://hal.archives-ouvertes.fr/hal-00643807
, A taxonomy of problems with fast parallel algorithms, Information and control, vol.64, issue.1-3, pp.2-22, 1985.
, Penalized likelihood for sparse contingency tables with an application to full-length cdna libraries, BMC bioinformatics, vol.8, issue.1, p.476, 2007.
DOI : 10.1186/1471-2105-8-476
URL : https://bmcbioinformatics.biomedcentral.com/track/pdf/10.1186/1471-2105-8-476
, Optimal solutions for sparse principal component analysis, Journal of Machine Learning Research, vol.9, pp.1269-1294, 2008.
, First-order methods for sparse covariance selection, SIAM Journal on Matrix Analysis and Applications, vol.30, issue.1, pp.56-66, 2008.
, A direct formulation for sparse PCA using semidefinite programming, Advances in Neural Information Processing Systems, pp.41-48, 2005.
, A convex formulation for learning scale-free networks via submodular relaxation, Advances in Neural Information Processing Systems, pp.1250-1258, 2012.
, Convex and semi-nonnegative matrix factorizations. Pattern Analysis and Machine Intelligence, IEEE Transactions on, vol.32, issue.1, pp.45-55, 2010.
DOI : 10.1109/tpami.2008.277
URL : http://ranger.uta.edu/~chqding/papers/Ding-Li-Jordan.pdf
, Optimally sparse representation in general (nonorthogonal) dictionaries via 1 minimization, Proceedings of the National Academy of Sciences, vol.100, issue.5, pp.2197-2202, 2003.
DOI : 10.1073/pnas.0437847100
URL : https://www.pnas.org/content/pnas/100/5/2197.full.pdf
, Structure learning in graphical modeling, Annual Review of Statistics and Its Application, vol.4, pp.365-393, 2017.
DOI : 10.1146/annurev-statistics-060116-053803
URL : http://arxiv.org/pdf/1606.02359
, Image denoising via sparse and redundant representations over learned dictionaries, IEEE Transactions on Image processing, vol.15, issue.12, pp.3736-3745, 2006.
DOI : 10.1109/tip.2006.881969
, Simultaneous cartoon and texture image inpainting using morphological component analysis (mca), Applied and Computational Harmonic Analysis, vol.19, issue.3, pp.340-358, 2005.
DOI : 10.1016/j.acha.2005.03.005
URL : https://doi.org/10.1016/j.acha.2005.03.005
, See all by looking at a few: Sparse modeling for finding representative objects, 2012 IEEE Conference on Computer Vision and Pattern Recognition, pp.1600-1607, 2012.
DOI : 10.1109/cvpr.2012.6247852
URL : http://www.cis.jhu.edu/~ehsan/Downloads/SMRS-CVPR12-Ehsan.pdf
, Sparse subspace clustering: Algorithm, theory, and applications. IEEE transactions on pattern analysis and machine intelligence, vol.35, pp.2765-2781, 2013.
DOI : 10.1109/tpami.2013.57
URL : http://arxiv.org/pdf/1203.1005
, Stable recovery with analysis decomposable priors, Proc. SampTA'13, pp.113-116, 2013.
URL : https://hal.archives-ouvertes.fr/hal-00926727
, Primal and dual active-set methods for convex quadratic programming, Mathematical Programming, pp.1-40, 2015.
DOI : 10.1007/s10107-015-0966-2
URL : http://arxiv.org/pdf/1503.08349
, Primal and dual active-set methods for convex quadratic programming, Mathematical Programming, vol.159, issue.1, pp.469-508, 2016.
DOI : 10.1007/s10107-015-0966-2
URL : http://arxiv.org/pdf/1503.08349
, Corrupted sensing: Novel guarantees for separating structured signals, IEEE Transactions on Information Theory, vol.60, issue.2, pp.1223-1247, 2014.
DOI : 10.1109/tit.2013.2293654
URL : http://arxiv.org/pdf/1305.2524.pdf
, Matrix reconstruction with the local max norm, Advances in Neural Information Processing Systems, pp.935-943, 2012.
, Cutting plane methods in machine learning, Optimization for Machine Learning, 2011.
, An algorithm for quadratic programming, Naval Research Logistics (NRL), vol.3, issue.1-2, pp.95-110, 1956.
DOI : 10.1002/nav.3800030109
, Gauge optimization and duality, SIAM Journal on Optimization, vol.24, issue.4, pp.1999-2022, 2014.
DOI : 10.1137/130940785
URL : http://arxiv.org/pdf/1310.2639
, Sparse inverse covariance estimation with the graphical lasso, Biostatistics, vol.9, issue.3, pp.432-441, 2008.
DOI : 10.1093/biostatistics/kxm045
URL : https://academic.oup.com/biostatistics/article-pdf/9/3/432/17742149/kxm045.pdf
, Regularization paths for generalized linear models via coordinate descent, Journal of statistical software, vol.33, issue.1, p.1, 2010.
DOI : 10.18637/jss.v033.i01
URL : https://www.jstatsoft.org/index.php/jss/article/view/v033i01/v33i01.pdf
, Inferring cellular networks using probabilistic graphical models, Science, vol.303, issue.5659, pp.799-805, 2004.
DOI : 10.1126/science.1094068
, Identifying independence in bayesian networks, Networks, vol.20, issue.5, pp.507-534, 1990.
, High dimensional structured superposition models, Advances In Neural Information Processing Systems, pp.3691-3699, 2016.
, Low-rank and sparse structure pursuit via alternating minimization, Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, pp.600-609, 2016.
, Global optimality in tensor factorization, deep learning, and beyond, 2015.
, Conditional gradient algorithms for norm-regularized smooth convex optimization, Mathematical Programming, vol.152, issue.1-2, pp.75-112, 2015.
DOI : 10.1007/s10107-014-0778-9
URL : https://hal.archives-ouvertes.fr/hal-00978368
, Learning bayesian networks: The combination of knowledge and statistical data, Machine learning, vol.20, issue.3, pp.197-243, 1995.
, Iteration complexity analysis of block coordinate descent methods, 2013.
DOI : 10.1007/s10107-016-1057-8
URL : http://arxiv.org/pdf/1310.6957
, Learning sparse gaussian graphical models with overlapping blocks, Advances in Neural Information Processing Systems, pp.3808-3816, 2016.
, Covariance matrix selection and estimation via penalised normal likelihood, Biometrika, vol.93, issue.1, pp.85-98, 2006.
, Estimation of non-normalized statistical models by score matching, Journal of Machine Learning Research, vol.6, pp.695-709, 2005.
, Group lasso with overlap and graph lasso, ICML, 2009.
, Revisiting frank-wolfe: Projection-free sparse convex optimization, ICML (1), pp.427-435, 2013.
, On learning discrete graphical models using greedy methods, Advances in Neural Information Processing Systems, pp.1935-1943, 2011.
, A dirty model for multi-task learning, Advances in Neural Information Processing Systems, pp.964-972, 2010.
, Structured variable selection with sparsityinducing norms, JMLR, vol.12, pp.2777-2824, 2011.
URL : https://hal.archives-ouvertes.fr/inria-00377732
, Proximal methods for hierarchical sparse coding, JMLR, vol.12, pp.2297-2334, 2011.
URL : https://hal.archives-ouvertes.fr/inria-00516723
, Topological sorting of large networks, Communications of the ACM, vol.5, issue.11, pp.558-562, 1962.
, Linear convergence of gradient and proximalgradient methods under the polyak-?ojasiewicz condition, Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pp.795-811, 2016.
, Tensor decompositions and applications, SIAM review, vol.51, issue.3, pp.455-500, 2009.
, Probabilistic graphical models: principles and techniques, 2009.
, Accelerating ista with an active set strategy, OPT 2011: 4th International Workshop on Optimization for Machine Learning, p.7, 2011.
URL : https://hal.archives-ouvertes.fr/hal-00696992
, A pathwise algorithm for covariance selection, Optimization for Machine Learning, pp.479-494, 2011.
, On the global linear convergence of Frank-Wolfe optimization variants, Advances in Neural Information Processing Systems, vol.28, pp.496-504, 2015.
URL : https://hal.archives-ouvertes.fr/hal-01248675
, Block-coordinate frankwolfe optimization for structural svms, 2012.
URL : https://hal.archives-ouvertes.fr/hal-00720158
, Using causal information and local measures to learn bayesian networks, Uncertainty in Artificial Intelligence, pp.243-250, 1993.
, A generic column generation principle: derivation and convergence analysis, Operational Research, vol.15, issue.2, pp.163-198, 2015.
, Graphical models, vol.17, 1996.
, Learning the parts of objects by non-negative matrix factorization, Nature, vol.401, issue.6755, p.788, 1999.
, Efficient structure learning of markov networks using l_1-regularization, Advances in neural Information processing systems, pp.817-824, 2007.
, Sparse estimation of large covariance matrices via a nested lasso penalty, The Annals of Applied Statistics, pp.245-263, 2008.
, Using modified lasso regression to learn large undirected graphs in a probabilistic framework, Proceedings of the National Conference on Artificial Intelligence, vol.20, p.801, 2005.
, Estimation of high-dimensional graphical models using regularized score matching, Electronic Journal of Statistics, vol.10, issue.1, pp.806-854, 2016.
DOI : 10.1214/16-ejs1126
URL : https://doi.org/10.1214/16-ejs1126
, Robust subspace segmentation by low-rank representation, Proceedings of the 27th international conference on machine learning (ICML-10), pp.663-670, 2010.
, Tensor completion for estimating missing values in visual data. Pattern Analysis and Machine Intelligence, IEEE Transactions on, vol.35, issue.1, pp.208-220, 2013.
, A Unified Optimization View on Generalized Matching Pursuit and Frank-Wolfe, Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, vol.54, pp.860-868, 2017.
, Greedy algorithms for cone constrained optimization with convergence guarantees, Advances in Neural Information Processing Systems, pp.773-784, 2017.
, Sparse modeling for image and vision processing, Foundations and Trends® in Computer Graphics and Vision, vol.8, issue.2-3, pp.85-283, 2014.
DOI : 10.1561/0600000058
URL : https://hal.archives-ouvertes.fr/hal-01081139
, Structured sparsity and generalization, The Journal of Machine Learning Research, vol.13, issue.1, pp.671-690, 2012.
, Convexity in source separation: Models, geometry, and algorithms, IEEE Signal Processing Magazine, vol.31, issue.3, pp.87-95, 2014.
, The achievable performance of convex demixing, 2013.
, Sharp recovery bounds for convex demixing, with applications, Foundations of Computational Mathematics, vol.14, issue.3, pp.503-567, 2014.
, High-dimensional graphs and variable selection with the lasso. The annals of statistics, pp.1436-1462, 2006.
, Learning latent variable gaussian graphical models, Proceedings of the 31st International Conference on Machine Learning (ICML-14), pp.1269-1277, 2014.
, Spectral bounds for sparse pca: Exact and greedy algorithms, Advances in Neural Information Processing Systems, pp.915-922, 2006.
, Fonctions convexes duales et points proximaux dans un espace hilbertien, CR Acad. Sci. Paris Ser. A Math, vol.255, pp.2897-2899, 1962.
URL : https://hal.archives-ouvertes.fr/hal-01867195
, Proximité et dualité dans un espace hilbertien, vol.93, pp.273-299, 1965.
DOI : 10.24033/bsmf.1625
URL : http://www.numdam.org/article/BSMF_1965__93__273_0.pdf
, Gap safe screening rules for sparsity enforcing penalties, J. Mach. Learn. Res, vol.18, issue.128, pp.1-33, 2017.
, A unified framework for high-dimensional analysis of m-estimators with decomposable regularizers, Statistical Science, vol.27, issue.4, pp.538-557, 2012.
, Efficiency of coordinate descent methods on huge-scale optimization problems, SIAM Journal on Optimization, vol.22, issue.2, pp.341-362, 2012.
, Complexity bounds for primal-dual methods minimizing the model of objective function, 2015.
, Numerical optimization, 2006.
, Convex relaxation for combinatorial penalties, 2012.
URL : https://hal.archives-ouvertes.fr/hal-00694765
, A unified perspective on convex structured sparsity: Hierarchical, symmetric, submodular norms and beyond, 2016.
URL : https://hal.archives-ouvertes.fr/hal-01412385
, Group Lasso with overlaps: the Latent Group Lasso approach, 2011.
URL : https://hal.archives-ouvertes.fr/inria-00628498
, Multi-task feature selection, Statistics Department, 2006.
, Joint covariate selection and joint subspace selection for multiple classification problems, Statistics and Computing, vol.20, issue.2, pp.231-252, 2010.
, Beyond low rank+ sparse: Multiscale low rank matrix decomposition, IEEE journal of selected topics in signal processing, vol.10, issue.4, pp.672-687, 2016.
, Sparse spatial autoregressions, Statistics and Probability Letters, vol.33, issue.3, pp.291-297, 1997.
, Efficient block-coordinate descent algorithms for the group lasso, Mathematical Programming Computation, vol.5, issue.2, pp.143-169, 2013.
, Forward -Backward Greedy Algorithms for Atomic Norm Regularization, IEEE Transactions on Signal Processing, vol.63, issue.21, pp.5798-5811, 2015.
, High-dimensional graphical model selection using l1-regularized logistic regression, Annals of Statistics, 2009.
, Improved greedy algorithms for learning graphical models, IEEE Transactions on Information Theory, vol.61, issue.6, pp.3457-3468, 2015.
, Intersecting singularities for multi-structured estimation, ICML (3), pp.1157-1165, 2013.
URL : https://hal.archives-ouvertes.fr/hal-00918253
, Tight convex relaxations for sparse matrix factorization, Advances in Neural Information Processing Systems, pp.3284-3292, 2014.
URL : https://hal.archives-ouvertes.fr/hal-01101878
, Convex Analysis, 1970.
, The group-lasso for generalized linear models: uniqueness of solutions and efficient algorithms, Proceedings of the 25th international conference on Machine learning, pp.848-855, 2008.
, Sparse permutation invariant covariance estimation, Electronic Journal of Statistics, vol.2, pp.494-515, 2008.
DOI : 10.1214/08-ejs176
URL : https://doi.org/10.1214/08-ejs176
, Learning graphical model structure using l1-regularization paths, AAAI, vol.7, pp.1278-1283, 2007.
, Stochastic methods for l1-regularized loss minimization, Journal of Machine Learning Research, vol.12, pp.1865-1892, 2011.
, Group regularized estimation under structural hierarchy, 2014.
, An algorithm for fast recovery of sparse causal graphs, Social science computer review, vol.9, issue.1, pp.62-72, 1991.
, Learning graphical models with hubs, Journal of Machine Learning Research, vol.15, issue.1, pp.3297-3331, 2014.
, Inverse covariance estimation with structured groups, 26th International Joint Conference on Artificial Intelligence, 2017.
, Regression shrinkage and selection via the Lasso, J. Roy. Stat. Soc. B, vol.58, issue.1, 1996.
, On the solution of ill-posed problems and the method of regularization, Doklady Akademii Nauk, vol.151, pp.501-504, 1963.
, Convex tensor decomposition via structured Schatten norm regularization, Advances in Neural information Processing Systems, pp.1331-1339, 2013.
, Just relax: Convex programming methods for subset selection and sparse approximation, p.404, 2004.
, Convergence of a block coordinate descent method for nondifferentiable minimization, Journal of optimization theory and applications, vol.109, issue.3, pp.475-494, 2001.
, Model selection with low complexity priors. Information and Inference: A, Journal of the IMA, vol.4, issue.3, pp.230-287, 2015.
URL : https://hal.archives-ouvertes.fr/hal-00842603
, Low complexity regularization of linear inverse problems, Sampling Theory, a Renaissance, pp.103-153, 2015.
URL : https://hal.archives-ouvertes.fr/hal-01018927
, On diagonal dominance arguments for bounding a ?1 ? . Linear Algebra and its applications, vol.14, pp.211-217, 1976.
, Subspace clustering, IEEE Signal Processing Magazine, vol.28, issue.2, pp.52-68, 2011.
, Fast column generation for atomic norm regularization, Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, vol.54, pp.547-556, 2017.
URL : https://hal.archives-ouvertes.fr/hal-01502575
, Learning the effect of latent variables in gaussian graphical models with unobserved variables, 2018.
, Multitask learning meets tensor factorization: task imputation via convex optimization, Advances in Neural Information Processing Systems, vol.27, pp.2825-2833, 2014.
, Theoretical and experimental analyses of tensor-based regression and classification, Neural Computation, vol.4, issue.28, pp.686-715, 2016.
, Convergence theory in nonlinear programming. Integer and nonlinear programming, pp.1-36, 1970.
, Finding the nearest point in a polytope, Mathematical Programming, vol.11, issue.1, pp.128-149, 1976.
, Finding the nearest point in a polytope, Mathematical Programming, vol.11, issue.1, pp.128-149, 1976.
, Compressive principal component pursuit. Information and Inference: A, Journal of the IMA, vol.2, issue.1, pp.32-68, 2013.
, Coordinate descent algorithms. Mathematical Programming, vol.151, pp.3-34, 2015.
, Robust pca via outlier pursuit, Advances in Neural Information Processing Systems, pp.2496-2504, 2010.
, Speeding up latent variable gaussian graphical model estimation via nonconvex optimization, Advances in Neural Information Processing Systems, pp.1930-1941, 2017.
, Hierarchical sparse modeling: A choice of two regularizers, 2015.
, Oracle based active set algorithm for scalable elastic net subspace clustering, Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp.3928-3937, 2016.
, Generalized conditional gradient for sparse estimation, 2014.
, Model selection and estimation in regression with grouped variables, Journal of The Royal Statistical Society Series B, vol.68, issue.1, pp.49-67, 2006.
, Model selection and estimation in regression with grouped variables, J. Roy. Stat. Soc. B, vol.68, pp.49-67, 2006.
, Model selection and estimation in the gaussian graphical model, Biometrika, pp.19-35, 2007.
, Truncated power method for sparse eigenvalue problems, Journal of Machine Learning Research, vol.14, pp.899-925, 2013.
, Sparse pca: Convex relaxations, algorithms and applications, Handbook on Semidefinite, Conic and Polynomial Optimization, pp.915-940, 2012.
, Structure learning of probabilistic graphical models: a comprehensive survey, 2011.
, Regularization and variable selection via the elastic net, Journal of the Royal Statistical Society: Series B (Statistical Methodology), vol.67, issue.2, pp.301-320, 2005.
, Sparse principal component analysis, Journal of computational and graphical statistics, vol.15, issue.2, pp.265-286, 2006.