A Communication-Efficient Algorithm for Federated Multilevel Stochastic Compositional Optimization

Recent literature shows a growing interest in the integration of federated learning (FL) and multilevel stochastic compositional optimization (MSCO), which arises in meta-learning and reinforcement learning. It is known that a bottleneck in FL is communication efficiency, when compared to non-distributed methods. Yet, it remains unclear whether communication-efficient algorithms exist for MSCO in distributed settings. Single-loop optimizations, used in recent methods, structurally require communications per fixed samples generated, resulting in communication complexity being no less than sample complexity, hence lower bounded by <inline-formula><tex-math notation="LaTeX">$\mathcal{O}(1/\epsilon)$</tex-math></inline-formula>, for reaching an <inline-formula><tex-math notation="LaTeX">$\epsilon$</tex-math></inline-formula>-accurate solution. This paper studies distributed MSCO of a smooth and strongly convex objective with smooth gradients. Based on a double-loop strategy, we proposed Federated Stochastic Compositional Gradient Extrapolation (F<sc>ed</sc>SCGE), a federated MSCO method that attains an optimal <inline-formula><tex-math notation="LaTeX">$\mathcal{O}(\log\frac{1}{\epsilon})$</tex-math></inline-formula> communication complexity while maintaining an (almost) optimal <inline-formula><tex-math notation="LaTeX">$\tilde{\mathcal{O}}(1/\epsilon)$</tex-math></inline-formula> sample complexity, both of which independent of client number, making the approach scalable. Our analysis leverages the random gradient extrapolation method (RGEM) in <xref ref-type="bibr" rid="ref19">[19]</xref> and generalizes it by overcoming the biased gradients of MSCO. To the best of our knowledge, our work is the first to show the simultaneous attainability of both complexity bounds for distributed MSCO.