Cardinality-constrained structured data-fitting problems

Fan, Zhenan; Fang, Huang; Friedlander, Michael P.

Open Journal of Mathematical Optimization, Tome 5 (2024), article no. 2, 21 p.

A memory-efficient solution framework is proposed for the cardinality-constrained structured data-fitting problem. Dual-based atom-identification rules reveal the structure of the optimal primal solution from near-optimal dual solutions, which allows for a simple and computationally efficient algorithm that translates any feasible dual solution into a primal solution satisfying the cardinality constraint. Rigorous guarantees bound the quality of a near-optimal primal solution given any dual-based method that generates dual iterates converging to an optimal dual solution. Numerical experiments on real-world datasets support the analysis and demonstrate the efficiency of the proposed approach.

Keywords: convex analysis, sparse optimization, low-rank optimization, primal-retrieval

[1] Allen-Zhu, Zeyuan; Hazan, Elad; Hu, Wei; Li, Yuanzhi Linear convergence of a frank-wolfe type algorithm over trace-norm balls, NIPS’17: Proceedings of the 31st International Conference on Neural Information Processing Systems, Curran Associates Inc., 2017, pp. 6191-6200

[2] Annergren, Mariette ADMM for ${\ell }_1$ Regularized Optimization Problems and Applications Oriented Input Design for MPC, 2012 (licentiate thesis, Stockholm, Sweden)

[3] Aravkin, Aleksandr Y.; Burke, James V.; Drusvyatskiy, Dmitry; Friedlander, Michael P.; MacPhee, Kellie J. Foundations of gauge and perspective duality, SIAM J. Optim., Volume 28 (2018) no. 3, pp. 2406-2434 | Zbl | DOI | MR

[4] Aravkin, Aleksandr Y.; Burke, James V.; Drusvyatskiy, Dmitry; Friedlander, Michael P.; Roy, Scott Level-set methods for convex optimization, Math. Program., Volume 174 (2018) no. 1-2, pp. 359-390 | DOI | MR | Zbl

[5] Argyriou, Andreas; Evgeniou, Theodoros; Pontil, Massimiliano Convex multi-task feature learning, Mach. Learn., Volume 73 (2008) no. 3, pp. 243-272 | DOI | Zbl

