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