acceptodds
Under review as a conference paper at ICLR 2027

Online Convex Optimization with Warm Starts: Upper and Lower Regret Bounds

Abstract

Online learners often begin from a retrieved, teacher-supplied, or previously trained parameter whose reliability is unknown. We study how this warm start affects static regret through its distance to the closest offline optimum. If that distance is revealed, online gradient descent achieves regret proportional to the distance times the square root of the horizon, and a matching lower bound holds at every distance up to half the domain diameter. Without the distance, a learning-rate ensemble and a translated parameter-free method adapt to its realized value, yet no algorithm can attain the oracle rate within one universal constant at every distance. Perfect trust in an exact warm start also entails linear sensitivity to small errors. With a known strong-convexity modulus, regularized follow-the-leader obtains a quadratic distance term without distance-dependent tuning, although its additive logarithmic term remains unmatched. A two-point bandit bound holds for oblivious losses in dimension at least two when a certified interior ball around the warm start contains a closest optimum. Logistic-loss experiments using the same online and offline objective illustrate the benefit of reliable retrieval and the cost of corruption.

Primary area:
learning theory
Keywords:
online convex optimization, warm starts, learning-augmented algorithms, static regret, parameter-free online learning, strong convexity, bandit convex optimization

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_PTZsOpenReview ↗
Rating
2
Confidence
3
Informativeness
1
Presentation
3
Soundness
2
Read review
Paper summary

The paper studies warm-start online convex optimization and derives regret bounds based on the initial point’s distance to the minimizers. It also considers lower bounds, strongly convex functions, multi-task learning, and bandit feedback.

Critical strengths

Strengths:

-The paper is readable.

Critical weaknesses

Weaknesses

-Insufficient Discussion and Comparison with Existing Methods: The algorithm in Theorem 4 appears to combine standard OGD experts over a geometric grid of step sizes using a Hedge master. Since Theorem 5 also provides a parameter-free guarantee without knowledge of the warm-start distance ε\varepsilon, the authors should clarify the distinct role and contribution of the grid-based construction in Theorem 4. In particular, how does its regret guarantee compare with that of Theorem 5 and existing learning-rate aggregation methods? A discussion of the relative advantages and limitations of these approaches, especially regarding their dependence on ε\varepsilon, aggregation overhead, and behavior when the warm start is highly accurate, would help clarify the motivation for presenting both constructions.

-Unclear Parameter Trade-offs and Theoretical Guarantees: Theorem 5 combines existing Krichevsky–Trofimov (KT) and constrained-set reduction techniques to obtain a regret guarantee without prior knowledge of the initialization distance (\varepsilon). Although the method does not require explicitly estimating (\varepsilon), its guarantee depends on a reference scale (\rho) that must be chosen in advance. Decreasing (\rho) improves the bound at an exact warm start ε=0)\varepsilon=0), but increases the logarithmic term when ε>0\varepsilon>0. It would be helpful to characterize this trade-off more precisely and discuss how ρ\rho can be selected when ε\varepsilon is unknown. Furthermore, a quantitative comparison with Theorem 4 would clarify the regimes in which the KT-based approach provides a tighter guarantee, accounting for the logarithmic dependence on ε\varepsilon, the reference scale ρ\rho, and the grid-aggregation overhead. In light of the consistency–sensitivity trade-off established in Theorem 7, it would also be useful to clarify whether the dependence on ρ\rho reflects a limitation of the analysis or a more fundamental limitation of the proposed guarantee. Finally, the derivation of the final constants, particularly the effect of the constrained-set reduction on the KT bound, should be made sufficiently explicit to facilitate verification.

-Limited Experimental Analysis to Support the Practical Claims: The experimental evaluation provides limited evidence for the broader claims regarding the benefits of warm starts and the effectiveness of the proposed methods. The experiments rely on a single dataset and a single warm-start recovery mechanism. The authors should evaluate sensitivity to task ordering, task similarity, initialization quality, and different horizons and problem dimensions. Reporting confidence intervals or standard errors and including a fairly tuned no-warm-start baseline would also strengthen the empirical evidence. Further implementation details are needed for reproducibility. Overall, the experiments provide preliminary evidence of the benefits of warm starts but do not sufficiently support the broader claims of superiority.

