  In this paper, we investigate the problem of stochastic multi-level
compositional optimization, where the objective function is a composition of
multiple smooth but possibly non-convex functions. Existing methods for solving
this problem either suffer from sub-optimal sample complexities or need a huge
batch size. To address these limitations, we propose a Stochastic Multi-level
Variance Reduction method (SMVR), which achieves the optimal sample complexity
of $\mathcal{O}\left(1 / \epsilon^{3}\right)$ to find an $\epsilon$-stationary
point for non-convex objectives. Furthermore, when the objective function
satisfies the convexity or Polyak-{\L}ojasiewicz (PL) condition, we propose a
stage-wise variant of SMVR and improve the sample complexity to
$\mathcal{O}\left(1 / \epsilon^{2}\right)$ for convex functions or
$\mathcal{O}\left(1 /\left(\mu\epsilon\right)\right)$ for non-convex functions
satisfying the $\mu$-PL condition. The latter result implies the same
complexity for $\mu$-strongly convex functions. To make use of adaptive
learning rates, we also develop Adaptive SMVR, which achieves the same
complexities but converges faster in practice. All our complexities match the
lower bounds not only in terms of $\epsilon$ but also in terms of $\mu$ (for PL
or strongly convex functions), without using a large batch size in each
iteration.
