PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Vaneet Aggarwal

arXiv:2610.00254v1cs.LG

TL;DR

The paper asks what regret is attainable when feasible-set access is limited to an exact linear oracle and oracle work is constrained by both a total budget and a strict per-round cap. The lower bound combines a universal-feasibility hull restriction with recurring phase costs, while counted approximate-gradient updates in interleaved blocks provide the matching upper bound. A constant number of calls per round gives order T^3/4 regret.

  • Problem

    The paper asks what regret is attainable when feasible-set access is limited to an exact linear oracle and oracle work is constrained by both a total budget and a strict per-round cap.

    Source: §1 · p. 1

  • Method

    The lower bound combines a universal-feasibility hull restriction with recurring phase costs, while counted approximate-gradient updates in interleaved blocks provide the matching upper bound.

    Source: §1 · p. 2, §4.1 · p. 6

  • Results

    A constant number of calls per round gives order T^3/4 regret.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The joint-budget characterization identifies the dimension-free minimax oracle cost, while the smooth construction quantifies curvature effects and the regime where the general rate remains sharp.

    Source: §6 · p. 20

    For fixed positive βD/G and Q* = Θ(T), the stated lower and upper bounds are Ω(GDT^2/3) and O(GDT^3/4); a matching dimension-uniform upper bound in this regime remains open.

    Source: §5.2 · p. 19

Abstract

from arXiv · show

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.

1. Introduction

The paper studies dimension-free online convex optimization when feasible-set access is restricted to an exact linear oracle, under both total and strict per-round call limits. It matches lower and upper bounds and develops a lower-bound mechanism based on universal feasibility and recurring support costs.

Main result

  • With a constant number of oracle calls per round, regret is order T^3/4; order T calls per round and T^2 total calls suffice for order √T regret.The guarantee is uniform over finite dimensions and supplied balls.Source: §1 · p. 2

Lower-bound mechanism

  • Universal feasibility forces each action into the convex hull of the supplied ball and the oracle replies received before that action.The finite-body argument reproduces the observed replies on a smaller consistent body; for randomized learners, feasibility events are intersected before selecting the transcript-dependent subset.Source: §1 · p. 2
  • Fresh phase directions make earlier oracle points poorly aligned, while concentrating weight on a few newly useful points incurs a shared-simplex support penalty.With m phases, making most phases inexpensive requires order m new oracle points per phase, so Q* ≍ m^2 and regret is order T/√m; all phases share one minimizer.Source: §1 · p. 2

Achievability and smoothness

  • A counted approximate-gradient method uses balanced blocks and two interleaved copies to meet the total allowance and strict per-round cap simultaneously.For prescribed smoothness, an analytic radial penalty changes the support cost from order N^-1/2 to order N^-1 in its quadratic regime.Source: §1 · p. 2

Main result

  • Theorem 4.1 gives matching lower and upper bounds under simultaneous total and per-round oracle budgets, with a lower bound covering arbitrary randomized queries and full loss feedback.The feasibility reduction and recurring phase construction support the lower bound; finite-call implementations and physical-round schedules support achievability.Source: §1 · p. 2

Achievability and smoothness

  • The smooth analysis gives a curvature-dependent lower bound, identifies when the general minimax rate remains sharp, and derives necessary oracle budgets.Theorem 5.1 gives two-sided bounds for the smooth class; Corollary 5.3 identifies the threshold and Corollary 5.5 translates it into budget requirements.Source: §1 · pp. 2–3

2. Related work

Related work studies regret–computation tradeoffs under total, per-round, and amortized oracle budgets, as well as rates that exploit loss regularity. This paper positions its contribution as matching lower bounds for dimension-free tradeoffs and explicit accounting for simultaneous caps.

Total oracle budgets

  • Lu et al. (2025) obtain O(T^(1−θ/2)) regret with O(T^(2θ)) total calls for 0 ≤ θ ≤ 1, while this paper establishes a matching lower bound for the dimension-free tradeoff.Their framework treats upper-linearizable objectives, with convex optimization as a special case; the paper treats the total budget as an exact input.Source: §2 · p. 3

Strict per-round budgets

  • Online Frank–Wolfe gives O(T^3/4) regret with one call every round, but a total or amortized count alone does not impose a roundwise cap.The paper characterizes every integer cap B ≥ 1 and combines it with an independent total allowance Q.Source: §2 · p. 3

