Submodular meets Spectral: Greedy Algorithms for Subset Selection, Sparse Approximation and Dictionary Selection

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.

Cited by in corpus (76)

• Near-Optimal Sensor Placement for Linear Inverse Problems
• A convex model for non-negative matrix factorization and dimensionality reduction on physical space
• Greedy Sampling of Graph Signals
• Guarantees for Greedy Maximization of Non-submodular Functions with Applications
• Coresets via Bilevel Optimization for Continual Learning and Streaming
• Maximization of Approximately Submodular Functions
• Guaranteed Non-convex Optimization: Submodular Maximization over Continuous Domains
• Good Subnetworks Provably Exist: Pruning via Greedy Forward Selection
• Curvature and Optimal Algorithms for Learning and Minimizing Submodular Functions
• Variational Information Maximization for Feature Selection
• A Survey on Recent Progress in the Theory of Evolutionary Algorithms for Discrete Optimization
• Approximate Supermodularity of Kalman Filter Sensor Selection
• Resilient Non-Submodular Maximization over Matroid Constraints
• Robust Maximization of Non-Submodular Objectives
• Deep Submodular Functions
• Submodular Optimization under Noise
• A Marketplace for Data: An Algorithmic Solution
• Evolutionary Self-Expressive Models for Subspace Clustering
• Fast Maximization of Non-Submodular, Monotonic Functions on the Integer Lattice
• Greedy permanent magnet optimization
• Stochastic Conditional Gradient++
• Actuator Placement for Optimizing Network Performance under Controllability Constraints
• Scalable Greedy Algorithms for Transfer Learning
• GRAD-MATCH: Gradient Matching based Data Subset Selection for Efficient Deep Model Training
• Diversifying Sparsity Using Variational Determinantal Point Processes
• Exploiting structure of chance constrained programs via submodularity
• Distributionally Robust Submodular Maximization
• Maximizing Submodular or Monotone Functions under Partition Matroid Constraints by Multi-objective Evolutionary Algorithms
• Batch greedy maximization of non-submodular functions: Guarantees and applications to experimental design
• Approximate Submodular Functions and Performance Guarantees
• A Fast Greedy Algorithm for Generalized Column Subset Selection
• Robust Training in High Dimensions via Block Coordinate Geometric Median Descent
• Optimal approximation for unconstrained non-submodular minimization
• Approximate Supermodularity Bounds for Experimental Design
• Non-submodular Function Maximization subject to a Matroid Constraint, with Applications
• Efficient Feature Group Sequencing for Anytime Linear Prediction
• Submodular Norms with Applications To Online Facility Location and Stochastic Probing
• Fully Dynamic Submodular Maximization over Matroids
• Forward-Selected Panel Data Approach for Program Evaluation
• Learning Some Popular Gaussian Graphical Models without Condition Number Bounds
• Submodularity on Hypergraphs: From Sets to Sequences
• Black Box Submodular Maximization: Discrete and Continuous Settings
• DeepLight: Deep Lightweight Feature Interactions for Accelerating CTR Predictions in Ad Serving
• Weakly Submodular Maximization Beyond Cardinality Constraints: Does Randomization Help Greedy?
• Resilient Monotone Submodular Function Maximization
• Network Resilience Assessment via QoS Degradation Metrics: An Algorithmic Approach
• Randomized Greedy Methods for Weak Submodular Sensor Selection with Robustness Considerations
• Stochastic Learning of Nonstationary Kernels for Natural Language Modeling
• Joint Placement and Allocation of VNF Nodes with Budget and Capacity Constraints
• Bounded Degree Approximations of Stochastic Networks
• Multi-objective Evolutionary Algorithms are Still Good: Maximizing Monotone Approximately Submodular Minus Modular Functions
• Differentiable Greedy Networks
• Fitting High-Dimensional Interaction Models with Error Control
• Sensor placement minimizing the state estimation mean square error: Performance guarantees of greedy solutions
• An efficient branch-and-bound algorithm for submodular function maximization
• Sparse recovery via Orthogonal Least-Squares under presence of Noise
• Subspace selection for projection maximization with matroid constraints
• Multi-objective Evolutionary Algorithms are Generally Good: Maximizing Monotone Submodular Functions over Sequences
• Scalable Algorithms for the Sparse Ridge Regression
• Subspace Selection via DR-Submodular Maximization on Lattices
• Subset Selection for Gaussian Markov Random Fields
• Competition analysis on the over-the-counter credit default swap market
• Sampling Requirements and Accelerated Schemes for Sparse Linear Regression with Orthogonal Least-Squares
• Submodularity in Statistics: Comparing the Success of Model Selection Methods
• On Unconstrained Quasi-Submodular Function Optimization
• Controlled Islanding via Weak Submodularity
• Randomized Algorithms for Monotone Submodular Function Maximization on the Integer Lattice
• FPT Approximation Schemes for Maximizing Submodular Functions
• Two-Sided Weak Submodularity for Matroid Constrained Optimization and Regression
• Approximate Submodularity and Its Implications in Discrete Optimization
• Submodular Meta-Learning
• Scalable Projection-Free Optimization
• Performance-Complexity Tradeoffs in Greedy Weak Submodular Maximization with Random Sampling
• Insense: Incoherent Sensor Selection for Sparse Signals
• Efficient Processing of k-regret Minimization Queries with Theoretical Guarantees
• Training Data Subset Selection for Regression with Controlled Generalization Error