INTERACT: achieving low sample and communication complexities in decentralized bilevel learning over networks

Zhuqing Liu, Xin Zhang, Prashant Khanduri, Songtao Lu, Jia Liu

Introduction

Bilevel optimization has emerged as a cornerstone for modern machine learning, providing a mathematical framework for nested decision-making. In these problems, an "outer" optimization task depends on the optimal solution of an "inner" task. This structure is essential for applications such as meta-learning, hyperparameter optimization, and reinforcement learning.

However, as data generation shifts toward the "edge"—distributed across mobile devices, sensors, and autonomous vehicles—the need for decentralized solutions has become critical. In a decentralized setting, agents must collaborate over a peer-to-peer network to solve global problems without a central coordinator. This paper introduces INTERACT, the first framework to achieve both low sample and communication complexities for decentralized bilevel optimization.

The Challenge of Decentralized Bilevel Learning

Solving bilevel problems in a decentralized environment is significantly more complex than standard single-level optimization due to three primary factors:

  1. Tight Coupling: The gradient of the outer objective (the hyper-gradient) requires knowledge of the inner problem's optimal solution. Any error in solving the inner problem propagates to the outer loop.
  2. Network Noise: In peer-to-peer networks, agents only communicate with their immediate neighbors. This leads to "consensus errors," where local models drift apart due to heterogeneous data distributions.
  3. Efficiency Bottlenecks: Achieving high precision typically requires a prohibitive number of data samples and communication rounds, which is often unfeasible for resource-constrained edge devices.

The INTERACT Framework

To address these challenges, the researchers developed two primary algorithms designed to stabilize and accelerate the learning process:

1. INTERACT

This deterministic algorithm utilizes gradient tracking to mitigate the effects of data heterogeneity. By tracking the average gradient across the entire network, INTERACT ensures that each agent moves toward the global stationary point, effectively correcting the local drift that typically plagues decentralized methods. It employs the implicit function theorem to estimate the necessary hyper-gradients for the outer problem.

2. SVR-INTERACT

For large-scale applications where computing full gradients is computationally expensive, the authors introduced a stochastic variance-reduced version. SVR-INTERACT incorporates a recursive gradient estimator (inspired by SARAH/SPIDER techniques). This allows the algorithm to maintain high accuracy while processing only small batches of data, significantly reducing the sample complexity.

Key Theoretical Insights

The paper provides rigorous theoretical guarantees that set a new benchmark for the field:

  • Optimal Complexity: INTERACT is the first decentralized bilevel algorithm to achieve a communication complexity of $O(\epsilon^{-1})$ and a sample complexity of $O(n\epsilon^{-1})$.
  • Sample Efficiency via SVR: By utilizing variance reduction, SVR-INTERACT improves the sample complexity to $O(\sqrt{n}\epsilon^{-1})$. This means that as the dataset size ($n$) grows, the algorithm becomes increasingly more efficient than traditional stochastic methods.
  • Decoupling Communication and Sampling: A major finding is that SVR-INTERACT can reduce the number of required data samples without necessitating a corresponding increase in communication rounds, a vital feature for bandwidth-limited networks.

Empirical Performance

The researchers validated the framework using meta-learning tasks on the MNIST and CIFAR-10 datasets. The experiments simulated decentralized environments using Erdős-Rényi random graphs to test the algorithms under varying network connectivity.

Results Highlights: * Convergence Speed: Both INTERACT and SVR-INTERACT converged faster and reached lower error rates compared to established baselines like Decentralized SGD (D-SGD) and Gradient-Tracking SGD (GT-SGD). * Robustness: The algorithms proved resilient to different network topologies. Whether the network was sparse or dense, the convergence rate remained steady, demonstrating the effectiveness of the gradient tracking mechanism. * Practical Variance Reduction: SVR-INTERACT consistently showed the lowest sample complexity, confirming that the theoretical gains of variance reduction translate effectively to real-world computer vision tasks.

Future Directions

While INTERACT represents a significant leap forward, the authors identify several avenues for future research:

  • Relaxing Assumptions: Current proofs assume the inner subproblem is strongly convex. Extending this to non-convex inner problems would broaden the framework's applicability to deep neural networks.
  • Privacy and Security: Integrating Differential Privacy (DP) could protect local agent data during the gradient-sharing process.
  • Communication Compression: Implementing quantization or sparsification techniques could further reduce the bandwidth requirements for edge deployment.

Conclusion

INTERACT provides a robust and efficient path for scaling bilevel learning across decentralized networks. By successfully combining gradient tracking with stochastic variance reduction, the framework offers a theoretically grounded solution to the complexities of collaborative nested optimization, paving the way for more sophisticated learning at the edge.

Summary updated

BibTeX
@inproceedings{liu2022interact,
  author = {Zhuqing Liu and Xin Zhang and Prashant Khanduri and Songtao Lu and Jia Liu},
  title = {{INTERACT: achieving low sample and communication complexities in decentralized bilevel learning over networks}},
  booktitle = {MobiHoc},
  year = {2022},
  doi = {10.1145/3492866.3549721},
}
Figure