Loss regularity and constraint information

  • Linear-loss and smooth-convex oracle bounds retain dimension dependence, whereas this paper quantifies a smoothness-dependent lower bound uniform over dimensions.Membership and separation methods use different constraint information and are excluded from the linear-oracle comparison.Source: §2 · p. 3

Lower-bound mechanism and proof ingredients

  • Offline simplex-support lower bounds do not explain the online fourth-root tradeoff; the paper makes support costs recur as new phase information arrives.Its feasibility reduction handles arbitrary learners, while the upper proof adapts blocking, approximate projection, and a Frank–Wolfe gap certificate to exact total and per-round accounting.Source: §2 · p. 3

Comparison conventions

  • Table 1 reports regret divided by GD, with prior rows as upper bounds and Θ entries as matching minimax bounds; dimension and smoothness dependencies are explicit.Strict per-round, total, and amortized call conventions differ, and total or amortized counts can concentrate calls at block boundaries.Source: §2 · pp. 3–4, Table 1 · p. 4

3. System model and preliminaries

The model gives the learner an inscribed ball, a diameter bound, and access to the unknown feasible set only through a fixed exact linear oracle. It defines admissibility under both call caps and formulates minimax regret, with dimension-independent inequalities supporting the bounds.

3.1. Online protocol and oracle access

  • The unknown compact convex set contains the supplied ball and has diameter at most D; further constraint information comes from a fixed measurable exact oracle with fixed tie-breaking.The learner may choose arbitrary query directions, observes globally defined convex G-Lipschitz losses, and may receive full loss feedback.Source: §3.1 · p. 5
  • An admissible learner must be feasible almost surely on every instance consistent with the supplied data and obey the total-call limit and any strict per-round cap.Calls are charged even in preprocessing, which is assigned to round one; calls after feedback can affect only future actions, and no membership, separation, or projection oracle is supplied.Source: §3.1 · p. 5

3.2. Minimax regret and elementary inequalities

  • The joint minimax value is the infimum over admissible learners of worst-case expected regret across dimensions, consistent bodies and oracles, and deterministic oblivious loss sequences.For prescribed smoothness β, the smooth value uses the same definition with an additional smoothness requirement; the smoothness bound is supplied to the learner.Source: §3.2 · pp. 5–6
  • The upper proof combines an inequality with a squared-distance potential, while the lower proof uses a support-size bound on the Euclidean norm of nonnegative mass.Both statements apply independently of ambient dimension.Source: §3.2 · p. 6

4. Sharp regret under simultaneous oracle budgets

The section characterizes regret under simultaneous total and per-round oracle budgets, proving matching upper and lower bounds with feasibility restricted by the learner’s finite oracle transcript. It also derives total-only and strict-only tradeoffs, including corollaries for target regret and joint caps.

4. Sharp regret under simultaneous oracle budgets

  • The effective total allowance Q*=min{Q, BT} determines the joint-budget rate; the upper bound enforces both budgets on every execution, and the lower bound applies to arbitrary randomized learners.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.Source: §4 · p. 6
  • When Q ≤ BT, the total allowance determines the rate; when Q ≥ BT, the per-round capacity does, and Θ(GD√T) is reached once q* is of order T^2.Scheduling adds no asymptotic penalty, and multiplying usable oracle work by 16 halves the oracle-dependent term below that threshold.Source: §4 · p. 6

4.1. Achievability: counted updates and interleaved blocks

  • Counted approximate-gradient updates combined with balanced blocks attain the total-budget tradeoff using at most (M − 1)H calls, with the terminal block requiring no update.Balancing the number of blocks and calls per update yields the fourth-root dependence while preserving feasibility and pathwise comparator-uniform guarantees.Source: §4.1 · pp. 8–9
  • Two interleaved copies compute updates during intervening blocks, distributing calls so the schedule respects the strict per-round cap B as well as the total budget.The construction uses gradients observed by each copy and works for every realized loss sequence, including adaptive ones.Source: §4.1 · pp. 9–10