Questions for authors
  1. Since each loss function ℓi\ell_i is assumed to be convex and LL-Lipschitz on KK, the bound ∣∣gi∣∣2≤L||g_i||_2\leq L may already follow from these assumptions. Please clarify whether this condition is intended as an additional assumption or is included for emphasis.

  2. The choice J=⌈log⁡2n⌉J=\lceil\log_2 n\rceil and the associated geometric grid require further justification. Please explain how the grid guarantees sufficient coverage of the oracle step size over the full admissible range of the unknown initialization distance. It would also be useful to discuss whether an alternative grid design or aggregation strategy could reduce the number of experts, the approximation error, or the aggregation overhead.

  3. The regret bound in Theorem 4 includes an aggregation term of order DLnln⁡ln⁡nDL\sqrt{n\ln\ln n}, which does not depend on the initialization distance ε\varepsilon and can dominate the oracle term when the warm start is highly accurate. The authors should clarify the regimes in which the resulting guarantee remains competitive with the known-distance oracle bound. In particular, how does the guarantee behave when ε=0\varepsilon=0, and can the proposed analysis provide a sharper bound in this regime?

  4. In Theorem 4, each OGD expert updates using the subgradient gi∈∂ℓi(wˉi)g_i\in\partial\ell_i(\bar w_i)evaluated at the master’s prediction wˉi\bar w_i, rather than at the expert’s own iterate wi(j)w_i^{(j)}. Although the standard OGD potential inequality can apply to such updates without requiring gi∈∂ℓi(wi(j))g_i\in\partial\ell_i(w_i^{(j)}), the analysis connecting the expert updates, the Hedge aggregation bound, and the regret on the original loss sequence should be made explicit. Please clarify the precise linearized loss sequence used in the Hedge analysis and explain how the resulting OGD bounds for the individual experts yield the stated regret guarantee.

2 comments

Thank you for your detailed comments and questions about the algorithm comparisons, parameter choices, and experimental scope.

W1: Why present both the grid and parameter-free methods?

The grid is an elementary multiscale benchmark, not a new aggregation technique. With M=1+⌈log⁡2n⌉M=1+\lceil\log_2 n\rceil, the sharpened Theorem 4 gives

+\frac{LD}{2\sqrt n}+LD\sqrt{\frac{n\ln M}{2}}.$$ It uses $M$ projected updates per round and has an additive cost independent of $\varepsilon$. Hilbert KT uses one projection, is anytime, and has an explicit reference-wealth cost at exact advice. With $\rho=B/(2L)$, Theorem 5 implies $$r_n\le B+2L\varepsilon\sqrt{n\ln(1+96n^2L^2\varepsilon^2/B^2)}.$$ The known-horizon Normal-potential bound in Theorem 7 has a sharper budget-dependent logarithm. Sections 5–6 distinguish these guarantees and their information requirements. There is no universal ordering for every $n,\varepsilon,B$: the grid has no selected consistency budget but can be weak for accurate starts; KT offers a declared budget with method-specific logarithmic dependence; the Normal method supplies the sharp comparison in the stated regime but requires the horizon. **W2: Choosing $\rho$ and tracing the constants.** Choose a tolerable excess-loss budget $B$ before the task, then set $\rho=B/(2L)$. Alternatively, fix a declared geometric scale $\rho=\kappa D$. Neither choice uses the eventual optimizer distance. These are theoretical calibration choices, not estimates of the unknown distance. The retained coordinate-wise empirical curve is a separate heuristic and is not used to validate a Hilbert-space budget. Theorem 6 shows that reducing a small consistency budget has a fundamental cost at positive distance, including linear regret at zero budget. It does not imply that every constant or the extra horizon dependence in the KT bound is optimal. Theorem 7 demonstrates that the latter can be improved with a known-horizon algorithm. The matching regime $B\le L\varepsilon\sqrt n$ describes the analysis; it is not a prescription to tune $B$ using unavailable information. For the constraint reduction, let $W=\mathcal K-h$, $z_i$ be the unconstrained prediction, $u_i=\Pi_W(z_i)$, and $v_i\in\partial\operatorname{dist}(z_i,W)$ be the outward unit projection vector, or zero inside $W$. The modified feedback is $$a_i=\tfrac12(g_i+\\|g_i\\|v_i),\qquad \\|a_i\\|\le L, \qquad \langle g_i,u_i-u\rangle\le2\langle a_i,z_i-u\rangle.$$ Appendix C.2 proves this inequality using the convex half-scaled distance surrogate. Applying the published KT result to $a_i/L$ and multiplying by $2L$ yields the factor two, the constant $24$ inside the logarithm, and the correction $1/(e\sqrt{\pi n})$ in Theorem 5. The explicit shared-wealth recurrence is included there as well. **Q1: Does Lipschitzness already bound the subgradient?** Not every relative subgradient on a constrained domain is bounded. For example, the zero function on $[0,1]$ has every $g\le0$ as a relative subgradient at zero. Lipschitzness on a neighborhood bounds ambient subgradients, but does not remove boundary normal-cone terms from the relative subdifferential. Section 3 now explicitly requires the feedback oracle to select a subgradient of norm at most $L$. The lower-bound proof refers to bounded ambient subgradients. Appendix C.3 gives the boundary example and a convex Lipschitz extension that supplies the intended convention.

