通过联合梯度下降实现多目标在线凸优化

《European Journal of Operational Research》:Multi-objective online convex optimization via joint gradient descent

【字体: 大 中 小 】 时间:2026年09月18日 来源:European Journal of Operational Research 7.0

编辑推荐:

   本文基于ε-非支配性提出了一种新型的多目标遗憾度量; 针对多目标在线凸优化问题,提出了一种联合梯度下降算法; 所提出的算法可证明地实现了次线性多目标遗憾; 实验结果表明所提出的算法具有优越的性能。 引言 许多现实世界的决策问题涉及多个且往往相互冲突的性能标准,这些标准需要同

  

本文基于ε-非支配性提出了一种新型的多目标遗憾度量;
针对多目标在线凸优化问题,提出了一种联合梯度下降算法;
所提出的算法可证明地实现了次线性多目标遗憾;
实验结果表明所提出的算法具有优越的性能。

引言
许多现实世界的决策问题涉及多个且往往相互冲突的性能标准,这些标准需要同时优化。经典的多目标优化(MOO)理论通过刻画高效解集来解决此类问题,这些解集在目标空间中的像构成帕累托前沿(Ehrgott等,2025,Sharma和Kumar,2022)。虽然这一框架非常适合静态和离线场景,但在动态和顺序环境中却显得力不从心,因为在动态和顺序环境中,决策必须反复做出,而无法预知未来的结果(Grillo等,2025,Liang等,2022)。

近年来,在线凸优化(OCO)作为一种在不确定性下进行顺序决策的基本范式应运而生,通过遗憾分析提供性能保证(Hazan,2022,Huang等,2025)。更具体地说,OCO可以被视为学习者与对手之间的一场重复博弈(Hazan,2022)。在第t轮中,学习者基于过去的观察信息(可能包括之前的决策以及先前观察到的损失或梯度/次梯度)从凸集X?R?中做出决策x?。随后,对手揭示一个凸损失函数f?(x?),该函数事先未知且可能随时间变化。学习者的目标是最小化遗憾,遗憾定义为目标时间范围T内学习者的累积损失与事后最优比较者累积损失之差(Hazan,2022),即:

遗憾_T({x?}_{t=1}^T) = Σ_{t=1}^T f?(x?) ? min_{x∈X} Σ_{t=1}^T f?(x)

其中x* = argmin_{x∈X} Σ_{t=1}^T f?(x)为比较者。遗憾(1)意味着:如果算法的遗憾随时间以次线性速度增长,则其平均性能损失在无穷时间范围T上趋于零。已有各种OCO算法被提出以最小化遗憾(Hazan等,2007,Wang等,2020,Zhang等,2019,Zinkevich,2003),这些算法为在线决策提供了理论保证。

上述对手揭示标量值损失的OCO被称为单目标OCO(SO-OCO)。将OCO扩展到多目标场景,便得到了多目标在线凸优化(MO-OCO)(Jiang等,2023),其中每个决策都会使对手施加一个向量值损失。然而,与SO-OCO不同,MO-OCO由于其多目标特性,不存在标准的优化性概念或唯一的离线基准(Ehrgott,2005,Ehrgott等,2025),因为在多个目标之间的权衡是不可避免的。因此,定义一种能够忠实反映多目标性能的适当遗憾度量,构成了MO-OCO中的核心挑战。现有的MO-OCO方法通常依赖标量化技术(Cesa-Bianchi等,2022,Liu等,2024,Lyu等,2019,Mahdavi等,2013),将问题转化为一系列单目标更新。最常见的标量化方法是将多个目标线性组合(Achddou等,2024,Busa-Fekete等,2017,Cesa-Bianchi等,2022,Liu等,2024)。此外,还研究了基于ε-约束(Mahdavi等,2013)和参考点技术的方法(Lyu等,2019,Lyu等,2024)。尽管这些方法在算法上较为简便,但其理论保证和经验表现高度依赖于标量化参数的选择。更重要的是,由此产生的遗憾概念通常与特定的标量化方案绑定,使其难以进行几何解释,也难以在不同方法之间进行比较。

此外,已有少数工作从多目标角度研究了MO-OCO问题。Blackwell(1956)和Mannor等(2014)认为学习者的目标是使平均向量损失函数收敛到一个预先已知的封闭目标集。然而,对于MO-OCO问题,目标集是一组(弱)非支配点,这事先是未知的。Tiedemann等(2015)引入了MO-OCO算法竞争性分析的框架。Savary和Wiecek(2023)为MO-OCO问题提出了一种基于集合的遗憾度量,用于评估多序列在线决策的整体性能。Turgay等(2018)为多目标上下文老虎机问题提出了一种称为帕累托次优间隙(PSG)的度量。Jiang等(2023)将PSG推广到MO-OCO问题,并定义了序列式帕累托次优间隙(S-PSG)作为MO-OCO的多目标遗憾。S-PSG衡量的是决策序列的累积损失与事后多目标优化问题的帕累托前沿之间的差异。然而,与经典静态遗憾不同,后者在单目标情况下可能取负值,S-PSG始终为非负值。表1从决策结构、性能度量和离线基准三个方面,将本文工作与代表性的MO-OCO表述进行了对比。

