Decentralized Stochastic Bilevel Optimization with Improved per-Iteration Complexity

Xuxing Chen, Minhui Huang, Shiqian Ma, Krishna Balasubramanian
Proceedings of the 40th International Conference on Machine Learning, PMLR 202:4641-4671, 2023.

Abstract

Bilevel optimization recently has received tremendous attention due to its great success in solving important machine learning problems like meta learning, reinforcement learning, and hyperparameter optimization. Extending single-agent training on bilevel problems to the decentralized setting is a natural generalization, and there has been a flurry of work studying decentralized bilevel optimization algorithms. However, it remains unknown how to design the distributed algorithm with sample complexity and convergence rate comparable to SGD for stochastic optimization, and at the same time without directly computing the exact Hessian or Jacobian matrices. In this paper we propose such an algorithm. More specifically, we propose a novel decentralized stochastic bilevel optimization (DSBO) algorithm that only requires first order stochastic oracle, Hessian-vector product and Jacobian-vector product oracle. The sample complexity of our algorithm matches the currently best known results for DSBO, while our algorithm does not require estimating the full Hessian and Jacobian matrices, thereby possessing to improved per-iteration complexity.

Cite this Paper

BibTeX
@InProceedings{pmlr-v202-chen23n, title = {Decentralized Stochastic Bilevel Optimization with Improved per-Iteration Complexity}, author = {Chen, Xuxing and Huang, Minhui and Ma, Shiqian and Balasubramanian, Krishna}, booktitle = {Proceedings of the 40th International Conference on Machine Learning}, pages = {4641--4671}, year = {2023}, editor = {Krause, Andreas and Brunskill, Emma and Cho, Kyunghyun and Engelhardt, Barbara and Sabato, Sivan and Scarlett, Jonathan}, volume = {202}, series = {Proceedings of Machine Learning Research}, month = {23--29 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v202/chen23n/chen23n.pdf}, url = {https://proceedings.mlr.press/v202/chen23n.html}, abstract = {Bilevel optimization recently has received tremendous attention due to its great success in solving important machine learning problems like meta learning, reinforcement learning, and hyperparameter optimization. Extending single-agent training on bilevel problems to the decentralized setting is a natural generalization, and there has been a flurry of work studying decentralized bilevel optimization algorithms. However, it remains unknown how to design the distributed algorithm with sample complexity and convergence rate comparable to SGD for stochastic optimization, and at the same time without directly computing the exact Hessian or Jacobian matrices. In this paper we propose such an algorithm. More specifically, we propose a novel decentralized stochastic bilevel optimization (DSBO) algorithm that only requires first order stochastic oracle, Hessian-vector product and Jacobian-vector product oracle. The sample complexity of our algorithm matches the currently best known results for DSBO, while our algorithm does not require estimating the full Hessian and Jacobian matrices, thereby possessing to improved per-iteration complexity.} }
Endnote
%0 Conference Paper %T Decentralized Stochastic Bilevel Optimization with Improved per-Iteration Complexity %A Xuxing Chen %A Minhui Huang %A Shiqian Ma %A Krishna Balasubramanian %B Proceedings of the 40th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2023 %E Andreas Krause %E Emma Brunskill %E Kyunghyun Cho %E Barbara Engelhardt %E Sivan Sabato %E Jonathan Scarlett %F pmlr-v202-chen23n %I PMLR %P 4641--4671 %U https://proceedings.mlr.press/v202/chen23n.html %V 202 %X Bilevel optimization recently has received tremendous attention due to its great success in solving important machine learning problems like meta learning, reinforcement learning, and hyperparameter optimization. Extending single-agent training on bilevel problems to the decentralized setting is a natural generalization, and there has been a flurry of work studying decentralized bilevel optimization algorithms. However, it remains unknown how to design the distributed algorithm with sample complexity and convergence rate comparable to SGD for stochastic optimization, and at the same time without directly computing the exact Hessian or Jacobian matrices. In this paper we propose such an algorithm. More specifically, we propose a novel decentralized stochastic bilevel optimization (DSBO) algorithm that only requires first order stochastic oracle, Hessian-vector product and Jacobian-vector product oracle. The sample complexity of our algorithm matches the currently best known results for DSBO, while our algorithm does not require estimating the full Hessian and Jacobian matrices, thereby possessing to improved per-iteration complexity.
APA
Chen, X., Huang, M., Ma, S. & Balasubramanian, K.. (2023). Decentralized Stochastic Bilevel Optimization with Improved per-Iteration Complexity. Proceedings of the 40th International Conference on Machine Learning, in Proceedings of Machine Learning Research 202:4641-4671 Available from https://proceedings.mlr.press/v202/chen23n.html.

Related Material