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