[6] Atamtūrk, Alper; Gómez, Andrés Safe screening rules for ${\ell }_0$-regression, Proceedings of International Conference on Machine Learning, 2020 (https://arxiv.org/abs/2004.08773)

[7] Bao, Runxue; Gu, Bin; Huang, Heng Fast oscar and owl with safe screening rules, Proceedings of International Conference on Machine Learning, 2020 (https://arxiv.org/abs/2006.16433)

[8] Beck, Amir; Teboulle, Marc A fast iterative shrinkage-thresholding algorithm for linear inverse problems, SIAM J. Imaging Sci., Volume 2 (2009) no. 1, pp. 183-202 | DOI | MR | Zbl

[9] van den Berg, Ewout; Friedlander, Michael P. Probing the Pareto frontier for basis pursuit solutions, SIAM J. Sci. Comput., Volume 31 (2008) no. 2, pp. 890-912 | DOI | MR | Zbl

[10] van den Berg, Ewout; Friedlander, Michael P. Sparse optimization with least-squares constraints, SIAM J. Optim., Volume 21 (2011) no. 4, pp. 1201-1229 | DOI | MR | Zbl

[11] van den Berg, Ewout; Friedlander, Michael P.; Hennenfent, Gilles; Herrmann, Felix J.; Saab, Rayan; Yilmaz, Özgür Algorithm 890: Sparco: A testing framework for sparse reconstruction, ACM Trans. Math. Softw., Volume 35 (2008) no. 4, 29, 16 pages | DOI

[12] Bezanson, Jeff; Edelman, Alan; Karpinski, Stefan; Shah, Viral B. Julia: A fresh approach to numerical computing, SIAM Rev., Volume 59 (2017) no. 1, pp. 65-98 | Zbl | DOI | MR

[13] Bonnefoy, Antoine; Emiya, Valentin; Ralaivola, Liva; Gribonval, Rémi Dynamic screening: Accelerating first-order algorithms for the lasso and group-lasso, IEEE Trans. Signal Process., Volume 63 (2015) no. 19, pp. 5121-5132 | DOI | MR | Zbl

[14] Burke, James V.; Moré, Jorge J. On the identification of active constraints, SIAM J. Numer. Anal., Volume 25 (1988) no. 5, pp. 1197-1211 | DOI | MR | Zbl

[15] Candès, Emmanuel J.; Eldar, Yonina C.; Strohmer, Thomas; Voroninski, Vladislav Phase retrieval via matrix completion, SIAM J. Imaging Sci., Volume 6 (2013) no. 1, pp. 199-225 | Zbl | DOI | MR

[16] Candès, Emmanuel J.; Li, Xiaodong; Ma, Yi; Wright, John Robust principal component analysis?, J. Assoc. Comput. Mach., Volume 58 (2011) no. 3, 11, 37 pages | Zbl | MR

[17] Candès, Emmanuel J.; Plan, Yaniv Matrix Completion With Noise, Proc. IEEE, Volume 98 (2010) no. 6, pp. 925-936 | DOI

[18] Candès, Emmanuel J.; Recht, Benjamin Exact matrix completion via convex optimization, Commun. ACM, Volume 55 (2012) no. 6, pp. 111-119 | DOI

[19] Candès, Emmanuel J.; Romberg, Justin K.; Tao, Terence Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information, IEEE Trans. Inf. Theory, Volume 52 (2006) no. 2, pp. 489-509 | DOI | MR | Zbl

[20] Candès, Emmanuel J.; Strohmer, Thomas; Voroninski, Vladislav Phaselift: Exact and stable signal recovery from magnitude measurements via convex programming, Commun. Pure Appl. Math., Volume 66 (2013) no. 8, pp. 1241-1274 | DOI | MR | Zbl

[21] Chandrasekaran, Venkat; Recht, Benjamin; Parrilo, Pablo A.; Willsky, Alan S. The convex geometry of linear inverse problems, Found. Comput. Math., Volume 12 (2012) no. 6, pp. 805-849 | MR | DOI | Zbl

[22] Chen, Scott Shaobing; Donoho, David L.; Saunders, Michael A. Atomic decomposition by basis pursuit, SIAM J. Sci. Comput., Volume 20 (1998) no. 1, pp. 33-61 | DOI | MR

[23] Ding, Lijun; Yurtsever, Alp; Cevher, Volkan; Tropp, Joel A.; Udell, Madeleine An optimal-storage approach to semidefinite programming using approximate complementarity, SIAM J. Optim., Volume 31 (2021) no. 4, pp. 2695-2725 | Zbl | DOI | MR

[24] Donoho, David L. Compressed sensing, IEEE Trans. Inf. Theory, Volume 52 (2006) no. 4, pp. 1289-1306 | DOI | Zbl | MR

[25] Donoho, David L. For most large underdetermined systems of linear equations the minimal ${\ell }_1$-norm near-solution approximates the sparsest near-solution, 2006 (technical report, Department of Statistics, Stanford University, Stanford)

[26] El Ghaoui, Laurent; Viallon, Vivian; Rabbani, Tarek Safe feature elimination in sparse supervised learning, Pac. J. Optim., Volume 8 (2012) no. 4, pp. 667-698 | MR | Zbl

[27] Fan, Zhenan; Jeong, Halyun; Joshi, Babhru; Friedlander, Michael P. Polar Deconvolution of Mixed Signals, IEEE Trans. Signal Process., Volume 70 (2022), pp. 2713-2727 | MR

[28] Fan, Zhenan; Jeong, Halyun; Sun, Yifan; Friedlander, Michael P. Atomic decomposition via polar alignment: The geometry of structured optimization, Found. Trends Optim., Volume 3 (2020) no. 4, pp. 280-366

[29] Fan, Zhenan; Sun, Yifan; Friedlander, Michael P. Bundle methods for dual atomic pursuit, Asilomar Conference on Signals, Systems, and Computers (ACSSC 2019), IEEE, 2019, pp. 264-270

[30] Fazel, M.; Goodman, J. Approximations for partially coherent optical imaging systems, 1998 (technical report)

[31] Frank, Marguerite; Wolfe, Philip An algorithm for quadratic programming, Nav. Res. Logist., Volume 3 (1956) no. 1-2, pp. 95-110 | DOI | MR

[32] Friedlander, Michael P.; Macêdo, Ives Low-rank spectral optimization via gauge duality, SIAM J. Sci. Comput., Volume 38 (2016) no. 3, p. A1616-A1638 | Zbl | DOI | MR

[33] Friedlander, Michael P.; Tseng, Paul Exact regularization of convex programs, SIAM J. Optim., Volume 18 (2007) no. 4, pp. 1326-1350 | DOI | MR | Zbl

[34] Georghiades, Athinodoros S.; Belhumeur, Peter N.; Kriegman, David J. From few to many: Illumination cone models for face recognition under variable lighting and pose, IEEE Trans. Pattern Anal. Mach. Intell., Volume 23 (2001) no. 6, pp. 643-660 | DOI

[35] Hare, Warren L. Identifying active manifolds in regularization problems, Fixed-Point Algorithms for Inverse Problems in Science and Engineering (Springer Optimization and Its Applications), Volume 49, Springer, 2011, pp. 261-271 | Zbl | DOI | MR

[36] Hare, Warren L.; Lewis, Adrian S. Identifying active constraints via partial smoothness and prox-regularity, J. Convex Anal., Volume 11 (2004) no. 2, pp. 251-266 | MR | Zbl

[37] Helmberg, Christoph; Rendl, Franz A spectral bundle method for semidefinite programming, SIAM J. Optim., Volume 10 (2000) no. 3, pp. 673-696 | DOI | MR | Zbl

[38] Hiriart-Urruty, Jean-Baptiste; Lemaréchal, Claude Fundamentals of Convex Analysis, Grundlehren. Text Editions, Springer, 2001 | Zbl | DOI

[39] Hong, Bin; Zhang, Weizhong; Liu, Wei; Ye, Jieping; Cai, Deng; He, Xiaofei; Wang, Jie Scaling up sparse support vector machines by simultaneous feature and sample reduction, ICML’17: Proceedings of the 34th International Conference on Machine Learning, JMLR, 2017, pp. 4016-4025

[40] Hsieh, Cho-Jui; Olsen, Peder A. Nuclear norm minimization via active subspace selection, ICML’14: Proceedings of the 31st International Conference on International Conference on Machine Learning, JMLR, 2014, pp. 575-583

[41] Jaggi, Martin Revisiting Frank–Wolfe: Projection-free sparse convex optimization, ICML’13: Proceedings of the 30th International Conference on International Conference on Machine Learning, JMLR, 2013, pp. 427-435

[42] Kakade, Sham; Shalev-Shwartz, Shai; Tewari, Ambuj On the duality of strong convexity and strong smoothness: Learning applications and matrix regularization (2009) (unpublished manuscript, https://home.ttic.edu/~shai/papers/KakadeShalevTewari09.pdf)

[43] Koh, Kwangmoo; Kim, Seung-Jean; Boyd, Stephen P. A method for large-scale ${\ell }_1$-regularized logistic regression, AAAI’07: Proceedings of the 22nd national conference on Artificial intelligence, AAAI Press, 2007

[44] Krislock, Nathan; Wolkowicz, Henry Explicit sensor network localization using semidefinite representations and facial reductions, SIAM J. Optim., Volume 20 (2010) no. 5, pp. 2679-2708 | DOI | MR | Zbl

[45] Kuang, Zhaobin; Geng, Sinong; Page, David A screening rule for ${\ell }_1$-regularized Ising model estimation, Adv. Neural Inf. Process. Syst., Volume 30 (2017), pp. 720-731 (NIPS 2017)

[46] Lin, Zhouchen; Liu, Risheng; Su, Zhixun Linearized alternating direction method with adaptive penalty for low rank representation, NIPS’11: Proceedings of the 24th International Conference on Neural Information Processing Systems, Curran Associates Inc., 2011, pp. 612-620

[47] Liu, Jun; Zhao, Zheng; Wang, Jie; Ye, Jieping Safe screening with variational inequalities and its application to lasso, ICML’14: Proceedings of the 31st International Conference on International Conference on Machine Learning, JMLR, 2014, pp. 289-297

[48] Mazumder, Rahul; Hastie, Trevor; Tibshirani, Robert Spectral regularization algorithms for learning large incomplete matrices, J. Mach. Learn. Res., Volume 11 (2010), pp. 2287-2322 | MR | Zbl

[49] Meinshausen, Nicolai; Bühlmann, Peter High dimensional graphs and variable selection with the lasso, Ann. Stat., Volume 34 (2006) no. 3, pp. 1436-1462 | DOI | MR | Zbl

[50] Ndiaye, Eugène; Fercoq, Olivier; Gramfort, Alexandre; Salmon, Joseph Gap safe screening rules for sparse-group lasso, NIPS’16: Proceedings of the 30th International Conference on Neural Information Processing Systems, Curran Associates Inc., 2016, pp. 388-396

[51] Ndiaye, Eugène; Fercoq, Olivier; Gramfort, Alexandre; Salmon, Joseph Gap safe screening rules for sparsity enforcing penalties, J. Mach. Learn. Res., Volume 18 (2017), 128, 33 pages | Zbl | MR

[52] Nutini, Julie; Schmidt, Mark; Hare, Warren L. “active-set complexity” of proximal gradient: How long does it take to find the sparsity pattern?, Optim. Lett., Volume 13 (2019) no. 4, pp. 645-655 | DOI | MR | Zbl

[53] Oustry, François A second-order bundle method to minimize the maximum eigenvalue function, Math. Program., Volume 89 (2000) no. 1, pp. 1-33 | DOI | MR | Zbl

[54] Raj, Anant; Olbrich, Jakob; Gärtner, Bernd; Schölkopf, Bernhard; Jaggi, Martin Screening rules for convex problems (2015) | arXiv

[55] Rennie, Jasson D. M.; Srebro, Nathan Fast maximum margin matrix factorization for collaborative prediction, ICML’05: Proceedings of the 22nd international conference on Machine learning, ACM Press, 2005, pp. 713-719 | DOI

[56] Rockafellar, R. Tyrrell Convex Analysis, Princeton Mathematical Series, 28, Princeton University Press, 1970 | DOI

[57] Tibshirani, Robert Regression shrinkage and selection via the lasso, J. R. Stat. Soc., Ser. B, Stat. Methodol., Volume 58 (1996) no. 1, pp. 267-288 | Zbl | MR

[58] Tropp, Joel A. Convex recovery of a structured signal from independent random linear measurements, Sampling Theory, a Renaissance (Applied and Numerical Harmonic Analysis), Birkhäuser/Springer, 2015, pp. 67-101 | DOI | Zbl

[59] Wang, Jie; Zhou, Jiayu; Liu, Jun; Wonka, Peter; Ye, Jieping A safe screening rule for sparse logistic regression, NIPS’14: Proceedings of the 27th International Conference on Neural Information Processing Systems, MIT Press, 2014, pp. 1053-1061

[60] Wang, Jie; Zhou, Jiayu; Wonka, Peter; Ye, Jieping Lasso screening rules via dual polytope projection, NIPS’13: Proceedings of the 26th International Conference on Neural Information Processing Systems, Curran Associates Inc., 2013, pp. 1070-1078

[61] Xiang, Zhen James; Wang, Yun; Ramadge, Peter J. Screening tests for lasso problems, IEEE Trans. Pattern Anal. Mach. Intell., Volume 39 (2017) no. 5, pp. 1008-1027 | DOI

[62] Yuan, Ming; Lin, Yi Model selection and estimation in regression with grouped variables, J. R. Stat. Soc., Ser. B, Stat. Methodol., Volume 68 (2006) no. 1, pp. 49-67 | DOI | MR | Zbl

[63] Yuan, Xiao-Tong; Li, Ping; Zhang, Tong Gradient hard thresholding pursuit, J. Mach. Learn. Res., Volume 18 (2018), 166, 43 pages | Zbl | MR