无悔的 M${}^{atural}$ 凹函数最大化：随机赌博算法和对抗完全信息设置的 NP 困难性
原文中文，约1500字，阅读约需4分钟。
📝
内容提要
本文研究了在线优化中的非凸目标函数，提出了改进的Frank-Wolfe算法和在线随机梯度上升算法，并证明了它们在遗憾界限上的有效性。研究还扩展到弱次模函数，展示了算法在非凸规划和子模函数优化中的应用效果。
🔎
延伸解读
非凸在线优化的遗憾保证
文章针对非凸目标函数，提出了改进的Frank-Wolfe算法和在线随机梯度上升算法。前者在可获取全梯度时，对未来最佳可行解的(1-1/e)-近似达到O(√T)遗憾界；后者在仅有梯度无偏估计时，遗憾界同为O(√T)，但近似度降为1/2。这为连续次模函数类的在线优化提供了理论保证。
弱次模函数的扩展
研究进一步将结果推广到γ-弱次模函数，并证明相同的次线性遗憾界。这意味着算法不仅适用于严格的次模函数，还能处理更广泛的弱次模结构，增强了理论框架的通用性，为相关非凸规划问题提供了更灵活的工具。
实验验证与应用场景
文章在多个问题实例上验证了算法的效率，包括非凸/非凹二次规划、子模集函数的多线性扩展以及D-最佳设计。这些实例展示了算法在非凸规划和子模函数优化中的实际应用潜力，为在线决策、强化学习等领域提供了可借鉴的优化方法。
❓
Q&A
什么是改进的Frank-Wolfe算法的主要特点？
改进的Frank-Wolfe算法在未来最佳可行解的(1-1/e)-近似下具有O(T的平方根)的遗憾界限。
在线随机梯度上升算法的遗憾界限是什么？
在线随机梯度上升算法在无偏估计情况下具有O(T的平方根)的遗憾界限，但对未来最佳可行解的近似度为1/2。
研究中提到的弱次模函数有什么应用？
研究结果推广到γ-弱次模函数，证明相同的次线性遗憾界限，显示算法在非凸规划中的应用效果。
本文中提到的算法在什么问题实例中展示了效率？
算法在非凸/非凹二次规划和子模集函数的多线性扩展等问题实例中展示了效率。
如何理解遗憾界限在在线优化中的重要性？
遗憾界限衡量算法在在线优化中与最佳可行解的接近程度，影响算法的有效性和实用性。
本文的研究对在线优化领域有什么贡献？
本文提出了改进的算法并证明了其在非凸目标函数优化中的有效性，推动了在线优化领域的发展。
🏷️
