BriefGPT - AI 论文速递
·
在线凸优化下的在线次模最大化
💡
原文中文，约400字，阅读约需1分钟。
📝
内容提要
本文提出了针对连续次模函数类的在线优化过程，包括Frank-Wolfe算法的变体和在线随机梯度上升算法。证明了两种算法具有O（T的平方根）的遗憾界，并将结果推广到γ-弱次模函数。演示了算法的效率在几个问题实例上。
🎯
关键要点
- 本文研究在线优化过程，目标函数属于连续次模函数类。
- 提出了一种 Frank-Wolfe 算法的变体，能够访问目标函数的全梯度。
- 该算法对未来最佳可行解的（1-1/e）-近似具有 O（T 的平方根）的遗憾界。
- 针对只能获得梯度的无偏估计情况，提出了在线随机梯度上升算法。
- 在线随机梯度上升算法也具有 O（T 的平方根）的遗憾界，但对未来最佳可行解的近似度为 1/2。
- 结果推广到 γ-弱次模函数，证明相同的次线性遗憾界。
- 在多个问题实例上演示了算法的效率，包括非凸/非凹二次规划等。
🏷️
标签
➡️
