具有决策依赖分布且存在较大延迟的随机优化问题的数值方法

《Computers & Operations Research》:Numerical methods for stochastic optimization problems with decision-dependent distributions under large delays

【字体: 大 中 小 】 时间:2026年01月30日 来源:Computers & Operations Research 4.6

编辑推荐:

  邓立成|刘永超 中国大连理工大学数学科学学院,大连116024 摘要 本文旨在研究在集中式通信环境下,具有决策依赖分布的随机优化问题的性能稳定解与不动点。我们聚焦于系统中存在线性增长延迟且采用集中式通信协议的场景,提出了两种分布式异步算法。对于性能稳定解,我们设计了DASGD-

  邓立成|刘永超 中国大连理工大学数学科学学院,大连116024

摘要
本文旨在研究在集中式通信环境下,具有决策依赖分布的随机优化问题的性能稳定解与不动点。我们聚焦于系统中存在线性增长延迟且采用集中式通信协议的场景,提出了两种分布式异步算法。对于性能稳定解,我们设计了DASGD-GD算法,该算法将分布式异步随机梯度下降法与贪婪部署策略相结合。研究表明,DASGD-GD生成的迭代序列以O(k?α)的速率收敛到性能稳定解,其中α∈(0,1),这一速率取决于大延迟条件下随机优化问题的具体设置。对于不动点,我们提出了DASGD-AG算法,它将分布式异步随机梯度下降法与自适应梯度策略结合。实验表明,DASGD-AG生成的迭代序列以O(1lnk)的速率收敛到不动点。通过合成数据与真实世界数据,进一步验证了这两种算法的有效性。

引言
传统的随机优化问题通常假设数据遵循静态分布(Uryasev和Pardalos,2013;Rakhlin等人,2011)。然而,许多现实任务具有动态特性,如定价问题(Cooper等人,2006;Cheung等人,2017)、路线规划问题(Liebig等人,2017;Perdomo等人,2020)以及贷款审批问题(Inga和Sacoto-Cabrera,2023;Robinson和Sindhwani,2024),这些任务涉及可能受决策影响的 数据(Hardt等人,2016;Dong等人,2018)。这类问题可表述为具有决策依赖分布的随机优化问题,即minx∈RdEξ~D(x)?(x;ξ),其中?:Rd×Rm→R是决策向量x与随机向量ξ的平滑函数,分布映射D(?):Rd→P(Rm)将决策变量x映射到概率分布,E?表示基于分布D(x)的期望值。与传统随机优化问题不同,这类问题中决策向量与数据之间存在交互机制:决策者从数据集中抽取样本以更新决策变量,而这些样本的分布由分布映射D(x)决定。

具有决策依赖分布的随机优化问题可追溯到早期研究(Varaiya和Wets,1988;Jonsbr?ten等人,1998;Ahmed,2000;Dupacová,2006)。有兴趣的读者可参考Hellemo等人(2018)的文献,以获取关于决策依赖不确定性分类及各类模型的更全面概述。由于这类问题通常为非凸问题,Perdomo等人(2020)提出了性能稳定解的概念,即在该问题所对应的分布上求解传统随机优化问题。他们还提出了重复风险最小化与重复梯度下降两种算法来寻找性能稳定解。基于Perdomo等人(2020)的重复梯度下降方法,Mendler-Dünner等人(2020)提出了贪婪部署法与懒惰部署法。贪婪部署法每次迭代都从当前分布中独立抽取样本并进行更新;而懒惰部署法则从初始决策xk出发,利用来自分布D(xk)的多个样本进行超过1次的更新。与Mendler-Dünner等人(2020)的研究不同,Li和Wai(2022)考虑了样本会根据智能体及用户的先前状态进行调整的情况,他们提出了一种随机梯度下降算法,该算法可通过受控马尔可夫链驱动的带偏随机梯度来建模。Drusvyatskiy和Xiao(2023)证明,原本为静态问题设计的传统随机算法可直接用于寻找性能稳定解,且效率损失很小。针对最优解,Miller等人(2021)认为分布映射相对于决策变量具有全局线性结构,于是设计了两阶段算法:第一阶段通过最小二乘法估计分布映射,第二阶段则利用该估计值直接求解性能风险问题。Liu等人(2022)则针对没有全局线性结构分布映射的具有决策依赖分布的随机优化问题,开发了一种两步无导数方法,首先通过当前迭代的局部线性回归预测分布映射,再通过信赖域法寻找候选解。

