置换多面体上的贪心在线优化
该研究提出了在线线性优化问题的带有bandit反馈的算法,并使用Mirror Descent算法在特定案例中获得具有最小二乘优化后退限制的计算高效性的策略,证明了计算上以及最小二乘上的结果优化,为输出结果减少了冗余的符号。
Feb, 2012
本文研究使用二进制向量表示决策者可能的选择时的在线线性优化问题及其反悔,探讨了决策者在不同反馈条件下的最优反悔幅度,并提出了一种使用镜像下降算法和隐式归一化预测策略的解决方案,获得了半强盗情形的最优界限,同时也证明了在线组合优化基准算法的次优性。
Apr, 2012
研究在线组合优化问题下的半强化反馈,提出了一种结合FPL预测方法和新颖的损失估计程序(称为Geometric Resampling)的学习算法,并且在能够进行高效离线组合优化的任何决策集合上可以有效实现。假设决策集合的元素可以用至多m个非零项的d维二进制向量来描述,证明了我们算法的期望遗憾在T轮后是O(m sqrt(dT log d)),并且在全信息设置中也改进了FPL的最佳遗憾限制。
May, 2013
本文研究了在线组合优化问题中的半盲反馈,提出了一种优化算法来减少期望后悔。该算法以L_T*的平方根为增长率,在部分反馈方案中首次实现了此类保证,并在组合设置中首次实现了此类保证。
Feb, 2015
提出一种新的算法解决在无导数情况下的$adversarial convex bandit$ 问题,其包含了核方法、伯努利卷积的一般化和新的退火时间表。这个算法在要求多次迭代的场景中可以取得佳效果。
Jul, 2016
研究了在线凸优化中的竞争比率和算法,证明了一个新的下限。同时提出了两种新的算法,G-OBD和R-OBD并证明了其具有$O(m^{-1/2})$的竞争比率及成功降低了回归成本。
May, 2019
本研究分析了在线凸优化问题在不同情境下的处理方法,并在具有完全适应性对手的在线线性优化算法为在线凸优化算法提供了一个模板,同时将需要完全信息反馈的算法转换为具有相近遗憾界限的半强盗反馈算法。此外,通过对半强盗反馈中使用确定性算法的完全适应性对手和使用随机算法的毫无意识对手进行比较,我们证明了可以在面对不可避免对手时,设计针对完全适应性对手的算法使用仅具有随机半强盗反馈也能获得类似界限。基于此,我们提出了将一阶算法转换为零阶算法,并具有相近遗憾界限的通用元算法框架。我们的框架允许在不同情境下分析在线优化,如全信息反馈、强盗反馈、随机遗憾、对手遗憾和各类非稳定遗憾。利用我们的分析,我们提供了第一个使用线性优化预言机的无投影在线凸优化算法。
Feb, 2024
本研究针对非凸损失函数的分布式在线带式优化问题,提出了一种新的单点残余反馈算法,以解决传统算法在处理非凸损失时的劣势。通过使用动态遗憾度评估算法性能,研究显示该算法能够有效减少遗憾界限,且在数据采样复杂度上保持在$\mathcal{O}(1)$的水平,具有显著的实用价值和应用潜力。
Sep, 2024