Q2: What does the finite grid cover?

It covers distance scales from DD down to qJ=D2−J≤D/nq_J=D2^{-J}\le D/n, not arbitrarily small positive distances multiplicatively. Above qJq_J, the best adjacent dyadic scale gives factor 3/(22)3/(2\sqrt2) relative to the oracle potential. Below it, the smallest expert leaves the additive LD/(2n)LD/(2\sqrt n) term in the uniform bound. Appendix C.3 proves both cases, including the one-expert case n=1n=1. With geometric ratio b>1b>1, the nearest-scale factor becomes (b+1/b)/2(\sqrt b+1/\sqrt b)/2 and the number of experts is about 1+log⁡bn1+\log_b n. This makes the coverage/computation tradeoff explicit; base two is not claimed optimal.

Q3: What happens for accurate or exact advice?

The master term is O(LDnln⁡ln⁡n)O(LD\sqrt{n\ln\ln n}), with the iterated logarithm inside the square root. At ε=0\varepsilon=0, the refined bound is

LD2n+LDnln⁡M/2.\frac{LD}{2\sqrt n}+LD\sqrt{n\ln M/2}.

For ε>0\varepsilon>0, the ratio of the displayed grid bound to LεnL\varepsilon\sqrt n is

+\frac{D}{\varepsilon}\sqrt{\frac{\ln M}{2}}.$$ This quantifies the loss of competitiveness for very accurate starts. Adding a fixed-$h$ expert would remove the small expert floor at exact advice, but not the generic Hedge overhead. We have not inferred a necessary overhead for this structured grid from an unrestricted expert-advice lower bound. **Q4: How does the shared-gradient analysis imply regret on the actual losses?** Define $s_i(w)=\langle g_i,w\rangle$, where $g_i$ is observed at the master action $\bar w_i$. Every expert runs OGD on $s_i$. Convexity at the master action and Hedge give $$\begin{aligned} r_n&\le\sum_i\langle g_i,\bar w_i-w^\dagger\rangle\\\\ &\le\min_j\sum_i\langle g_i,w_{i,j}-w^\dagger\rangle +LD\sqrt{n\ln M/2}. \end{aligned}$$ The OGD potential for each common linear sequence then gives the expert term. It never requires $g_i\in\partial\ell_i(w_{i,j})$. The proof idea in Section 5 and the complete chain in Appendix C.3 now state this explicitly. **W3: Experimental scope, tuning, and reproducibility.** The retained experiments include retrieval corruption, shuffled and adversarial initialization diagnostics, and synthetic witness families. We add equal-budget warm/cold OGD tuning and centered RFTL. Both OGD variants receive five step multipliers and five separate validation seeds. Appendix D and the supplement provide seed-bootstrap intervals, paired differences, method recurrences, sample/source indices, validation scores, and numerical certificates. Mean regrets are $4.296$ for RFTL, $6.207$ for warm OGD, and $8.410$ for validation-tuned cold OGD. At a common validation-selected step, the paired warm-minus-cold difference is $-1.907$ $[-1.934,-1.880]$. These are targeted initialization and curvature checks, not evidence of superiority for every method. The checks use one dataset, without additional horizon or dimension studies. Validation and test seeds share the finite image pool, and images can recur across tasks. We state these limitations; the main contribution is theoretical, and the checks do not establish transfer to unseen task populations. We hope we have addressed your comments in a satisfactory manner.
Reviewer_QferOpenReview ↗
Rating
1
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies how warm starts affect static regret in online convex optimization. It measures warm-start quality by ε\varepsilon, the distance from the initial parameter to the set of offline optimal solutions. When ε\varepsilon is known, standard online gradient descent with an appropriate step size achieves O(Lεn)O(L\varepsilon\sqrt n) regret. The paper also provides a matching lower bound at prescribed distances. When ε\varepsilon is unknown, the authors consider learning-rate ensembles and parameter-free methods. They show that no algorithm without this knowledge can match the known-distance benchmark within a universal constant factor for every positive ε\varepsilon. Finally, classification experiments illustrate the benefits of reliable warm starts.

