arXiv · Machine Learning Theory· Vaneet Aggarwal·· 5 小时前AI 评分15
投影自由在线凸优化的尖锐 Oracle-Regret 权衡
Sharp Oracle-Regret Tradeoffs for Projection-Free Online Convex Optimization
AI 导读
论文刻画了仅依赖精确线性优化 Oracle 时在线凸优化的遗憾下界。在凸 G-Lipschitz 损失、直径 D、总 Oracle 调用 Q、每轮上限 B 的设定下，维度无关的极小极大期望遗憾为 Θ(GD·max{√T, T/(1+min{Q,BT})^1/4})。该下界对任意随机化学习器成立，并给出达到匹配率的计数近似梯度方法与总预算/每轮保证的特殊情形。
来源：arXiv · Machine Learning Theory · arxiv.org