Online Saddle Point Tracking with Decision-Dependent Data
Online Saddle Point Tracking with Decision-Dependent Data
复制标题
DOI：
10.48550/arxiv.2212.02693
复制
发表时间：
2022-12
期刊：
影响因子：
--
通讯作者：
Killian Wood;E. Dall’Anese
中科院分区：
文献类型：
--
作者：
Killian Wood;E. Dall’Anese
在这项工作中，我们考虑了一个时变随机鞍点问题，其中的目标是顺序显示，数据分布依赖于决策变量。这种类型的问题通过分布映射表达分布依赖，并且已知有两种不同类型的解-鞍点和平衡点。我们证明，在适当的条件下，在线原始-对偶型算法能够跟踪平衡点。相比之下，由于计算封闭形式的梯度的目标需要知识的分布图，我们提供了一个在线的随机原始对偶算法跟踪平衡轨迹。我们提供了预期和高概率的界限，后者利用子威布尔模型的梯度误差。我们说明了我们的电动汽车充电问题的结果，价格的响应遵循一个位置规模的家庭为基础的分布图。
In this work, we consider a time-varying stochastic saddle point problem in which the objective 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, under 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.