TRADING ACCURACY FOR SPARSITY IN OPTIMIZATION PROBLEMS WITH SPARSITY CONSTRAINTS

被引：89

作者：

Shalev-Shwartz, Shai ^{[1
]}

Srebro, Nathan ^{[2
]}

Zhang, Tong ^{[3
]}

机构：

[1] Hebrew Univ Jerusalem, Sch Comp Sci & Engn, Jerusalem, Israel

[2] Toyota Technol Inst, Chicago, IL 60637 USA

[3] Rutgers State Univ, Dept Stat, New Brunswick, NJ 08901 USA

来源：

SIAM JOURNAL ON OPTIMIZATION | 2010年 / 20卷 / 06期

关键词：

sparsity; linear prediction; GREEDY APPROXIMATION; CONVERGENCE; REGRESSION; SELECTION; SYSTEMS; LASSO; WOLFE;

D O I：

10.1137/090759574

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

We study the problem of minimizing the expected loss of a linear predictor while constraining its sparsity, i.e., bounding the number of features used by the predictor. While the resulting optimization problem is generally NP-hard, several approximation algorithms are considered. We analyze the performance of these algorithms, focusing on the characterization of the trade-off between accuracy and sparsity of the learned predictor in different scenarios.

引用

页码：2807 / 2832

页数：26

共 50 条

[1] Online Linear Optimization with Sparsity Constraints
Wang, Jun-Kun
Lu, Chi-Jen
Lin, Shou-De
ALGORITHMIC LEARNING THEORY, VOL 98, 2019, 98
[2] Adaptive Iterative Hard Thresholding for Least Absolute Deviation Problems with Sparsity Constraints
Li, Song
Liu, Dekai
Shen, Yi
JOURNAL OF FOURIER ANALYSIS AND APPLICATIONS, 2023, 29 (01)
[3] On Tractable Convex Relaxations of Standard Quadratic Optimization Problems under Sparsity Constraints
Bomze, Immanuel
Peng, Bo
Qiu, Yuzhou
Yildirim, E. Alper
JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS, 2025, 204 (03)
[4] Optimality conditions for group sparsity constrained optimization problems with equality and inequality constraints
Yi, Shouyu
Peng, Dingtao
Zhang, Xian
OPTIMIZATION, 2025,
[5] Sparsity Based Methods for Overparameterized Variational Problems
Giryes, R.
Elad, M.
Bruckstein, A. M.
SIAM JOURNAL ON IMAGING SCIENCES, 2015, 8 (03): : 2133 - 2159
[6] Structural properties of affine sparsity constraints
Dong, Hongbo
Ahn, Miju
Pang, Jong-Shi
MATHEMATICAL PROGRAMMING, 2019, 176 (1-2) : 95 - 135
[7] Convex and Network Flow Optimization for Structured Sparsity
Mairal, Julien
Jenatton, Rodolphe
Obozinski, Guillaume
Bach, Francis
JOURNAL OF MACHINE LEARNING RESEARCH, 2011, 12 : 2681 - 2720
[8] THE BENEFIT OF GROUP SPARSITY
Huang, Junzhou
Zhang, Tong
ANNALS OF STATISTICS, 2010, 38 (04) : 1978 - 2004
[9] AN EFFICIENT PROJECTION METHOD FOR NONLINEAR INVERSE PROBLEMS WITH SPARSITY CONSTRAINTS
Han, Deren
Jia, Zehui
Song, Yongzhong
Wang, David Z. W.
INVERSE PROBLEMS AND IMAGING, 2016, 10 (03) : 689 - 709
[10] A NEW GENERALIZED THRESHOLDING ALGORITHM FOR INVERSE PROBLEMS WITH SPARSITY CONSTRAINTS
Voronin, Sergey
Chartrand, Rick
2013 IEEE INTERNATIONAL CONFERENCE ON ACOUSTICS, SPEECH AND SIGNAL PROCESSING (ICASSP), 2013, : 1636 - 1640

← 1 2 3 4 5 →