为应对大规模数据集或复杂模型带来的巨大计算需求,人们开始研究具有决策依赖分布的多智能体随机优化问题(Li等人,2022;Piliouras和Yu,2023;Narang等人,2023;Deng和Liu,2025)。Li等人(2022)提出了一种结合贪婪部署的分布式随机梯度下降方法,证明该方法能以O(1k)的速率收敛到分布式具有决策依赖分布的随机优化问题的性能稳定解。Deng和Liu(2025)则将梯度追踪技术、贪婪部署策略与自适应梯度方法相结合,用于寻找分布式具有决策依赖分布的随机优化问题的性能稳定解与不动点。此外,Piliouras和Yu(2023)以及Narang等人(2023)从博弈论角度研究了具有决策依赖分布的多智能体随机优化问题。Narang等人(2023)假设每个智能体的分布映射都具有全局线性结构,他们提出将随机梯度下降法与自适应梯度方法结合,用于寻找具有决策依赖分布的博弈的纳什均衡。Piliouras和Yu(2023)则研究了略有不同的场景:他们认为对全局决策有响应的样本来自同一分布,并引入学习动力学来研究系统的动态行为,其中智能体使用强化学习算法。

在多智能体随机优化问题中,分布式同步算法需要等待最慢的智能体节点完成任务后,所有节点才能进入下一阶段,这使得整个系统容易受到单个节点故障的影响(Li等人,2013;Johnson和Zhang,2013)。为解决这一问题,分布式延迟异步算法得到了广泛研究(Lian等人,2016;Assran等人,2020;Feyzmahdavian和Johansson,2023)。当延迟有界时,人们可以根据最大延迟或平均延迟来确定算法的步长,例如Recht等人(2011)、Lian等人(2016)以及Feyzmahdavian等人(2016)研究了基于最大延迟的步长确定方法,而Agarwal和Duchi(2011)以及Glasgow和Wootters(2022)则研究了基于平均延迟的步长确定方法。当延迟呈次线性或线性增长时,则采用延迟自适应步长策略(Ren等人,2020;Zhou等人,2022;Wu等人,2022)来确保分布式异步算法的收敛性。

本文针对具有决策依赖分布的集中式多智能体随机优化问题展开研究,重点探讨了在集中式通信环境中存在次线性或线性增长延迟的场景。具体而言,我们考虑一个包含一个中心节点和n个工作节点的系统,该系统采用集中式通信协议:中心节点负责更新决策并将新决策发送给工作节点,而工作节点则计算梯度并将结果反馈给中心节点。针对大延迟情况,我们提出了DASGD-GD与DASGD-AG两种分布式异步算法,用于寻找性能稳定解与不动点。本文的贡献可总结如下:
(a) 我们提出了结合贪婪部署策略的分布式异步随机梯度下降方法DASGD-GD,用于寻找性能稳定解。该算法可在具有集中式通信协议的系统中运行,工作节点无需等待其他节点完成工作,即可根据当前迭代从分布中独立抽取样本计算梯度并发送给中心节点,这不仅减少了节点的空闲时间,提高了算法的容错能力,还显著提升了计算速度。通过选择合适的步长策略,我们证明DASGD-GD生成的迭代序列以O(k?α)的速率收敛到性能稳定解,其中α∈(0,1),这一速率取决于强凸性系数、目标函数的平滑性系数、决策依赖数据分布的敏感度参数以及延迟参数。据我们所知,DASGD-GD是首个专为寻找具有决策依赖分布的随机优化问题的性能稳定解而设计的算法。
(b) 我们提出了结合自适应梯度策略的分布式异步随机梯度下降方法DASGD-AG,用于寻找不动点,此时分布映射D(?)具有全局线性结构。该算法同样在具有集中式通信协议的系统中运行,工作节点无需等待其他节点即可独立计算梯度并发送给中心节点,中心节点则根据收到的梯度重新估计分布映射,并利用该估计值更新决策变量。通过选择合适的步长策略,我们证明DASGD-AG生成的迭代序列以O(1lnk)的速率收敛到不动点,这一速率与Wu等人(2022)研究中非凸目标函数的确定性优化问题的收敛速率相当。此外,我们还通过合成数据与真实世界数据进一步验证了DASGD-GD与DASGD-AG的有效性。

本文的其余结构如下:第2节介绍用于具有决策依赖分布的随机优化问题的DASGD-GD与DASGD-AG算法;第3节与第4节分别在标准假设条件下研究这两种算法的收敛性,其中第3节聚焦DASGD-GD,第4节聚焦DASGD-AG;第5节给出数值实验结果;第6节为结论性论述。