Critical strengths
  • The paper is well written and clearly presented.

  • The authors conduct empirical studies to support their theoretical findings.

Critical weaknesses
  • The technical novelty is very limited. Standard OCO analyses already allow arbitrary initial points and can therefore accommodate the warm-start setting. For example, Theorem 1 follows directly from the standard OGD potential analysis by retaining the initial-distance term. Theorem 2 and Proposition 1 mainly substitute particular step sizes into this bound, while Theorem 4 combines a standard learning-rate grid with Hedge aggregation. The authors should clarify the specific analytical challenges introduced by warm starts and explain which new technical ideas address them.

  • The authors should better explain the significance of studying the warm-start setting separately. As presented, the algorithms used are essentially the same as those in prior work, making it unclear what additional algorithmic insights this setting provides.

Questions for authors
  • The lower-bound analysis mainly uses variations of existing proof techniques, so its technical contribution is still limited.

  • The experimental results show that grid aggregation underperforms no-warm-start OGD. While this does not contradict the theoretical regret guarantees, it leaves the practical benefits of aggregation unclear. The authors should explain this performance gap and provide additional sensitivity analyses, particularly regarding learning-rate choices and aggregation overhead.

1 comment

Thank you for your careful review and for asking us to sharpen the technical contribution and its practical interpretation.

We agree that the OGD initialization term, step-size substitutions, and grid aggregation are standard. The revised paper does not claim these algorithms or their basic analyses as new. The main change is a quantitative lower-bound result with an explicitly limited matching statement.

Analytical challenge and technical contribution.

Translation to hh immediately turns a comparator-adaptive upper bound into a distance-dependent upper bound. It does not by itself establish a lower bound at an exact distance from the actual optimizer. A hard comparator can fail to minimize the final objective over the learner's original domain. Restricting the comparator to a ball around hh would also change the comparison class.

The barrier construction forces the full-domain optimizer to a prescribed distance. The anchoring construction preserves a common unpredictable prefix across exact and misspecified advice instances, while forcing the final optimizer to the chosen target. Section 6 now uses that construction to quantify the cost of a consistency budget, rather than only exclude a homogeneous bound. For every positive prescribed distance and finite horizon, revised Theorem 6 gives

