本文研究一种在线线性优化问题,其中学习者在每一轮进行决策之前可以访问 K 个 ' 暗示 ' 向量。本文设计了一种算法,可以在存在带有成本向量正相关性的 K 个暗示的凸组合时获得对数后悔,这显著扩展了以前只考虑 K=1 情况的相关工作。为了实现这一点,我们开发了一种方法,将许多任意 OLO 算法组合起来,以实现后验情况下最小后悔的对数更差因素,该结果独立地具有利益。
Oct, 2020
本文提出了一种新的在线学习模式,可以处理无界域和非 Lipschitz 损失的问题,并开发了新的基于套索的在线学习算法,同时利用此算法开发了新的鞍点优化算法,在无界域中实现对偶间隙的收敛;最终提供了第一个实现非 Lipschitz 损失下的动态遗憾度的算法,以及匹配的下界。
Jun, 2023
本文研究了无约束在线线性优化博弈中最小化后悔的算法,其中对于一个有界比较器集合,得到了该博弈的解及其渐进行为,同时针对更宽松的惩罚函数提出了相应的算法并得到了渐进解。
Feb, 2013
我们提供了一种在线学习算法,可以在不知道 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
提出和分析一种新型的 Follow-the-Perturbed-Leader 类型算法,用于在线方式解决一般的长期受约束的优化问题,其中目标和约束不一定是凸的。通过将随机线性扰动和强凸扰动分别引入原始和对偶方向,搜索全局极小极大点作为解决方案,并基于两个特定的预期静态累积遗憾定义,推导出这类问题的第一个次线性 $O (T^{8/9})$ 遗憾复杂度。该算法应用于解决长期(风险)受约束的河流污染源辨识问题,验证了理论结果的有效性,并表现出比现有方法更优越的性能。
Nov, 2023
我们研究具有 Lipschitz 损失的无约束在线线性优化问题,提出一种新的连续时间启发式算法,通过连续时间模型和离散时间对偶的方式实现渐进的梯度自适应和比较器范数自适应,克服了传统方法中梯度方差的缺陷并消除了未知 Lipschitz 常数的问题。
Sep, 2023
本文提出了基于多层在线集成的在线凸优化方法,具有两种不同的适应性水平,并针对强凸、指数 - 凹和凸损失函数分别获得了收敛等效性和遗憾上界。
Jul, 2023
本文提出了在线凸优化算法来解决无约束情况下在线预测和分类的问题,并证明了其相对于参数 x^* 几乎达到最优的遗憾界。
Nov, 2012
我们研究了私密在线学习的问题,特别是专家预测(OPE)和在线凸优化(OCO)。我们提出了一种将惰性在线学习算法转化为私密算法的新方法。我们通过使用现有的惰性算法解决这些问题,将我们的转化应用于差分隐私 OPE 和 OCO。我们的最终算法在高隐私水平 ε≪1 下获得显著改进的后悔,对于 DP-OPE 为√(Tlogd) + (T^(1/3) log (d))/ε^(2/3),对于 DP-OCO 为√T + (T^(1/3)√d)/ε^(2/3)。我们通过对 DP-OPE 进行下界的研究,进一步补充了我们的结果,表明这些速率对于一类自然的低转换私密算法来说是最优的。
Jun, 2024
机器学习模型通过训练来预测双重解估计,并从中构建原始估计,以形成双重可行解对。通过采用来自实际增广 Lagrangian 方法的技术,该训练方案可以改进,从而学习高度准确的有约束优化求解器,适用于凸和非凸问题。
Mar, 2024