中文

Operations Research Transactions >

2026 , Vol. 30 >Issue 2: 24 - 44

DOI: https://doi.org/10.15960/j.cnki.issn.1007-6093.2026.02.002

Fast algorithm for OWL1 norm constrained regression model

  • MEN Yanchao ,
  • LI Xudong
Expand
  • School of Data Science, Fudan University, Shanghai 200433, China

Received date: 2023-03-15

  Online published: 2026-06-12

Fold

Abstract

As machine learning algorithms continue to evolve and incorporate more features, effective variable selection has become a critical issue. To control the false discovery rate of regression coefficients in the variable selection, Bogdan et al. proposed the SLOPE model in 2015, which considers a linear regression model regularized by the OWL1 norm. In this paper, we consider a new regression model that uses an OWL1 norm constraint, enabling more flexible control of the false discovery rate through two parameters, $\lambda$ and $\tau$. We designed a fast algorithm that efficiently solves this model by using the dual semismooth Newton based proximal point algorithm (PPDNA). The algorithm's outer layer uses the proximal point algorithm, while the inner layer employs the semismooth Newton method to solve the subproblems efficiently. Meanwhile, the special structure of the generalized Jacobian induced by the projector onto the OWL1 norm ball is exploited to efficiently handle the corresponding Newton linear systems in the inner algorithm. Finally, we demonstrate the effectiveness and robustness of PPDNA by comparing it with two popular algorithms using both simulated data and large-scale real datasets.

Key words： OWL1 norm; semismooth Newton method; proximal point method

Cite this article

MEN Yanchao , LI Xudong . Fast algorithm for OWL1 norm constrained regression model[J]. Operations Research Transactions, 2026 , 30(2) : 24 -44 . DOI: 10.15960/j.cnki.issn.1007-6093.2026.02.002

References

