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 条

[21] SPECTRAL UNMIXING WITH SPARSITY AND STRUCTURING CONSTRAINTS
Ben Mhenni, Ramzi
Bourguignon, Sebastien
Ninin, Jordan
Schmidt, Frederic
2018 9TH WORKSHOP ON HYPERSPECTRAL IMAGE AND SIGNAL PROCESSING: EVOLUTION IN REMOTE SENSING (WHISPERS), 2018,
[22] Robust Face Recognition with Individual and Group Sparsity Constraints
Chen, Tianjiao
Qu, Lei
Wei, Sui
FOUNDATIONS OF INTELLIGENT SYSTEMS (ISKE 2013), 2014, 277 : 105 - 114
[23] Regularizers for structured sparsity
Micchelli, Charles A.
Morales, Jean M.
Pontil, Massimiliano
ADVANCES IN COMPUTATIONAL MATHEMATICS, 2013, 38 (03) : 455 - 489
[24] COLLAGE-BASED INVERSE PROBLEMS FOR IFSM WITH ENTROPY MAXIMIZATION AND SPARSITY CONSTRAINTS
Kunze, Herb
La Torre, Davide
Vrscay, Edward
IMAGE ANALYSIS & STEREOLOGY, 2013, 32 (03) : 183 - 188
[25] Adaptive Iterative Hard Thresholding for Least Absolute Deviation Problems with Sparsity Constraints
Song Li
Dekai Liu
Yi Shen
Journal of Fourier Analysis and Applications, 2023, 29
[26] A new iterative firm-thresholding algorithm for inverse problems with sparsity constraints
Voronin, Sergey
Woerdeman, Hugo J.
APPLIED AND COMPUTATIONAL HARMONIC ANALYSIS, 2013, 35 (01) : 151 - 164
[27] A Firs Order Optimization Algorithm for Statistical Learning with Hierarchical Sparsity Structure
Zhang, Dewei
Liu, Yin
Tajbakhsh, Sam Davanloo
INFORMS JOURNAL ON COMPUTING, 2022, 34 (02) : 1126 - 1140
[28] Sparsity-enforcing regularisation and ISTA revisited
Daubechies, Ingrid
Defrise, Michel
De Mol, Christine
INVERSE PROBLEMS, 2016, 32 (10)
[29] Weakly decomposable regularization penalties and structured sparsity
van de Geer, Sara
SCANDINAVIAN JOURNAL OF STATISTICS, 2014, 41 (01) : 72 - 86
[30] REGULARIZATION PROPERTIES OF TIKHONOV REGULARIZATION WITH SPARSITY CONSTRAINTS
Ramlau, Ronny
ELECTRONIC TRANSACTIONS ON NUMERICAL ANALYSIS, 2008, 30 : 54 - 74

← 1 2 3 4 5 →