北大中文核心期刊
中国科学引文数据库（CSCD）来源期刊
中国科技核心期刊
入选数学领域高质量科技期刊
Scopus
EBSCO 

运筹学学报 >

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

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

OWL1范数约束回归模型的快速算法

  • 门彦超 ,
  • 郦旭东
展开
  • 复旦大学大数据学院, 上海 200433

收稿日期: 2023-03-15

  网络出版日期: 2026-06-12

基金资助

国家自然科学基金 (Nos. 12271107, 62141407), 上海市科学技术委员会基础研究重点项目 (No. 21JC1400600)

收起

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

摘要

随着机器学习技术的发展,模型中的特征数量不断增加,如何进行有效的变量筛选成为一个非常重要的课题。为控制回归系数的错误发生率,Bogdan等(2015)提出在回归模型中加入OWL1范数正则项的SLOPE模型进行变量选择。与前者不同,本文考虑OWL1范数约束回归模型。该模型与SLOPE模型相似,采用多重假设检验的视角进行变量选择,并通过两个参数的调节,更灵活地控制检验的错误发现率。在算法方面,本文基于对偶半光滑牛顿的邻近点算法(PPDNA)快速求解了OWL1范数约束回归模型。该算法外层使用邻近点算法而内层利用半光滑牛顿法高效求解子问题。同时,本文利用了OWL1范数球投影算子广义Jacobian的特殊结构来加速内层算法中的牛顿线性系统的求解。最后,通过在模拟数据及大规模真实数据集上与两种流行算法进行对比,本文验证了新算法的稳健性与有效性。

关键词： OWL1范数; 半光滑牛顿算法; 邻近点算法

本文引用格式

门彦超 , 郦旭东 . OWL1范数约束回归模型的快速算法[J]. 运筹学学报, 2026 , 30(2) : 24 -44 . DOI: 10.15960/j.cnki.issn.1007-6093.2026.02.002

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

参考文献

[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
文章导航

/

〈 〉