# Variance Reduced methods for Non-convex Composition Optimization

arXiv: https://arxiv.org/abs/1711.04416 · HTML: https://mlsanity.com/paper/1711.04416/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Nov 2017.

## Built on by (most cited first, 5 of 5)

- [Optimal Algorithms for Stochastic Multi-Level Compositional Optimization](https://mlsanity.com/paper/2202.07530/) (2022)
- [Projection-Free Algorithm for Stochastic Bi-level Optimization](https://mlsanity.com/paper/2110.11721/) (2021)
- [Streamlining in the Riemannian Realm: Efficient Riemannian Optimization with Loopless Variance Reduction](https://mlsanity.com/paper/2403.06677/) (2024)
- [Global Nash Equilibrium in Non-convex Multi-player Game: Theory and Algorithms](https://mlsanity.com/paper/2301.08015/) (2023)
- [Digital Over-the-Air Federated Learning in Multi-Antenna Systems](https://mlsanity.com/paper/2302.14648/) (2023)

## Abstract (arXiv)

This paper explores the non-convex composition optimization in the form including inner and outer finite-sum functions with a large number of component functions. This problem arises in some important applications such as nonlinear embedding and reinforcement learning. Although existing approaches such as stochastic gradient descent (SGD) and stochastic variance reduced gradient (SVRG) descent can be applied to solve this problem, their query complexity tends to be high, especially when the number of inner component functions is large. In this paper, we apply the variance-reduced technique to derive two variance reduced algorithms that significantly improve the query complexity if the number of inner component functions is large. To the best of our knowledge, this is the first work that establishes the query complexity analysis for non-convex stochastic composition. Experiments validate the proposed algorithms and theoretical analysis.