Performance-Complexity Tradeoffs in Greedy Weak Submodular Maximization
  with Random Sampling
  Many problems in signal processing and machine learning can be formalized as
weak submodular optimization tasks. For such problems, a simple greedy
algorithm (\textsc{Greedy}) is guaranteed to find a solution achieving the
objective with a value no worse than $1-e^{-1/c}$ of the optimal, where $c$ is
the multiplicative weak-submodularity constant. Due to the high cost of
querying large-scale systems, the complexity of \textsc{Greedy} becomes
prohibitive in contemporary 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 \textsc{Greedy}'s
performance through two metrics: (i) probability of identifying an optimal
subset, and (ii) suboptimality with respect to the optimal solution. The latter
implies that uniform sampling strategies with a fixed sampling size achieve a
non-trivial approximation factor; however, we show that with overwhelming
probability, these methods fail to find the optimal subset. Our analysis shows
that the failure of uniform sampling strategies with fixed sample size can be
circumvented by successively increasing the size of the search space. Building
upon this insight, we propose a simple progressive stochastic greedy algorithm
and study its approximation guarantees. Moreover, we demonstrate effectiveness
of the proposed method in dimensionality reduction applications and feature
selection tasks for clustering and object tracking.
