- 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 , 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 , 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 , but increases the logarithmic term when . It would be helpful to characterize this trade-off more precisely and discuss how can be selected when 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 , the reference scale , 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 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
-
Since each loss function is assumed to be convex and -Lipschitz on , the bound may already follow from these assumptions. Please clarify whether this condition is intended as an additional assumption or is included for emphasis.
-
The choice 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.
-
The regret bound in Theorem 4 includes an aggregation term of order , which does not depend on the initialization distance 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 , and can the proposed analysis provide a sharper bound in this regime?
-
In Theorem 4, each OGD expert updates using the subgradient evaluated at the master’s prediction , rather than at the expert’s own iterate . Although the standard OGD potential inequality can apply to such updates without requiring , 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
Q2: What does the finite grid cover?
It covers distance scales from down to , not arbitrarily small positive distances multiplicatively. Above , the best adjacent dyadic scale gives factor relative to the oracle potential. Below it, the smallest expert leaves the additive term in the uniform bound. Appendix C.3 proves both cases, including the one-expert case . With geometric ratio , the nearest-scale factor becomes and the number of experts is about . 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 , with the iterated logarithm inside the square root. At , the refined bound is
For , the ratio of the displayed grid bound to 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.
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+⌈log2n⌉, 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.