BriefGPT.xyz
Sep, 2023
在线凸优化下的在线次模最大化
Online Submodular Maximization via Online Convex Optimization
HTML
PDF
T. Si-Salem, G. Özcan, I. Nikolaou, E. Terzi, S. Ioannidis
TL;DR
研究了在线环境下的通用拟阵约束下的单调子模最大化问题，证明了一大类子模函数在在线凸优化问题中的优化等价性，通过合适的舍入方案，实现了在组合优化中达到次线性后悔的 OCO 算法。同时，该规约也适用于多种不同版本的在线学习问题，包括动态后悔、游走和乐观学习等。
Abstract
We study
monotone submodular maximization
under
general matroid constraints
in the online setting. We prove that online optimization of a large class of submodular functions, namely,
→