# Technical Program

## Paper Detail

 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.