aiqbench analysis
This research establishes tight dimension-free regret bounds for projection-free online convex optimization under strict linear oracle constraints, revealing fundamental tradeoffs between query budgets and learning performance. The findings provide a theoretical ceiling for algorithms that must maintain feasibility without explicit projection steps, which is critical for scalable reinforcement learning and high-dimensional decision-making systems. By characterizing the cost of universal feasibility through fixed-body constructions, the work clarifies the inherent limitations when access to the feasible set is restricted to oracle calls alone.
Sharp Oracle-Regret Tradeoffs for Projection-Free Online Convex Optimization
arXiv:2610.00254v1 Announce Type: new 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.
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.
Machine Learning (cs.LG)
arXiv:2610.00254 [cs.LG]
(or arXiv:2610.00254v1 [cs.LG] for this version)
https://doi.org/10.48550/arXiv.2610.00254 Focus to learn more arXiv-issued DOI via DataCite (pending registration)
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Full text under the publisher's open licence · 281 words
Related coverage
From Non-Convex to Strongly Convex: Curvature-Adaptive FTPL for Online Optimization
arXiv · Jun 3, 2026
Parameter-Free Dynamic Regret for Online Convex Optimization under Heavy-Tailed Noise
arXiv · Jul 31, 2026
Sharp Root Anti-Concentration via Projective Incidence and Ordered Root Laws
arXiv · Aug 4, 2026
Decentralized Projection-free Online Upper-Linearizable Optimization with Applications to DR-Submodular Optimization
arXiv · Oct 1, 2026