Sharp Oracle-Regret Tradeoffs for Projection-Free Online Convex Optimization

# Sharp Oracle–Regret Tradeoffs for Projection-Free Online Convex Optimization
Source: [https://arxiv.org/html/2610.00254](https://arxiv.org/html/2610.00254)
\\jmlrpages

###### 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 convexGG\-Lipschitz losses, diameter at mostDD, a total allowance ofQQoracle calls, and a strict limit ofBBcalls per round, the dimension\-free minimax expected regret isΘ⁡\(G​D​max⁡\{T,T/\(1\+min⁡\{Q,B​T\}\)1/4\}\)\\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 theT3/4T^\{3/4\}rate with one call per round and the quadratic total budget needed forT\\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\.

††proceedings::###### keywords

Online convex optimization, linear optimization oracle, oracle complexity, minimax regret

## 1Introduction

Online convex optimization compares a sequence of feasible decisions with the best fixed decision in hindsight\. For convexGG\-Lipschitz losses on a set of diameterDD, projected gradient descent guaranteesO⁡\(G​D​T\)O\(GD\\sqrt\{T\}\)regret\([Zinkevich, 2003](https://arxiv.org/html/2610.00254#bib.bib2)\)\. When projection is expensive, a linear optimization oracle offers a simpler way to obtain feasible points\. Online Frank–Wolfe methods achieveO⁡\(G​D​T3/4\)O\(GDT^\{3/4\}\)regret with one oracle call per round\([Hazan and Kale, 2012](https://arxiv.org/html/2610.00254#bib.bib4);[Weibel et al\., 2026](https://arxiv.org/html/2610.00254#bib.bib12)\), and blocked approximate\-projection methods trade total oracle work against regret\([Garber and Kretzu, 2022](https://arxiv.org/html/2610.00254#bib.bib9);[Lu et al\., 2025](https://arxiv.org/html/2610.00254#bib.bib14)\)\.

Oracle work has two distinct resource constraints\. A total budget limits the number of calls over the entire horizon, whereas a strict per\-round limit controls how much work can be completed before the next decision\. A method that uses few calls on average may still require a long computation at a block boundary\. The converse question is equally important: can a learner improve the tradeoff by choosing arbitrary queries, storing all previous replies, or using more computation between calls?

We study both questions in an oracle\-only model\. The learner knows an inscribed ball and a diameter upper bound, and obtains all further information about the feasible set from a fixed exact linear oracle\. Feasibility is required on every instance consistent with this information\. For total budgetQQand strict per\-round budgetBB, define the effective total allowanceQ∗=min⁡\{Q,B​T\}Q\_\{\*\}=\\min\\\{Q,BT\\\}\. Our main result is

ℛjoint​\(T,Q,B,G,D\)=Θ⁡\(G​D​max⁡\{T,T\(Q∗\+1\)1/4\}\)\.\\mathcal\{R\}\_\{\\mathrm\{joint\}\}\(T,Q,B;G,D\)=\\Theta\\\!\\left\(GD\\max\\\!\\left\\\{\\sqrt\{T\},\\frac\{T\}\{\(Q\_\{\*\}\+1\)^\{1/4\}\}\\right\\\}\\right\)\.\(1\.1\)The guarantee is uniform over finite dimensions and supplied balls\. TakingB=∞B=\\inftyrecovers the total\-budget problem; takingQ=B​TQ=BTrecovers the strict per\-round problem\. In particular, a constant number of calls per round gives orderT3/4T^\{3/4\}regret, while orderTTcalls per round and orderT2T^\{2\}calls in total suffice for orderT\\sqrt\{T\}regret\.

#### Technical novelty: deriving the feasible\-action restriction\.

The lower bound applies to every admissible randomized learner, rather than to a prescribed update family\. LetSSbe the finite set of oracle replies available before an action\. On a finite\-vertex body, the smaller bodyconv⁡\(C∪S\)\\operatorname\{conv\}\(C\\cup S\), whereCCis the supplied ball, admits an exact oracle that reproduces those replies with the same tie\-breaking\. Feasibility on indistinguishable instances therefore forces the action into this hull\. To establish the claim for randomized queries, we fix an alternative body and oracle for every subset of the vertex set, intersect the corresponding probability\-one feasibility events, and only then select the subset generated by the transcript\. This order of quantifiers turns universal feasibility into a geometric constraint while leaving the learner’s query rule and intermediate computation unrestricted\.

#### Technical novelty: recurring oracle cost against one comparator\.

The standard simplex support estimate penalizes a point supported onNNvertices by a norm of orderN−1/2N^\{\-1/2\}\([Lan, 2013](https://arxiv.org/html/2610.00254#bib.bib6);[Jaggi, 2013](https://arxiv.org/html/2610.00254#bib.bib5)\)\. An online lower bound must additionally account for reuse of earlier vertices\. Our construction couples independent cube blocks to one shared simplex\. Each phase reveals a direction in a fresh cube block\. Oracle points acquired before the phase are poorly aligned with that direction with high probability\. Points acquired during the phase can align with it, but placing substantial weight on only a few such points incurs the simplex penalty\. Withmmphases, making most phases inexpensive requires ordermmnew oracle points per phase\. ThusQ∗≍m2Q\_\{\*\}\\asymp m^\{2\}, while regret is of orderT/mT/\\sqrt\{m\}, producing the fourth\-root dependence in \([1\.1](https://arxiv.org/html/2610.00254#S1.E1)\)\. All phases share one minimizer, so the lower bound is for static regret\.

#### Achievability and smoothness\.

The upper analysis matches this information cost under both resource constraints\. A comparator\-uniform distance certificate bounds the length of each feasible update\. Balanced blocks then expose the tradeoff between the number of decisions and the accuracy of each update\. Two interleaved copies distribute the updates over physical rounds, satisfying the total allowance and the strict cap simultaneously\. For smooth losses, replacing the norm penalty by an analytic radial penalty changes the support cost from orderN−1/2N^\{\-1/2\}to orderN−1N^\{\-1\}in its quadratic regime\. This yields an explicit dependence of the lower bound on the prescribed smoothness\.

#### Contributions\.

1. 1\.Theorem[4\.2](https://arxiv.org/html/2610.00254#Thmtheorem2)gives the matching lower and upper bounds under simultaneous total and per\-round budgets\. Its fixed\-body lower bound covers arbitrary randomized queries and allows full loss feedback\. Lemma[4\.7](https://arxiv.org/html/2610.00254#Thmtheorem7)and Proposition[4\.8](https://arxiv.org/html/2610.00254#Thmtheorem8)give the feasibility reduction and the recurring phase construction\.
2. 2\.Propositions[4\.5](https://arxiv.org/html/2610.00254#Thmtheorem5)and[4\.6](https://arxiv.org/html/2610.00254#Thmtheorem6)give finite\-call implementations and their physical\-round schedules\. Corollaries[4\.9](https://arxiv.org/html/2610.00254#Thmtheorem9)–[4\.13](https://arxiv.org/html/2610.00254#Thmtheorem13)recover the total\-budget tradeoff, the strict per\-round rate, and the oracle requirements for a target regret\. Table[1](https://arxiv.org/html/2610.00254#S2.T1)relates these consequences to previous upper bounds\.
3. 3\.Theorem[5\.14](https://arxiv.org/html/2610.00254#Thmtheorem14)gives two\-sided bounds for the smooth class under the same joint budgets\. Corollary[5\.16](https://arxiv.org/html/2610.00254#Thmtheorem16)identifies when the general minimax rate remains sharp and gives the curvature\-sensitive lower rate below that threshold\. Corollary[5\.18](https://arxiv.org/html/2610.00254#Thmtheorem18)translates it into necessary oracle budgets\.

## 2Related work

#### Total oracle budgets\.

Blocking and approximate projection provide the basic regret–computation tradeoff\. With a linear total number of oracle calls,[Garber and Kretzu \(2022\)](https://arxiv.org/html/2610.00254#bib.bib9)obtainO⁡\(T3/4\)O\(T^\{3/4\}\)regret, including an adaptive\-regret guarantee\. More generally, the tradeoffO⁡\(T1−θ/2\)O\(T^\{1\-\\theta/2\}\)regret withO⁡\(T2​θ\)O\(T^\{2\\theta\}\)total calls,0≤θ≤10\\leq\\theta\\leq 1, follows from[Lu et al\. \(2025\)](https://arxiv.org/html/2610.00254#bib.bib14)\. Their framework treats upper\-linearizable objectives, with convex optimization as a special case; we report that convex case here\. Theorem[4\.2](https://arxiv.org/html/2610.00254#Thmtheorem2)establishes a matching lower bound for this entire dimension\-free tradeoff and makes the total budget an exact input rather than an asymptotic operation count\.

#### Strict per\-round budgets\.

Online Frank–Wolfe already achievesO⁡\(T3/4\)O\(T^\{3/4\}\)regret with one call in every round\([Hazan and Kale, 2012](https://arxiv.org/html/2610.00254#bib.bib4);[Weibel et al\., 2026](https://arxiv.org/html/2610.00254#bib.bib12)\)\. The same order is obtained from the total\-budget tradeoff atθ=1/2\\theta=1/2, but a total or amortized count alone does not impose a roundwise cap\. We characterize every integer capB≥1B\\geq 1, obtainingΘ\(max\{T,T3/4B−1/4\}\)\\Theta\(\\max\\\{\\sqrt\{T\},T^\{3/4\}B^\{\-1/4\}\\\}\), and combine it with an independent total allowanceQQ\. The upper construction uses overlapping block computations, as in[Garber and Kretzu \(2022\)](https://arxiv.org/html/2610.00254#bib.bib9), and an independent\-copy schedule related to delayed online learning\([Joulani et al\., 2013](https://arxiv.org/html/2610.00254#bib.bib7)\)\. The additional result is a matching converse and an explicit schedule for arbitrary simultaneous caps\.

#### Loss regularity and constraint information\.

Randomized perturbed\-leader methods exploit linearity or smoothness to obtain different regret rates\([Kalai and Vempala, 2005](https://arxiv.org/html/2610.00254#bib.bib3);[Hazan and Minasyan, 2020](https://arxiv.org/html/2610.00254#bib.bib8)\)\. The corresponding linear\-oracle bounds retain dimension dependence: for linear losses, one call per round givesO⁡\(d​T\)O\(\\sqrt\{dT\}\)normalized regret; for smooth convex losses, the amortized one\-call regime givesO⁡\(\(d\+β​D/G\)​T2/3\)O\(\(\\sqrt\{d\}\+\\beta D/G\)T^\{2/3\}\)\. Our smooth analysis instead quantifies a lower bound uniform over dimensions, with the dependence onβ\\betadisplayed\. Membership and separation methods\([Mhammedi, 2022](https://arxiv.org/html/2610.00254#bib.bib10);[Mhammedi, 2025](https://arxiv.org/html/2610.00254#bib.bib11)\)use different constraint information and are not included in the linear\-oracle comparison\.

#### Lower\-bound mechanism and proof ingredients\.

Offline linear\-oracle lower bounds use the difficulty of approximating a dense simplex point by a sparse convex combination\([Lan, 2013](https://arxiv.org/html/2610.00254#bib.bib6);[Jaggi, 2013](https://arxiv.org/html/2610.00254#bib.bib5)\)\. An optimal nonsmooth offline method usesO⁡\(ε−2\)O\(\\varepsilon^\{\-2\}\)calls\([Thekumparampil et al\., 2020](https://arxiv.org/html/2610.00254#bib.bib13)\); repeating one fixed offline objective therefore does not explain the online fourth\-root tradeoff\. The present construction makes the support cost recur as new phase information arrives\. The feasibility reduction establishes the support restriction for arbitrary learners, and a conditional Hoeffding argument handles adaptive query histories\([Hoeffding, 1963](https://arxiv.org/html/2610.00254#bib.bib1)\)\. On the upper side, the distance potential is inherited from online gradient descent\([Zinkevich, 2003](https://arxiv.org/html/2610.00254#bib.bib2)\), while blocking, approximate projection, and the Frank–Wolfe gap certificate follow[Garber and Kretzu \(2022\)](https://arxiv.org/html/2610.00254#bib.bib9)and[Jaggi \(2013\)](https://arxiv.org/html/2610.00254#bib.bib5)\. The proofs below adapt these ingredients to exact total and per\-round accounting\.

Table[1](https://arxiv.org/html/2610.00254#S2.T1)reports static regret divided byG​DGD\. A strict limit applies in every physical round; a total limit applies over the horizon; an amortized count divides total work byTT\. The latter two conventions can allow calls to be concentrated at block boundaries\. Let

Ψ\(T,q\)=max\{T,Tq−1/4\},Q∗=min\{Q,BT\}\.\\Psi\(T,q\)=\\max\\\{\\sqrt\{T\},Tq^\{\-1/4\}\\\},\\qquad Q\_\{\*\}=\\min\\\{Q,BT\\\}\.\(2\.1\)TheOOentries are upper guarantees and theΘ\\Thetaentries are matching minimax bounds\. The dependence on dimensionddand smoothnessβ\\betais explicit\.

Table 1:Online regret with exact linear optimization access\. Regret is divided byG​DGD\. Prior rows report upper bounds; theΘ\\Thetaentries give matching minimax bounds in the model of Section[3](https://arxiv.org/html/2610.00254#S3)\.WorkRegret /G​DGDOracle callsFunction classBudgetPrevious upper bounds[Hazan and Kale \(2012\)](https://arxiv.org/html/2610.00254#bib.bib4)O⁡\(T3/4\)O\(T^\{3/4\}\)One per roundConvex,GG\-LipschitzStrict per\-round[Weibel et al\. \(2026\)](https://arxiv.org/html/2610.00254#bib.bib12)O⁡\(T3/4\)O\(T^\{3/4\}\)One per roundConvex,GG\-LipschitzStrict per\-round[Garber and Kretzu \(2022\)](https://arxiv.org/html/2610.00254#bib.bib9)O⁡\(T3/4\)O\(T^\{3/4\}\)At mostTTtotalConvex,GG\-LipschitzTotal[Lu et al\. \(2025\)](https://arxiv.org/html/2610.00254#bib.bib14)O⁡\(T1−θ/2\)O\(T^\{1\-\\theta/2\}\)O⁡\(T2​θ\)O\(T^\{2\\theta\}\)total per agentConvex,GG\-Lipschitz specializationTotal \(batched\)[Hazan and Minasyan \(2020\)](https://arxiv.org/html/2610.00254#bib.bib8)
Linear caseO⁡\(d​T\)O\(\\sqrt\{dT\}\)One per roundLinear,GG\-LipschitzStrict per\-round[Hazan and Minasyan \(2020\)](https://arxiv.org/html/2610.00254#bib.bib8)
Smooth caseO⁡\(\(d\+β​D/G\)CLOSEO\\big\(\(\\sqrt\{d\}\+\\beta D/G\)
OPENT2/3\)\{\}\\hskip 9\.24994ptT^\{2/3\}\\big\)At mostTTtotalConvex,GG\-Lipschitz,β\\beta\-smoothAmortizedThis paperTheorem[4\.2](https://arxiv.org/html/2610.00254#Thmtheorem2)Θ⁡\(Ψ⁡\(T,Q∗\+1\)\)\\Theta\\big\(\\Psi\(T,Q\_\{\*\}\+1\)\\big\)QQtotal;BBper roundConvex,GG\-LipschitzJointCorollary[4\.9](https://arxiv.org/html/2610.00254#Thmtheorem9)Θ⁡\(Ψ⁡\(T,Q\+1\)\)\\Theta\\big\(\\Psi\(T,Q\+1\)\\big\)At mostQQtotalConvex,GG\-LipschitzTotalCorollary[4\.10](https://arxiv.org/html/2610.00254#Thmtheorem10)Θ\(max\{T,\\Theta\\\!\\big\(\\max\\\{\\sqrt\{T\},
T3/4B−1/4\}\)\{\}\\hskip 9\.24994ptT^\{3/4\}B^\{\-1/4\}\\\}\\big\)At mostBBper roundConvex,GG\-LipschitzStrict per\-roundTheorem[5\.14](https://arxiv.org/html/2610.00254#Thmtheorem14)Lower:Ω⁡\(Ψλ​\(T,Q∗\+1\)\)\\Omega\(\\Psi\_\{\\lambda\}\(T,Q\_\{\*\}\+1\)\)
Upper:O⁡\(Ψ⁡\(T,Q∗\+1\)\)O\(\\Psi\(T,Q\_\{\*\}\+1\)\)QQtotal;BBper roundConvex,GG\-Lipschitz,β\\beta\-smoothJoint
HereQ∗=min⁡\{Q,B​T\}Q\_\{\*\}=\\min\\\{Q,BT\\\},Ψ\(T,q\)=max\{T,Tq−1/4\}\\Psi\(T,q\)=\\max\\\{\\sqrt\{T\},Tq^\{\-1/4\}\\\},λ=β​D/\(3​G\)\\lambda=\\beta D/\(\\sqrt\{3\}G\), andΨλ\(T,q\)=max\{T,Tmin\{q−1/4,\(λ/q\)1/3\}\}\\Psi\_\{\\lambda\}\(T,q\)=\\max\\\{\\sqrt\{T\},T\\min\\\{q^\{\-1/4\},\(\\lambda/q\)^\{1/3\}\\\}\\\}\. Also,0≤θ≤10\\leq\\theta\\leq 1andddis the dimension\. The Lu et al\. row reports convex regret for a fixed communication network\. The two Hazan–Minasyan guarantees are in expectation\. The smooth bounds match whenλ≥\(Q∗\+1\)1/4\\lambda\\geq\(Q\_\{\*\}\+1\)^\{1/4\}orQ∗\+1≥T2Q\_\{\*\}\+1\\geq T^\{2\}\.

## 3System model and preliminaries

### 3\.1Online protocol and oracle access

The learner is given a finite\-dimensional Euclidean spaceEE, a horizonT≥1T\\geq 1, constantsG,D\>0G,D\>0, oracle budgets, and a ballC=BE​\(c,r\)C=B\_\{E\}\(c,r\)withr\>0r\>0\. The unknown compact convex setKKsatisfiesC⊆KC\\subseteq Kanddiam⁡\(K\)≤D\\operatorname\{diam\}\(K\)\\leq D\. All further constraint information is obtained from a fixed measurable exact oracle

𝒪K​\(v\)∈arg​minx∈K⁡⟨v,x⟩\.\\mathcal\{O\}\_\{K\}\(v\)\\in\\argmin\_\{x\\in K\}\\langle v,x\\rangle\.\(3\.1\)The oracle’s tie\-breaking rule is fixed\. Query directions are arbitrary\. In roundtt, the learner choosesxtx\_\{t\}and then observes a globally defined convexGG\-Lipschitz lossft:E→ℝf\_\{t\}:E\\to\\mathbb\{R\}\. Full loss feedback is allowed; the upper algorithms use only a subgradient at the played action\. Static regret is

RegT=∑t=1Tft​\(xt\)−min⁡∑t=1Tu∈K⁡ft​\(u\)\.\\operatorname\{Reg\}\_\{T\}=\\sum\_\{t=1\}^\{T\}f\_\{t\}\(x\_\{t\}\)\-\\min\_\{u\\in K\}\\sum\_\{t=1\}^\{T\}f\_\{t\}\(u\)\.\(3\.2\)All decision rules are measurable and finish each round\. A randomized learner samples a seed at initialization and uses deterministic rules conditional on that seed\.

###### Definition 3\.1\(Admissibility\)\.

A learner is admissible if it is feasible almost surely on every compact convex set, fixed exact oracle, and loss sequence consistent with the supplied data\. Its total number of calls is at most the integerQ≥0Q\\geq 0almost surely\. For a finite strict capB≥1B\\geq 1, at mostBBcalls are made in each physical round\. Every call is charged, with preprocessing assigned to round one\. We writeB=∞B=\\inftywhen only the total budget is imposed\.

Calls can occur before or after a round’s feedback, subject to these caps and the temporal order of the observations\. Calls made before choosingxtx\_\{t\}may depend only on feedback from earlier rounds\. Afterftf\_\{t\}is observed, further calls may use that feedback but can affect only future actions; all calls made in either part of roundttcount toward that round’s cap\. The diameter is an upper bound, so a smaller body containingCCremains a consistent instance\. Loss formulas are globally defined and have no promised relationship to the feasible set; the same formulas are used when comparing consistent bodies\. The learner may perform arbitrary intermediate computation, including optimization over the hull of known feasible points\. No membership, separation, or projection oracle forKKis supplied\.

### 3\.2Minimax regret and elementary inequalities

Letℛjoint​\(T,Q,B,G,D\)\\mathcal\{R\}\_\{\\mathrm\{joint\}\}\(T,Q,B;G,D\)be the infimum, over admissible learners, of worst\-case expected regret\. The supremum ranges over finite dimensions, supplied balls, consistent bodies and fixed oracles, and deterministic oblivious loss sequences; expectation is over the learner’s seed\. The total\-only and strict\-only values are

ℛ⁡\(T,Q,G,D\)\\displaystyle\\mathcal\{R\}\(T,Q;G,D\)=ℛjoint​\(T,Q,∞,G,D\),\\displaystyle=\\mathcal\{R\}\_\{\\mathrm\{joint\}\}\(T,Q,\\infty;G,D\),\(3\.3\)ℛround​\(T,B,G,D\)\\displaystyle\\mathcal\{R\}\_\{\\mathrm\{round\}\}\(T,B;G,D\)=ℛjoint​\(T,B​T,B,G,D\)\.\\displaystyle=\\mathcal\{R\}\_\{\\mathrm\{joint\}\}\(T,BT,B;G,D\)\.For a prescribedβ≥0\\beta\\geq 0, the smooth valueℛjoint,β\\mathcal\{R\}\_\{\\mathrm\{joint\},\\beta\}uses the same definition with the additional requirement

∥∇ft​\(x\)−∇ft​\(y\)∥2≤β​∥x−y∥2\(x,y∈E\)\.\\lVert\\nabla f\_\{t\}\(x\)\-\\nabla f\_\{t\}\(y\)\\rVert\_\{2\}\\leq\\beta\\lVert x\-y\\rVert\_\{2\}\\qquad\(x,y\\in E\)\.\(3\.4\)The smoothness bound is supplied to the learner\.

For any played subgradientgt∈∂ft​\(xt\)g\_\{t\}\\in\\partial f\_\{t\}\(x\_\{t\}\), convexity and Lipschitz continuity give

ft​\(xt\)−ft​\(u\)≤⟨gt,xt−u⟩,∥gt∥2≤G\.f\_\{t\}\(x\_\{t\}\)\-f\_\{t\}\(u\)\\leq\\langle g\_\{t\},x\_\{t\}\-u\\rangle,\\qquad\\lVert g\_\{t\}\\rVert\_\{2\}\\leq G\.\(3\.5\)The upper proof uses this inequality together with a squared\-distance potential\. The lower proof uses the fact that a nonnegative vector with total massaaon at mostNNcoordinates has Euclidean norm at leasta/Na/\\sqrt\{N\}\. Both statements apply independently of the ambient dimension\.

## 4Sharp regret under simultaneous oracle budgets

The effective total allowanceQ∗=min⁡\{Q,B​T\}Q\_\{\*\}=\\min\\\{Q,BT\\\}determines the joint\-budget rate\. The upper bound below enforces both budgets on every execution, while the lower bound holds for arbitrary randomized learners\.

###### Theorem 4\.2\(Joint\-budget characterization\)\.

LetT≥1T\\geq 1andQ≥0Q\\geq 0be integers\. LetBBbe a positive integer or∞\\infty, and setq∗=1\+min⁡\{Q,B​T\}q\_\{\*\}=1\+\\min\\\{Q,BT\\\}\. Then

G​D100​Ψ​\(T,q∗\)≤ℛjoint​\(T,Q,B,G,D\)≤6​G​D​Ψ​\(T,q∗\)\.\\frac\{GD\}\{100\}\\Psi\(T,q\_\{\*\}\)\\leq\\mathcal\{R\}\_\{\\mathrm\{joint\}\}\(T,Q,B;G,D\)\\leq 6GD\\Psi\(T,q\_\{\*\}\)\.\(4\.1\)The upper bound is attained by a deterministic learner and holds for every realized adaptive loss sequence\. For each learner, the lower bound is witnessed by a deterministic oblivious loss sequence on a fixed body with a fixed exact oracle\.

### 4\.1Achievability: counted updates and interleaved blocks

The construction combines an approximate\-gradient update with a block schedule\. We first bound the number of calls required by one update, then telescope the distance potential over blocks, and finally allocate those calls to physical rounds\. The stopping rule is the quadratic Frank–Wolfe gap certificate\([Jaggi, 2013](https://arxiv.org/html/2610.00254#bib.bib5)\); the use of blocked approximate projections follows[Garber and Kretzu \(2022\)](https://arxiv.org/html/2610.00254#bib.bib9)\.

#### One feasible update\.

The ideal projected\-gradient step would projecty=x−η​gy=x\-\\eta gontoKK\. Instead, we minimize the quadratic∥z−y∥22/2\\lVert z\-y\\rVert\_\{2\}^\{2\}/2approximately overKKusing only convex combinations of feasible points\. The required certificate is a comparator\-uniform distance inequality, not an accurate reconstruction of the projection\. Starting fromxxkeeps the initial quadratic value small enough to bound the number of failed stopping tests\.

###### Lemma 4\.4\(Counted approximate gradient step\)\.

Letx∈Kx\\in K,∥g∥2≤A\\lVert g\\rVert\_\{2\}\\leq A,A\>0A\>0,η\>0\\eta\>0, andη​A≤D\\eta A\\leq D\. For any integerH≥1H\\geq 1, sety=x−η​gy=x\-\\eta gandε=η​A​D/H\\varepsilon=\\eta AD/\\sqrt\{H\}\. Algorithm[4\.1](https://arxiv.org/html/2610.00254#S4.SS1.SSS0.Px1)returns a feasiblex\+x^\{\+\}in at mostHHoracle calls, including its successful test, with

∥x\+−u∥22≤∥x−η​g−u∥22\+2​ε\(u∈K\)\.\\lVert x^\{\+\}\-u\\rVert\_\{2\}^\{2\}\\leq\\lVert x\-\\eta g\-u\\rVert\_\{2\}^\{2\}\+2\\varepsilon\\qquad\(u\\in K\)\.\(4\.2\)

\{algorithm2e\}

\[htbp\]Counted feasible update\\KwInx∈Kx\\in K,gg,A\>0A\>0,∥g∥2≤A\\lVert g\\rVert\_\{2\}\\leq A,0<η​A≤D0<\\eta A\\leq D, integerH≥1H\\geq 1y←x−η​gy\\leftarrow x\-\\eta g;z←xz\\leftarrow x;ε←η​A​D/H\\varepsilon\\leftarrow\\eta AD/\\sqrt\{H\}\\Forj=1,…,Hj=1,\\ldots,Hv←𝒪K​\(z−y\)v\\leftarrow\\mathcal\{O\}\_\{K\}\(z\-y\);Γ←⟨z−y,z−v⟩\\Gamma\\leftarrow\\langle z\-y,z\-v\\rangle\\IfΓ≤ε\\Gamma\\leq\\varepsilon\\KwRetzzγ←min⁡\{Γ/D2,1\}\\gamma\\leftarrow\\min\\\{\\Gamma/D^\{2\},1\\\};z←\(1−γ\)​z\+γ​vz\\leftarrow\(1\-\\gamma\)z\+\\gamma v

###### Proof\.

Leth⁡\(z\)=∥z−y∥22/2h\(z\)=\\lVert z\-y\\rVert\_\{2\}^\{2\}/2\. Initially,

h⁡\(x\)=η2​∥g∥222≤η2​A22\.h\(x\)=\\frac\{\\eta^\{2\}\\lVert g\\rVert\_\{2\}^\{2\}\}\{2\}\\leq\\frac\{\\eta^\{2\}A^\{2\}\}\{2\}\.Each iterate is a convex combination of feasible points\. Since∥z−v∥2≤D\\lVert z\-v\\rVert\_\{2\}\\leq D, quadratic expansion gives

h⁡\(z\+γ⁡\(v−z\)\)≤h⁡\(z\)−γ​Γ\+γ2​D22\.h\(z\+\\gamma\(v\-z\)\)\\leq h\(z\)\-\\gamma\\Gamma\+\\frac\{\\gamma^\{2\}D^\{2\}\}\{2\}\.The tolerance satisfiesε≤D2\\varepsilon\\leq D^\{2\}\. If a test fails andΓ≤D2\\Gamma\\leq D^\{2\}, takingγ=Γ/D2\\gamma=\\Gamma/D^\{2\}decreaseshhbyΓ2/\(2​D2\)\>ε2/\(2​D2\)\\Gamma^\{2\}/\(2D^\{2\}\)\>\\varepsilon^\{2\}/\(2D^\{2\}\)\. IfΓ\>D2\\Gamma\>D^\{2\}, takingγ=1\\gamma=1decreaseshhby more thanD2/2≥ε2/\(2​D2\)D^\{2\}/2\\geq\\varepsilon^\{2\}/\(2D^\{2\}\)\. Every failed test therefore decreaseshhby more than

ε22​D2=η2​A22​H\.\\frac\{\\varepsilon^\{2\}\}\{2D^\{2\}\}=\\frac\{\\eta^\{2\}A^\{2\}\}\{2H\}\.There cannot beHHfailures, since their combined decrease would exceed the initial value of the nonnegative functionhh\. A successful test consequently occurs among the firstHHcalls; its oracle call has been counted\.

At that test, minimality ofvvgives⟨z−y,z−u⟩≤⟨z−y,z−v⟩=Γ≤ε\\langle z\-y,z\-u\\rangle\\leq\\langle z\-y,z\-v\\rangle=\\Gamma\\leq\\varepsilonfor everyu∈Ku\\in K\. Thus

∥z−u∥22=∥y−u∥22−∥z−y∥22\+2​⟨z−y,z−u⟩≤∥y−u∥22\+2​ε,\\lVert z\-u\\rVert\_\{2\}^\{2\}=\\lVert y\-u\\rVert\_\{2\}^\{2\}\-\\lVert z\-y\\rVert\_\{2\}^\{2\}\+2\\langle z\-y,z\-u\\rangle\\leq\\lVert y\-u\\rVert\_\{2\}^\{2\}\+2\\varepsilon,which is \([4\.2](https://arxiv.org/html/2610.00254#S4.E2)\) withx\+=zx^\{\+\}=z\. ∎

#### Balanced blocks\.

Partition theTTrounds intoMMnonempty consecutive blocks of lengthsbib\_\{i\}differing by at most one, with the longer blocks first\. Write

S=∑i=1Mbi2=T2M\+r0​\(1−r0/M\)≤T2M\+M4,r0=T−M⁡⌊T/M⌋\.S=\\sum\_\{i=1\}^\{M\}b\_\{i\}^\{2\}=\\frac\{T^\{2\}\}\{M\}\+r\_\{0\}\(1\-r\_\{0\}/M\)\\leq\\frac\{T^\{2\}\}\{M\}\+\\frac\{M\}\{4\},\\qquad r\_\{0\}=T\-M\\lfloor T/M\\rfloor\.\(4\.3\)Play a fixed pointxix\_\{i\}throughout blockii, starting atcc, and letgig\_\{i\}be the sum of its played subgradients, so∥gi∥2≤G​bi\\lVert g\_\{i\}\\rVert\_\{2\}\\leq Gb\_\{i\}\. Chooseη=D/\(G​S\)\\eta=D/\(G\\sqrt\{S\}\)\. On each nonterminal block apply Algorithm[4\.1](https://arxiv.org/html/2610.00254#S4.SS1.SSS0.Px1)withAi=G​biA\_\{i\}=Gb\_\{i\}and toleranceεi=η​D​G​bi/H\\varepsilon\_\{i\}=\\eta DGb\_\{i\}/\\sqrt\{H\}\. Its condition holds sincebi≤Sb\_\{i\}\\leq\\sqrt\{S\}\.

\{algorithm2e\}

\[htbp\]Blocked online optimization with a counted update\\KwInHorizonTT, integers1≤M≤T1\\leq M\\leq TandH≥1H\\geq 1,G,D\>0G,D\>0, centerc∈Kc\\in KPartition the horizon into consecutive blocksIiI\_\{i\}of balanced lengthsbib\_\{i\}, longer blocks firstS←∑i=1Mbi2S\\leftarrow\\sum\_\{i=1\}^\{M\}b\_\{i\}^\{2\};η←D/\(G​S\)\\eta\\leftarrow D/\(G\\sqrt\{S\}\);x1←cx\_\{1\}\\leftarrow c\\Fori=1,…,Mi=1,\\ldots,Mgi←0g\_\{i\}\\leftarrow 0\\ForEacht∈Iit\\in I\_\{i\}Playxix\_\{i\}, observeftf\_\{t\}, choosest∈∂ft​\(xi\)s\_\{t\}\\in\\partial f\_\{t\}\(x\_\{i\}\)gi←gi\+stg\_\{i\}\\leftarrow g\_\{i\}\+s\_\{t\}\\Ifi<Mi<Mxi\+1←x\_\{i\+1\}\\leftarrowAlgorithm[4\.1](https://arxiv.org/html/2610.00254#S4.SS1.SSS0.Px1)with\(xi,gi,G​bi,η,H\)\(x\_\{i\},g\_\{i\},Gb\_\{i\},\\eta,H\)

###### Proposition 4\.5\(Exact finite\-budget upper bound\)\.

For any integers1≤M≤T1\\leq M\\leq TandH≥1H\\geq 1, this algorithm makes at most\(M−1\)​H\(M\-1\)Hcalls and satisfies

RegT≤G​D​\(∑i=1Mbi2\+T−bMH\)\.\\operatorname\{Reg\}\_\{T\}\\leq GD\\left\(\\sqrt\{\\sum\_\{i=1\}^\{M\}b\_\{i\}^\{2\}\}\+\\frac\{T\-b\_\{M\}\}\{\\sqrt\{H\}\}\\right\)\.\(4\.4\)The terminal block requires no update\.

###### Proof\.

For any comparatoru∈Ku\\in K, convexity bounds regret by∑i⟨gi,xi−u⟩\\sum\_\{i\}\\langle g\_\{i\},x\_\{i\}\-u\\rangle\. Fori<Mi<M, expansion of \([4\.2](https://arxiv.org/html/2610.00254#S4.E2)\) yields

⟨gi,xi−u⟩≤∥xi−u∥22−∥xi\+1−u∥222​η\+η2​∥gi∥22\+εiη\.\\langle g\_\{i\},x\_\{i\}\-u\\rangle\\leq\\frac\{\\lVert x\_\{i\}\-u\\rVert\_\{2\}^\{2\}\-\\lVert x\_\{i\+1\}\-u\\rVert\_\{2\}^\{2\}\}\{2\\eta\}\+\\frac\{\\eta\}\{2\}\\lVert g\_\{i\}\\rVert\_\{2\}^\{2\}\+\\frac\{\\varepsilon\_\{i\}\}\{\\eta\}\.Fori=Mi=M, Young’s inequality gives⟨gM,xM−u⟩≤∥xM−u∥22/\(2​η\)\+η​∥gM∥22/2\\langle g\_\{M\},x\_\{M\}\-u\\rangle\\leq\\lVert x\_\{M\}\-u\\rVert\_\{2\}^\{2\}/\(2\\eta\)\+\\eta\\lVert g\_\{M\}\\rVert\_\{2\}^\{2\}/2\. The sum telescopes to

D22​η\+η​G2​S2\+G​DH​∑i<Mbi=G​D​S\+G​D​\(T−bM\)H\.\\frac\{D^\{2\}\}\{2\\eta\}\+\\frac\{\\eta G^\{2\}S\}\{2\}\+\\frac\{GD\}\{\\sqrt\{H\}\}\\sum\_\{i<M\}b\_\{i\}=GD\\sqrt\{S\}\+\\frac\{GD\(T\-b\_\{M\}\)\}\{\\sqrt\{H\}\}\.There are exactlyM−1M\-1possible updates, each using at mostHHcalls\. This proves both claims, includingM=1M=1\. ∎

#### The total\-budget specialization\.

Set

M=min⁡\{T,⌊1\+1\+4​Q2⌋\},H=M\.M=\\min\\\!\\left\\\{T,\\left\\lfloor\\frac\{1\+\\sqrt\{1\+4Q\}\}\{2\}\\right\\rfloor\\right\\\},\\qquad H=M\.\(4\.5\)ThenM⁡\(M−1\)≤QM\(M\-1\)\\leq Q, so Proposition[4\.5](https://arxiv.org/html/2610.00254#Thmtheorem5)respects the hard budget\. By \([4\.3](https://arxiv.org/html/2610.00254#S4.E3)\) andM≤TM\\leq T,

RegT≤\(1\+5/2\)​G​D​TM\.\\operatorname\{Reg\}\_\{T\}\\leq\(1\+\\sqrt\{5\}/2\)GD\\frac\{T\}\{\\sqrt\{M\}\}\.\(4\.6\)IfM=TM=T, this is already less than3​G​D​T3GD\\sqrt\{T\}\. Otherwise maximality in \([4\.5](https://arxiv.org/html/2610.00254#S4.E5)\) givesQ\+1≤M⁡\(M\+1\)≤2​M2Q\+1\\leq M\(M\+1\)\\leq 2M^\{2\}, so the right side is at most\(1\+5/2\)​21/4​G​D​T/\(Q\+1\)1/4<3​G​D​T/\(Q\+1\)1/4\(1\+\\sqrt\{5\}/2\)2^\{1/4\}GDT/\(Q\+1\)^\{1/4\}<3GDT/\(Q\+1\)^\{1/4\}\. AtQ=0Q=0, the exact bound \([4\.4](https://arxiv.org/html/2610.00254#S4.E4)\) isG​D​TGDT, with no calls\. All inequalities are pathwise and comparator\-uniform\. The two terms in \([4\.4](https://arxiv.org/html/2610.00254#S4.E4)\) explain the design\. More blocks reduce the online\-gradient term, approximatelyG​D​T/MGDT/\\sqrt\{M\}for balanced blocks\. More calls per update reduce the accumulated approximation term, approximatelyG​D​T/HGDT/\\sqrt\{H\}\. With total work on the order ofM​HMH, balancingMMandHHproduces the fourth\-root tradeoff\. The exact choice usesM⁡\(M−1\)≤QM\(M\-1\)\\leq Q, because the terminal update is absent\. For example, two blocks are available with two calls\. The same balance underlies the prior total\-budget tradeoffs in Section[2](https://arxiv.org/html/2610.00254#S2)\.

#### Scheduling under a strict cap\.

A single blocked copy may concentrate its calls at block boundaries\. To distribute this work over rounds, run one copy on the odd blocks and one on the even blocks, with both copies initialized atcc\. An update based on blockiiis computed during blocki\+1i\+1and used in blocki\+2i\+2\. Each copy therefore receives its next action before its next assigned block starts\.

###### Proposition 4\.6\(Finite\-call interleaved schedule\)\.

Partition the horizon intoMMbalanced blocks, and choose an integerH≥1H\\geq 1\. Forℓ∈\{1,2\}\\ell\\in\\\{1,2\\\}, letSℓS\_\{\\ell\}be the sum of squared block lengths assigned to copyℓ\\ell\. LetWWbe the sum of the lengths of all blocks except the terminal block of each nonempty copy\. If

H≤B​⌊T/M⌋H\\leq B\\lfloor T/M\\rfloor\(4\.7\)whenever an update is required, the two\-copy algorithm makes at most\(M−2\)\+​H\(M\-2\)\_\{\+\}Hcalls, at mostBBin any round, and satisfies

RegT≤G​D​\(S1\+S2\+WH\)\.\\operatorname\{Reg\}\_\{T\}\\leq GD\\left\(\\sqrt\{S\_\{1\}\}\+\\sqrt\{S\_\{2\}\}\+\\frac\{W\}\{\\sqrt\{H\}\}\\right\)\.\(4\.8\)Here\(M−2\)\+=max⁡\{M−2,0\}\(M\-2\)\_\{\+\}=\\max\\\{M\-2,0\\\}, and empty copies contribute zero\.

###### Proof\.

Use step sizeηℓ=D/\(G​Sℓ\)\\eta\_\{\\ell\}=D/\(G\\sqrt\{S\_\{\\ell\}\}\)for each nonempty copy\. At the end of a nonterminal block of that copy, its aggregate gradient is known\. Execute the next counted update during the intervening block, using at mostBBcalls in each physical round\. Every intervening block has at least⌊T/M⌋\\lfloor T/M\\rfloorrounds, so \([4\.7](https://arxiv.org/html/2610.00254#S4.E7)\) guarantees completion\. Only one update is computed in an intervening block\. For example, during block two, the odd copy computes the action for block three from the gradients of block one, while the even copy plays its initial action\. During block three, the even copy computes the action for block four\.

The odd and even copies have⌈M/2⌉\\lceil M/2\\rceiland⌊M/2⌋\\lfloor M/2\\rfloorblocks\. Each nonempty copy omits its final update, leaving\(M−2\)\+\(M\-2\)\_\{\+\}updates, each of at mostHHcalls\. Applying the distance\-potential proof of Proposition[4\.5](https://arxiv.org/html/2610.00254#Thmtheorem5)separately to the two copies gives \([4\.8](https://arxiv.org/html/2610.00254#S4.E8)\), for every common comparatoru∈Ku\\in K\. ∎

WithH=MH=M, the balanced\-block identity \([4\.3](https://arxiv.org/html/2610.00254#S4.E3)\), Cauchy–Schwarz, andW≤TW\\leq Tgive

RegT≤\(1\+5/2\)​G​D​TM,N≤M​\(M−2\)\+\.\\operatorname\{Reg\}\_\{T\}\\leq\(1\+\\sqrt\{5/2\}\)GD\\frac\{T\}\{\\sqrt\{M\}\},\\qquad N\\leq M\(M\-2\)\_\{\+\}\.\(4\.9\)The termS1\+S2\\sqrt\{S\_\{1\}\}\+\\sqrt\{S\_\{2\}\}accounts for running two learning processes\. The additional factor is constant becauseS1\+S2S\_\{1\}\+S\_\{2\}is the squared\-length sum of the original balanced partition\.

#### Joint\-budget parameter choice\.

Put

S0=min⁡\{Q\+1,B​T\},M=min⁡\{T,max⁡\{1,⌊S0/2⌋\}\},H=M\.S\_\{0\}=\\min\\\{Q\+1,BT\\\},\\qquad M=\\min\\\!\\left\\\{T,\\max\\\!\\left\\\{1,\\left\\lfloor\\sqrt\{S\_\{0\}/2\}\\right\\rfloor\\right\\\}\\right\\\},\\qquad H=M\.\(4\.10\)The total budget enters asQ\+1Q\+1because each copy omits its terminal update, whereas the physical\-round capacity has exactlyB​TBTcall slots and receives no such additive term\. If an update is needed, thenM≥3M\\geq 3andM2≤S0/2M^\{2\}\\leq S\_\{0\}/2\. Since⌊T/M⌋≥T/\(2​M\)\\lfloor T/M\\rfloor\\geq T/\(2M\), this implies \([4\.7](https://arxiv.org/html/2610.00254#S4.E7)\) for finiteBB\. Moreover,M≥3M\\geq 3impliesS0≥18S\_\{0\}\\geq 18, henceQ≥17Q\\geq 17, and thereforeM​\(M−2\)\+≤M2≤\(Q\+1\)/2≤QM\(M\-2\)\_\{\+\}\\leq M^\{2\}\\leq\(Q\+1\)/2\\leq Q\. WhenM≤2M\\leq 2, there are no updates and both caps hold directly\.

The elementary boundmax⁡\{1,⌊x⌋\}≥x/2\\max\\\{1,\\lfloor x\\rfloor\\\}\\geq x/2forx≥0x\\geq 0, followed byS0≥q∗/2S\_\{0\}\\geq q\_\{\*\}/2, yields

M≥min⁡\{T,S0\}2​2≥min⁡\{T,q∗\}4\.M\\geq\\frac\{\\min\\\{T,\\sqrt\{S\_\{0\}\}\\\}\}\{2\\sqrt\{2\}\}\\geq\\frac\{\\min\\\{T,\\sqrt\{q\_\{\*\}\}\\\}\}\{4\}\.\(4\.11\)Consequently \([4\.9](https://arxiv.org/html/2610.00254#S4.E9)\) gives

RegT≤2​\(1\+5/2\)​G​D​Ψ​\(T,q∗\)<6​G​D​Ψ​\(T,q∗\)\.\\operatorname\{Reg\}\_\{T\}\\leq 2\(1\+\\sqrt\{5/2\}\)GD\\Psi\(T,q\_\{\*\}\)<6GD\\Psi\(T,q\_\{\*\}\)\.\(4\.12\)All updates use gradients already observed by their own copy, so the argument holds for every realized loss sequence, including adaptive sequences\. The construction has also shown exactly where the two budgets enter:QQlimits the number of solves, andBBlimits the time available to finish each solve\.

### 4\.2Lower bound: feasible hulls and recurring support cost

The lower bound has two components\. Universal feasibility restricts what an action can do with a finite transcript\. A product\-body construction then makes acquiring useful new replies necessary in many phases\. Throughout, the body and oracle are fixed independently of the learner’s seed and of the sampled losses\.

###### Lemma 4\.7\(Feasible actions on a finite\-vertex oracle\)\.

LetK=conv⁡\(V\)K=\\operatorname\{conv\}\(V\)for a finite setVVwith a fixed total order, and letC⊆KC\\subseteq Kbe the supplied ball\. Suppose the oracle returns the first minimizing point ofVV\. For every admissible learner and every fixed globally defined loss sequence, almost surely

xt∈conv⁡\(C∪St\),x\_\{t\}\\in\\operatorname\{conv\}\(C\\cup S\_\{t\}\),\(4\.13\)whereStS\_\{t\}is the set of replies received beforextx\_\{t\}\. The conclusion holds simultaneously over any finite collection of loss sequences\.

###### Proof\.

For eachS⊆VS\\subseteq V, fix the alternative bodyKS=conv⁡\(C∪S\)K\_\{S\}=\\operatorname\{conv\}\(C\\cup S\)\. It contains the same ball, is full\-dimensional, and has diameter at mostDD\. Define its oracle as follows: return the first minimizing point ofSSwhenever its value is no larger than the minimum overCC; otherwise return a ball minimizer\. The minimum over the empty set is\+∞\+\\infty\. For a nonzero directionvv, the ball minimizer isc−r​v/∥v∥2c\-rv/\\lVert v\\rVert\_\{2\}; atv=0v=0usecc\. This defines a fixed measurable exact oracle on each alternative body before any interaction\.

If the original oracle answers a query withw∈Sw\\in S, thenwwminimizes overC∪SC\\cup S\. Every tied point inSSalso minimizes overKK, so none precedeswwin the fixed order\. The alternative oracle therefore gives exactly the same reply, including ties with the ball\.

Fix a loss sequence\. LetFSF\_\{S\}be the probability\-one set of seeds on which the learner is feasible onKSK\_\{S\}with this oracle and these same globally defined losses\. There are finitely many subsets, henceF=⋂S⊆VFSF=\\bigcap\_\{S\\subseteq V\}F\_\{S\}has probability one\. For a seed inFF, take the actual reply setStS\_\{t\}on the original body\. Running the learner onKStK\_\{S\_\{t\}\}with the same seed reproduces the transcript up toxtx\_\{t\}: each previous original reply belongs toStS\_\{t\}, and the query, action, and feedback rules consequently agree by induction\. The reproduced action is feasible onKStK\_\{S\_\{t\}\}, proving \([4\.13](https://arxiv.org/html/2610.00254#S4.E13)\)\. A further finite intersection covers a finite collection of losses\. ∎

The order of quantifiers is essential: the finite family of alternative bodies is fixed first, the events on which feasibility holds are intersected second, and the realized transcript selectsStS\_\{t\}only afterward\. Conversely, every point inconv⁡\(C∪St\)\\operatorname\{conv\}\(C\\cup S\_\{t\}\)is feasible on every consistent convex body, because it is a convex combination of known feasible points\.

This conclusion does not restrict computation over the known hull\. The learner may solve any auxiliary optimization over it, discard or reweight replies, and choose any adaptive query direction\. What it cannot do is certify feasibility outside the hull from this transcript alone\. The same restriction applies when the hard body is a product: only the oracle replies and supplied ball are available as constraint information\.

###### Proposition 4\.8\(Fixed\-body high\-probability lower bound\)\.

FixT,QT,Qand0<δ<1/20<\\delta<1/2, and writeq=Q\+1q=Q\+1\. There exist a fixed full\-dimensional body, supplied ball, fixed deterministic exact oracle, and finite distribution of oblivious convexGG\-Lipschitz loss sequences such that every admissible learner with budgetQQsatisfies

ℙf,ω\{RegT≥G​D40max\{T,Tq1/4\}\}≥1−δ\.\\mathbb\{P\}\_\{f,\\omega\}\\\!\\left\\\{\\operatorname\{Reg\}\_\{T\}\\geq\\frac\{GD\}\{40\}\\max\\\!\\left\\\{\\sqrt\{T\},\\frac\{T\}\{q^\{1/4\}\}\\right\\\}\\right\\\}\\geq 1\-\\delta\.\(4\.14\)Every sequence has a common minimizer\. For each learner, a deterministic sequence in the support satisfies the same bound over its seed alone\. Forq≤T2q\\leq T^\{2\}, the dimension isO⁡\(q​log⁡\(q/δ\)\)O\(\\sqrt\{q\}\\log\(q/\\delta\)\); atδ=1/4\\delta=1/4the supplied radius is at leastD/\(256​6​q\)D/\(256\\sqrt\{6q\}\)\. Forq\>T2q\>T^\{2\}, dimensionO⁡\(T​log⁡\(T/δ\)\)O\(T\\log\(T/\\delta\)\)suffices\.

###### Proof\.

#### Construction and common minimizer\.

The cube coordinates carry fresh phase information, while the simplex coordinates will penalize concentration on too few newly acquired replies\. Using separate cube blocks lets one comparator optimize all phases simultaneously; using a shared simplex ensures that the cost depends on how much weight an action places on its new replies\.

AssumeG=D=1G=D=1andq=Q\+1≤T2q=Q\+1\\leq T^\{2\}\. Set

m=⌈q⌉,L=⌊T/m⌋,n=64​m,k=⌈8​log⁡m​qδ⌉,a=1/6\.m=\\lceil\\sqrt\{q\}\\rceil,\\quad L=\\lfloor T/m\\rfloor,\\quad n=64m,\\quad k=\\left\\lceil 8\\log\\frac\{mq\}\{\\delta\}\\right\\rceil,\\quad a=1/\\sqrt\{6\}\.\(4\.15\)Work temporarily in the affine Euclidean spaceℋ=ℝm​k×\{w∈ℝn:𝟏⊤​w=a\}\\mathcal\{H\}=\\mathbb\{R\}^\{mk\}\\times\\\{w\\in\\mathbb\{R\}^\{n\}:\\mathbf\{1\}^\{\\top\}w=a\\\}\. WithΔn=\{w≥0:𝟏⊤​w=1\}\\Delta\_\{n\}=\\\{w\\geq 0:\\mathbf\{1\}^\{\\top\}w=1\\\}, define

K\\displaystyle K=\[−am​k,am​k\]m​k×a​Δn,\\displaystyle=\\left\[\-\\frac\{a\}\{\\sqrt\{mk\}\},\\frac\{a\}\{\\sqrt\{mk\}\}\\right\]^\{mk\}\\times a\\Delta\_\{n\},c\\displaystyle c=\(0,a​𝟏/n\),\\displaystyle=\(0,a\\mathbf\{1\}/n\),\(4\.16\)C\\displaystyle C=Bℋ​\(c,r\),\\displaystyle=B\_\{\\mathcal\{H\}\}\(c,r\),r\\displaystyle r=a2​max⁡\{m​k,n\}\.\\displaystyle=\\frac\{a\}\{2\\max\\\{\\sqrt\{mk\},n\\\}\}\.\(4\.17\)The cube and simplex have diameters2​a2aand2​a\\sqrt\{2\}a, respectively, soKKhas diameter one in the product metric\. A radius\-rrdisplacement fromccchanges every coordinate by at mostrr: the cube constraints remain satisfied and every simplex coordinate stays at leasta/\(2​n\)a/\(2n\)\. ThusC⊆KC\\subseteq K, andKKis full\-dimensional inℋ\\mathcal\{H\}, of dimensionm​k\+n−1mk\+n\-1\. An affine isometry identifies this space with an ordinary Euclidean space without changing any oracle or distance statement\. Fix an order on the vertices\(a​s/m​k,a​eℓ\)\(as/\\sqrt\{mk\},ae\_\{\\ell\}\),s∈\{−1,1\}m​ks\\in\\\{\-1,1\\\}^\{mk\}, and always return the first minimizer\.

Sample independent uniform sign vectorsσj∈\{−1,1\}k\\sigma\_\{j\}\\in\\\{\-1,1\\\}^\{k\}and setuj=σj/ku\_\{j\}=\\sigma\_\{j\}/\\sqrt\{k\}\. In phasejj, consisting ofLLrounds, reveal the loss

ft​\(z,w\)=12​\(⟨uj,zj⟩\+∥w∥2\)\.f\_\{t\}\(z,w\)=\\frac\{1\}\{\\sqrt\{2\}\}\\bigl\(\\langle u\_\{j\},z\_\{j\}\\rangle\+\\lVert w\\rVert\_\{2\}\\bigr\)\.\(4\.18\)The remainingT−m​LT\-mLlosses are zero\. These are globally convex and11\-Lipschitz onℋ\\mathcal\{H\}, since the two components in \([4\.18](https://arxiv.org/html/2610.00254#S4.E18)\) act on orthogonal coordinate spaces and each has Lipschitz constant one\. The point

zj∗=−aσj/m​k\(j=1,…,m\),w∗=a𝟏/nz\_\{j\}^\{\*\}=\-a\\sigma\_\{j\}/\\sqrt\{mk\}\\quad\(j=1,\\ldots,m\),\\qquad w^\{\*\}=a\\mathbf\{1\}/n\(4\.19\)minimizes every loss overKK: the optimal cube value is−a/m\-a/\\sqrt\{m\}, and the minimum simplex norm isa/na/\\sqrt\{n\}\. All instantaneous regret terms are consequently nonnegative\.

#### Previously acquired replies\.

For independent uniform signsξi\\xi\_\{i\}and any fixeds∈\[−1,1\]ks\\in\[\-1,1\]^\{k\}, the exponential\-moment calculation

𝔼exp\(−12∑isiξi\)=∏icosh\(si/2\)≤ek/8\\mathbb\{E\}\\exp\\\!\\left\(\-\\tfrac\{1\}\{2\}\\sum\_\{i\}s\_\{i\}\\xi\_\{i\}\\right\)=\\prod\_\{i\}\\cosh\(s\_\{i\}/2\)\\leq e^\{k/8\}givesℙ\{∑isiξi<−k/2\}≤e−k/8\\mathbb\{P\}\\\{\\sum\_\{i\}s\_\{i\}\\xi\_\{i\}<\-k/2\\\}\\leq e^\{\-k/8\}by Markov’s inequality\. This is the usual Hoeffding argument\([Hoeffding, 1963](https://arxiv.org/html/2610.00254#bib.bib1)\), and also holds conditionally whenssis measurable with respect to the past and the signs are independent of that past\.

Fix a call\-allocation convention before analyzing the transcript\. Points returned during preprocessing are available before every phase\. Calls after one phase’s final feedback and before the next action are assigned to the next phase, as are all subsequent calls within that phase\. Calls after the nonzero\-loss horizon may be ignored, since their replies cannot affect its actions\. At the start of phasejj, before its first loss has been revealed, condition on the seed, past signs, and the oracle points acquired before the phase\. Every such point is fixed and independent ofσj\\sigma\_\{j\}\. For such a pointvv, its cube block has the forma​sj/m​kas\_\{j\}/\\sqrt\{mk\}, whence

⟨uj,zj​\(v\)⟩=ak​m​∑ℓ=1kσj,ℓ​sj,ℓ\.\\langle u\_\{j\},z\_\{j\}\(v\)\\rangle=\\frac\{a\}\{k\\sqrt\{m\}\}\\sum\_\{\\ell=1\}^\{k\}\\sigma\_\{j,\\ell\}s\_\{j,\\ell\}\.Conditionally on the pre\-phase history, a union bound over its at mostQQoracle points gives failure probability at mostQe−k/8Qe^\{\-k/8\}\. Averaging this conditional probability over the history and then union bounding over themmphases gives an eventℰ\\mathcal\{E\}with

ℙ\(ℰ\)≥1−mQe−k/8≥1−δ,⟨uj,zj\(v\)⟩≥−a2​m\\mathbb\{P\}\(\\mathcal\{E\}\)\\geq 1\-mQe^\{\-k/8\}\\geq 1\-\\delta,\\qquad\\langle u\_\{j\},z\_\{j\}\(v\)\\rangle\\geq\-\\frac\{a\}\{2\\sqrt\{m\}\}\(4\.20\)for every oracle point acquired before its phase\. No union bound over possible adaptive query directions is needed\. Every point ofCCsatisfies the same inequality, because∥zj∥2≤r≤a/\(2​m\)\\lVert z\_\{j\}\\rVert\_\{2\}\\leq r\\leq a/\(2\\sqrt\{m\}\)\. Points acquired during the phase are not subject to this concentration argument\.

#### Newly acquired replies\.

LetNjN\_\{j\}be the number of calls in phasejj; then∑jNj≤Q\\sum\_\{j\}N\_\{j\}\\leq Q\. On the probability\-one event of Lemma[4\.7](https://arxiv.org/html/2610.00254#Thmtheorem7), every action in phasejjcan be writtenx=\(1−p\)​ypre\+p​ynewx=\(1\-p\)y\_\{\\mathrm\{pre\}\}\+py\_\{\\mathrm\{new\}\},0≤p≤10\\leq p\\leq 1, whereyprey\_\{\\mathrm\{pre\}\}combines the supplied ball and oracle points acquired before the phase, andynewy\_\{\\mathrm\{new\}\}combines at mostNjN\_\{j\}points acquired during the phase\. Allowing even points obtained later in that phase only enlarges this set of representations\. Empty groups have weight zero\. Onℰ\\mathcal\{E\},

⟨uj,zj​\(x\)−zj∗⟩≥a⁡\(1−p\)2​m\.\\langle u\_\{j\},z\_\{j\}\(x\)\-z\_\{j\}^\{\*\}\\rangle\\geq\\frac\{a\(1\-p\)\}\{2\\sqrt\{m\}\}\.\(4\.21\)The simplex component ofynewy\_\{\\mathrm\{new\}\}has massaaon at mostNjN\_\{j\}coordinates\. By Cauchy–Schwarz, its norm is at leasta/Nja/\\sqrt\{N\_\{j\}\}\. Nonnegative coordinates give∥w⁡\(x\)∥2≥a​p/Nj\\lVert w\(x\)\\rVert\_\{2\}\\geq ap/\\sqrt\{N\_\{j\}\}\. ForNj≥1N\_\{j\}\\geq 1,

ft​\(x\)−ft​\(x∗\)≥12​\[a⁡\(1−p\)2​m\+a​pNj−an\]\.f\_\{t\}\(x\)\-f\_\{t\}\(x^\{\*\}\)\\geq\\frac\{1\}\{\\sqrt\{2\}\}\\left\[\\frac\{a\(1\-p\)\}\{2\\sqrt\{m\}\}\+\\frac\{ap\}\{\\sqrt\{N\_\{j\}\}\}\-\\frac\{a\}\{\\sqrt\{n\}\}\\right\]\.\(4\.22\)ForNj=0N\_\{j\}=0, setp=0p=0and omit the fraction containingNjN\_\{j\}\. This inequality allows arbitrary reweighting of the full oracle history\. Its two positive terms cannot be avoided simultaneously: reducing the pre\-phase weight1−p1\-prequires increasing the newly acquired weightpp\. If the phase has onlyNjN\_\{j\}newly acquired points, that increase costsp/Njp/\\sqrt\{N\_\{j\}\}in the shared simplex\. Equivalently, minimizing the positive part overp∈\[0,1\]p\\in\[0,1\]selects the smaller of the two coefficients; it does not remove both\. For each realized transcript, enlarging the action hull to include all points eventually obtained in the current phase can only strengthen the learner, so the inequality also holds for the original causal action\.

#### Summing the recurring cost\.

IfNj≤4​mN\_\{j\}\\leq 4m, the first two terms in brackets in \([4\.22](https://arxiv.org/html/2610.00254#S4.E22)\) sum to at leasta/\(2​m\)a/\(2\\sqrt\{m\}\), whereasa/n=a/\(8​m\)a/\\sqrt\{n\}=a/\(8\\sqrt\{m\}\)\. Every round in that phase has regret at least3/\(16​3​m\)3/\(16\\sqrt\{3m\}\)\. SinceQ<m2Q<m^\{2\}, fewer thanm/4m/4phases haveNj\>4​mN\_\{j\}\>4m\. The other phases contribute nonnegatively, andm≤Tm\\leq T,m​L≥T/2mL\\geq T/2, andm≤2​qm\\leq 2\\sqrt\{q\}\. Therefore, onℰ\\mathcal\{E\},

RegT≥3​m4​L​316​3​m≥9128​6​Tq1/4\>140​Tq1/4\.\\operatorname\{Reg\}\_\{T\}\\geq\\frac\{3m\}\{4\}L\\frac\{3\}\{16\\sqrt\{3m\}\}\\geq\\frac\{9\}\{128\\sqrt\{6\}\}\\frac\{T\}\{q^\{1/4\}\}\>\\frac\{1\}\{40\}\\frac\{T\}\{q^\{1/4\}\}\.\(4\.23\)The parameter choice now has a direct interpretation\. Withmmphases, buying more than4​m4mreplies in most phases would require orderm2m^\{2\}calls, which the budget does not provide\. A constant fraction of phases therefore retain per\-round loss of orderm−1/2m^\{\-1/2\}\. Choosingmmon the order ofQ\+1\\sqrt\{Q\+1\}yields the fourth\-root dependence\.

This includesQ=0Q=0andT=1T=1\. At zero budget the concentration event is automatic and all actions lie in the supplied ball\.

#### Fixed losses, geometry, and the statistical term\.

The body, supplied ball, and oracle above were fixed before either the signs or the seed\. The sign distribution has finite support\. For each learner, averaging the probability of \([4\.23](https://arxiv.org/html/2610.00254#S4.E23)\) over that support gives some fixed sign sequence for which the success probability over the seed alone is at least1−δ1\-\\delta\. This sequence may depend on the learner, but not on its realized seed\. No minimax interchange or seed\-dependent choice of the body is used\.

The dimension ism​k\+64​m−1=O⁡\(q​log⁡\(q/δ\)\)mk\+64m\-1=O\(\\sqrt\{q\}\\log\(q/\\delta\)\)\. Atδ=1/4\\delta=1/4,q≤m2q\\leq m^\{2\}implies

k≤8​log⁡\(4​m3\)\+1≤13\+24​log⁡m≤24​m\.k\\leq 8\\log\(4m^\{3\}\)\+1\\leq 13\+24\\log m\\leq 24m\.Thusm​k≤n\\sqrt\{mk\}\\leq n, andr=a/\(128​m\)≥1/\(256​6​q\)r=a/\(128m\)\\geq 1/\(256\\sqrt\{6q\}\)\. Scaling the centered Euclidean coordinates byDDand using lossesf~t​\(x\)=G​D​ft​\(x/D\)\\widetilde\{f\}\_\{t\}\(x\)=GDf\_\{t\}\(x/D\)gives the stated diameter, Lipschitz constant, radius, and regret\.

A second fixed body supplies the statistical term whenq\>T2q\>T^\{2\}\. Setk=⌈8​log⁡\(T/δ\)⌉k=\\lceil 8\\log\(T/\\delta\)\\rceil,b=D/\(2​T​k\)b=D/\(2\\sqrt\{Tk\}\), andK=\[−b,b\]T​kK=\[\-b,b\]^\{Tk\}\. In roundtt, reveal

ft​\(x\)=Gk​⟨σt,x\(t\)⟩,f\_\{t\}\(x\)=\\frac\{G\}\{\\sqrt\{k\}\}\\langle\\sigma\_\{t\},x^\{\(t\)\}\\rangle,\(4\.24\)where theTTblocks are disjoint and the sign vectors are independent\. The common minimizer has blocksu\(t\)=−b​σtu^\{\(t\)\}=\-b\\sigma\_\{t\}and loss−GD/\(2T\)\-GD/\(2\\sqrt\{T\}\)in every round\. Before feedback, feasibility givesxt\(t\)=b​stx\_\{t\}^\{\(t\)\}=bs\_\{t\}withst∈\[−1,1\]ks\_\{t\}\\in\[\-1,1\]^\{k\}independent of the fresh signs\. The same conditional sign bound shows that, with probability at least1−Te−k/8≥1−δ1\-Te^\{\-k/8\}\\geq 1\-\\delta, every round has loss at least−GD/\(4T\)\-GD/\(4\\sqrt\{T\}\)\. HenceRegT≥G​D​T/4\\operatorname\{Reg\}\_\{T\}\\geq GD\\sqrt\{T\}/4\. This argument holds even with an explicit description of the cube and unlimited calls\. Its dimension isT​kTk; supply the centered radius\-bbball and fix an ordered vertex oracle\.

Forq\>T2q\>T^\{2\}, the maximum in \([4\.14](https://arxiv.org/html/2610.00254#S4.E14)\) equalsT\\sqrt\{T\}, completing the bound in this branch\. The finite\-support averaging argument extracts a deterministic oblivious loss sequence for each learner, and all its per\-round regret terms remain nonnegative\. ∎

###### Proof of Theorem[4\.2](https://arxiv.org/html/2610.00254#Thmtheorem2)\.

The construction in \([4\.10](https://arxiv.org/html/2610.00254#S4.E10)\)–\([4\.12](https://arxiv.org/html/2610.00254#S4.E12)\) proves the upper bound and respects both caps\. For the lower bound, every jointly constrained learner makes at mostQ∗Q\_\{\*\}calls in total\. Apply Proposition[4\.8](https://arxiv.org/html/2610.00254#Thmtheorem8)with this total allowance andδ=1/4\\delta=1/4\. The fixed sequence extracted for that learner has nonnegative regret on every feasible execution and satisfies the high\-probability lower bound\. Hence

𝔼​RegT≥3​G​D160​Ψ​\(T,Q∗\+1\)≥G​D100​Ψ​\(T,Q∗\+1\)\.\\mathbb\{E\}\\operatorname\{Reg\}\_\{T\}\\geq\\frac\{3GD\}\{160\}\\Psi\(T,Q\_\{\*\}\+1\)\\geq\\frac\{GD\}\{100\}\\Psi\(T,Q\_\{\*\}\+1\)\.Taking the worst case over instances and then the infimum over learners proves \([4\.1](https://arxiv.org/html/2610.00254#S4.E1)\)\. ∎

### 4\.3Consequences and recovery of previous rates

The total\-only and strict\-only problems are special cases of Theorem[4\.2](https://arxiv.org/html/2610.00254#Thmtheorem2)\. Their upper constants can be sharpened using the constructions already analyzed\.

###### Corollary 4\.9\(Total oracle budget\)\.

For every integerQ≥0Q\\geq 0,

G​D100​Ψ​\(T,Q\+1\)≤ℛ⁡\(T,Q,G,D\)≤3​G​D​Ψ​\(T,Q\+1\)\.\\frac\{GD\}\{100\}\\Psi\(T,Q\+1\)\\leq\\mathcal\{R\}\(T,Q;G,D\)\\leq 3GD\\Psi\(T,Q\+1\)\.\(4\.25\)

###### Proof\.

SetB=∞B=\\inftyin Theorem[4\.2](https://arxiv.org/html/2610.00254#Thmtheorem2)for the lower bound\. The single\-copy choice \([4\.5](https://arxiv.org/html/2610.00254#S4.E5)\) and bound \([4\.6](https://arxiv.org/html/2610.00254#S4.E6)\) give the upper constant33\. ∎

###### Corollary 4\.10\(Strict per\-round budget\)\.

For every integerB≥1B\\geq 1,

G​D100 21/4​max⁡\{T,T3/4B1/4\}\\displaystyle\\frac\{GD\}\{100\\,2^\{1/4\}\}\\max\\\!\\left\\\{\\sqrt\{T\},\\frac\{T^\{3/4\}\}\{B^\{1/4\}\}\\right\\\}≤ℛround​\(T,B,G,D\)\\displaystyle\\leq\\mathcal\{R\}\_\{\\mathrm\{round\}\}\(T,B;G,D\)\(4\.26\)≤5​G​D​max⁡\{T,T3/4B1/4\}\.\\displaystyle\\leq 5GD\\max\\\!\\left\\\{\\sqrt\{T\},\\frac\{T^\{3/4\}\}\{B^\{1/4\}\}\\right\\\}\.

###### Proof\.

SetQ=B​TQ=BTin Theorem[4\.2](https://arxiv.org/html/2610.00254#Thmtheorem2)\. SinceB​T\+1≤2​B​TBT\+1\\leq 2BT, its lower bound implies the stated lower constant\. The schedule \([4\.10](https://arxiv.org/html/2610.00254#S4.E10)\) now hasS0=B​TS\_\{0\}=BT, soM≥min⁡\{T,B​T\}/\(2​2\)M\\geq\\min\\\{T,\\sqrt\{BT\}\\\}/\(2\\sqrt\{2\}\)\. In \([4\.9](https://arxiv.org/html/2610.00254#S4.E9)\), this gives upper constant\(1\+5/2\)​2​2<5\(1\+\\sqrt\{5/2\}\)\\sqrt\{2\\sqrt\{2\}\}<5\. ∎

###### Corollary 4\.12\(Budgets for a target regret\)\.

Let1/2≤α≤11/2\\leq\\alpha\\leq 1andq∗=1\+min⁡\{Q,B​T\}q\_\{\*\}=1\+\\min\\\{Q,BT\\\}\. A uniform guarantee of orderG​D​TαGDT^\{\\alpha\}is possible if and only if

q∗=Ω⁡\(T4​\(1−α\)\)\.q\_\{\*\}=\\Omega\\bigl\(T^\{4\(1\-\\alpha\)\}\\bigr\)\.\(4\.27\)More explicitly, a guarantee𝔼​RegT≤C0​G​D​Tα\\mathbb\{E\}\\operatorname\{Reg\}\_\{T\}\\leq C\_\{0\}GDT^\{\\alpha\}requires

q∗≥T4​\(1−α\)\(100​C0\)4,q\_\{\*\}\\geq\\frac\{T^\{4\(1\-\\alpha\)\}\}\{\(100C\_\{0\}\)^\{4\}\},\(4\.28\)andq∗≥T4​\(1−α\)q\_\{\*\}\\geq T^\{4\(1\-\\alpha\)\}suffices for regret at most6​G​D​Tα6GDT^\{\\alpha\}\. With only a total cap, the minimum sufficient order ofQ\+1Q\+1isT4​\(1−α\)T^\{4\(1\-\\alpha\)\}\. With only a strict cap, the minimum sufficient order ofBBismax⁡\{1,T3−4​α\}\\max\\\{1,T^\{3\-4\\alpha\}\\\}\.

###### Proof\.

The lower half of Theorem[4\.2](https://arxiv.org/html/2610.00254#Thmtheorem2)impliesC0​Tα≥T/\(100​q∗1/4\)C\_\{0\}T^\{\\alpha\}\\geq T/\(100q\_\{\*\}^\{1/4\}\), which rearranges to \([4\.28](https://arxiv.org/html/2610.00254#S4.E28)\)\. Conversely,q∗≥T4​\(1−α\)q\_\{\*\}\\geq T^\{4\(1\-\\alpha\)\}bounds the oracle\-dependent term byTαT^\{\\alpha\}, andT≤Tα\\sqrt\{T\}\\leq T^\{\\alpha\}\. This proves the sufficient bound\. The total\-only assertion setsB=∞B=\\infty\. For a strict\-only budget,q∗=B​T\+1q\_\{\*\}=BT\+1; inversion givesB=Ω⁡\(T3−4​α\)B=\\Omega\(T^\{3\-4\\alpha\}\)when that power grows, and the smallest allowed cap is11\. The matching choices follow from Corollary[4\.10](https://arxiv.org/html/2610.00254#Thmtheorem10)\. ∎

Atα=1\\alpha=1, zero calls suffice by playingccthroughout\. Atα=3/4\\alpha=3/4, a linear total budget and one call per round suffice\. Atα=1/2\\alpha=1/2, the necessary and sufficient scales areQ=Θ⁡\(T2\)Q=\\Theta\(T^\{2\}\)andB=Θ⁡\(T\)B=\\Theta\(T\)when both restrictions are imposed\.

###### Corollary 4\.13\(The polynomial tradeoff under joint caps\)\.

For0≤θ≤10\\leq\\theta\\leq 1, take

Qθ=⌈T2​θ⌉−1,Bθ=max⁡\{1,⌈T2​θ−1⌉\}\.Q\_\{\\theta\}=\\lceil T^\{2\\theta\}\\rceil\-1,\\qquad B\_\{\\theta\}=\\max\\\{1,\\lceil T^\{2\\theta\-1\}\\rceil\\\}\.\(4\.29\)Then

ℛjoint​\(T,Qθ,Bθ,G,D\)=Θ⁡\(G​D​T1−θ/2\)\.\\mathcal\{R\}\_\{\\mathrm\{joint\}\}\(T,Q\_\{\\theta\},B\_\{\\theta\};G,D\)=\\Theta\(GDT^\{1\-\\theta/2\}\)\.\(4\.30\)

###### Proof\.

BecauseBθ​T≥T2​θ\>QθB\_\{\\theta\}T\\geq T^\{2\\theta\}\>Q\_\{\\theta\}, the effective allowance satisfiesq∗=Qθ\+1=⌈T2​θ⌉q\_\{\*\}=Q\_\{\\theta\}\+1=\\lceil T^\{2\\theta\}\\rceil\. HenceT2​θ≤q∗≤2​T2​θT^\{2\\theta\}\\leq q\_\{\*\}\\leq 2T^\{2\\theta\}, whileT1−θ/2≥TT^\{1\-\\theta/2\}\\geq\\sqrt\{T\}\. Equation \([4\.30](https://arxiv.org/html/2610.00254#S4.E30)\) follows from Theorem[4\.2](https://arxiv.org/html/2610.00254#Thmtheorem2)\. ∎

The pair of total\-work and regret exponents in \([4\.29](https://arxiv.org/html/2610.00254#S4.E29)\)–\([4\.30](https://arxiv.org/html/2610.00254#S4.E30)\) recovers the convex case of[Lu et al\. \(2025\)](https://arxiv.org/html/2610.00254#bib.bib14)\. The corollary additionally imposes the stated strict cap and supplies the matching lower bound\. It concerns the centralized oracle problem; communication requirements in the decentralized setting are separate\.

## 5Joint budgets with prescribed smoothness

A prescribed smoothness bound changes the lower\-bound construction because the norm penalty becomes increasingly curved as the simplex dimension grows\. An analytic replacement preserves the same phase mechanism while controlling curvature\. The upper algorithm of Section[4\.1](https://arxiv.org/html/2610.00254#S4.SS1)remains valid for this smaller loss class\.

Define

λ=β​D3​G,Ψλ\(T,q\)=max\{T,Tmin\{q−1/4,\(λ/q\)1/3\}\}\.\\lambda=\\frac\{\\beta D\}\{\\sqrt\{3\}G\},\\qquad\\Psi\_\{\\lambda\}\(T,q\)=\\max\\\!\\left\\\{\\sqrt\{T\},T\\min\\\!\\left\\\{q^\{\-1/4\},\(\\lambda/q\)^\{1/3\}\\right\\\}\\right\\\}\.\(5\.1\)
###### Theorem 5\.14\(Smooth losses under joint budgets\)\.

For everyβ≥0\\beta\\geq 0and the budgets of Theorem[4\.2](https://arxiv.org/html/2610.00254#Thmtheorem2), letq∗=1\+min⁡\{Q,B​T\}q\_\{\*\}=1\+\\min\\\{Q,BT\\\}\. Then

G​D240​Ψλ​\(T,q∗\)≤ℛjoint,β​\(T,Q,B,G,D\)≤6​G​D​Ψ​\(T,q∗\)\.\\frac\{GD\}\{240\}\\Psi\_\{\\lambda\}\(T,q\_\{\*\}\)\\leq\\mathcal\{R\}\_\{\\mathrm\{joint\},\\beta\}\(T,Q,B;G,D\)\\leq 6GD\\Psi\(T,q\_\{\*\}\)\.\(5\.2\)The upper algorithm is deterministic\. For every0<δ<1/20<\\delta<1/2, a fixed body, fixed exact oracle, and finite distribution of globally real\-analytic convexGG\-Lipschitz losses with gradient Lipschitz constant at mostβ\\betasatisfy

ℙf,ω\{RegT≥G​D160Ψλ\(T,q∗\)\}≥1−δ\\mathbb\{P\}\_\{f,\\omega\}\\\!\\left\\\{\\operatorname\{Reg\}\_\{T\}\\geq\\frac\{GD\}\{160\}\\Psi\_\{\\lambda\}\(T,q\_\{\*\}\)\\right\\\}\\geq 1\-\\delta\(5\.3\)for every admissible jointly constrained learner\. Every sequence has a common minimizer, and a deterministic oblivious sequence with this probability guarantee over the seed alone can be extracted for each learner\.

The two sides coincide in order whenλ≥q∗1/4\\lambda\\geq q\_\{\*\}^\{1/4\}\. Below this threshold, the theorem gives a curvature\-sensitive lower bound; the upper bound remains the general convex guarantee\. The threshold and the resulting budget requirements are stated explicitly after the proof\.

### 5\.1Analytic construction and proof

On the affine ambient space in \([4\.16](https://arxiv.org/html/2610.00254#S4.E16)\),∥w∥2≥a/n\\lVert w\\rVert\_\{2\}\\geq a/\\sqrt\{n\}even outside the simplex\. Thus the original norm penalty is analytic there, with gradient Lipschitz constant at mostn/a\\sqrt\{n\}/a\. Including the factor1/21/\\sqrt\{2\}gives smoothness at most3​n\\sqrt\{3n\}, which grows with the oracle budget\. To prescribe the curvature independently, forρ\>0\\rho\>0define

Pρ​\(w\)=ρ2\+∥w∥22−ρ\.P\_\{\\rho\}\(w\)=\\sqrt\{\\rho^\{2\}\+\\lVert w\\rVert\_\{2\}^\{2\}\}\-\\rho\.\(5\.4\)
###### Lemma 5\.15\(Regularity and quadratic estimates\)\.

The functionPρP\_\{\\rho\}is globally real\-analytic, convex,11\-Lipschitz, and has1/ρ1/\\rho\-Lipschitz gradient\. It is increasing in∥w∥2\\lVert w\\rVert\_\{2\}, and

Pρ​\(w\)≤∥w∥222​ρ,Pρ​\(w\)≥8​∥w∥2217​ρwhen​∥w∥2≤ρ/2\.P\_\{\\rho\}\(w\)\\leq\\frac\{\\lVert w\\rVert\_\{2\}^\{2\}\}\{2\\rho\},\\qquad P\_\{\\rho\}\(w\)\\geq\\frac\{8\\lVert w\\rVert\_\{2\}^\{2\}\}\{17\\rho\}\\quad\\text\{when \}\\lVert w\\rVert\_\{2\}\\leq\\rho/2\.\(5\.5\)

###### Proof\.

Lets=ρ2\+∥w∥22s=\\sqrt\{\\rho^\{2\}\+\\lVert w\\rVert\_\{2\}^\{2\}\}\. Direct differentiation gives

∇Pρ​\(w\)=ws,∇2Pρ​\(w\)=Is−w​w⊤s3\.\\nabla P\_\{\\rho\}\(w\)=\\frac\{w\}\{s\},\\qquad\\nabla^\{2\}P\_\{\\rho\}\(w\)=\\frac\{I\}\{s\}\-\\frac\{ww^\{\\top\}\}\{s^\{3\}\}\.The Hessian is positive semidefinite, with eigenvalues at most1/s≤1/ρ1/s\\leq 1/\\rho, and the gradient norm is at most one\. The strictly positive quantity inside the square root also proves real analyticity at every point\. Monotonicity in the radius is immediate\. Finally,

Pρ​\(w\)=∥w∥22ρ2\+∥w∥22\+ρ\.P\_\{\\rho\}\(w\)=\\frac\{\\lVert w\\rVert\_\{2\}^\{2\}\}\{\\sqrt\{\\rho^\{2\}\+\\lVert w\\rVert\_\{2\}^\{2\}\}\+\\rho\}\.The denominator is at least2​ρ2\\rho\. When∥w∥2≤ρ/2\\lVert w\\rVert\_\{2\}\\leq\\rho/2, it is at most\(1\+5/2\)​ρ<17​ρ/8\(1\+\\sqrt\{5\}/2\)\\rho<17\\rho/8\. These observations prove \([5\.5](https://arxiv.org/html/2610.00254#S5.E5)\)\. ∎

The penalty is used to prescribe the regularity of the losses in the lower\-bound instance\.

#### Why the smooth exponent changes\.

In normalized coordinates, write the penalty scale asρ=a/h\\rho=a/h\. At small radii,PρP\_\{\\rho\}is comparable to∥w∥22/ρ\\lVert w\\rVert\_\{2\}^\{2\}/\\rho\. Placing weightpponNNnewly acquired simplex vertices therefore gives a penalty on the order ofh​p2/Nhp^\{2\}/N, whereas pre\-phase weight still gives a signal loss of order\(1−p\)/m\(1\-p\)/\\sqrt\{m\}\. The relevant threshold becomesN≍h​mN\\asymp h\\sqrt\{m\}per phase, orQ∗≍h​m3/2Q\_\{\*\}\\asymp hm^\{3/2\}acrossmmphases\. Solving this balance yieldsT/m≍T​\(h/Q∗\)1/3T/\\sqrt\{m\}\\asymp T\(h/Q\_\{\*\}\)^\{1/3\}for positiveQ∗Q\_\{\*\}\. The proof also covers zero allowance by choosingh=min⁡\{λ,\(Q∗\+1\)1/4\}h=\\min\\\{\\lambda,\(Q\_\{\*\}\+1\)^\{1/4\}\\\}and uses the statistical construction when the required phase count exceedsTT\.

###### Proof of Theorem[5\.14](https://arxiv.org/html/2610.00254#Thmtheorem14)\.

The upper bound follows by applying the joint\-budget algorithm to the smooth loss class\. For the lower bound, it suffices to construct a hard instance for total allowanceQ∗=min⁡\{Q,B​T\}Q\_\{\*\}=\\min\\\{Q,BT\\\}, since every jointly constrained learner satisfies that allowance\. Within this proof writeQ0=Q∗Q\_\{0\}=Q\_\{\*\}andq=Q0\+1q=Q\_\{0\}\+1\. NormalizeG=D=1G=D=1and suppose first thatλ=β/3\>0\\lambda=\\beta/\\sqrt\{3\}\>0\. Put

h=min⁡\{λ,q1/4\},m=⌈\(q/h\)2/3⌉\.h=\\min\\\{\\lambda,q^\{1/4\}\\\},\\qquad m=\\left\\lceil\(q/h\)^\{2/3\}\\right\\rceil\.\(5\.6\)There is no requirement thath≥1h\\geq 1\. The inequalities needed below are

h\>0,h4≤q,m≥q,h≤m,q≤h​m3/2,m≤2​\(q/h\)2/3\.h\>0,\\quad h^\{4\}\\leq q,\\quad m\\geq\\sqrt\{q\},\\quad h\\leq\\sqrt\{m\},\\quad q\\leq hm^\{3/2\},\\quad m\\leq 2\(q/h\)^\{2/3\}\.\(5\.7\)They follow fromh≤q1/4h\\leq q^\{1/4\}and\(q/h\)2/3≥1\(q/h\)^\{2/3\}\\geq 1\.

#### Geometry, feedback, and the common minimizer\.

First supposem≤Tm\\leq T\. Choose

L=⌊T/m⌋,k=⌈8​log⁡m​qδ⌉,n=max⁡\{2,⌈16​h​m⌉\},a=1/6,ρ=a/h\.L=\\lfloor T/m\\rfloor,\\quad k=\\left\\lceil 8\\log\\frac\{mq\}\{\\delta\}\\right\\rceil,\\quad n=\\max\\\{2,\\lceil 16h\\sqrt\{m\}\\rceil\\\},\\quad a=1/\\sqrt\{6\},\\quad\\rho=a/h\.\(5\.8\)Use exactly the affine space, product body, ball, and ordered vertex oracle in \([4\.16](https://arxiv.org/html/2610.00254#S4.E16)\)–\([4\.17](https://arxiv.org/html/2610.00254#S4.E17)\), with thesem,k,nm,k,n\. The geometric verification for this body only requiresm,k≥1m,k\\geq 1andn≥2n\\geq 2, so the diameter is one and the supplied positive\-radius ball is contained in a full\-dimensional body\. The maximum with22in \([5\.8](https://arxiv.org/html/2610.00254#S5.E8)\) keeps this true even at arbitrarily small prescribed smoothness\.

Use independent sign vectors and phase directions as before, but replace \([4\.18](https://arxiv.org/html/2610.00254#S4.E18)\) by

ft​\(z,w\)=12​\(⟨uj,zj⟩\+Pρ​\(w\)\)in phase​j,f\_\{t\}\(z,w\)=\\frac\{1\}\{\\sqrt\{2\}\}\\bigl\(\\langle u\_\{j\},z\_\{j\}\\rangle\+P\_\{\\rho\}\(w\)\\bigr\)\\quad\\text\{in phase \}j,\(5\.9\)with trailing zero losses\. Lemma[5\.15](https://arxiv.org/html/2610.00254#Thmtheorem15)makes these functions convex, globally analytic, and globally11\-Lipschitz onℋ\\mathcal\{H\}\. Their gradient Lipschitz constant is at most

12​ρ=3​h≤3​λ=β\.\\frac\{1\}\{\\sqrt\{2\}\\rho\}=\\sqrt\{3\}h\\leq\\sqrt\{3\}\\lambda=\\beta\.Restriction to an affine space projects the gradient onto its translation space and preserves the bound\. The same global formulas and bounds hold on every alternative body used in Lemma[4\.7](https://arxiv.org/html/2610.00254#Thmtheorem7)\.

The common minimizer remains \([4\.19](https://arxiv.org/html/2610.00254#S4.E19)\), becausePρP\_\{\\rho\}is increasing in the simplex norm\. Its penalty satisfies

Pρ​\(w∗\)≤a22​ρ​n=a​h2​n≤a32​m\.P\_\{\\rho\}\(w^\{\*\}\)\\leq\\frac\{a^\{2\}\}\{2\\rho n\}=\\frac\{ah\}\{2n\}\\leq\\frac\{a\}\{32\\sqrt\{m\}\}\.\(5\.10\)All per\-round regret terms are again nonnegative\.

#### The support cost in one phase\.

The conditional sign argument in \([4\.20](https://arxiv.org/html/2610.00254#S4.E20)\) is independent of the radial penalty, so its event still has probability at least1−δ1\-\\delta\. Intersect it with the probability\-one hull event\. For an action of new weightppin a phase withNj≥1N\_\{j\}\\geq 1calls, the signal and support inequalities give

⟨uj,zj​\(x\)−zj∗⟩≥a⁡\(1−p\)2​m,∥w⁡\(x\)∥2≥a​pNj\.\\langle u\_\{j\},z\_\{j\}\(x\)\-z\_\{j\}^\{\*\}\\rangle\\geq\\frac\{a\(1\-p\)\}\{2\\sqrt\{m\}\},\\qquad\\lVert w\(x\)\\rVert\_\{2\}\\geq\\frac\{ap\}\{\\sqrt\{N\_\{j\}\}\}\.\(5\.11\)SupposeNj≤4​h​mN\_\{j\}\\leq 4h\\sqrt\{m\}and sets0=a​p/4​h​ms\_\{0\}=ap/\\sqrt\{4h\\sqrt\{m\}\}\. Then∥w⁡\(x\)∥2≥s0\\lVert w\(x\)\\rVert\_\{2\}\\geq s\_\{0\}and

s0ρ=p​h2​m1/4≤12\.\\frac\{s\_\{0\}\}\{\\rho\}=\\frac\{p\\sqrt\{h\}\}\{2m^\{1/4\}\}\\leq\\frac\{1\}\{2\}\.Monotonicity and the lower estimate in Lemma[5\.15](https://arxiv.org/html/2610.00254#Thmtheorem15)show

Pρ​\(w⁡\(x\)\)≥8​s0217​ρ=2​a​p217​m\.P\_\{\\rho\}\(w\(x\)\)\\geq\\frac\{8s\_\{0\}^\{2\}\}\{17\\rho\}=\\frac\{2ap^\{2\}\}\{17\\sqrt\{m\}\}\.\(5\.12\)Only the guaranteed lower radiuss0s\_\{0\}, not the learner’s actual radius, is required to be in the quadratic regime\. Combining \([5\.11](https://arxiv.org/html/2610.00254#S5.E11)\)–\([5\.12](https://arxiv.org/html/2610.00254#S5.E12)\) and subtracting \([5\.10](https://arxiv.org/html/2610.00254#S5.E10)\) gives

ft​\(x\)−ft​\(x∗\)\\displaystyle f\_\{t\}\(x\)\-f\_\{t\}\(x^\{\*\}\)≥a2​m​\(1−p2\+2​p217−132\)≥471088​3​m\.\\displaystyle\\geq\\frac\{a\}\{\\sqrt\{2m\}\}\\left\(\\frac\{1\-p\}\{2\}\+\\frac\{2p^\{2\}\}\{17\}\-\\frac\{1\}\{32\}\\right\)\\geq\\frac\{47\}\{1088\\sqrt\{3m\}\}\.\(5\.13\)The bracket decreases on\[0,1\]\[0,1\], and its value atp=1p=1is47/54447/544\. IfNj=0N\_\{j\}=0, takep=0p=0and usePρ≥0P\_\{\\rho\}\\geq 0; the same lower bound follows\. This also handles a threshold4​h​m<14h\\sqrt\{m\}<1, when every phase satisfying the threshold has no calls\.

#### Summation and parameter balance\.

By \([5\.7](https://arxiv.org/html/2610.00254#S5.E7)\),∑jNj≤Q0<q≤h​m3/2\\sum\_\{j\}N\_\{j\}\\leq Q\_\{0\}<q\\leq hm^\{3/2\}\. Thus fewer thanm/4m/4phases haveNj\>4​h​mN\_\{j\}\>4h\\sqrt\{m\}\. At least3​m/43m/4phases satisfy \([5\.13](https://arxiv.org/html/2610.00254#S5.E13)\) throughout theirLLrounds\. Usingm​L≥T/2mL\\geq T/2and the upper bound onmmin \([5\.7](https://arxiv.org/html/2610.00254#S5.E7)\),

RegT\\displaystyle\\operatorname\{Reg\}\_\{T\}≥3​m4​L​471088​3​m≥1418704​6​T​\(h/q\)1/3\>1160​T​\(h/q\)1/3\.\\displaystyle\\geq\\frac\{3m\}\{4\}L\\frac\{47\}\{1088\\sqrt\{3m\}\}\\geq\\frac\{141\}\{8704\\sqrt\{6\}\}T\(h/q\)^\{1/3\}\>\\frac\{1\}\{160\}T\(h/q\)^\{1/3\}\.\(5\.14\)Moreover,

T\(h/q\)1/3=Tmin\{q−1/4,\(λ/q\)1/3\}\.T\(h/q\)^\{1/3\}=T\\min\\\{q^\{\-1/4\},\(\\lambda/q\)^\{1/3\}\\\}\.SinceTTis an integer,m≤Tm\\leq Tis equivalent to\(q/h\)2/3≤T\(q/h\)^\{2/3\}\\leq T, so this quantity is at leastT\\sqrt\{T\}in the present branch\. This proves the desired high\-probability maximum\.

#### The statistical branch and zero smoothness\.

Ifm\>Tm\>T, the oracle\-dependent term is smaller thanT\\sqrt\{T\}\. The fixed\-cube linear construction \([4\.24](https://arxiv.org/html/2610.00254#S4.E24)\) gives the stronger high\-probability thresholdT/4\\sqrt\{T\}/4, with a common minimizer and gradient Lipschitz constant zero\. It also coversλ=0\\lambda=0directly, where the oracle\-dependent term in \([5\.2](https://arxiv.org/html/2610.00254#S5.E2)\) vanishes\.

#### Fixed instances, dimension, and rescaling\.

In the phase branch,n≤16​m\+1n\\leq 16m\+1, so the dimension ism​k\+n−1=O⁡\(m​log⁡\(m​q/δ\)\)mk\+n\-1=O\(m\\log\(mq/\\delta\)\), wherem=⌈max⁡\{q,\(q/λ\)2/3\}⌉m=\\lceil\\max\\\{\\sqrt\{q\},\(q/\\lambda\)^\{2/3\}\\\}\\rceil\. In the statistical branch it isO⁡\(T​log⁡\(T/δ\)\)O\(T\\log\(T/\\delta\)\)\. In both cases the body and ordered oracle are fixed independently of the seed and the signs\. The finite\-support averaging argument in Proposition[4\.8](https://arxiv.org/html/2610.00254#Thmtheorem8)extracts a deterministic oblivious loss sequence for each learner\.

Scale the coordinates byDDand the losses byG​DGD\. Lipschitz constants scale byGGand gradient Lipschitz constants byG/DG/D, so the normalized parameter is exactlyλ=β​D/\(3​G\)\\lambda=\\beta D/\(\\sqrt\{3\}G\)\. The high\-probability constant is1/1601/160\. Atδ=1/4\\delta=1/4, nonnegative regret gives expected constant3/640≥1/2403/640\\geq 1/240, proving the lower half of \([5\.2](https://arxiv.org/html/2610.00254#S5.E2)\)\. The same construction gives \([5\.3](https://arxiv.org/html/2610.00254#S5.E3)\)\. ∎

### 5\.2Smoothness threshold and oracle requirements

###### Corollary 5\.16\(Smoothness threshold\)\.

Letq∗=1\+min⁡\{Q,B​T\}q\_\{\*\}=1\+\\min\\\{Q,BT\\\}and define

β∗=3​GD​q∗1/4\.\\beta\_\{\*\}=\\frac\{\\sqrt\{3\}G\}\{D\}\\,q\_\{\*\}^\{1/4\}\.\(5\.15\)Ifβ≥β∗\\beta\\geq\\beta\_\{\*\}, then

ℛjoint,β​\(T,Q,B,G,D\)=Θ⁡\(G​D​Ψ​\(T,q∗\)\)\.\\mathcal\{R\}\_\{\\mathrm\{joint\},\\beta\}\(T,Q,B;G,D\)=\\Theta\\bigl\(GD\\Psi\(T,q\_\{\*\}\)\\bigr\)\.\(5\.16\)Whenq∗≥T2q\_\{\*\}\\geq T^\{2\}, the same matching statement holds for everyβ≥0\\beta\\geq 0, with rateΘ⁡\(G​D​T\)\\Theta\(GD\\sqrt\{T\}\)\. If0≤β<β∗0\\leq\\beta<\\beta\_\{\*\}, the curvature\-sensitive lower bound is

ℛjoint,β​\(T,Q,B,G,D\)≥G​D240​max⁡\{T,T​\(β​D3​G​q∗\)1/3\}\.\\mathcal\{R\}\_\{\\mathrm\{joint\},\\beta\}\(T,Q,B;G,D\)\\geq\\frac\{GD\}\{240\}\\max\\\!\\left\\\{\\sqrt\{T\},T\\left\(\\frac\{\\beta D\}\{\\sqrt\{3\}Gq\_\{\*\}\}\\right\)^\{1/3\}\\right\\\}\.\(5\.17\)

###### Proof\.

The two terms in the inner minimum in \([5\.1](https://arxiv.org/html/2610.00254#S5.E1)\) are equal exactly whenλ=q∗1/4\\lambda=q\_\{\*\}^\{1/4\}, orβ=β∗\\beta=\\beta\_\{\*\}\. Above that threshold the minimum equalsq∗−1/4q\_\{\*\}^\{\-1/4\}, so Theorem[5\.14](https://arxiv.org/html/2610.00254#Thmtheorem14)has matching lower and upper orders\. Below it the minimum equals\(λ/q∗\)1/3\(\\lambda/q\_\{\*\}\)^\{1/3\}, giving \([5\.17](https://arxiv.org/html/2610.00254#S5.E17)\)\. Ifq∗≥T2q\_\{\*\}\\geq T^\{2\}, the upper rateΨ⁡\(T,q∗\)\\Psi\(T,q\_\{\*\}\)isT\\sqrt\{T\}, and the statistical lower bound matches it for allβ\\beta\. ∎

###### Corollary 5\.18\(Necessary joint budgets for smooth losses\)\.

Let1/2≤α≤11/2\\leq\\alpha\\leq 1andC0\>0C\_\{0\}\>0\. A uniform guarantee𝔼​RegT≤C0​G​D​Tα\\mathbb\{E\}\\operatorname\{Reg\}\_\{T\}\\leq C\_\{0\}GDT^\{\\alpha\}for theβ\\beta\-smooth class requires

1\+min⁡\{Q,B​T\}≥min⁡\{T4​\(1−α\)\(240​C0\)4,λ​T3​\(1−α\)\(240​C0\)3\}\.1\+\\min\\\{Q,BT\\\}\\geq\\min\\\!\\left\\\{\\frac\{T^\{4\(1\-\\alpha\)\}\}\{\(240C\_\{0\}\)^\{4\}\},\\frac\{\\lambda T^\{3\(1\-\\alpha\)\}\}\{\(240C\_\{0\}\)^\{3\}\}\\right\\\}\.\(5\.18\)In particular, for fixed positiveλ\\lambda, a dimension\-freeO⁡\(G​D​T\)O\(GD\\sqrt\{T\}\)guarantee requiresQ=Ω⁡\(T3/2\)Q=\\Omega\(T^\{3/2\}\)and, under a finite strict cap,B=Ω⁡\(T1/2\)B=\\Omega\(T^\{1/2\}\)\. Ifλ=Ω⁡\(T\)\\lambda=\\Omega\(\\sqrt\{T\}\), these necessary scales becomeQ=Ω⁡\(T2\)Q=\\Omega\(T^\{2\}\)andB=Ω⁡\(T\)B=\\Omega\(T\), which are sufficient by Theorem[4\.2](https://arxiv.org/html/2610.00254#Thmtheorem2)\.

###### Proof\.

Theorem[5\.14](https://arxiv.org/html/2610.00254#Thmtheorem14)implies

min\{q∗−1/4,\(λ/q∗\)1/3\}≤240C0Tα−1\.\\min\\\{q\_\{\*\}^\{\-1/4\},\(\\lambda/q\_\{\*\}\)^\{1/3\}\\\}\\leq 240C\_\{0\}T^\{\\alpha\-1\}\.At least one of the two quantities on the left is at most the right side\. Rearranging the corresponding inequality gives one of the two thresholds in \([5\.18](https://arxiv.org/html/2610.00254#S5.E18)\), and hence their minimum\. Becauseq∗=1\+min⁡\{Q,B​T\}q\_\{\*\}=1\+\\min\\\{Q,BT\\\}, each resource must exceed this necessary effective allowance up to the additive one\. Settingα=1/2\\alpha=1/2proves the stated consequences\. The general convex upper bound gives sufficiency in the last regime\. ∎

## 6Conclusion

The joint\-budget characterization identifies the minimax oracle cost of dimension\-free online convex optimization\. Universal feasibility and recurring support costs give the lower bound, while counted updates and interleaved blocks attain it under simultaneous total and per\-round caps\. The smooth construction quantifies how prescribed curvature changes the lower bound and identifies the regime in which the general rate remains sharp\.

## References

- Garber and Kretzu \(2022\)D\. Garber and B\. KretzuNew projection\-free algorithms for online convex optimization with adaptive regret guarantees\.InProceedings of the Thirty Fifth Conference on Learning Theory,Cited by:[§1](https://arxiv.org/html/2610.00254#S1.p1.1),[§2](https://arxiv.org/html/2610.00254#S2.SS0.SSS0.Px1.p1.1),[§2](https://arxiv.org/html/2610.00254#S2.SS0.SSS0.Px2.p1.1),[§2](https://arxiv.org/html/2610.00254#S2.SS0.SSS0.Px4.p1.1),[Table 1](https://arxiv.org/html/2610.00254#S2.T1.2.5.1.1.1),[§4\.1](https://arxiv.org/html/2610.00254#S4.SS1.p1.1),[Remark 4\.11](https://arxiv.org/html/2610.00254#Thmtheorem11.p1.1.1)\.
- Hazan and Kale \(2012\)E\. Hazan and S\. KaleProjection\-free online learning\.InProceedings of the 29th International Conference on Machine Learning,Cited by:[§1](https://arxiv.org/html/2610.00254#S1.p1.1),[§2](https://arxiv.org/html/2610.00254#S2.SS0.SSS0.Px2.p1.1),[Table 1](https://arxiv.org/html/2610.00254#S2.T1.2.3.1.1.1),[Remark 4\.11](https://arxiv.org/html/2610.00254#Thmtheorem11.p1.1.1)\.
- Hazan and Minasyan \(2020\)E\. Hazan and E\. MinasyanFaster projection\-free online learning\.InProceedings of the Thirty Third Conference on Learning Theory,Cited by:[§2](https://arxiv.org/html/2610.00254#S2.SS0.SSS0.Px3.p1.1),[Table 1](https://arxiv.org/html/2610.00254#S2.T1.2.7.1.1.1),[Table 1](https://arxiv.org/html/2610.00254#S2.T1.2.8.1.1.1),[Remark 5\.17](https://arxiv.org/html/2610.00254#Thmtheorem17.p1.1.1)\.
- Hoeffding \(1963\)W\. HoeffdingProbability inequalities for sums of bounded random variables\.Journal of the American Statistical Association58\(301\),pp\. 13–30\.Cited by:[§2](https://arxiv.org/html/2610.00254#S2.SS0.SSS0.Px4.p1.1),[§4\.2](https://arxiv.org/html/2610.00254#S4.SS2.SSS0.Px2.p1.2)\.
- Jaggi \(2013\)M\. JaggiRevisiting Frank–Wolfe: projection\-free sparse convex optimization\.InProceedings of the 30th International Conference on Machine Learning,Cited by:[§1](https://arxiv.org/html/2610.00254#S1.SS0.SSS0.Px2.p1.1),[§2](https://arxiv.org/html/2610.00254#S2.SS0.SSS0.Px4.p1.1),[§4\.1](https://arxiv.org/html/2610.00254#S4.SS1.p1.1)\.
- Joulaniet al\.\(2013\)P\. Joulani, A\. György, and C\. SzepesváriOnline learning under delayed feedback\.InProceedings of the 30th International Conference on Machine Learning,Cited by:[§2](https://arxiv.org/html/2610.00254#S2.SS0.SSS0.Px2.p1.1)\.
- Kalai and Vempala \(2005\)A\. Kalai and S\. VempalaEfficient algorithms for online decision problems\.Journal of Computer and System Sciences71\(3\),pp\. 291–307\.Cited by:[§2](https://arxiv.org/html/2610.00254#S2.SS0.SSS0.Px3.p1.1)\.
- Lan \(2013\)G\. LanThe complexity of large\-scale convex programming under a linear optimization oracle\.Note:arXiv:1309\.5550Cited by:[§1](https://arxiv.org/html/2610.00254#S1.SS0.SSS0.Px2.p1.1),[§2](https://arxiv.org/html/2610.00254#S2.SS0.SSS0.Px4.p1.1)\.
- Luet al\.\(2025\)Y\. Lu, M\. Pedramfar, and V\. AggarwalDecentralized projection\-free online upper\-linearizable optimization with applications to DR\-submodular optimization\.Transactions on Machine Learning Research\.Note:arXiv:2501\.18183Cited by:[§1](https://arxiv.org/html/2610.00254#S1.p1.1),[§2](https://arxiv.org/html/2610.00254#S2.SS0.SSS0.Px1.p1.1),[Table 1](https://arxiv.org/html/2610.00254#S2.T1.2.6.1.1.1),[§4\.3](https://arxiv.org/html/2610.00254#S4.SS3.p7.1),[Remark 4\.11](https://arxiv.org/html/2610.00254#Thmtheorem11.p1.1.1)\.
- Mhammedi \(2022\)Z\. MhammediEfficient projection\-free online convex optimization with membership oracle\.InProceedings of the Thirty Fifth Conference on Learning Theory,Cited by:[§2](https://arxiv.org/html/2610.00254#S2.SS0.SSS0.Px3.p1.1)\.
- Mhammedi \(2025\)Z\. MhammediOnline convex optimization with a separation oracle\.InProceedings of the Thirty Eighth Conference on Learning Theory,Cited by:[§2](https://arxiv.org/html/2610.00254#S2.SS0.SSS0.Px3.p1.1)\.
- Thekumparampilet al\.\(2020\)K\. K\. Thekumparampil, P\. Jain, P\. Netrapalli, and S\. OhProjection efficient subgradient method and optimal nonsmooth Frank–Wolfe method\.InAdvances in Neural Information Processing Systems,Cited by:[§2](https://arxiv.org/html/2610.00254#S2.SS0.SSS0.Px4.p1.1)\.
- Weibelet al\.\(2026\)J\. Weibel, P\. Gaillard, W\. M\. Koolen, and A\. TaylorOptimized projection\-free algorithms for online learning: construction and worst\-case analysis\.InProceedings of the 29th International Conference on Artificial Intelligence and Statistics,Vol\.300,pp\. 5122–5130\.Cited by:[§1](https://arxiv.org/html/2610.00254#S1.p1.1),[§2](https://arxiv.org/html/2610.00254#S2.SS0.SSS0.Px2.p1.1),[Table 1](https://arxiv.org/html/2610.00254#S2.T1.2.4.1.1.1),[Remark 4\.11](https://arxiv.org/html/2610.00254#Thmtheorem11.p1.1.1)\.
- Zinkevich \(2003\)M\. ZinkevichOnline convex programming and generalized infinitesimal gradient ascent\.InProceedings of the Twentieth International Conference on Machine Learning,Cited by:[§1](https://arxiv.org/html/2610.00254#S1.p1.1),[§2](https://arxiv.org/html/2610.00254#S2.SS0.SSS0.Px4.p1.1)\.