在线预测具有总变差界限的序列
文章探讨带有噪声梯度反馈的非平稳随机优化框架,在比较序列变化的动态策略中,研究在线学习算法的动态后悔,并引入了 Total Variation ball 等新颖变分约束来建模比较序列,并基于基于小波的非参数回归理论,设计出一个多项式时间算法,并证明了该算法达到了几乎最优的动态后悔,该策略适应未知的半径。
Sep, 2020
我们考虑一个新的框架,其中一个连续但有界的随机变量具有随时间变化的未观察到的边界,并在有界随机变量的分布的参数上考虑边界。我们引入了扩展对数似然估计,并设计算法通过在线最大似然估计来跟踪边界。由于所得到的优化问题不是凸的,我们利用最近关于凸优化的规范化梯度下降(NGD)的理论结果,最终导出在线规范化梯度下降算法。我们基于仿真研究和实际风电功率预测问题说明和讨论了我们方法的工作原理。
Jun, 2023
在本文中,我们通过在线优化的视角,考虑了一个遵循随时间变化的分布的随机优化问题序列。假设损失函数满足 Polyak-Lojasiewicz 条件,我们应用在线随机梯度下降并建立了其动态遗憾界,其中包含由随机性引起的累积分布漂移和累积梯度偏差。我们采用的分布测度是 Wasserstein 距离,它在没有绝对连续性假设或具有时变支持集时具有良好定义。我们还建立了在线随机近端梯度下降的遗憾界,当目标函数被正则化时。此外,我们展示了上述框架如何应用于条件风险价值(CVaR)学习问题。特别地,我们改进了对 CVaR 问题 PL 条件发现的现有证明,从而得到了在线随机梯度下降的遗憾界。
Sep, 2023
在高维离散空间中,假设函数具有有限的总变异性,本文通过导出最小化 (平方) L2 估计误差率,表明了:总变异性去噪(融合拉索)优于拉普拉斯平滑和拉普拉斯特征图等较简单的估计器。
May, 2016
对于趋势过滤,我们通过将对总变异率的 k-1 阶差异惩罚与最小二乘估计相结合,并使用 “插值向量” 来上界 “有效稀疏度”,为其建立自适应结果。我们证明了 k∈{1,2,3,4} 的结果,并指示了如何导出 k∈$\mathbb {N}$ 的一般情况。
Apr, 2019
在线凸优化中,考虑具有对抗性时变约束的情景,在这种情况下,行动必须相对于固定约束集是可行的,同时在平均上还需要近似满足附加的时变约束。我们提出了一种算法,通过线性优化预言机(LOO)访问这个集合来保证在一个长度为 T 的序列上,通过总共 T 次对 LOO 的调用,相对于损失函数产生的后悔为 $ ilde {O}(T^{3/4})$,对于约束的违反是 $O (T^{7/8})$(忽略除了 $T$ 以外的所有量)。尤其地,这些边界适用于序列中的任何区间。我们还提出了一种更高效的算法,它仅需要对软约束进行一阶预言机访问,并在整个序列上获得类似的边界。我们将后者扩展到了强化学习的场景,并在期望上获得了类似的边界(作为 $T$ 的函数)。
Feb, 2024
本研究关注在线凸优化的动态遗憾,通过探索称为路径变化的时间变化机制,提出了一些动态遗憾改进的变差上限,并证明他们在已有的下限条件下是最优的。
May, 2016
使用先进的证明技术和 Zinkevich-style 动态遗憾最小化框架,本研究提出了一个强适应的在线学习算法,其总变化控制下的动态遗憾为 O (n^(1/3)*C_n^(2/3)),并且可以扩展到局部自适应非参数回归问题中。
Apr, 2021