IDEAS home Printed from https://ideas.repec.org/a/spr/coopap/v86y2023i2d10.1007_s10589-023-00506-y.html
   My bibliography  Save this article

Sparse optimization via vector k-norm and DC programming with an application to feature selection for support vector machines

Author

Listed:
  • Manlio Gaudioso

    (Università della Calabria)

  • Giovanni Giallombardo

    (Università della Calabria)

  • Giovanna Miglionico

    (Università della Calabria)

Abstract

Sparse optimization is about finding minimizers of functions characterized by a number of nonzero components as small as possible, such paradigm being of great practical relevance in Machine Learning, particularly in classification approaches based on support vector machines. By exploiting some properties of the k-norm of a vector, namely, of the sum of its k largest absolute-value components, we formulate a sparse optimization problem as a mixed-integer nonlinear program, whose continuous relaxation is equivalent to the unconstrained minimization of a difference-of-convex function. The approach is applied to Feature Selection in the support vector machine framework, and tested on a set of benchmark instances. Numerical comparisons against both the standard $$\ell _1$$ ℓ 1 -based support vector machine and a simple version of the Slope method are presented, that demonstrate the effectiveness of our approach in achieving high sparsity level of the solutions without impairing test-correctness.

Suggested Citation

  • Manlio Gaudioso & Giovanni Giallombardo & Giovanna Miglionico, 2023. "Sparse optimization via vector k-norm and DC programming with an application to feature selection for support vector machines," Computational Optimization and Applications, Springer, vol. 86(2), pages 745-766, November.
    • Handle: RePEc:spr:coopap:v:86:y:2023:i:2:d:10.1007_s10589-023-00506-y
    DOI: 10.1007/s10589-023-00506-y
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10589-023-00506-y
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10589-023-00506-y?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Toshiki Sato & Yuichi Takano & Ryuhei Miyashiro & Akiko Yoshise, 2016. "Feature subset selection for logistic regression via mixed integer optimization," Computational Optimization and Applications, Springer, vol. 64(3), pages 865-880, July.
    2. Fan J. & Li R., 2001. "Variable Selection via Nonconcave Penalized Likelihood and its Oracle Properties," Journal of the American Statistical Association, American Statistical Association, vol. 96, pages 1348-1360, December.
    3. F. Rinaldi & F. Schoen & M. Sciandrone, 2010. "Concave programming for minimizing the zero-norm over polyhedral sets," Computational Optimization and Applications, Springer, vol. 46(3), pages 467-486, July.
    4. Bertolazzi, P. & Felici, G. & Festa, P. & Fiscon, G. & Weitschek, E., 2016. "Integer programming models for feature selection: New extensions and a randomized solution algorithm," European Journal of Operational Research, Elsevier, vol. 250(2), pages 389-399.
    5. Le An & Pham Tao, 2005. "The DC (Difference of Convex Functions) Programming and DCA Revisited with DC Models of Real World Nonconvex Optimization Problems," Annals of Operations Research, Springer, vol. 133(1), pages 23-46, January.
    6. Manlio Gaudioso & Giovanni Giallombardo & Giovanna Miglionico & Adil M. Bagirov, 2018. "Minimizing nonsmooth DC functions via successive DC piecewise-affine approximations," Journal of Global Optimization, Springer, vol. 71(1), pages 37-55, May.
    7. Kaisa Joki & Adil M. Bagirov & Napsu Karmitsa & Marko M. Mäkelä, 2017. "A proximal bundle method for nonsmooth DC optimization utilizing nonconvex cutting planes," Journal of Global Optimization, Springer, vol. 68(3), pages 501-535, July.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Pietro D’Alessandro & Manlio Gaudioso & Giovanni Giallombardo & Giovanna Miglionico, 2024. "The Descent–Ascent Algorithm for DC Programming," INFORMS Journal on Computing, INFORMS, vol. 36(2), pages 657-671, March.
    2. Le Thi, H.A. & Pham Dinh, T. & Le, H.M. & Vo, X.T., 2015. "DC approximation approaches for sparse optimization," European Journal of Operational Research, Elsevier, vol. 244(1), pages 26-46.
    3. Welington Oliveira, 2020. "Sequential Difference-of-Convex Programming," Journal of Optimization Theory and Applications, Springer, vol. 186(3), pages 936-959, September.
    4. A. M. Bagirov & N. Hoseini Monjezi & S. Taheri, 2021. "An augmented subgradient method for minimizing nonsmooth DC functions," Computational Optimization and Applications, Springer, vol. 80(2), pages 411-438, November.
    5. Hoai An Le Thi & Vinh Thanh Ho & Tao Pham Dinh, 2019. "A unified DC programming framework and efficient DCA based approaches for large scale batch reinforcement learning," Journal of Global Optimization, Springer, vol. 73(2), pages 279-310, February.
    6. Min Tao & Jiang-Ning Li, 2023. "Error Bound and Isocost Imply Linear Convergence of DCA-Based Algorithms to D-Stationarity," Journal of Optimization Theory and Applications, Springer, vol. 197(1), pages 205-232, April.
    7. Bai, Jushan & Liao, Yuan, 2016. "Efficient estimation of approximate factor models via penalized maximum likelihood," Journal of Econometrics, Elsevier, vol. 191(1), pages 1-18.
    8. Manlio Gaudioso & Giovanni Giallombardo & Giovanna Miglionico, 2020. "Essentials of numerical nonsmooth optimization," 4OR, Springer, vol. 18(1), pages 1-47, March.
    9. Welington Oliveira, 2019. "Proximal bundle methods for nonsmooth DC programming," Journal of Global Optimization, Springer, vol. 75(2), pages 523-563, October.
    10. Jeon, Jong-June & Kwon, Sunghoon & Choi, Hosik, 2017. "Homogeneity detection for the high-dimensional generalized linear model," Computational Statistics & Data Analysis, Elsevier, vol. 114(C), pages 61-74.
    11. Hoai An Le Thi & Manh Cuong Nguyen, 2017. "DCA based algorithms for feature selection in multi-class support vector machine," Annals of Operations Research, Springer, vol. 249(1), pages 273-300, February.
    12. Xiang Zhang & Yichao Wu & Lan Wang & Runze Li, 2016. "Variable selection for support vector machines in moderately high dimensions," Journal of the Royal Statistical Society Series B, Royal Statistical Society, vol. 78(1), pages 53-76, January.
    13. Jun Sun & Wentao Qu, 2022. "DCA for Sparse Quadratic Kernel-Free Least Squares Semi-Supervised Support Vector Machine," Mathematics, MDPI, vol. 10(15), pages 1-17, August.
    14. M. V. Dolgopolik, 2020. "New global optimality conditions for nonsmooth DC optimization problems," Journal of Global Optimization, Springer, vol. 76(1), pages 25-55, January.
    15. Najmeh Hoseini Monjezi & S. Nobakhtian, 2021. "A filter proximal bundle method for nonsmooth nonconvex constrained optimization," Journal of Global Optimization, Springer, vol. 79(1), pages 1-37, January.
    16. Ye He & Ling Zhou & Yingcun Xia & Huazhen Lin, 2023. "Center‐augmented ℓ2‐type regularization for subgroup learning," Biometrics, The International Biometric Society, vol. 79(3), pages 2157-2170, September.
    17. Weirong Li & Wensheng Zhu, 2024. "Subgroup analysis with concave pairwise fusion penalty for ordinal response," Statistical Papers, Springer, vol. 65(6), pages 3327-3355, August.
    18. Dongdong Zhang & Shaohua Pan & Shujun Bi & Defeng Sun, 2023. "Zero-norm regularized problems: equivalent surrogates, proximal MM method and statistical error bound," Computational Optimization and Applications, Springer, vol. 86(2), pages 627-667, November.
    19. Manlio Gaudioso & Giovanni Giallombardo & Giovanna Miglionico, 2022. "Essentials of numerical nonsmooth optimization," Annals of Operations Research, Springer, vol. 314(1), pages 213-253, July.
    20. Enrico Civitelli & Matteo Lapucci & Fabio Schoen & Alessio Sortino, 2021. "An effective procedure for feature subset selection in logistic regression based on information criteria," Computational Optimization and Applications, Springer, vol. 80(1), pages 1-32, September.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:coopap:v:86:y:2023:i:2:d:10.1007_s10589-023-00506-y. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.