Abstract

Screening rules were recently introduced as a technique for explicitly identifying active structures such as sparsity, in optimization problem arising in machine learning. This has led to new methods of acceleration based on a substantial dimension reduction. We show that screening rules stem from a combination of natural properties of subdifferential sets and optimality conditions, and can hence be understood in a unified way. Under mild assumptions, we analyze the number of iterations needed to identify the optimal active set for any converging algorithm. We show that it only depends on its convergence rate.

Author information

Contact details are reproduced from the original publication and may be historical.

Keywords

  • Convex optimization
  • screening rules
  • active set identification
  • nonsmooth optimization

Mathematics Subject Classification

49M29, 65K05, 90C06, 90C25

References

  1. J. Bolte, T. P. Nguyen, J. Peypouquet, B. W. Suter: From error bounds to the complexity of first-order descent methods for convex functions, Math. Programming 165 (2017) 471-–507.https://doi.org/10.1007/s10107-016-1091-6Google Scholar
  2. A. Bonnefoy, V. Emiya, L. Ralaivola, R. Gribonval: A dynamic screening principle for the lasso, EUSIPCO (2014) 6–10.Google Scholar
  3. J. M. Borwein, H. Wolkowicz: Facial reduction for a cone-convex programming problem, J. Australian Math. Soc. 30/3 (1981) 369–380.https://doi.org/10.1017/S1446788700017250Google Scholar
  4. A. L. Brearley, G. Mitra, H. P. Williams: Analysis of mathematical programming problems prior to applying the simplex algorithm, Math. Programming 8/1 (1975) 54–83.https://doi.org/10.1007/BF01580428Google Scholar
  5. L. Condat: Fast projection onto the simplex and the l1 ball, Math. Programming A 158/1-2 (2016) 575–585.https://doi.org/10.1007/s10107-015-0946-6Google Scholar
  6. D. Drusvyatskiy, H. Wolkowicz: The many faces of degeneracy in conic optimization, Found. Trends Optimization 3/2 (2017) 77–170.https://doi.org/10.1561/240000001Google Scholar
  7. C. Dünner, S. Forte, M. Takáč, M. Jaggi: Primal-dual rates and certificates, Proc. Machine Learning Research 48 (2016) 783–792.Google Scholar
  8. B. Efron, T. J. Hastie, I. M. Johnstone, R. Tibshirani: Least angle regression, Ann. Statistics 32/2 (2004) 407–499.https://doi.org/10.1214/009053604000000067Google Scholar
  9. L. El Ghaoui, V. Viallon, T. Rabbani: Safe feature elimination in sparse supervised learning, J. Pacific Optimimization 8/4 (2012) 667–698.Google Scholar
  10. J. Fan, J. Lv: Sure independence screening for ultrahigh dimensional feature space, J. R. Stat. Soc. Ser. B Stat. Method. 70/5 (2008) 849–911.https://doi.org/10.1111/j.1467-9868.2008.00674.xGoogle Scholar
  11. O. Fercoq, A. Gramfort, J. Salmon: Mind the duality gap: safer rules for the lasso, Proc. Machine Learning Research 37 (2015) 333–342.Google Scholar
  12. J. Giesen, J. K. Müller, S. Laue, S. Swiercy: Approximating concavely parameterized optimization problems, Neural Inform. Processing Systems 25 (2012) 2105–2113.Google Scholar
  13. J-B. Hiriart-Urruty, C. Lemaréchal: Fundamentals of Convex Analysis, Springer, Berlin (2001).https://doi.org/10.1007/978-3-642-56468-0Google Scholar
  14. T. B. Johnson, C. Guestrin: Blitz: A principled meta-algorithm for scaling sparse optimization, Proc. Machine Learning Research 37 (2015) 1171–1179.Google Scholar
  15. T. B. Johnson, C. Guestrin: Unified methods for exploiting piecewise linear structure in convex optimization, Neural Inform. Processing Systems 29 (2016) 4754–4762.Google Scholar
  16. A. Jourani, L. Thibault, D. Zagrodny: C 1,ω(·) -regularity and Lipschitz-like properties of subdifferential, Proc. Lond. Math. Soc. (3) 105/1 (2012) 189–223.https://doi.org/10.1112/plms/pdr062Google Scholar
  17. E. Kalnay, M. Kanamitsu, R. Kistler, W. Collins, D. Deaven, L. Gandin, M. Iredell, S. Saha, G. White, J. Woollen, Y. Zhu, M. Chelliah, W. Ebisuzaki, W. Higgins, J. Janowiak, K. C. Mo, C. Ropelewski, J. Wang, A. Leetmaa, R. Reynolds, R. Jenne, D. Joseph: The NCEP/NCAR 40-year reanalysis project, Bull. Amer. Meteor. Soc. 77/3 (1996) 437–472.https://doi.org/10.1175/1520-0477(1996)077<0437:TNYRP>2.0.CO;2Google Scholar
  18. M. Le Morvan, J.-P. Vert: WHinter: A working set algorithm for high-dimensional sparse second order interaction models, Proc. Machine Learning Research 80 (2018) 3632–3641.Google Scholar
  19. S. Lee, P. Breheny: Strong rules for nonconvex penalties and their implications for efficient algorithms in high-dimensional regression, J. Comp. Graph. Statistics 24/4 (2015) 1074–1091.https://doi.org/10.1080/10618600.2014.975231Google Scholar
  20. J. Liang, J. Fadili, G. Peyré: Activity identification and local linear convergence of forward-backward-type methods, SIAM J. Optimization 27/1 (2017) 408–437.https://doi.org/10.1137/16M106340XGoogle Scholar
  21. J. Mairal: Sparse Coding for Machine Learning, Image Processing and Computer Vision, PhD Thesis, École Normale Supérieure de Cachan (2010).Google Scholar
  22. H. Markowitz: The optimization of a quadratic function subject to linear constraints, Naval Res. Logist. Quart. 3 (1956) 111–133.https://doi.org/10.1002/nav.3800030110Google Scholar
  23. M. Massias, A. Gramfort, J. Salmon: Celer: a Fast Solver for the Lasso with Dual Extrapolation, Proc. Machine Learning Research 80 (2018) 3315–3324.Google Scholar
  24. M. Massias, S. Vaiter, A. Gramfort, J. Salmon: Dual extrapolation for sparse GLMs, J. Machine Learning Research 21/234 (2020) 1–33.Google Scholar
  25. C. Mészáros, U. H. Suhl: Advanced preprocessing techniques for linear and quadratic programming, OR Spectrum 25/4 (2003) 575–595.https://doi.org/10.1007/s00291-003-0130-xGoogle Scholar
  26. C. Michelot: A finite algorithm for finding the projection of a point onto the canonical simplex of Rn, J. Optimization Theory Appl. 50/1 (1986) 195–200.https://doi.org/10.1007/BF00938486Google Scholar
  27. E. Ndiaye, O. Fercoq, A. Gramfort, J. Salmon: GAP safe screening rules for sparse multi-task and multi-class models, in: NIPS 2015, Proc. 28th Int. Conf. Neural Inform. Processing Systems 1 (2015) 811–819.Google Scholar
  28. E. Ndiaye, O. Fercoq, A. Gramfort, J. Salmon: GAP safe screening rules for Sparse-Group Lasso, in: NIPS 2016, Advances in Neural Inform. Processing Systems 29 (2016) 1–9.Google Scholar
  29. E. Ndiaye, O. Fercoq, A. Gramfort, J. Salmon: Gap safe screening rules for sparsity enforcing penalties, J. Machine Learning Research 18/128 (2017) 1–33.Google Scholar
  30. E. Ndiaye, T. Le, O. Fercoq, J. Salmon, I. Takeuchi: Safe grid search with optimal complexity, Proc. Machine Learning Research 97 (2019) 4771–4780.Google Scholar
  31. J. Nutini, I. Laradji, M. Schmidt: Let’s make block coordinate descent go fast: Faster greedy rules, message-passing, active-set complexity, and superlinear convergence, arXiv: 1712.08859 (2017).Google Scholar
  32. K. Ogawa, Y. Suzuki, I. Takeuchi: Safe screening of non-support vectors in pathwise SVM computation, Proc. Machine Learning Research 28 (2013) 1382–1390.Google Scholar
  33. M. R. Osborne, B. Presnell, B. A. Turlach: A new approach to variable selection in least squares problems, IMA J. Numer. Analysis 20/3 (2000) 389–403.https://doi.org/10.1093/imanum/20.3.389Google Scholar
  34. A. Raj, J. Olbrich, B. Gärtner, B. Schölkopf, M. Jaggi: Screening rules for convex problems, arXiv: 1609.07478 (2016).Google Scholar
  35. A. Rakotomamonjy, G. Gasso, J. Salmon: Screening rules for lasso with non-convex sparse regularizers, Proc. Machine Learning Research 97 (2019) 5341–5350.Google Scholar
  36. R. T. Rockafellar: Convex Analysis, Princeton University Press, Princeton (1997).Google Scholar
  37. R. T. Rockafellar, R. Wets: Variational Analysis, Grundlehren der mathematischen Wissenschaften 317, Springer, Berlin (2009).Google Scholar
  38. S. Shalev-Shwartz. Online learning and online convex optimization, Found. Trends Machine Learning 4/2 (2012) 107–194.https://doi.org/10.1561/2200000018Google Scholar
  39. S. Shalev-Shwartz, S. Ben-David: Understanding Machine Learning: From Theory to Algorithms, Cambridge University Press, Cambridge (2014).https://doi.org/10.1017/CBO9781107298019Google Scholar
  40. A. Shibagaki, M. Karasuyama, K. Hatano, I. Takeuchi: Simultaneous safe screening of features and samples in doubly sparse modeling, Proc. Machine Learning Research 48 (2016) 1577–1586.Google Scholar
  41. N. Simon, J. Friedman, T. Hastie, R. Tibshirani: A sparse-group lasso, J. Comput. Graph. Statistics 22/2 (2013) 231–245.https://doi.org/10.1080/10618600.2012.681250Google Scholar
  42. Y. Sun, H. Jeong, J. Nutini, M. Schmidt: Are we there yet? Manifold identification of gradient-related proximal methods, Proc. Machine Learning Research 89 (2019) 1110–1119.Google Scholar
  43. R. Tibshirani: Regression shrinkage and selection via the lasso, J. R. Stat. Soc. Ser. B Stat. Method. 58/1 (1996) 267–288.https://doi.org/10.1111/j.2517-6161.1996.tb02080.xGoogle Scholar
  44. R. Tibshirani, J. Bien, J. Friedman, T. J. Hastie, N. Simon, J. Taylor, R. J. Tibshirani: Strong rules for discarding predictors in lasso-type problems, J. R. Stat. Soc. Ser. B Stat. Method. 74/2 (2012) 245–266.https://doi.org/10.1111/j.1467-9868.2011.01004.xGoogle Scholar
  45. J. Wang, J. Zhou, J. Liu, P. Wonka, J. Ye: A safe screening rule for sparse logistic regression, in: NIPS 2014, Proc. 27th Int. Conf. Neural Inform. Processing Systems 1 (2014) 1053–1061.Google Scholar
  46. Z. J. Xiang, H. Xu, P. J. Ramadge: Learning sparse representations of high dimensional data on large scale dictionaries, in: NIPS 2011 (2011) 900–908.Google Scholar
  47. M. Yuan, Y. Lin: Model selection and estimation in regression with grouped variables, J. R. Stat. Soc. Ser. B Stat. Method. 68/1 (2006).https://doi.org/10.1111/j.1467-9868.2005.00532.xGoogle Scholar

Suggested citation

E. Ndiaye, O. Fercoq, J. Salmon. “Screening Rules and its Complexity for Active Set Identification.” Journal of Convex Analysis 28 (2021), No. 4, 1053–1072. https://doi.org/10.68381/jca28061

Download BibTeXPublished by Heldermann Verlag.

Published by Heldermann Verlag, 2021. Rights now held by Banach Press LLC.