Alternating Projected SGD for Equality-constrained Bilevel Optimization

Quan Xiao, Han Shen, Wotao Yin, Tianyi Chen
Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, PMLR 206:987-1023, 2023.

Abstract

Bilevel optimization, which captures the inherent nested structure of machine learning problems, is gaining popularity in many recent applications. Existing works on bilevel optimization mostly consider either the unconstrained problems or the constrained upper-level problems. In this context, this paper considers the stochastic bilevel optimization problems with equality constraints in both upper and lower levels. By leveraging the special structure of the equality constraints problem, the paper first presents an alternating projected SGD approach to tackle this problem and establishes the $\tilde{\cal O}(\epsilon^{-2})$ sample and iteration complexity that matches the state-of-the-art complexity of ALSET Chen et al. (2021) for stochastic unconstrained bilevel problems. To further save the cost of projection, the paper presents an alternating projected SGD approach with lazy projection and establishes the $\tilde{\cal O}(\epsilon^{-2}/T)$ upper-level and $\tilde{\cal O}(\epsilon^{-1.5}/T^{\frac{3}{4}})$ lower-level projection complexity of this new algorithm, where $T$ is the upper-level projection interval. Application to federated bilevel optimization has been presented to showcase the performance of our algorithms. Our results demonstrate that equality-constrained bilevel optimization with strongly-convex lower-level problems can be solved as efficiently as stochastic single-level optimization problems.

Cite this Paper

BibTeX
@InProceedings{pmlr-v206-xiao23a, title = {Alternating Projected SGD for Equality-constrained Bilevel Optimization}, author = {Xiao, Quan and Shen, Han and Yin, Wotao and Chen, Tianyi}, booktitle = {Proceedings of The 26th International Conference on Artificial Intelligence and Statistics}, pages = {987--1023}, year = {2023}, editor = {Ruiz, Francisco and Dy, Jennifer and van de Meent, Jan-Willem}, volume = {206}, series = {Proceedings of Machine Learning Research}, month = {25--27 Apr}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v206/xiao23a/xiao23a.pdf}, url = {https://proceedings.mlr.press/v206/xiao23a.html}, abstract = {Bilevel optimization, which captures the inherent nested structure of machine learning problems, is gaining popularity in many recent applications. Existing works on bilevel optimization mostly consider either the unconstrained problems or the constrained upper-level problems. In this context, this paper considers the stochastic bilevel optimization problems with equality constraints in both upper and lower levels. By leveraging the special structure of the equality constraints problem, the paper first presents an alternating projected SGD approach to tackle this problem and establishes the $\tilde{\cal O}(\epsilon^{-2})$ sample and iteration complexity that matches the state-of-the-art complexity of ALSET Chen et al. (2021) for stochastic unconstrained bilevel problems. To further save the cost of projection, the paper presents an alternating projected SGD approach with lazy projection and establishes the $\tilde{\cal O}(\epsilon^{-2}/T)$ upper-level and $\tilde{\cal O}(\epsilon^{-1.5}/T^{\frac{3}{4}})$ lower-level projection complexity of this new algorithm, where $T$ is the upper-level projection interval. Application to federated bilevel optimization has been presented to showcase the performance of our algorithms. Our results demonstrate that equality-constrained bilevel optimization with strongly-convex lower-level problems can be solved as efficiently as stochastic single-level optimization problems.} }
Endnote
%0 Conference Paper %T Alternating Projected SGD for Equality-constrained Bilevel Optimization %A Quan Xiao %A Han Shen %A Wotao Yin %A Tianyi Chen %B Proceedings of The 26th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2023 %E Francisco Ruiz %E Jennifer Dy %E Jan-Willem van de Meent %F pmlr-v206-xiao23a %I PMLR %P 987--1023 %U https://proceedings.mlr.press/v206/xiao23a.html %V 206 %X Bilevel optimization, which captures the inherent nested structure of machine learning problems, is gaining popularity in many recent applications. Existing works on bilevel optimization mostly consider either the unconstrained problems or the constrained upper-level problems. In this context, this paper considers the stochastic bilevel optimization problems with equality constraints in both upper and lower levels. By leveraging the special structure of the equality constraints problem, the paper first presents an alternating projected SGD approach to tackle this problem and establishes the $\tilde{\cal O}(\epsilon^{-2})$ sample and iteration complexity that matches the state-of-the-art complexity of ALSET Chen et al. (2021) for stochastic unconstrained bilevel problems. To further save the cost of projection, the paper presents an alternating projected SGD approach with lazy projection and establishes the $\tilde{\cal O}(\epsilon^{-2}/T)$ upper-level and $\tilde{\cal O}(\epsilon^{-1.5}/T^{\frac{3}{4}})$ lower-level projection complexity of this new algorithm, where $T$ is the upper-level projection interval. Application to federated bilevel optimization has been presented to showcase the performance of our algorithms. Our results demonstrate that equality-constrained bilevel optimization with strongly-convex lower-level problems can be solved as efficiently as stochastic single-level optimization problems.
APA
Xiao, Q., Shen, H., Yin, W. & Chen, T.. (2023). Alternating Projected SGD for Equality-constrained Bilevel Optimization. Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 206:987-1023 Available from https://proceedings.mlr.press/v206/xiao23a.html.

Related Material