LEARN:一种针对异常值默默抵抗的鲁棒在线优化的反凸损失
本文提出了解决约束在线凸优化问题的框架。通过将问题转化为在线凸-凹优化问题,提出了一种有效的算法,可以实现收敛性较好的结果。同时,本文还为从中提取多点强化信号的约束在线凸优化问题提供了解决方案。
Nov, 2011
本文提出了一种针对非可分离损失函数的在线学习框架,通过引入新型算法设计和分析,该模型具有高效的在线学习算法,具有亚线性遗憾和在线转换界限; 进一步开发了可扩展的随机梯度下降求解器,经过实验在真实数据集上证明,该方法比近期提出的切割面算法快得多。
Oct, 2014
提出了一种适应性在线梯度下降算法,用于解决具有长期约束的在线凸优化问题,可以处理任意凸约束,该算法在损失和约束违规方面分别具有O(T^max{β,1−β})和O(T^(1−β/2))的累积遗憾界,优于Mahdavi等(2012年)最好的已知累积遗憾界,该算法的性能已在实践中得到验证。
Dec, 2015
本文通过引入新的后悔分解和Bregman散度的泛化来对在线学习的两个算法进行分析,得出了较为简洁的结论,提出了对于复合目标的算法,并提供了一种细化的算法族。
Sep, 2017
本文介绍了在线学习的基本概念和现代在线凸优化的视角,并针对凸丢失,在欧几里得和非欧几里得环境中介绍了一阶和二阶算法。同时,还特别关注了算法参数调优和在无界域上的学习,并介绍了对非凸损失的处理方法和信息缺失的决策问题中的多臂赌博机问题。
Dec, 2019
本文研究了在线情况下健壮线性回归问题,提出了一种基于随机梯度下降方法和L1损失函数的高效算法,能够在存在污染数据情况下有效检测和去除异常值,算法复杂度与污染比例相关。
Jul, 2020
本研究考虑在线凸优化问题的相对Lipschitz收敛性和相对强凸性,扩展了已知的算法在相对设置下的遗憾界,特别是基于正则聚类领导者算法和在线镜像下降算法的算法,同时将这些结果进一步扩展到具有额外正则化的算法。
Oct, 2020
本研究分析了在线凸优化问题在不同情境下的处理方法,并在具有完全适应性对手的在线线性优化算法为在线凸优化算法提供了一个模板,同时将需要完全信息反馈的算法转换为具有相近遗憾界限的半强盗反馈算法。此外,通过对半强盗反馈中使用确定性算法的完全适应性对手和使用随机算法的毫无意识对手进行比较,我们证明了可以在面对不可避免对手时,设计针对完全适应性对手的算法使用仅具有随机半强盗反馈也能获得类似界限。基于此,我们提出了将一阶算法转换为零阶算法,并具有相近遗憾界限的通用元算法框架。我们的框架允许在不同情境下分析在线优化,如全信息反馈、强盗反馈、随机遗憾、对手遗憾和各类非稳定遗憾。利用我们的分析,我们提供了第一个使用线性优化预言机的无投影在线凸优化算法。
Feb, 2024
通过黑匣子减少,我们使用简化域上定义的替代损失函数,构建了一种只需要进行一次投影的通用OCO算法,对于一轮在线问题,我们维护每种类型函数的一组专家,并通过元算法聚合他们的预测。我们的方法的关键在于针对强凸函数设计的专家损失函数,并通过创新地将遗憾分解为元遗憾和专家遗憾,从而对替代损失函数的遗憾和原损失函数的遗憾之间的差异进行了严格的研究,并在强凸性条件下仔细控制了元遗憾。通过这种方式,我们建立了一轮中的通用凸函数、指数凹函数和强凸函数的最优遗憾上界,并通过增强专家损失函数来利用光滑性质,从而证明了我们的算法可以达到多种类型的凸函数和光滑函数的小损失遗憾。
May, 2024