论文标题
与决策有关的数据在线跟踪跟踪
Online Saddle Point Tracking with Decision-Dependent Data
论文作者
论文摘要
在这项工作中，我们考虑了一个随时间变化的随机鞍点问题，其中依次揭示了目标，并且数据分布取决于决策变量。这种类型的问题通过分布图表达了分布依赖性，并且已知具有两种不同类型的溶液 - 粘点和平衡点。我们证明，在适当的条件下，在线原始偶型算法能够跟踪平衡点。相比之下，由于该物镜的计算封闭形式梯度需要了解分布图的知识，因此我们提供了一种在线随机二线算法，用于跟踪平衡轨迹。我们在期望和高概率上提供界限，后者利用子韦布尔模型来解决梯度误差。我们在电动汽车充电问题上说明了结果，在该问题中，对价格的响应能力遵循位置尺度家庭的分销图。
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.