符号与基本定义:除非另有说明,本文中的向量均为列向量。Rd表示带有范数‖x‖=〈x,x〉的d维欧几里得空间。?0?表示全零向量,即(00…0)?∈Rd。Id∈Rd×d为单位矩阵。对于任意两个正序列{ak}和{bk},若存在正常数c使得ak≤cbk,则称ak=O(bk)。对于给定的σ-代数F,E[?|F]表示在F条件下的条件期望。τk表示第k次迭代时梯度的延迟。?f(x;x′)?表示Eξ~D(x′)?(x;ξ),而?f(x)?表示Eξ~D(x)?(x;ξ)。为明确表达,我们用??(x;ξ)表示对第一个变量x的梯度,用?ξ?(x;ξ)表示对第二个变量ξ的梯度,用?x,ξ?(x;ξ)表示对(x,ξ)二者的梯度,用?f(x)表示对x的梯度。

算法片段
DASGD-GD与DASGD-AG算法
在本节中,我们提出了DASGD-GD与DASGD-AG算法,用于在大延迟情况下寻找性能稳定解与不动点。为描述此类延迟,我们用τk表示第k次迭代时梯度的延迟。在本文中,我们考虑延迟呈次线性或线性增长的情况,即满足τk≤min{k,akb+c},其中a∈(0,1),b∈(0,1],c≥0。

首先,我们介绍专为寻找性能稳定解而设计的DASGD-GD算法……

DASGD-GD的收敛性
在本节中,我们研究DASGD-GD的收敛性。为保证该算法的收敛性,我们首先提出以下假设。
假设1:目标函数与随机梯度
假设存在μ>0,使得对于所有x,x′∈Rd,都有?(x;ξ)≥?(x′;ξ)+〈??(x′;ξ),x?x′〉+μ2‖x?x′‖2;
假设存在L>0,使得对于所有x,x′∈Rd,ξ,ξ′∈Ξ,都有‖??(x;ξ)???(x′;ξ′)‖≤L{‖x?x′‖+‖ξ?ξ′‖};
假设存在σ>0,使得对于所有x∈Rd,都有Eξ~D(x)‖??(x;ξ)??Eξ′~D(x)?(x;ξ′)‖2≤σ2。

在假设1中,条件(i)与(ii)是具有决策依赖分布的随机优化问题中常用的假设(Mendler-Dünner等人……)

DASGD-AG的收敛性
在本节中,我们研究DASGD-AG的收敛性。为保证该算法的收敛性,我们首先提出以下假设。
假设3:分布映射
存在概率测度P,使得对于所有的ξ,都有ξ~D(x)?ξ=Ax+ζ,其中ζ~P,A∈Rp×d,?μ?表示Eζ~Pζ,?Σ?表示Eζ~P[(ζ?μ)(ζ?μ)]。

假设3意味着该分布相对于决策变量是线性的。在假设3的前提下,问题(1)可转化为标准的随机优化问题,即minx∈RdEζ~P?(x;Ax+ζ),该问题等价于一个非凸问题……

数值模拟
为展示算法1与算法2的实际性能,我们在基于合成数据的高斯均值估计问题以及基于真实数据集的战略二元分类问题(Hopkins等人,1999)上进行了实验。实验环境为包含一个中心节点与25个工作节点的分布式架构。在两个实验中,我们采用了以下延迟模型:对于所有k∈N,若τk?1≤min{k,akb+c}?1,则τk=τk?1+1;否则,当b∈(0,1)时,τk从[0,min{k,?akb+c?}]中随机选取,或者τk=ak。结论方面,我们研究了SO-DD问题,并提出了两种分布式异步算法DASGD-GD和DASGD-AG,旨在在大延迟的集中式通信环境下寻找具有良好性能的稳定解以及SO-DD问题的平衡点。我们的研究结果表明,当SO-DD问题在大延迟条件下退化为确定性优化问题时,定理1和定理2中所给出的收敛速率与Wu等人(2022年)的研究结果一致。据我们所知,DASGD-GD和DASGD-AG是目前尚未有类似算法出现的。CRediT作者贡献说明:邓立成:撰写——审阅与编辑,撰写——初稿。刘永超:撰写——审阅与编辑,指导工作。致谢:本项工作得到了中国国家重点研发计划编号2023YFA1009200、国家自然科学基金编号12471283以及中国中央高校基本科研业务费项目DUT24LK001的支持。
相关新闻
生物通微信公众号
微信
新浪微博

热点排行

    今日动态 | 人才市场 | 新技术专栏 | 中国科学人 | 云展台 | BioHot | 云讲堂直播 | 会展中心 | 特价专栏 | 技术快讯 | 免费试用

    版权所有 生物通

    Copyright© eBiotrade.com, All Rights Reserved

    联系信箱:

    粤ICP备09063491号