Complexity of Single Loop Algorithms for Nonlinear Programming with Stochastic Objective and Constraints

Ahmet Alacaoglu, Stephen J Wright
Proceedings of The 27th International Conference on Artificial Intelligence and Statistics, PMLR 238:4627-4635, 2024.

Abstract

We analyze the sample complexity of single-loop quadratic penalty and augmented Lagrangian algorithms for solving nonconvex optimization problems with functional equality constraints. We consider three cases, in all of which the objective is stochastic, that is, an expectation over an unknown distribution that is accessed by sampling. The nature of the equality constraints differs among the three cases: deterministic and linear in the first case, deterministic and nonlinear in the second case, and stochastic and nonlinear in the third case. Variance reduction techniques are used to improve the complexity. To find a point that satisfies $\varepsilon$-approximate first-order conditions, we require $\widetilde{O}(\varepsilon^{-3})$ complexity in the first case, $\widetilde{O}(\varepsilon^{-4})$ in the second case, and $\widetilde{O}(\varepsilon^{-5})$ in the third case. For the first and third cases, they are the first algorithms of “single loop” type that also use $O(1)$ samples at each iteration and still achieve the best-known complexity guarantees.

Cite this Paper

BibTeX
@InProceedings{pmlr-v238-alacaoglu24a, title = {Complexity of Single Loop Algorithms for Nonlinear Programming with Stochastic Objective and Constraints}, author = {Alacaoglu, Ahmet and J Wright, Stephen}, booktitle = {Proceedings of The 27th International Conference on Artificial Intelligence and Statistics}, pages = {4627--4635}, year = {2024}, editor = {Dasgupta, Sanjoy and Mandt, Stephan and Li, Yingzhen}, volume = {238}, series = {Proceedings of Machine Learning Research}, month = {02--04 May}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v238/alacaoglu24a/alacaoglu24a.pdf}, url = {https://proceedings.mlr.press/v238/alacaoglu24a.html}, abstract = {We analyze the sample complexity of single-loop quadratic penalty and augmented Lagrangian algorithms for solving nonconvex optimization problems with functional equality constraints. We consider three cases, in all of which the objective is stochastic, that is, an expectation over an unknown distribution that is accessed by sampling. The nature of the equality constraints differs among the three cases: deterministic and linear in the first case, deterministic and nonlinear in the second case, and stochastic and nonlinear in the third case. Variance reduction techniques are used to improve the complexity. To find a point that satisfies $\varepsilon$-approximate first-order conditions, we require $\widetilde{O}(\varepsilon^{-3})$ complexity in the first case, $\widetilde{O}(\varepsilon^{-4})$ in the second case, and $\widetilde{O}(\varepsilon^{-5})$ in the third case. For the first and third cases, they are the first algorithms of “single loop” type that also use $O(1)$ samples at each iteration and still achieve the best-known complexity guarantees.} }
Endnote
%0 Conference Paper %T Complexity of Single Loop Algorithms for Nonlinear Programming with Stochastic Objective and Constraints %A Ahmet Alacaoglu %A Stephen J Wright %B Proceedings of The 27th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2024 %E Sanjoy Dasgupta %E Stephan Mandt %E Yingzhen Li %F pmlr-v238-alacaoglu24a %I PMLR %P 4627--4635 %U https://proceedings.mlr.press/v238/alacaoglu24a.html %V 238 %X We analyze the sample complexity of single-loop quadratic penalty and augmented Lagrangian algorithms for solving nonconvex optimization problems with functional equality constraints. We consider three cases, in all of which the objective is stochastic, that is, an expectation over an unknown distribution that is accessed by sampling. The nature of the equality constraints differs among the three cases: deterministic and linear in the first case, deterministic and nonlinear in the second case, and stochastic and nonlinear in the third case. Variance reduction techniques are used to improve the complexity. To find a point that satisfies $\varepsilon$-approximate first-order conditions, we require $\widetilde{O}(\varepsilon^{-3})$ complexity in the first case, $\widetilde{O}(\varepsilon^{-4})$ in the second case, and $\widetilde{O}(\varepsilon^{-5})$ in the third case. For the first and third cases, they are the first algorithms of “single loop” type that also use $O(1)$ samples at each iteration and still achieve the best-known complexity guarantees.
APA
Alacaoglu, A. & J Wright, S.. (2024). Complexity of Single Loop Algorithms for Nonlinear Programming with Stochastic Objective and Constraints. Proceedings of The 27th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 238:4627-4635 Available from https://proceedings.mlr.press/v238/alacaoglu24a.html.

Related Material