Online Saddle Point Tracking with Decision-Dependent Data

Killian Reed Wood, Emiliano Dall’Anese
Proceedings of The 5th Annual Learning for Dynamics and Control Conference, PMLR 211:1416-1428, 2023.

Abstract

In this work, we consider a time-varying stochastic saddle point problem in which the objec- tive is revealed sequentially, and the data distribution depends on the decision variables. Problems of this type express the distributional dependence via a distributional map, and are known to have two distinct types of solutions—saddle points and equilibrium points. We demonstrate that, un- der suitable conditions, online primal-dual type algorithms are capable of tracking equilibrium points. In contrast, since computing closed-form gradient of the objective requires knowledge of the distributional map, we offer an online stochastic primal-dual algorithm for tracking equilibrium trajectories. We provide bounds in expectation and in high probability, with the latter leveraging a sub-Weibull model for the gradient error. We illustrate our results on an electric vehicle charging problem where responsiveness to prices follows a location-scale family based distributional map

Cite this Paper

BibTeX
@InProceedings{pmlr-v211-wood23a, title = {Online Saddle Point Tracking with Decision-Dependent Data}, author = {Wood, Killian Reed and Dall'Anese, Emiliano}, booktitle = {Proceedings of The 5th Annual Learning for Dynamics and Control Conference}, pages = {1416--1428}, year = {2023}, editor = {Matni, Nikolai and Morari, Manfred and Pappas, George J.}, volume = {211}, series = {Proceedings of Machine Learning Research}, month = {15--16 Jun}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v211/wood23a/wood23a.pdf}, url = {https://proceedings.mlr.press/v211/wood23a.html}, abstract = {In this work, we consider a time-varying stochastic saddle point problem in which the objec- tive is revealed sequentially, and the data distribution depends on the decision variables. Problems of this type express the distributional dependence via a distributional map, and are known to have two distinct types of solutions—saddle points and equilibrium points. We demonstrate that, un- der suitable conditions, online primal-dual type algorithms are capable of tracking equilibrium points. In contrast, since computing closed-form gradient of the objective requires knowledge of the distributional map, we offer an online stochastic primal-dual algorithm for tracking equilibrium trajectories. We provide bounds in expectation and in high probability, with the latter leveraging a sub-Weibull model for the gradient error. We illustrate our results on an electric vehicle charging problem where responsiveness to prices follows a location-scale family based distributional map} }
Endnote
%0 Conference Paper %T Online Saddle Point Tracking with Decision-Dependent Data %A Killian Reed Wood %A Emiliano Dall’Anese %B Proceedings of The 5th Annual Learning for Dynamics and Control Conference %C Proceedings of Machine Learning Research %D 2023 %E Nikolai Matni %E Manfred Morari %E George J. Pappas %F pmlr-v211-wood23a %I PMLR %P 1416--1428 %U https://proceedings.mlr.press/v211/wood23a.html %V 211 %X In this work, we consider a time-varying stochastic saddle point problem in which the objec- tive is revealed sequentially, and the data distribution depends on the decision variables. Problems of this type express the distributional dependence via a distributional map, and are known to have two distinct types of solutions—saddle points and equilibrium points. We demonstrate that, un- der suitable conditions, online primal-dual type algorithms are capable of tracking equilibrium points. In contrast, since computing closed-form gradient of the objective requires knowledge of the distributional map, we offer an online stochastic primal-dual algorithm for tracking equilibrium trajectories. We provide bounds in expectation and in high probability, with the latter leveraging a sub-Weibull model for the gradient error. We illustrate our results on an electric vehicle charging problem where responsiveness to prices follows a location-scale family based distributional map
APA
Wood, K.R. & Dall’Anese, E.. (2023). Online Saddle Point Tracking with Decision-Dependent Data. Proceedings of The 5th Annual Learning for Dynamics and Control Conference, in Proceedings of Machine Learning Research 211:1416-1428 Available from https://proceedings.mlr.press/v211/wood23a.html.

Related Material