Jan, 2017

跟随压缩的领袖：更快的特征向量在线学习和更快的 MMWU

PDF
TL;DR研究在线问题的顶部特征向量的计算方法。提出了一种 follow-the-compressed-leader（FTCL）算法，能够在不牺牲运行时间的情况下实现最优遗憾率。该算法在敌对和随机环境中均能提供最优解决方案，解决了在线特征向量问题的两个未解之谜。
online problemtop eigenvectormachine learningfollow-the-compressed-leaderregret
发现论文，激发创造
  • 跟随扰动领袖进行自适应在线预测

    应用聚合策略进行预测时，需要自适应调整学习速率以避免复杂度和当前损失率之间的分析难题；本文基于 Kalai 和 Vempala（2003）的 “Follow the Perturbed Leader”（FPL）算法，在两种不同的专家类别下得出了可调学习速率的损失界限，其中前者的损失界限与迄今为止最佳结果匹配，而后者为新结果。

    Apr, 2005

  • 广义隐式 Follow-The-Regularized-Leader

    该研究提出了一种新的在线学习算法，即广义隐式 FTRL，该算法扩展了 FTRL 框架的范围，可恢复已知算法，设计新的更新规则，直接改善遗憾的最坏情况的上界。

    May, 2023

  • 无特征分解训练基于深度网络的线性最小二乘问题

    本文通过一种去除特征值分解的方法，解决了深度学习框架中的一个困境：如何在网络中显式编码已知的几何概念，并演示了此方法在多种实际情况下的鲁棒性和性能优越性。

    Apr, 2020

  • 在线非凸学习：跟随扰动领袖是最优的

    研究基于非凸损失的在线学习问题，证明了经典的 Perturbed Leader 算法在该设置下可达到最佳遗憾率，进一步证明乐观的 FTPL 算法在序列损失可预测时的遗憾界更优。

    Mar, 2019

  • 无尺度在线学习

    本文设计并分析了一种不需要任何上限或下限的在线线性优化算法，实现了适应损失向量范数的缩放不变性，并且通过 FTRL 和 MD 元算法实现了最优遗憾，并为无界决策集开发了一种非真空遗憾绑定的自适应算法，并对基于 MD 的无标度算法在无界域上的下限进行了研究。

    Jan, 2016

  • 可扩展的鲁棒矩阵恢复：Frank-Wolfe 遇上 Proximal 方法

    该研究提出了一个基于 Frank-Wolfe 和近端方法的算法，以（基本上）线性的迭代成本来解决矩阵从压缩和严重损坏的观测中恢复的问题，证明其可行性，讨论了收敛结果和实现细节，并在可视数据上进行了良好的数值实验。

    Mar, 2014

  • 利用数值稀疏性进行高效学习：更快的特征向量计算和回归

    本文提出了更快的算法来解决数据矩阵中回归和特征向量计算问题，使用这些算法，即使在稀疏矩阵的情况下，也可以获得近似的线性运行时间。

    Nov, 2018

  • 在线低秩矩阵补全

    本文研究在线低秩矩阵完成问题，提出了一个基于探索 - 利用策略及用户聚类技术的 OCTAL 方法，可以在多项臂赌博机问题的基础上获取 $ O ({m polylog} (M+N) T^{2/3})$ 的遗憾，并在 Rank-1 情况下得到 $O ({m polylog} (M+N) T^{1/2})$ 的近似率。

    Sep, 2022

  • 在线策略学习与矩阵补全的推理

    基于矩阵完成赌徒问题 (MCB) 和在线梯度下降算法，探索碎状历史特征的在线决策问题。研究比较不同勘探概率和步长调度下的策略学习和后悔表现，同时研究基于反向反比加权 (IPW) 的去偏方法和在线策略推理的通用框架，通过实验验证理论结果，应用于旧金山停车定价项目数据，取得了引人注目的发现和超过基准策略的表现。

    Apr, 2024

  • 从 Oja 算法到乘法权重更新方法及应用

    奥贾算法是一个众所周知的在线算法，主要用于随机主成分分析的背景中。我们进行了一个简单但新颖的观察，即当应用于共享公共特征向量的任意对称矩阵序列时，并不一定是随机的，奥贾算法的遗憾可以直接以预测专家建议问题的众所周知的乘积权重更新方法的遗憾为界限。讨论了在 $ eals^n$ 上的单位球上具有二次形式的优化的几个应用。

    Oct, 2023