4.2. Lower bound: feasible hulls and recurring support cost

  • Universal feasibility confines each action to the hull of the supplied ball and prior oracle replies, and a fixed product-body construction makes new replies costly across phases despite a common minimizer.The lower bound uses fresh phase directions and a shared simplex; with q = Q + 1, it gives the fourth-root dependence, with dimension O(√q log(q/δ)) when q ≤ T^2.Source: §4.2 · pp. 10–11
  • For q > T^2, a second fixed-body construction supplies the statistical term, with every round’s loss bounded below with probability at least 1−δ even with unlimited calls.The construction uses T disjoint blocks with independent sign vectors and a common minimizer; it also works when the learner has an explicit cube description.Source: §4.2 · p. 14
  • The fixed-body lower-bound argument extracts, for each learner, an oblivious loss sequence with nonnegative regret on every feasible execution and the stated high-probability lower bound.The sequence may depend on the learner, but not on its realized seed; the proof then applies the proposition with the learner’s total allowance to establish the minimax lower bound.Source: §4.2 · pp. 13–14

4.3. Consequences and recovery of previous rates

  • Total-only and strict-only budgets are special cases of the simultaneous-budget theorem, with sharpened upper constants from the analyzed constructions.The total-only corollary gives a constant-factor bound in terms of Ψ(T, Q + 1).Source: §4.3 · p. 14
  • At B = 1, the strict per-round guarantee is Θ(GDT^3/4), and increasing B improves the oracle-dependent rate by B^1/4.The one-call upper order agrees with cited online Frank–Wolfe and linear-total-budget guarantees, while the lower bound makes it minimax over admissible randomized learners.Source: §4.3 · pp. 14–15
  • For target regret GDT^α, 1/2 ≤ α ≤ 1, the effective allowance q* must scale as T^4(1−α); this is sufficient, while total-only and strict-only caps require Q + 1 of that order and B of order max{1, T^(3−4α)}.At α = 1/2, the necessary and sufficient scales are Q = Θ(T^2) and B = Θ(T) when both restrictions are imposed.Source: §4.3 · p. 15
  • The joint-cap polynomial tradeoff recovers the convex case of Lu et al. (2025), while additionally imposing a strict cap and providing a matching lower bound.The result concerns the centralized oracle problem; decentralized communication requirements are separate.Source: §4.3 · p. 15

5. Joint budgets with prescribed smoothness

The smooth-loss analysis constructs analytic hard instances to quantify how prescribed curvature changes the oracle-dependent lower bound. It identifies a smoothness threshold above which the general convex rate is sharp, while the fixed-smoothness, linear-budget regime retains a gap between dimension-free lower and upper bounds.

5.1. Analytic construction and proof

  • The proof preserves the phase mechanism while replacing the norm penalty with an analytic radial penalty that controls curvature; the general upper algorithm still applies to the smooth loss class.The penalty is increasing in the simplex norm, preserving the common minimizer.Source: §5 · p. 16, §5.1 · p. 18
  • The lower-bound instance uses globally real-analytic convex G-Lipschitz losses with gradient Lipschitz constant at most β and a common minimizer.A deterministic oblivious loss sequence with the probability guarantee can be extracted for each learner.Source: §5 · p. 16
  • A quadratic-regime penalty makes phase-local support cost scale as hp^2/N, shifting the phase threshold to N ≍ h√m and total allowance to Q* ≍ hm^3/2.Balancing yields T/√m ≍ T(h/Q*)^1/3 for positive Q*.Source: §5.1 · p. 17

5.2. Smoothness threshold and oracle requirements

  • Above the smoothness threshold, the general convex rate is matching; below it, the lower bound depends on curvature while the upper bound remains the general convex guarantee.The theorem’s analytic construction supplies the curvature-sensitive lower bound.Source: §5 · p. 16, §5.2 · p. 19
  • For fixed positive βD/G and Q* = Θ(T), the dimension-free lower bound is Ω(GDT^2/3) while the upper bound is O(GDT^3/4); a matching upper bound remains open.The cited T^2/3 upper bound has additional dimension dependence.Source: §5.2 · p. 19

6. Conclusion

The paper characterizes the dimension-free minimax oracle cost under simultaneous total and per-round budgets. Universal feasibility and recurring support costs yield the lower bound, while counted updates and interleaved blocks attain it; the smooth construction further quantifies curvature’s effect.

6. Conclusion

  • The joint-budget characterization identifies the dimension-free minimax oracle cost, matching a lower bound from universal feasibility and recurring support costs with an upper bound from counted updates and interleaved blocks.The smooth construction quantifies how prescribed curvature changes the lower bound and identifies where the general rate remains sharp.Source: §6 · p. 20
Loading 2610.00254v1…