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 条

[41] Wavelet shrinkage using adaptive structured sparsity constraints
Tomassi, Diego
Milone, Diego
Nelson, James D. B.
SIGNAL PROCESSING, 2015, 106 : 73 - 87
[42] MAXIMUM LIKELIHOOD ESTIMATION UNDER PARTIAL SPARSITY CONSTRAINTS
Routtenberg, Tirza
Eldar, Yonina C.
Tong, Lang
2013 IEEE INTERNATIONAL CONFERENCE ON ACOUSTICS, SPEECH AND SIGNAL PROCESSING (ICASSP), 2013, : 6421 - 6425
[43] A stochastic convergence analysis for Tikhonov regularization with sparsity constraints
Gerth, Daniel
Ramlau, Ronny
INVERSE PROBLEMS, 2014, 30 (05)
[44] TIME VARYING LINEAR PREDICTION USING SPARSITY CONSTRAINTS
Chetupalli, Srikanth Raj
Sreenivas, T. V.
2014 IEEE INTERNATIONAL CONFERENCE ON ACOUSTICS, SPEECH AND SIGNAL PROCESSING (ICASSP), 2014,
[45] OPTIMAL CONTROL OF NONLINEAR ELLIPTIC PROBLEMS WITH SPARSITY
Ponce, Augusto C.
Wilmet, Nicolas
SIAM JOURNAL ON CONTROL AND OPTIMIZATION, 2018, 56 (04) : 2513 - 2535
[46] Estimation and Testing Under Sparsity Preface
van de Geer, Sara
ESTIMATION AND TESTING UNDER SPARSITY: ECOLE D'ETE DE PROBABILITES DE SAINT-FLOUR XLV - 2015, 2016, 2159 : VII - +
[47] On the Role of Sparsity and DAG Constraints for Learning Linear DAGs
Ng, Ignavier
Ghassami, AmirEmad
Zhang, Kun
ADVANCES IN NEURAL INFORMATION PROCESSING SYSTEMS 33, NEURIPS 2020, 2020, 33
[48] REDUCING THE SEARCH SPACE FOR HYPERPARAMETER OPTIMIZATION USING GROUP SPARSITY
Cho, Minsu
Hegde, Chinmay
2019 IEEE INTERNATIONAL CONFERENCE ON ACOUSTICS, SPEECH AND SIGNAL PROCESSING (ICASSP), 2019, : 3627 - 3631
[49] Convex ensemble learning with sparsity and diversity
Yin, Xu-Cheng
Huang, Kaizhu
Yang, Chun
Hao, Hong-Wei
INFORMATION FUSION, 2014, 20 : 49 - 59
[50] Learning with Structured Sparsity
Huang, Junzhou
Zhang, Tong
Metaxas, Dimitris
JOURNAL OF MACHINE LEARNING RESEARCH, 2011, 12 : 3371 - 3412

← 1 2 3 4 5 →