Timezone: »

 
Spotlight
Optimal Algorithms for Stochastic Multi-Level Compositional Optimization
Wei Jiang · Bokun Wang · Yibo Wang · Lijun Zhang · Tianbao Yang

Wed Jul 20 08:05 AM -- 08:10 AM (PDT) @ Room 327 - 329
in OPT: First Order »
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 this limitation, 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-Ł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 /(\mu\epsilon)\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 optimal 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.
Keywords: OPT: Non-Convex · OPT: Optimization and Learning under Uncertainty · OPT: Stochastic · T: Optimization

Author Information

Wei Jiang (Nanjing University)
Bokun Wang (The University of Iowa)
Yibo Wang (Nanjing University)
Lijun Zhang (Nanjing University)
Tianbao Yang (The University of Iowa)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors