# Stochastic Nested Compositional Bi-level Optimization for Robust Feature Learning

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 47 references that are in the map.
- First posted on arXiv 11 Jul 2023.

## Builds on (most cited first, 26 of 26)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Nonparametric regression using deep neural networks with ReLU activation function](https://mlsanity.com/paper/1708.06633/) (2017)
- [Approximation Methods for Bilevel Programming](https://mlsanity.com/paper/1802.02246/) (2018)
- [Bilevel Optimization: Convergence Analysis and Enhanced Design](https://mlsanity.com/paper/2010.07962/) (2020)
- [A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Critic](https://mlsanity.com/paper/2007.05170/) (2020)
- [Mini-batch Stochastic Approximation Methods for Nonconvex Stochastic Composite Optimization](https://mlsanity.com/paper/1308.6594/) (2013)
- [Provably Faster Algorithms for Bilevel Optimization](https://mlsanity.com/paper/2106.04692/) (2021)
- [A framework for bilevel optimization that enables stochastic and global variance reduction algorithms](https://mlsanity.com/paper/2201.13409/) (2022)
- [Stochastic Compositional Gradient Descent: Algorithms for Minimizing Compositions of Expected-Value Functions](https://mlsanity.com/paper/1411.3803/) (2014)
- [A Single-Timescale Method for Stochastic Bilevel Optimization](https://mlsanity.com/paper/2102.04671/) (2021)
- [Amortized Implicit Differentiation for Stochastic Bilevel Optimization](https://mlsanity.com/paper/2111.14580/) (2021)
- [A Single Time-Scale Stochastic Approximation Method for Nested Stochastic Optimization](https://mlsanity.com/paper/1812.01094/) (2018)
- [Solving Stochastic Compositional Optimization is Nearly as Easy as Solving Stochastic Optimization](https://mlsanity.com/paper/2008.10847/) (2020)
- [Biased Stochastic First-Order Methods for Conditional Stochastic Optimization and Applications in Meta Learning](https://mlsanity.com/paper/2002.10790/) (2020)
- [Accelerating Stochastic Composition Optimization](https://mlsanity.com/paper/1607.07329/) (2016)
- [Decentralized Gossip-Based Stochastic Bilevel Optimization over Communication Networks](https://mlsanity.com/paper/2206.10870/) (2022)
- [Optimal Algorithms for Stochastic Bilevel Optimization under Relaxed Smoothness Conditions](https://mlsanity.com/paper/2306.12067/) (2023)
- [Multi-Level Composite Stochastic Optimization via Nested Variance Reduction](https://mlsanity.com/paper/1908.11468/) (2019)
- [Stochastic Multi-level Composition Optimization Algorithms with Level-Independent Convergence Rates](https://mlsanity.com/paper/2008.10526/) (2020)
- [Multi-Level Stochastic Gradient Methods for Nested Composition Optimization](https://mlsanity.com/paper/1801.03600/) (2018)
- [Decentralized Bilevel Optimization](https://mlsanity.com/paper/2206.05670/) (2022)
- [Decentralized Stochastic Bilevel Optimization with Improved per-Iteration Complexity](https://mlsanity.com/paper/2210.12839/) (2022)
- [Efficiently Escaping Saddle Points in Bilevel Optimization](https://mlsanity.com/paper/2202.03684/) (2022)
- [A Stochastic Subgradient Method for Nonsmooth Nonconvex Multi-Level Composition Optimization](https://mlsanity.com/paper/2001.10669/) (2020)
- [Convergence of a Stochastic Subgradient Method with Averaging for Nonsmooth Nonconvex Constrained Optimization](https://mlsanity.com/paper/1912.07580/) (2019)
- [Distributionally Robust Learning with Weakly Convex Losses: Convergence Rates and Finite-Sample Guarantees](https://mlsanity.com/paper/2301.06619/) (2023)

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

- [Constrained Bi-Level Optimization: Proximal Lagrangian Value function Approach and Hessian-free Algorithm](https://mlsanity.com/paper/2401.16164/) (2024)

## Abstract (arXiv)

We develop and analyze stochastic approximation algorithms for solving nested compositional bi-level optimization problems. These problems involve a nested composition of T potentially non-convex smooth functions in the upper-level, and a smooth and strongly convex function in the lower-level. Our proposed algorithm does not rely on matrix inversions or mini-batches and can achieve an ε-stationary solution with an oracle complexity of approximately tildeOT(1/ε2), assuming the availability of stochastic first-order oracles for the individual functions in the composition and the lower-level, which are unbiased and have bounded moments. Here, tildeOT hides polylog factors and constants that depend on T. The key challenge we address in establishing this result relates to handling three distinct sources of bias in the stochastic gradients. The first source arises from the compositional nature of the upper-level, the second stems from the bi-level structure, and the third emerges due to the utilization of Neumann series approximations to avoid matrix inversion. To demonstrate the effectiveness of our approach, we apply it to the problem of robust feature learning for deep neural networks under covariate shift, showcasing the benefits and advantages of our methodology in that context.