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 条

[31] INTEGRATED MODELING AND RECONSTRUCTION WITH SPARSITY CONSTRAINTS FOR FDOT
Baritaux, Jean-Charles
Guerquin-Kern, Matthieu
Unser, Michael
2009 IEEE INTERNATIONAL SYMPOSIUM ON BIOMEDICAL IMAGING: FROM NANO TO MACRO, VOLS 1 AND 2, 2009, : 173 - 176
[32] A Box-Spline Framework for Inverse Problems With Continuous-Domain Sparsity Constraints
Pourya, Mehrsa
Boquet-Pujadas, Aleix
Unser, Michael
IEEE TRANSACTIONS ON COMPUTATIONAL IMAGING, 2024, 10 : 790 - 805
[33] Greedy Sparsity-Constrained Optimization
Bahmani, Sohail
Raj, Bhiksha
Boufounos, Petros T.
JOURNAL OF MACHINE LEARNING RESEARCH, 2013, 14 : 807 - 841
[34] An iterative thresholding-like algorithm for inverse problems with sparsity constraints in Banach space
Bredies, K.
JOURNAL OF INVERSE AND ILL-POSED PROBLEMS, 2009, 17 (01): : 19 - 26
[35] Multiclass Relevance Vector Machines: Sparsity and Accuracy
Psorakis, Ioannis
Damoulas, Theodoros
Girolami, Mark A.
IEEE TRANSACTIONS ON NEURAL NETWORKS, 2010, 21 (10): : 1588 - 1598
[36] Sparsity considerations for dependent variables
Alquier, Pierre
Doukhan, Paul
ELECTRONIC JOURNAL OF STATISTICS, 2011, 5 : 750 - 774
[37] Mirror averaging with sparsity priors
Dalalyan, Arnak S.
Tsybakov, Alexandre B.
BERNOULLI, 2012, 18 (03) : 914 - 944
[38] Preconditioning PDE-constrained optimization with L1-sparsity and control constraints
Porcelli, Margherita
Simoncini, Valeria
Stoll, Martin
COMPUTERS & MATHEMATICS WITH APPLICATIONS, 2017, 74 (05) : 1059 - 1075
[39] Sums of squares and semidefinite program relaxations for polynomial optimization problems with structured sparsity
Waki, Hayato
Kim, Sunyoung
Kojima, Masakazu
Muramatsu, Masakazu
SIAM JOURNAL ON OPTIMIZATION, 2006, 17 (01) : 218 - 242
[40] Time-frequency localization from sparsity constraints
Borgnat, Pierre
Flandrin, Patrick
2008 IEEE INTERNATIONAL CONFERENCE ON ACOUSTICS, SPEECH AND SIGNAL PROCESSING, VOLS 1-12, 2008, : 3785 - 3788

← 1 2 3 4 5 →