  Variance reduction techniques such as SPIDER/SARAH/STORM have been
extensively studied to improve the convergence rates of stochastic non-convex
optimization, which usually maintain and update a sequence of estimators for a
single function across iterations. What if we need to track multiple functional
mappings across iterations but only with access to stochastic samples of
$\mathcal{O}(1)$ functional mappings at each iteration? There is an important
application in solving an emerging family of coupled compositional optimization
problems in the form of $\sum_{i=1}^m f_i(g_i(\mathbf{w}))$, where $g_i$ is
accessible through a stochastic oracle. The key issue is to track and estimate
a sequence of $\mathbf g(\mathbf{w})=(g_1(\mathbf{w}), \ldots,
g_m(\mathbf{w}))$ across iterations, where $\mathbf g(\mathbf{w})$ has $m$
blocks and it is only allowed to probe $\mathcal{O}(1)$ blocks to attain their
stochastic values and Jacobians. To improve the complexity for solving these
problems, we propose a novel stochastic method named Multi-block-Single-probe
Variance Reduced (MSVR) estimator to track the sequence of $\mathbf
g(\mathbf{w})$. It is inspired by STORM but introduces a customized error
correction term to alleviate the noise not only in stochastic samples for the
selected blocks but also in those blocks that are not sampled. With the help of
the MSVR estimator, we develop several algorithms for solving the
aforementioned compositional problems with improved complexities across a
spectrum of settings with non-convex/convex/strongly
convex/Polyak-{\L}ojasiewicz (PL) objectives. Our results improve upon prior
ones in several aspects, including the order of sample complexities and
dependence on the strong convexity parameter. Empirical studies on multi-task
deep AUC maximization demonstrate the better performance of using the new
estimator.
