| Paper ID | MLSP-28.6 |
| Paper Title |
On the Performance-Complexity Tradeoff in Stochastic Greedy Weak Submodular Optimization |
| Authors |
Abolfazl Hashemi, Haris Vikalo, Gustavo de Veciana, University of Texas at Austin, United States |
| Session | MLSP-28: ML and Time Series |
| Location | Gather.Town |
| Session Time: | Thursday, 10 June, 14:00 - 14:45 |
| Presentation Time: | Thursday, 10 June, 14:00 - 14:45 |
| Presentation |
Poster
|
| Topic |
Machine Learning for Signal Processing: [OTH-BGDT] Big Data |
| IEEE Xplore Open Preview |
Click here to view in IEEE Xplore |
| Virtual Presentation |
Click here to watch in the Virtual Conference |
| Abstract |
Weak submodular optimization underpins many problems in signal processing and machine learning. For such problems, under a cardinality constraint, a simple greedy algorithm is guaranteed to find a solution with a value no worse than $1-e^{-\gamma}$ of the optimal. Given the high cost of queries to large-scale signal processing models, the complexity of \textsc{Greedy} becomes prohibitive in modern applications. In this work, we study the tradeoff between performance and complexity when one resorts to random sampling strategies to reduce the query complexity of \textsc{Greedy}. Specifically, we quantify the effect of uniform sampling strategies on the performance through two criteria: (i) the probability of identifying an optimal subset, and (ii) the suboptimality of the solution’s value with respect to the optimal. Building upon this insight, we propose a simple progressive stochastic greedy algorithm, study its approximation guarantees, and consider its applications to dimensionality reduction and feature selection tasks. |
