论文标题
随机鞍点问题与决策分布
Stochastic Saddle Point Problems with Decision-Dependent Distributions
论文作者
论文摘要
本文着重于与决策依赖性分布的随机鞍点问题。这些问题是其目标是随机收益函数的期望值，并且其数据分布在响应决策变量的响应中漂移 - 这种现象由分布图代表。适应分配转移的一种常见方法是一旦揭示了新的分布或重复进行重复进行重复决定。我们介绍了平衡点的概念，这是这种重复的重复进行程序的固定点，并为它们的存在和独特性提供了足够的条件。为了找到平衡点，我们开发了确定性和随机原始偶对算法，并在后者中以前的和多项式衰减的步进时间表中证明了它们的收敛性，并在后者中进行了恒定的阶跃尺寸。通过建模从随机梯度估计器作为亚韦布尔随机变量出现的误差，我们提供了预期的误差界限，并且在每种迭代中都具有很高的可能性。如果没有其他对分布图的了解，则计算鞍点是棘手的。因此，我们提出了分布图的条件（我们称之为相反的混合物优势），以确保该目标是强烈的convex-rong-concave。最后，我们证明具有单个功能评估的无衍生算法能够近似鞍点
This paper focuses on stochastic saddle point problems with decision-dependent distributions. These are problems whose objective is the expected value of a stochastic payoff function and whose data distribution drifts in response to decision variables--a phenomenon represented by a distributional map. A common approach to accommodating distributional shift is to retrain optimal decisions once a new distribution is revealed, or repeated retraining. We introduce the notion of equilibrium points, which are the fixed points of this repeated retraining procedure, and provide sufficient conditions for their existence and uniqueness. To find equilibrium points, we develop deterministic and stochastic primal-dual algorithms and demonstrate their convergence with constant step-size in the former and polynomial decay step-size schedule in the latter. By modeling errors emerging from a stochastic gradient estimator as sub-Weibull random variables, we provide error bounds in expectation and in high probability that hold for each iteration. Without additional knowledge of the distributional map, computing saddle points is intractable. Thus we propose a condition on the distributional map--which we call opposing mixture dominance--that ensures that the objective is strongly-convex-strongly-concave. Finally, we demonstrate that derivative-free algorithms with a single function evaluation are capable of approximating saddle points