在本文中,我们从以遗憾为中心的角度研究MO-OCO。我们提出了一种基于ε-非支配性的多目标遗憾,将学习者的累积性能解释为使累积损失向量达到离线弱非支配集所需的均匀平移。这一表征在单目标情况下自然恢复了经典遗憾的概念,并在帕累托最优性与在线遗憾分析之间建立了合理的联系。我们进一步证明,这种多目标遗憾具有一个等价的极小化极大形式,揭示了涉及决策变量和标量化变量的潜在鞍点结构。基于这一表征,我们开发了一种高效的一阶算法,称为在线联合梯度下降(OJGD)。在标准凸性假设下,所提出的方法实现了次线性多目标遗憾。在凸学习任务和多项任务基准上的实证结果进一步证明了OJGD的实际有效性。

本文的主要贡献总结如下:
• 我们提出了一种基于ε-非支配性的多目标遗憾,并推导了多目标在线凸优化的等价极小化极大形式;
• 基于所提遗憾的等价形式,我们开发了在线联合梯度下降(OJGD)算法,并证明了次线性多目标遗憾保证;
• 我们在多个基准任务上对OJGD进行了实证评估,证明其与现有MO-OCO方法相比具有优越或具有竞争力的性能。

本文其余部分安排如下:第2节介绍凸多目标优化的一些必要知识。第3节提出了一种基于ε-非支配性的多目标遗憾,并分析了其性质。第4节提出了OJGD算法,并提供了算法收敛性的理论保证。第5节给出了实验结果。最后,在第6节中我们得出了一些结论。

小节内容

预备知识与凸多目标优化
全文中向量均为以粗体表示的列向量。对于向量x∈R?,我们用x?表示向量x的第i个分量。我们用x?y表示两个向量x和y的内积。我们用‖x‖表示标准欧几里得范数,即‖x‖=√(x?x)。对于p∈N,我们用[p]表示集合{1,2,…,p}。我们用e∈R?表示一个所有分量均为1的向量。此外,e?表示第i个分量为1、其余为0的向量。我们用Π?(y)表示点y在集合X上的欧几里得投影。

多目标在线遗憾
在本节中,我们首先将SO-OCO扩展到多目标场景。然后,我们引入一种具有几何和优化学解释的多目标遗憾度量。

与SO-OCO框架类似,MO-OCO可以描述为学习者与对手之间的博弈过程:在每一轮t∈[T]中,学习者需要基于已观察到的历史信息对未来未知数据做出决策x?∈X。随后,对手揭示一个向量损失函数F?:X→R?,学习者根据此函数接收对应的向量损失F?(x?)。

在线联合梯度下降算法
在本节中,基于多目标遗憾的等价极小化极大表示(5),我们提出了一种在线联合梯度下降(OJGD)算法,并建立了累积多目标遗憾的理论界。

实验结果
为了全面评估所提出的多目标在线凸优化算法的性能,本节从三个递进维度组织了实验:理论收敛性、架构泛化性和工业适用性。我们首先在两个合成的多目标在线监督学习任务上进行凸优化实验,以严格验证理想凸损失曲面下的数学收敛性。随后,我们进行

结论
在本文中,我们通过遗憾最小化的视角研究了多目标在线凸优化。我们提出了一种基于ε-非支配性的多目标遗憾。该遗憾度量的是学习者累积损失向量到事后弱非支配集的均匀平移。利用凸对偶性,我们进一步推导了该遗憾的等价极小化极大形式,揭示了其潜在的鞍点结构,并为遗憾分析和算法设计提供了基础。

CRediT作者贡献声明
郭杰源:撰写——原稿,可视化,软件,方法论,形式分析,概念化。
邵利真:撰写——审阅与编辑,监督,资金获取。
赵方圆:撰写——审阅与编辑,形式分析。

利益冲突声明
作者声明,他们不存在可能影响本文所报告工作的已知的竞争性经济利益或个人关系。

致谢
本工作部分由国家自然科学基金(编号:12071025)资助。

郭杰源 | 邵利真 | 赵方圆
相关新闻
生物通微信公众号
微信
新浪微博

热点排行

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

    版权所有 生物通

    Copyright© eBiotrade.com, All Rights Reserved

    联系信箱:

    粤ICP备09063491号