在线学习的投影二次回归
本论文提出采用 Frank-Wolfe 技术的高效在线学习算法,避免了投影步骤,同时在在线凸优化方面获得了一系列遗憾界,特别是在随机在线平滑凸优化方面。此外,我们的算法具有参数自由性和产生稀疏决策的优点,并将算法应用到协作过滤的计算密集型应用中,并在标准数据集上显示出理论上的改进。
Jun, 2012
本研究提出了一种在线学习算法,名为 Online Compact Convex Factorization Machine (OCCFM),使用一种新的凸化方法来进行因式分解模型的在线学习。该算法采用线性优化而非传统的投影操作来优化模型,理论上证明了它在在线学习场景中的优越性能,并在多个真实数据集上进行了验证。
Feb, 2018
基于在线凸优化和曲率的可行集合的分析,本文提出了一种新的方法通过利用可行集合的曲率来实现快速收敛,不仅可以适用于凸损失函数,同时还能在随机、对抗性和受干扰的环境下获得良好的性能。
Feb, 2024
本文提出了一个新的在线凸优化框架,能够利用过去的决策历史对当前损失进行建模,并引入了 “p 有效内存容量” 来量化过去决策对当前损失的最大影响。在此框架下,证明了一些政策遗憾的较好上界,并展示了该框架对于各种在线学习任务的适用性。
Oct, 2022
我们研究了私密在线学习的问题,特别是专家预测(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
本论文提出了使用二阶锥松弛方法来解决具有离群值时使用线性回归模型所遇到的混合整数优化问题,相比于现有方法使用的大 M 约束进行的线性化,该方法具有更强的弛豫度且性能更优。
Jul, 2023
本文提出了解决约束在线凸优化问题的框架。通过将问题转化为在线凸 - 凹优化问题,提出了一种有效的算法,可以实现收敛性较好的结果。同时,本文还为从中提取多点强化信号的约束在线凸优化问题提供了解决方案。
Nov, 2011
研究了在线环境下的通用拟阵约束下的单调子模最大化问题,证明了一大类子模函数在在线凸优化问题中的优化等价性,通过合适的舍入方案,实现了在组合优化中达到次线性后悔的 OCO 算法。同时,该规约也适用于多种不同版本的在线学习问题,包括动态后悔、游走和乐观学习等。
Sep, 2023
通过黑匣子减少,我们使用简化域上定义的替代损失函数,构建了一种只需要进行一次投影的通用 OCO 算法,对于一轮在线问题,我们维护每种类型函数的一组专家,并通过元算法聚合他们的预测。我们的方法的关键在于针对强凸函数设计的专家损失函数,并通过创新地将遗憾分解为元遗憾和专家遗憾,从而对替代损失函数的遗憾和原损失函数的遗憾之间的差异进行了严格的研究,并在强凸性条件下仔细控制了元遗憾。通过这种方式,我们建立了一轮中的通用凸函数、指数凹函数和强凸函数的最优遗憾上界,并通过增强专家损失函数来利用光滑性质,从而证明了我们的算法可以达到多种类型的凸函数和光滑函数的小损失遗憾。
May, 2024