Stochastic Multi-Level Compositional Optimization Algorithms over
  Networks with Level-Independent Convergence Rate
Hongchang Gao
Stochastic multi-level compositional optimization problems cover many new
machine learning paradigms, e.g., multi-step model-agnostic meta-learning,
which require efficient optimization algorithms for large-scale applications.
This paper studies the decentralized stochastic multi-level optimization
algorithm, which is challenging because the multi-level structure and
decentralized communication scheme may make the number of levels affect the
order of the convergence rate. To this end, we develop two novel decentralized
optimization algorithms to deal with the multi-level function and its gradient.
Our theoretical results show that both algorithms can achieve the
level-independent convergence rate for nonconvex problems under much milder
conditions compared with existing single-machine algorithms. To the best of our
knowledge, this is the first work that achieves the level-independent
convergence rate under the decentralized setting. Moreover, extensive
experiments confirm the efficacy of our proposed algorithms.