\sqrt{n\min\\{n,1+\ln(1+L\varepsilon\sqrt{n}/B)\\}}.$$ The proof combines a classical origin-budget argument with an explicit tail estimate and linear saturation. We credit those existing ingredients and do not present the use of random signs, or the origin-budget phenomenon itself, as new. The claim is the resulting finite-horizon exact-optimizer-distance statement on the fixed compact interval. Revised Theorem 7 uses a published algorithm to match the order for $0 < B \le L\varepsilon\sqrt{n}$. **What studying the warm start separately tells us.** The analysis exposes a concrete choice: how much excess cumulative loss to tolerate relative to an exact initialization. A declared budget $B$ answers that question without estimating $\varepsilon$. The lower bound then quantifies the unavoidable recovery cost at positive distances. At zero budget, that cost has order $nL\varepsilon$, not $L\varepsilon\sqrt{n}$. This is an interpretation of trust in the supplied parameter and of the guarantees available from existing algorithms, not a proposal for another OGD update. The known-distance case is explicitly an oracle benchmark. It separates initialization quality from the difficulty of assessing that quality. The repeated-task discussion similarly concerns supplied parameters and a conditional hard family, not a new meta-learning procedure or a guarantee of learning better initializations. **Grid performance and sensitivity.** The grid competes with shared-gradient experts initialized at $h$; cold OGD is not one of those trajectories. Its theorem therefore does not guarantee improvement over cold OGD. We retain the original diagnostic and do not claim an aggregation benefit from it. The revised analysis makes its limitations quantitative. With $M=1+\lceil\log_2 n\rceil$, the ratio of the refined grid bound to the oracle benchmark is $$\frac{3}{2\sqrt{2}}+\frac{D}{2n\varepsilon} +\frac{D}{\varepsilon}\sqrt{\frac{\ln M}{2}}.$$ Appendix C.3 derives the cutoff contribution and the dependence on geometric spacing. More generally, master rate $\gamma > 0$ contributes $\ln M/\gamma+\gamma nL^2D^2/8$ to the standard bound. Thus reducing this rate increases the initial learning cost, while increasing it enlarges the quadratic rate term. These are theoretical sensitivities, not a measured explanation of the full empirical gap; convexity slack and the coupled expert trajectories also matter. The added empirical comparison isolates initialization with equal tuning budgets. Both warm and cold OGD receive five step multipliers and five separate validation seeds. At the common validation-selected multiplier $2$, the paired warm-minus-cold difference is $-1.907$ with interval $[-1.934,-1.880]$. Separately tuned warm and cold means are $6.207$ and $8.410$. This supports the initialization comparison under the stated protocol, not a claim that aggregation is practically superior. A broader empirical investigation of aggregation remains outside the targeted additions. We hope we have addressed your comments in a satisfactory manner.
Reviewer_hfesOpenReview ↗
Rating
3
Confidence
3
Informativeness
1
Presentation
3
Soundness
3
Read review
Paper summary

This paper investigates online convex optimization (OCO) over compact domains when the learner is initialized at a supplied warm-start parameter h∈Kh \in \mathcal{K}, characterizing static regret as a function of the ex-post distance ε=dist⁡(h,W⋆)\varepsilon = \operatorname{dist}(h, \mathcal{W}^\star) to the offline optimizer set. The authors establish that when ε\varepsilon is known, online gradient descent achieves a minimax-optimal Θ(εLn)\Theta(\varepsilon L \sqrt{n}) rate via a matching piecewise-linear barrier lower bound that pins the offline optimizer to any prescribed distance ε∈[0,D/2]\varepsilon \in [0, D/2]. When ε\varepsilon is unknown, the paper pairs grid aggregation and translated parameter-free Krichevsky–Trofimov reductions with an anchoring impossibility result ruling out uniform constant-factor oracle adaptation, alongside analyses of local consistency-sensitivity tradeoffs, μ\mu-strongly convex Regularized Follow-The-Leader (RFTL), feasible two-point bandit extensions, and empirical validation on synthetic witnesses and UCI Digits.

Critical strengths
  1. The paper introduces a piecewise-linear barrier and anchoring construction that pins the unique offline minimizer of the full-domain cumulative loss to an exact prescribed distance ε∈[0,D/2]\varepsilon \in [0, D/2] inside a compact set, placing the distance-to-optimizer-set metric on a rigorous minimax footing.

  2. The theoretical framework cleanly separates the intrinsic value of a warm start from the algorithmic cost of adapting to it without knowing ε\varepsilon, contrasting the logarithmic/grid overhead required for general convex losses against the ε\varepsilon-free μ2ε2\frac{\mu}{2}\varepsilon^2 distance dependence (and accompanying harmonic stability floor) unlocked by intrinsic μ\mu-strong convexity.

  3. The mathematical proofs, including the pathwise application of the Cutkosky–Orabona constrained reduction in the parameter-free bandit setting and the spherical Poincaré inequality second-moment bound for two-point feedback, are technically sound, transparent about their assumptions, and well-supported by synthetic and real-data retrieval corruption diagnostics.

