A Stochastic Linearized Augmented Lagrangian Method for Decentralized Bilevel Optimization

Songtao Lu, Siliang Zeng, Xiaodong Cui, Mark S. Squillante, Lior Horesh, Brian Kingsbury, Jia Liu, Mingyi HongNeurIPS 2022 · OpenReview

TL;DR

The authors introduce SLAM (Stochastic Linearized Augmented Lagrangian Method), the first decentralized algorithm for bilevel optimization that achieves a linear speedup relative to the number of computing nodes. By utilizing a single-loop, single-timescale approach, SLAM matches the theoretical convergence complexity of standard decentralized SGD for simpler single-level problems, making it highly efficient for large-scale multi-agent learning.

The Challenge of Decentralized Bilevel Optimization

Many modern machine learning paradigms—such as Meta-Learning, Hyperparameter Optimization, and Actor-Critic Reinforcement Learning—are naturally "bilevel." In these problems, an upper-level (UL) task depends on the optimal solution of a lower-level (LL) task. For example, in reinforcement learning, an "actor" optimizes a policy based on a "critic's" value function evaluation.

As datasets and model complexities grow, it becomes necessary to distribute these tasks across a network of nodes (decentralized learning). This introduces a twofold challenge:

  1. Coupling: The UL and LL variables are mathematically intertwined, making joint optimization difficult.
  2. Consensus: In a decentralized setting without a central coordinator, nodes must communicate to agree on a shared global model.

Existing methods often require expensive "double-loop" structures—solving the LL problem to completion for every single UL update—or lack the theoretical guarantees needed to prove they scale efficiently as more nodes are added to the network.

The SLAM Approach

To overcome these bottlenecks, the authors propose SLAM, which stands out by being a single-loop, single-timescale algorithm. Instead of fully solving the LL problem at each step, SLAM performs a single linearized update for both levels simultaneously.

Key technical components include:

  • Linearized Augmented Lagrangian: The constrained consensus problem is transformed into an Augmented Lagrangian framework. The objective is then linearized to allow for simple, computationally cheap gradient-based updates.
  • Successive Dual Updates: The algorithm tracks dual variables to enforce consensus across the network for both UL and LL variables.
  • Mixing Matrices: SLAM uses communication rounds between neighbors (defined by a network graph) to spread information, integrating this directly into the update rules.
Decentralized implementation of the SLAM algorithm.

The paper also introduces two specialized variants catering to different multi-agent architectures: SLAM-L (consensus only at the lower level) and SLAM-U (consensus only at the upper level).

Key Insights and Theoretical Guarantees

  • Linear Speedup: The most significant breakthrough is that SLAM achieves a convergence rate of $\mathcal{O}(1/(n\epsilon^2))$. This means that doubling the number of nodes ($n$) theoretically cuts the required iterations to reach a specific error ($\epsilon$) in half.
  • Theoretical Parity: SLAM is the first decentralized bilevel algorithm to match this gold-standard convergence rate, putting it on par with decentralized single-level optimization (like standard decentralized SGD).
  • Single-Timescale Efficiency: Unlike many bilevel algorithms that require the LL to be updated much faster than the UL (two-timescale), SLAM allows both to move at the same pace. This simplifies hyperparameter tuning and stabilizes training.
Comparison of SLAM with prior decentralized bilevel optimization methods, highlighting its superior convergence rate.

Experimental Results

The method was evaluated on two Multi-Agent Reinforcement Learning (MARL) benchmarks:

  1. Cooperative Navigation: Agents must reach landmarks while avoiding collisions, requiring a shared understanding of the global state.
  2. Pursuit-Evasion Game: Agents on a ring graph must cooperate to capture evaders.

In numerical tests, SLAM (applied as "SLAM-AC" for Actor-Critic) converged faster and achieved higher average rewards than established benchmarks like DAC (Decentralized Actor-Critic) and MDAC (Mini-batch DAC). Furthermore, the algorithm showed strong performance across different graph topologies (e.g., Erdos-Renyi and Ring graphs), proving its versatility for various network infrastructures.

Limitations and Future Work

  • Lower-Level Convexity: The current theoretical proof relies on the LL objective being strongly convex. While common in many applications (like the "critic" in RL), extending this to non-convex LL problems remains an open challenge.
  • Communication Overhead: While SLAM is highly efficient in terms of iterations, each iteration still requires communication between neighbors. Future work could explore "communication-efficient" versions that skip rounds or use compressed gradients.
  • Hyperparameter Sensitivity: Like most Augmented Lagrangian methods, performance can be sensitive to the choice of the penalty parameter and step sizes.

Summary updated

Abstract

Bilevel optimization has been shown to be a powerful framework for formulating multi-task machine learning problems, e.g., reinforcement learning (RL) and meta-learning, where the decision variables are coupled in both levels of the minimization problems. In practice, the learning tasks would be located at different computing resource environments, and thus there is a need for deploying a decentralized training framework to implement multi-agent and multi-task learning. We develop a stochastic linearized augmented Lagrangian method (SLAM) for solving general nonconvex bilevel optimization problems over a graph, where both upper and lower optimization variables are able to achieve a consensus. We also establish that the theoretical convergence rate of the proposed SLAM to the Karush-Kuhn-Tucker (KKT) points of this class of problems is on the same order as the one achieved by the classical distributed stochastic gradient descent for only single-level nonconvex minimization problems. Numerical results tested on multi-agent RL problems showcase the superiority of SLAM compared with the benchmarks.
BibTeX
@inproceedings{lu2022stochastic,
  author = {Songtao Lu and Siliang Zeng and Xiaodong Cui and Mark S. Squillante and Lior Horesh and Brian Kingsbury and Jia Liu and Mingyi Hong},
  title = {{A Stochastic Linearized Augmented Lagrangian Method for Decentralized Bilevel Optimization}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=Liu2el6uTc},
}
Figure