# INTERACT: Achieving Low Sample and Communication Complexities in Decentralized Bilevel Learning over Networks

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 49 references that are in the map.
- First posted on arXiv 27 Jul 2022.

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

- [Meta-Learning with Implicit Gradients](https://mlsanity.com/paper/1909.04630/) (2019)
- [TADAM: Task dependent adaptive metric for improved few-shot learning](https://mlsanity.com/paper/1805.10123/) (2018)
- [Approximation Methods for Bilevel Programming](https://mlsanity.com/paper/1802.02246/) (2018)
- [Hyperparameter optimization with approximate gradient](https://mlsanity.com/paper/1602.02355/) (2016)
- [Bilevel Optimization: Convergence Analysis and Enhanced Design](https://mlsanity.com/paper/2010.07962/) (2020)
- [A Near-Optimal Algorithm for Stochastic Bilevel Optimization via Double-Momentum](https://mlsanity.com/paper/2102.07367/) (2021)
- [Provably Faster Algorithms for Bilevel Optimization](https://mlsanity.com/paper/2106.04692/) (2021)
- [Self-Tuning Networks: Bilevel Optimization of Hyperparameters using Structured Best-Response Functions](https://mlsanity.com/paper/1903.03088/) (2019)
- [Stochastic AUC Maximization with Deep Neural Networks](https://mlsanity.com/paper/1908.10831/) (2019)
- [Collaborative Deep Learning in Fixed Topology Networks](https://mlsanity.com/paper/1706.07880/) (2017)
- [A Single Time-Scale Stochastic Approximation Method for Nested Stochastic Optimization](https://mlsanity.com/paper/1812.01094/) (2018)
- [A Decentralized Parallel Algorithm for Training Generative Adversarial Nets](https://mlsanity.com/paper/1910.12999/) (2019)
- [Bi-level Actor-Critic for Multi-agent Coordination](https://mlsanity.com/paper/1909.03510/) (2019)
- [Stochastic Optimization of Areas Under Precision-Recall Curves with Provable Convergence](https://mlsanity.com/paper/2104.08736/) (2021)
- [Penalty Method for Inversion-Free Deep Bilevel Optimization](https://mlsanity.com/paper/1911.03432/) (2019)
- [Tighter Analysis of Alternating Stochastic Gradient Method for Stochastic Nested Problems](https://mlsanity.com/paper/2106.13781/) (2021)
- [A Decentralized Proximal Point-type Method for Saddle Point Problems](https://mlsanity.com/paper/1910.14380/) (2019)
- [Improving the Sample and Communication Complexity for Decentralized Non-Convex Optimization: A Joint Gradient Estimation and Tracking Approach](https://mlsanity.com/paper/1910.05857/) (2019)
- [BOML: A Modularized Bilevel Optimization Library in Python for Meta Learning](https://mlsanity.com/paper/2009.13357/) (2020)
- [On ℓp-hyperparameter Learning via Bilevel Nonsmooth Optimization](https://mlsanity.com/paper/1806.01520/) (2018)
- [GT-STORM: Taming Sample, Communication, and Memory Complexities in Decentralized Non-Convex Learning](https://mlsanity.com/paper/2105.01231/) (2021)

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

- [DIAMOND: Taming Sample and Communication Complexities in Decentralized Bilevel Optimization](https://mlsanity.com/paper/2212.02376/) (2022)
- [DePRL: Achieving Linear Convergence Speedup in Personalized Decentralized Learning with Shared Representations](https://mlsanity.com/paper/2312.10815/) (2023)
- [Serverless Federated AUPRC Optimization for Multi-Party Collaborative Imbalanced Data Mining](https://mlsanity.com/paper/2308.03035/) (2023)
- [A Penalty-Based Method for Communication-Efficient Decentralized Bilevel Programming](https://mlsanity.com/paper/2211.04088/) (2022)
- [Argus: Federated Non-convex Bilevel Learning over 6G Space-Air-Ground Integrated Network](https://mlsanity.com/paper/2505.09106/) (2025)
- [Nonconvex Decentralized Stochastic Bilevel Optimization under Heavy-Tailed Noise](https://mlsanity.com/paper/2509.15543/) (2025)
- [DUET: Decentralized Bilevel Optimization without Lower-Level Strong Convexity](https://mlsanity.com/paper/2606.21153/) (2026)
- [On the Communication Complexity of Decentralized Stochastic Bilevel Optimization](https://mlsanity.com/paper/2311.11342/) (2023)

## Abstract (arXiv)

In recent years, decentralized bilevel optimization problems have received increasing attention in the networking and machine learning communities thanks to their versatility in modeling decentralized learning problems over peer-to-peer networks (e.g., multi-agent meta-learning, multi-agent reinforcement learning, personalized training, and Byzantine-resilient learning). However, for decentralized bilevel optimization over peer-to-peer networks with limited computation and communication capabilities, how to achieve low sample and communication complexities are two fundamental challenges that remain under-explored so far. In this paper, we make the first attempt to investigate the class of decentralized bilevel optimization problems with nonconvex and strongly-convex structure corresponding to the outer and inner subproblems, respectively. Our main contributions in this paper are two-fold: i) We first propose a deterministic algorithm called INTERACT (inner-gradient-descent-outer-tracked-gradient) that requires the sample complexity of O(n ε-1) and communication complexity of O(ε-1) to solve the bilevel optimization problem, where n and ε > 0 are the number of samples at each agent and the desired stationarity gap, respectively. ii) To relax the need for full gradient evaluations in each iteration, we propose a stochastic variance-reduced version of INTERACT (SVR-INTERACT), which improves the sample complexity to O(√n ε-1) while achieving the same communication complexity as the deterministic algorithm. To our knowledge, this work is the first that achieves both low sample and communication complexities for solving decentralized bilevel optimization problems over networks. Our numerical experiments also corroborate our theoretical findings.