arXiv：cs.LG（机器学习，全量分类）· Vaneet Aggarwal·· 14 小时前AI 评分36
无投影在线凸优化的精确 Oracle-Regret 权衡
Sharp Oracle-Regret Tradeoffs for Projection-Free Online Convex Optimization
AI 导读
研究在仅能访问精确线性优化 oracle 的条件下，在线凸优化可达到的遗憾界。对凸 G-Lipschitz 损失、直径不超过 D、总 oracle 调用预算 Q、每轮严格限制 B 次调用，无维度 minimax 期望遗憾为 Θ(GD·max{√T, T/(1+min{Q,BT})^{1/4}})，下界适用于任意随机化学习器。
正文
Abstract:We characterize the regret attainable in online convex optimization when access to the feasible set is limited to an exact linear optimization oracle. The learner is given an inscribed ball and a diameter bound and must remain feasible on every consistent instance. For convex $G$-Lipschitz losses, diameter at most $D$, a total allowance of $Q$ oracle calls, and a strict limit of $B$ calls per round, the dimension-free minimax expected regret is $\Theta(GD\max\{\sqrt T,T/(1+\min\{Q,BT\})^{1/4}\})$. The lower bound applies to arbitrary randomized learners. Universal feasibility first forces each action into the hull of the supplied ball and the preceding oracle replies. A fixed-body construction then couples fresh phase directions to a shared simplex, making useful replies costly repeatedly even though all losses have a common minimizer. A counted approximate-gradient method with interleaved blocks attains the matching rate. Total-budget and strict per-round guarantees follow as special cases, including the $T^{3/4}$ rate with one call per round and the quadratic total budget needed for $\sqrt T$ regret. For prescribed smoothness $\beta$, an analytic construction yields a curvature-dependent lower bound and identifies the threshold above which the general characterization remains sharp.
| Subjects: | Machine Learning (cs.LG) |
| Cite as: | arXiv:2610.00254 [cs.LG] |
| (or arXiv:2610.00254v1 [cs.LG] for this version) | |
| https://doi.org/10.48550/arXiv.2610.00254 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Vaneet Aggarwal [view email]
[v1]
Wed, 23 Sep 2026 22:25:52 UTC (31 KB)
来源：arXiv：cs.LG（机器学习，全量分类） · arxiv.org