Asynchronous Distributed Bilevel Optimization
This work addresses scalability and reliability challenges in distributed machine learning tasks like hyperparameter optimization, though it is incremental as it builds on existing bilevel optimization methods.
The paper tackles the problem of bilevel optimization in distributed settings by proposing an asynchronous algorithm to avoid communication overhead, privacy risks, and straggler issues, achieving an iteration complexity of O(1/ε²) and demonstrating effectiveness on public datasets.
Bilevel optimization plays an essential role in many machine learning tasks, ranging from hyperparameter optimization to meta-learning. Existing studies on bilevel optimization, however, focus on either centralized or synchronous distributed setting. The centralized bilevel optimization approaches require collecting massive amount of data to a single server, which inevitably incur significant communication expenses and may give rise to data privacy risks. Synchronous distributed bilevel optimization algorithms, on the other hand, often face the straggler problem and will immediately stop working if a few workers fail to respond. As a remedy, we propose Asynchronous Distributed Bilevel Optimization (ADBO) algorithm. The proposed ADBO can tackle bilevel optimization problems with both nonconvex upper-level and lower-level objective functions, and its convergence is theoretically guaranteed. Furthermore, it is revealed through theoretic analysis that the iteration complexity of ADBO to obtain the $ε$-stationary point is upper bounded by $\mathcal{O}(\frac{1}{ε^2})$. Thorough empirical studies on public datasets have been conducted to elucidate the effectiveness and efficiency of the proposed ADBO.