[1] Bogdan M, Ewout V D B, Sabatti C, et al. SLOPE-adaptive variable selection via convex optimization [J]. The Annals of Applied Statistics, 2015, 9(3): 1103-1140.
[2] Zeng X, Figueiredo M A T. The ordered weighted l1norm: Atomic formulation, projections, and algorithms [EB/OL]. [2023-03-10]. arXiv: 1409.4271.
[3] Kruskal J B. Nonmetric multidimensional scaling: A numerical method [J]. Psychometrika, 1964, 29: 115-129.
[4] Barlow R E, Bartholomew D J, Bremner J M, et al. Statistical inference under order restrictions: The theory and application of isotonic regression [J]. International Statistical Review, 1973, 41(3).
[5] Best M J , Chakravarti N. Active set algorithms for isotonic regression, A unifying framework [J]. Mathematical Programming, 1990, 47(1-3): 425-439.
[6] Nesterov Y. A method of solving a convex programming problem with convergence rate O(1/k2) [J]. Doklady Akademii nauk SSSR, 1983, 269(3): 543-547.
[7] Beck A, Teboulle M. A fast iterative shrinkage-thresholding algorithm for linear inverse problems [J]. SIAM Journal on Imaging Sciences, 2009, 2(1): 183-202.
[8] Li X D, Sun D F, Toh K C. A highly eficient semismooth Newton augmented Lagrangian method for solving Lasso problems [J]. SIAM Journal on Optimization, 2018, 28: 433-458.
[9] Li X D, Sun D F, Toh K C. On efficiently solving the subproblems of a level-set method for fused Lasso problems [J]. SIAM Journal on Optimization, 2018, 28: 1842-1866.
[10] Luo Z Y, Sun D F, Toh K C, et al. Solving the OSCAR and SLOPE models using a semismooth Newton-based augmented Lagrangian method [J]. Journal of Machine Learning Research, 2019, 20: 1-25.
[11] Li X D, Sun D F, Toh K C. On the efficient computation of a generalized Jacobian of the projector over the Birkhoff polytope [J]. Mathematical Programming, 2020, 179: 419-446.
[12] Davis D. An O(n log(n)) algorithm for projecting onto the ordered weighted l1norm ball [EB/OL]. [2023-02-11]. arXiv:1505.00870.
[13] Li Q Z, Li X D. Fast projection onto the ordered weighted l1 norm ball [J]. Science China Mathematics, 2022, 65: 869-886.
[14] Liu Y J, Xu J J, Lin L Y. An easily implementable algorithm for efficient projection onto the ordered weighted l1norm ball [J]. Journal of the Operations Research Society of China, 2023, 11: 925-940.
[15] Lin M X, Liu Y J, Sun D F, et al. Efficient sparse semismooth Newton methods for the clustered Lasso problem [J]. SIAM Journal on Optimization, 2019, 29(3): 2026-2052.
[16] Zhang Y J, Zhang N, Sun D F, et al. A proximal point dual Newton algorithm for solving group graphical Lasso problems [J]. SIAM Journal on Optimization, 2020, 30: 2197-2220.
[17] Zhang N, Zhang Y J, Sun D F, et al. An efficient linearly convergent regularized proximal point algorithm for fused multiple graphical Lasso problems [J]. SIAM Journal on Mathematics of Data Science, 2021, 3: 524-543.
[18] She Y Y. Sparse regression with exact clustering [J]. Electronic Journal of Statistics, 2010, 4: 1055-1096.
[19] Petry S, Flexeder C, Tutz G. Pairwise Fused Lasso [R]. Munich: University of Munich, 2011.
[20] Danaher P, Wang P, Witten D M. The joint graphical Lasso for inverse covariance estimation across multiple classes [J]. Journal of the Royal Statistical Society Series B: Statistical Methodology, 2014, 76: 373-397.
[21] Ahmed A, Xing E P. Recovering time-varying networks of dependencies in social and biological studies [J]. Proceedings of the National Academy of Sciences, 2009, 106(29): 11878-11883.
[22] Yang S, Lu Z, Shen X, et al. Fused multiple graphical Lasso [J]. SIAM Journal on Optimization, 2015, 25(2): 916-943.
[23] Rockafellar R T. Monotone operators and the proximal point algorithm [J]. SIAM Journal on Control and Optimization, 1976, 14: 877-898.
[24] 郦旭东. 复合凸优化的快速邻近点算法[J]. 计算数学, 2020, 42(4): 385-404.
[25] Rockafellar R T. Convex Analysis [M]. Princeton: Princeton University Press, 1970.
[26] Pang J S. Newton’s method for B-differentiable equations [J]. Mathematics of Operations Research, 1990, 15(2): 311-341.
[27] Pang J S, Ralph D. Piecewise smoothness, local invertibility, and parametric analysis of normal maps [J]. Mathematics of Operations Research, 1996, 21: 401-426.
[28] Han J, Sun D. Newton and quasi-Newton methods for normal maps with polyhedral sets [J]. Journal of Optimization Theory and Applications, 1997, 94: 659-676.
[29] Facchinei F, Pang J S. Finite-Dimensional Variational Inequalities and Complementarity Problems [M]. New York: Springer, 2003.
[30] Pang J S, Qi L. A globally convergent Newton method for convex SC1 minimization problems [J]. Journal of Optimization Theory and Applications, 1995, 85(3): 633-648.
[31] Rockafellar R T, Wets R J B. Variational Analysis [M]. New York: Springer, 2009.
[32] Luque F J. Asymptotic convergence analysis of the proximal point algorithm [J]. SIAM Journal on Control and Optimization, 1984, 22: 277-293.
[33] Robinson S M. An implicit-function theorem for generalized variational inequalities [R]. Madison: University of Wisconsin-Madison, 1976.
[34] Sun J. On Monotropic piecewise quadratic programming [D]. Seattle: University of Washington, 1986.
[35] Robinson S M. Some continuity properties of polyhedral multifunctions [M]//König H, Korte B, Ritter K. (eds.) Mathematical Programming Studies, Heidelberg: Springer, 1981, 14: 206- 204.
[36] Zhao X Y, Sun D F, Toh K C. A Newton-CG augmented Lagrangian method for semidefinite programming [J]. SIAM Journal on Optimization, 2010, 20(4): 1737-1765.
[37] Golub G H, Loan C F V. Matrix Computations [M]. Baltimore: Johns Hopkins University Press, 1996.
[38] Gabay D, Mercier B. A dual algorithm for the solution of nonlinear variational problems via finite element approximation [J]. Computers & Mathematics with Applications, 1976, 2(1): 17-40.
[39] Glowinski R, Marroco A. Sur l’approximation, par éléments finis d’ordre un, et la résolution, par pénalisation-dualité d’une classe de problèmes de Dirichlet non linéaires [J]. Revue fra?caise d’automatique, informatique, recherche opérationnelle. Analyse numérique, 1975, 9: 41-76.
[40] Chen L, Sun D F, Toh K C. An efficient inexact symmetric Gauss-Seidel based majorized ADMM for high-dimensional convex composite conic programming [J]. Mathematical Programming, 2017, 161(1-2): 237-270.
[41] Fazel M, Pong T K, Sun D, et al. Hankel matrix rank minimization with applications to system identification and realization [J]. SIAM Journal on Matrix Analysis and Applications, 2013, 34(3): 946-977.
[42] Huang L, Jia J, Yu B, et al. Predicting execution time of computer programs using sparse polynomial regression [C]//Proceedings of the 33th International Conference on Neural Information Processing Systems, 2010: 881-891.
[43] Benjamini Y, Hochberg Y. Controlling the false discovery rate: A practical and powerful approach to multiple testing [J]. Journal of the Royal Statistical Society Series B: Statistical Methodology, 1995, 57(1): 289-300.
Options
Outlines

/

〈 〉