Critical weaknesses
  1. The impossibility of uniform adaptation in Theorem 6 relies on sending ε=∣u∣→0\varepsilon = |u| \to 0 at a fixed horizon n=2mn=2m, which only rules out purely homogeneous CεLnC\varepsilon L\sqrt{n} bounds and leaves open a quantitative logarithmic lower bound on compact sets analogous to existing unconstrained comparator-adaptive tradeoffs (e.g., No-regret algorithms for unconstrained online convex optimization, Matthew Streeter and H. Brendan McMahan, 2012; Dimension-free exponentiated gradient, Francesco Orabona, 2013; Unconstrained online linear learning in Hilbert spaces: Minimax algorithms and normal approximations, H. Brendan McMahan and Francesco Orabona, 2014).

  2. Similarly, the local sensitivity versus consistency lower bound in Theorem 7 and Corollary 2 (max⁡Ln8δ,Lδ−C0\max{\frac{L\sqrt{n}}{8}\delta, L\delta - C_0}) is derived from a single-round triangle inequality that is dominated by the standard prescribed-distance minimax bound for any n≥64n \ge 64, and the accompanying tuned OGD upper bound only matches it at the specific oracle scale C0=Θ(Lnε)C_0 = \Theta(L\sqrt{n}\varepsilon) (see e.g., Dimension-free exponentiated gradient, Francesco Orabona, 2013; Optimal robustness-consistency trade-offs for learning-augmented online algorithms, Alexander Wei and Fred Zhang, 2020).

  3. Several upper and lower bounds, such as the strongly convex RFTL guarantee in Theorem 8 (whose Theorem 9 lower bound only captures the first-round μ2ε2\frac{\mu}{2}\varepsilon^2 term and leaves the 2L2μHn\frac{2L^2}{\mu}H_n harmonic baseline unmatched) and the two-point bandit bound in Proposition 2 (which requires oracle knowledge of ε\varepsilon and a certified interior ball B(h,r)⊆KB(h,r) \subseteq \mathcal{K}, or else loses the d\sqrt{d} factor in Proposition 5), are direct specializations of standard textbook mechanisms (See e.g., Introduction to Online Convex Optimization, Elad Hazan, 2016; Learning-to-Learn Stochastic Gradient Descent with Biased Regularization, Giulia Denevi, Carlo Ciliberto, Riccardo Grazzi, and Massimiliano Pontil, 2019; An optimal algorithm for bandit and zero-order convex optimization with two-point feedback, Ohad Shamir, 2017; Online convex optimization in the bandit setting: Gradient descent without a gradient, Abraham D. Flaxman, Adam Tauman Kalai, and H. Brendan McMahan, 2005).

  4. In the UCI Digits evaluation, the per-round objective is λ\lambda-strongly convex (λ=10−2\lambda = 10^{-2}), yet the authors omit Warm-start RFTL (Theorem 8) from the real-data comparison and replace the exact Hilbert-space parameter-free reduction of Theorem 5 with an under-specified coordinate-wise KT heuristic, which the authors might consider addressing by detailing the KT hyperparameters (ρ\rho, projection mechanism) and including or discussing the exact Theorem 5 and Theorem 8 algorithms.

Questions for authors

Please see weaknesses.

1 comment

Thank you for your comments. We agree with both criticisms and have strengthened the central analysis rather than presenting those results as a sharp tradeoff.

W1: A quantitative lower bound on the compact domain.

The revised Theorem 6 uses the fixed interval K=[−D/2,D/2]\mathcal K=[-D/2,D/2], warm start h=0h=0, and horizon nn. Let C0(n)(A)C_0^{(n)}(A) be the supremum of expected regret over deterministic admissible sequences with exact advice. If an algorithm does not receive ε\varepsilon and C0(n)(A)≤BC_0^{(n)}(A)\le B, then for every 0<ε≤D/20<\varepsilon\le D/2 and B>0B>0 there is a deterministic sequence with a unique optimizer at distance exactly ε\varepsilon such that

