基于单点残余反馈的分布式在线带式非凸优化
该论文提出了当对手可以适应在线算法的动作时,标准遗憾定义变得不再有效, 定义了替代的政策遗憾概念,用于测量在线算法在适应性对手下的性能,并研究了在线赌徒问题的情况,表明任何赌徒算法都无法针对带有无界内存的适应性对手保证次线性的政策遗憾,但同时提出了将标准遗憾限制在次线性边界以下的任何赌徒算法转换为政策遗憾限制在次线性边界以下的算法的一般技术, 并将这一结果扩展到其他遗憾变体。
Jun, 2012
研究在线组合优化问题下的半强化反馈,提出了一种结合FPL预测方法和新颖的损失估计程序(称为Geometric Resampling)的学习算法,并且在能够进行高效离线组合优化的任何决策集合上可以有效实现。假设决策集合的元素可以用至多m个非零项的d维二进制向量来描述,证明了我们算法的期望遗憾在T轮后是O(m sqrt(dT log d)),并且在全信息设置中也改进了FPL的最佳遗憾限制。
May, 2013
该研究考虑了单人和多人多臂老虎机模型的学习问题,提出了两种可分散策略,即E³ (立方)和E³-TS,它们显示出预期遗憾增长的上限为O(log^(1+ε)T),并解决了分散的在线学习所产生的附加成本问题。
May, 2015
本研究提出了一种基于在线随机梯度下降的广义线性赌博机算法,它使用单步SGD更新来利用过去的信息并使用汤普森抽样实现探索,能够在探索与利用之间取得平衡,在合成和实际数据集上始终优于现有算法,其总时间复杂度为T和d的线性比例,其中T是总轮次数,d是特征数量,并实现了O(T)的遗憾,其中T是回合数。
Jun, 2020
本文研究了$K$-武斗器下在非固态或时变偏好情况下动态遗憾最小化问题,设计了能够有效解决此问题的算法,证明了算法的最优性,并进行了大量模拟和与其他算法对比的实验。
Nov, 2021
研究在线学习中的非约束非子模最小化问题,并提出了一种基于梯度下降算法的解决方案,其中考虑了非子模函数特殊结构和成本的时滞,证明了算法在静态和延迟情况下的遗憾保证。
May, 2022
我们研究了面对自适应对手时的分布式在线和掷骰机凸优化问题。我们旨在在$M$个并行工作的机器上通过$T$轮和$R$次间歇通信来最小化平均遗憾。在假设底层成本函数是凸函数并且可以自适应生成的情况下,我们的研究结果表明,在机器能够访问所查询点的一阶梯度信息时,合作是没有益处的。这与对于随机函数的情况形成了对比,其中每台机器从固定分布中抽样成本函数。此外,我们深入研究了带有掷骰机(零阶)反馈的联邦在线优化更具挑战性的情况,在该情况下,机器只能访问所查询点的成本函数值。这里的关键发现是确定合作有益且甚至可能导致机器数量的线性加速的高维度情况。我们通过开发新的分布式单点和双点反馈算法,进一步说明了我们的研究结果在联邦对抗线性掷骰机中的应用。我们的工作是对限制反馈的联邦在线优化的系统理解的首次尝试,并在间歇通信情况下获得了一阶和零阶反馈的严格遗憾界。因此,我们的研究填补了联邦在线优化中随机和自适应环境之间的差距。
Nov, 2023
本研究分析了在线凸优化问题在不同情境下的处理方法,并在具有完全适应性对手的在线线性优化算法为在线凸优化算法提供了一个模板,同时将需要完全信息反馈的算法转换为具有相近遗憾界限的半强盗反馈算法。此外,通过对半强盗反馈中使用确定性算法的完全适应性对手和使用随机算法的毫无意识对手进行比较,我们证明了可以在面对不可避免对手时,设计针对完全适应性对手的算法使用仅具有随机半强盗反馈也能获得类似界限。基于此,我们提出了将一阶算法转换为零阶算法,并具有相近遗憾界限的通用元算法框架。我们的框架允许在不同情境下分析在线优化,如全信息反馈、强盗反馈、随机遗憾、对手遗憾和各类非稳定遗憾。利用我们的分析,我们提供了第一个使用线性优化预言机的无投影在线凸优化算法。
Feb, 2024
本文介绍了一种简单且实用的在线牛顿步骤算法,该算法在一类称为κ-凸的凸函数中具有最优(以时间长度衡量)的遗憾界,并且在包括线性、二次和广义线性模型在内的广泛实际损失函数中为最高效的已知方法。此外,我们研究了我们的二阶赌博算法在具有一定仿射结构的损失函数中适应在线凸优化,我们证明了延伸算法达到最优遗憾界,从而解决了在gradu2020non和sun2023optimal中提出的一个开放问题,即完全敌对噪声模型下的赌博LQR/LQG问题。最后,我们证明了BCO与(非仿射)内存的更一般问题更难,在光滑且二次损失的假设下,导出了一个T^{2/3}遗憾界的下界。
Feb, 2024