Stochastic Bilevel Distributed Optimization over a Network

Hongchang Gao, Bin Gu, My T. Thai

Bilevel optimization is a powerful framework for solving nested problems, where an upper-level objective depends on the optimal solution of a lower-level task. This structure is fundamental to many machine learning applications, including hyperparameter optimization, meta-learning, and neural architecture search. However, as data increasingly resides on decentralized networks—such as mobile devices or IoT sensors—traditional centralized bilevel algorithms face significant bottlenecks.

In their AISTATS 2023 paper, researchers Hongchang Gao, Bin Gu, and My T. Thai address these challenges by introducing two novel decentralized stochastic bilevel optimization algorithms: MDBO and VRDBO. These methods enable collaborative optimization across peer-to-peer networks without requiring a central coordinator or the exchange of massive second-order matrices.

The Decentralized Challenge

In a decentralized setting, data is distributed across nodes that can only communicate with their immediate neighbors. Bilevel optimization in this context introduces two primary difficulties:

  1. The Hypergradient Bottleneck: Computing the gradient for the upper-level problem (the hypergradient) typically requires second-order information, specifically Hessian and Jacobian matrices. In a distributed environment, communicating these large matrices is computationally and bandwidth-prohibitively expensive.
  2. Network Consensus: Nodes must reach a global consensus on the optimal parameters while only having access to local data and neighbor communications.

Proposed Methods: MDBO and VRDBO

To overcome these hurdles, the authors propose a Gradient Tracking mechanism. This allows each node to maintain a local estimate of the global gradient by syncing only model parameters and low-dimensional gradient estimators with neighbors.

  • MDBO (Momentum-based Decentralized Stochastic Bilevel Optimization): This algorithm utilizes a momentum-based approach for parameter updates, providing a robust and easy-to-implement baseline for decentralized bilevel tasks.
  • VRDBO (Variance-Reduction-based Decentralized Stochastic Bilevel Optimization): This more advanced method incorporates the STORM (Stochastic Recursive Momentum) estimator. By significantly reducing the variance inherent in stochastic gradients, VRDBO achieves faster convergence both theoretically and empirically.

A key innovation in both algorithms is that Hessian and Jacobian computations remain strictly local. Only the resulting low-dimensional vectors are shared, drastically reducing communication overhead.

Experimental Evaluation

The researchers evaluated the performance of MDBO and VRDBO on a hyperparameter optimization task for logistic regression using three standard datasets: a9a, ijcnn1, and covtype. The data was distributed i.i.d. across participants to simulate a collaborative learning environment.

Convergence and Efficiency

The experimental results demonstrate that the proposed algorithms, particularly VRDBO, significantly outperform existing decentralized baselines such as DSBO and GDSBO.

Training loss across three datasets (a9a, ijcnn1, covtype) showing the superior convergence speed of VRDBO.

As shown in the loss curves above, VRDBO (red line) converges much faster than the other methods across all tested datasets. This empirical success is backed by theoretical proofs establishing a linear speedup—the convergence rate improves proportionally as more nodes are added to the network.

Accuracy Gains

Beyond training loss, the algorithms also show superior performance in terms of validation accuracy.

Validation accuracy on the covtype dataset, illustrating the faster improvement and higher final accuracy of VRDBO.

In the covtype dataset experiments, VRDBO reaches higher accuracy levels more quickly than competing methods, confirming its effectiveness for large-scale decentralized bilevel optimization.

Key Insights and Future Directions

The study provides several critical insights:

  • Hessian-Free Communication: Global optima can be reached without sharing large second-order matrices, provided local math is synced via gradient tracking.
  • Scalability: The algorithms are well-suited for large networks, benefiting from a linear speedup as the number of workers increases.
  • Bias Management: The authors developed new theoretical strategies to bound consensus errors even when dealing with biased stochastic hypergradients.

While this work represents a major advancement, future research could address data heterogeneity (non-i.i.d. data), dynamic network topologies, and extending the analysis to non-convex lower-level problems.

Summary updated

BibTeX
@inproceedings{gao2023stochastic,
  author = {Hongchang Gao and Bin Gu and My T. Thai},
  title = {{Stochastic Bilevel Distributed Optimization over a Network}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2023},
  url = {https://openreview.net/forum?id=obzudXcnln},
}
Figure