\sqrt{n\min\\!\left\\{n,1+\ln\\!\left(1+\frac{L\varepsilon\sqrt n}{B}\right)\right\\}}.$$ This is a finite-horizon statement, not a limit as $\varepsilon\to0$. Appendix C.1 supplies a binomial-tail formulation and a complete elementary block proof, including $n=1$, odd horizons, and very small budgets. The key transfer is an anchoring suffix. After $m=\lfloor n/2\rfloor$ linear losses $g_iw$, with $|g_i|\le L/2$, append $m$ losses $L|w-u|$. The unique optimizer of the full objective is $u$, while the prefix actions do not depend on $u$. Consistency at $u=0$ bounds the expected prefix loss for every sign sequence. A positive-tail event then forces regret at $u=-\varepsilon$. We explicitly credit the origin-budget mechanism to the comparator-adaptive literature (Streeter and McMahan, 2012; Orabona, 2013). The exact-distance optimizer condition on the original compact domain is what the suffix enforces. **W2: The dominated local bound and the matching regime.** You are right that the original term $L\delta-C_0(A)$ is dominated by $L\delta\sqrt n/8$ for $n\ge64$. We have moved that local comparison to the appendix and stated this limitation there. It no longer carries the main consistency claim. At $B=0$, Theorem 6 gives $\mathbb{E} r_n\ge nL\varepsilon/6$ for $n\ge2$, and $L\varepsilon$ for $n=1$. Staying at $h$ gives the matching order $nL\varepsilon$. For $B>0$, revised Theorem 7 uses the known-horizon Normal-potential method of McMahan and Orabona (2014, Theorem 11) with the constrained reduction of Cutkosky and Orabona (2018, Theorem 3): $$r_n\le B+L\varepsilon\min\left\\{n, 2\sqrt{2\pi n\ln(1+cL\varepsilon\sqrt n/B)}\right\\}, \quad c=2(\sqrt2-1)\sqrt\pi.$$ Both branches hold for the same algorithm. The upper and lower orders match when $0<B\le L\varepsilon\sqrt n$; an additive-budget gap remains outside that regime. We do not claim an all-budget characterization or use the unknown distance as a tuning input. **W3: Standard mechanisms and unmatched terms.** We agree that centered RFTL and two-point smoothing are applications of established techniques. They are supporting results, not the principal novelty claim. The repeated-quadratic lower bound only isolates the first-round regularization term and does not match the harmonic term. Section 7 now makes this distinction explicit. Appendix C.4 also gives a nonsmooth strongly convex family with first-round expected regret at least $(L-\mu D)\varepsilon+\mu\varepsilon^2/2$, illustrating why strong convexity alone does not imply a universal quadratic distance law. The bandit extension retains its stated oracle-distance, certified-interior-ball, and oblivious-loss assumptions. The unknown-distance reduction still has the larger dimensional dependence. We have not claimed to remove that gap: replacing an almost-sure gradient bound by a second-moment bound in the KT reduction would require a different argument. **W4: RFTL and exact Hilbert-space KT on Digits.** Section 9 and Appendix D now add centered RFTL and fair OGD tuning on the same $30$ test seeds and $1{,}350$ tasks. RFTL has mean regret $4.296$ with a $95\\%$ seed-bootstrap interval $[4.275,4.317]$. Warm OGD has $6.207$ $[6.164,6.253]$, and validation-tuned cold OGD has $8.410$ $[8.362,8.458]$. RFTL uses known curvature and regularized prefix solves; we do not present this as an equal-computation comparison. Offline and prefix solves have computed convex optimality gaps below $10^{-10}$, with maximum accumulated RFTL loss-error certificate $0.001865$ per task. For KT, Appendix C.2 supplies the exact Hilbert recurrence, shared initial wealth $\rho$, modified feedback, and projection rule. Appendix D.2 separately specifies the coordinate-wise heuristic used in the retained diagnostic, including its one-round prediction delay and direct projection. That curve is not an empirical validation of Theorem 5. The added empirical table addresses the missing RFTL baseline; the Hilbert-space guarantee is supported by the explicit reduction and cited theorem, not a claim that the heuristic is equivalent to it. We hope we have addressed your comments in a satisfactory manner.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.