希尔伯特空间下的无约束在线线性学习:极小极大算法和正规近似
本文研究了无约束在线线性优化博弈中最小化后悔的算法,其中对于一个有界比较器集合,得到了该博弈的解及其渐进行为,同时针对更宽松的惩罚函数提出了相应的算法并得到了渐进解。
Feb, 2013
本文讨论在线线性优化问题,考虑可行操作集通过近似线性优化预言机具有 α 乘性逼近保证的情况,给出了新算法并提出了显著改进甚至多项式对数的预言机复杂度,同时得到了常数 c>0 的 alpha 遗憾界。
Sep, 2017
该研究提出了在线线性优化问题的带有 bandit 反馈的算法,并使用 Mirror Descent 算法在特定案例中获得具有最小二乘优化后退限制的计算高效性的策略,证明了计算上以及最小二乘上的结果优化,为输出结果减少了冗余的符号。
Feb, 2012
我们提供了一种在线学习算法,可以在不知道 G 或∥w∗∥的情况下,获得在 G-Lipschitz 凸损失函数上的遗憾 G∥w∗∥√(Tlog (∥w∗∥G√T)+∥w∗∥^2+G^2),这与具有此类知识的最佳界限 G∥w∗∥√T 匹配(除了对数因子),除非∥w∗∥或 G 太大,以至于即使 G∥w∗∥√T 在 T 中也大致线性。因此,在可以实现次线性遗憾的所有场景中,它匹配了最佳界限,这可以说是最 “有趣” 的情况。
May, 2024
在未知时间的在线学习中,我们应用最小二乘分析,提出了一种新的自适应算法,该算法可以应用于在线凸优化,追随摇摆的领导者,指数权重算法和一阶界,实验表明在在线线性优化方面,我们的算法表现优于许多其他现有算法。
Jul, 2013
研究线性随机赌博机的噪声模型,介绍一种基于加权最小二乘估计的算法,能够最小化后悔度,通过几何论证独立于噪声模型,能够紧密控制每个时间步骤的期望后悔度为 O (1/t),从而导致了累积后悔度的对数缩放。
Feb, 2024
本文针对具有强可观测无向反馈图的在线学习问题,在回报上下界方面进行了改进,并使用 FTRL 与 q-Tsallis 熵对结果进行了证明;同时扩展了该技术应用于时间变化图的情形,并提供了适用于所有 alpha>1 的改良下界。
May, 2023
我们研究了在线线性优化问题,探讨了半强盗、强盗和完全反馈三种情况下的极小后悔量,并提出了使用 Bregman 投影技术的梯度下降通用策略以及上下界解决方案,并在最后指出了指数加权平均预测者对于 L∞对手是次优解的问题。
May, 2011
通过 von Neumann 最小极大定理,我们研究了在线凸优化游戏的最优策略的遗憾。我们证明了,在这种对抗性环境中,最优策略的遗憾与随机进程设置中经验最小化算法的行为密切相关:它等于最小期望损失的总和与最小经验损失之间的差的最大值。我们展示了最优策略的遗憾具有自然的几何解释,因为它可以被视为一个上凸函数的 Jensen 不等式中的差距。利用此表达式,我们对各种在线学习问题的最优策略给出了上下界限制。我们的方法提供了无需构建学习算法的上界,而提供了对抗者的明确最优策略的下界。
Mar, 2009