带随机约束的在线凸优化算法研究

作     者：余季迟 

作者单位：中南大学 

学位级别：硕士

导师姓名：陈果

授予年度：2023年

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 081104[工学-模式识别与智能系统] 08[工学] 0835[工学-软件工程] 0811[工学-控制科学与工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主      题：在线优化 Bandit凸优化 随机约束 反馈延迟 Bregman距离 遗憾界分析 约束违背界分析 

摘      要：随着大数据的迅猛发展,如何从海量数据中挖掘重要信息的已成为一个亟待解决的难题。在线凸优化是一种具备理论保障、计算高效的通用学习范式,可为机器学习算法赋予自动更新和实时反馈的能力,从而适用于处理快速增长的大规模数据。本文旨在探究带随机约束的在线凸优化算法,以进一步提升其在处理大规模数据方面的效率和实用性。在线凸优化问题可以视为学习者与未知环境之间的连续博弈问题。每次博弈中,学习者先行动,但缺乏对未知环境的任何先验知识。因此,学习者基于历史信息制定一个出牌策略,即决策模型。未知环境随后行动,并根据学习者提供的决策模型生成损失函数和约束函数,导致产生相应的损失和约束。将T轮博弈后由算法决策的累计损失之和与事后最优决策的损失之和之间的差值称为遗憾(Regret),将约束函数在迭代T次后的累积值称为约束违背(Constraint Violations),这两者是带约束的在线凸优化中常用的性能指标。然而,传统的在线凸优化算法大多面向无约束优化问题,并且依赖完全信息梯度反馈信息。当无法直接获得函数梯度时,我们称其为Bandit信息。梯度投影算法是一种广泛使用的在线凸优化算法,但存在某些目标函数和约束集的Euclid投影难以有效计算的问题。实际中,在联邦学习等场景中,计算机在进行学习任务和通过无线链路传输时可能存在反馈延迟等问题,这些问题对在线凸优化算法和理论保障都带来了极大的挑战。本文围绕带随机约束的在线凸优化算法进行了比较系统的研究,从理论分析到数值仿真,一方面改进了已有算法的不足,另一方面提出了新的解决方案和理论保障。本文的主要研究内容包括以下两方面:第一,研究了一类带随机约束的在线凸优化问题,并针对损失函数和约束函数的梯度信息难以获取或计算复杂的静态Bandit场景,提出了基于虚拟队列的在线Bandit算法。进一步分析证明,当损失函数和约束函数在光滑凸的情况下,该算法可以达到O(T)的静态遗憾和约束违背。此外,当损失函数满足强凸性条件时,静态遗憾和约束违背可以进一步达到O(ln T),为目前已知最佳结果。最后,通过在线作业调度的数值仿真验证了Bandit算法的有效性。第二,研究了静态场景中基于反馈时延下的带随机约束的在线凸优化问题。提出了一种基于Bregman距离的镜像虚拟队列算法,以解决反馈延迟的问题。同时,在算法设计中考虑了更广泛意义下的Bregman距离来代替传统的Euclid距离。进一步分析证明,在损失函数和约束函数在光滑凸且反馈延迟为τ的情况下,该算法可以达到O((τT))的静态遗憾和约束违背,所得到的静态遗憾界和约束违背界为目前已知最好的结果。最后,通过时延场景下的在线作业调度数值仿真,分析了反馈延迟对算法性能的影响,并验证了算法的有效性。