NASH decomposes the validation utility into Shapley-informative component functions and aggregates them non-linearly to make Data Shapley-based data selection consistently effective.
Submodular meets Spectral: Greedy Algorithms for Subset Selection, Sparse Approximation and Dictionary Selection
3 Pith papers cite this work. Polarity classification is still indexing.
3
Pith papers citing it
abstract
We study the problem of selecting a subset of k random variables from a large set, in order to obtain the best linear prediction of another variable of interest. This problem can be viewed in the context of both feature selection and sparse approximation. We analyze the performance of widely used greedy heuristics, using insights from the maximization of submodular functions and spectral analysis. We introduce the submodularity ratio as a key quantity to help understand why greedy algorithms perform well even when the variables are highly correlated. Using our techniques, we obtain the strongest known approximation guarantees for this problem, both in terms of the submodularity ratio and the smallest k-sparse eigenvalue of the covariance matrix. We further demonstrate the wide applicability of our techniques by analyzing greedy algorithms for the dictionary selection problem, and significantly improve the previously known guarantees. Our theoretical analysis is complemented by experiments on real-world and synthetic data sets; the experiments show that the submodularity ratio is a stronger predictor of the performance of greedy algorithms than other spectral parameters.
citation-role summary
background 1
citation-polarity summary
verdicts
UNVERDICTED 3roles
background 1polarities
background 1representative citing papers
New data-dependent upper bounds for budgeted submodular maximization that dominate OPT and empirically tighten optimality certificates on real datasets.
PORE applies Pareto optimization with a robust evaluation function to noisy subset selection under cardinality constraints, outperforming greedy, POSS, and PONSS on real-world datasets.
citing papers explorer
-
Is Data Shapley Not Better than Random in Data Selection? Ask NASH
NASH decomposes the validation utility into Shapley-informative component functions and aggregates them non-linearly to make Data Shapley-based data selection consistently effective.
-
Data-dependent Evaluations for Budgeted Submodular Maximization
New data-dependent upper bounds for budgeted submodular maximization that dominate OPT and empirically tighten optimality certificates on real datasets.
-
Pareto Optimization with Robust Evaluation for Noisy Subset Selection
PORE applies Pareto optimization with a robust evaluation function to noisy subset selection under cardinality constraints, outperforming greedy, POSS, and PONSS on real-world datasets.