acceptodds
Under review as a conference paper at ICLR 2027

Discounted Online Convex Optimization with an Unknown Discount: Sharp Rates and Prefix–Endpoint Evaluation

Abstract

We study online convex optimization evaluated with a geometric discount that is unknown to the learner, so one decision sequence must work for every discount. With known horizon and curvature parameter, bounded subgradients, and possibly nonsmooth losses, we use the known-discount benchmark . This benchmark is attainable and minimax-correct up to absolute constants on a normalized family. We introduce Sharp-BDF, which queries one genuine subgradient and no function values per round, while matching the benchmark's leading constant simultaneously for all . The method recycles the quadratic surplus of each base learner through a shared compensation coefficient and transfers the guarantee from a finite forgetting grid to the full discount interval without an -net. The price of not knowing depends on the evaluation protocol. The worst-case additive excess is when every prefix must be served, but when only a single fixed endpoint is evaluated. Matching lower bounds hold even for randomized full-feedback algorithms and persist after subtracting the true minimax value on the steady-state discount set. A hybrid variant has constant adaptation at both scale extremes.

Primary area:
learning theory
Keywords:
online convex optimization, discounted regret, strong convexity, adaptive online learning

Reviews

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

This paper considers online optimization with discounted losses, where the discount factor is unknown to the learner. The authors aim to design an algorithm which performs well under two evaluation protocols, which they call fixed-endpoint and prefix evaluation. The main idea is to run a collection of experts with different effective memory lengths, each tailored to a different possible discount factor. The paper presents regret upper bounds for this algorithm, along with lower bounds which essentially match them. The validation is mainly theoretical, though the paper also includes some numerical experiments.

Critical strengths
  1. The upper and lower bounds essentially match, which suggests the analysis is tight for the setting as posed. As far as I can follow, the results are likely correct.
  2. The paper includes a numerical experiment, which helps ground the theory.
Critical weaknesses
  1. The setting is not well motivated. I could not see why this is an interesting or important theoretical question, and the introduction does not make the case. This matters because without a clear motivation, it is hard for a reader to judge the significance of the results, even if they are correct.
  2. The exposition is very difficult to follow. The paper is highly technical from the abstract onward, uses many terms before defining them, and does not prioritize how information is presented. A reader who is not already an expert in this specific line of work will struggle to understand the setting, the algorithm, or the relationship to prior work. This matters because a paper should situate, motivate, explain and teach, and in its current form the manuscript does not do these things for most readers.
Questions for authors

Clarifications:

  1. Relation to prior work. The paper seems like it might be a follow-up to Yang et al. (2026), but I could not follow the discussion of the relationship because it depends on many technical terms which are not yet defined. What exactly is new here relative to that work? I also had trouble with the related work table. What is the meaning of the "excess over comparator" column, and what type of object do its entries refer to? How do the entries relate to one another? The queries column lists 0 value queries explicitly for the proposed algorithm. Is this also implicitly zero for the other methods which use only gradients?

  2. Importance of the setting. The introduction seems to treat algorithmic choices like step sizes and learning rates as if they were the same thing as discounting as an objective. Could the authors clarify the distinction? I also did not follow the conclusion that trajectories are therefore evaluated under many "memory lengths." Does this mean different discount factors? From Figure 1, the two post-run evaluation protocols seem to bear some resemblance to best-arm identification versus regret in multi-armed bandits. Is this the right analogy? If so, making the connection explicit would help. The terms "fixed endpoint" and "prefix" are not familiar to me in this setting, so it would help to explain where they come from. Most of all, why should we care about performing well under both protocols?

Suggestions for revision:

  1. The abstract should be less technical. For example, the notation BT(λ) appears in the abstract, but it seems to be a novel quantity introduced by this paper. Similarly, the known-discount benchmark and the fixed-endpoint protocol may not be familiar to readers. I also did not understand what "scale extremes" or "a constant variant" refer to.

  2. The discussion of strong convexity in the second paragraph of the introduction was confusing to me. Is there supposed to be a connection between having a discount factor and ensuring strong convexity? If so, it should be explained, and if not, the discussion could be moved or removed.

  3. The third and fourth paragraphs of the introduction are too technical too early, with equations appearing before the setting and interaction protocol are defined. For example, is log(H_λ) a "usual" comparison? In what literature, and with what meaning?

  4. The basic interaction protocol and key aspects of the setting are folded into a notation paragraph alongside small details such as the base of the logarithm. I only understood the setting once I reached Section 3.2. I suggest presenting the setting and protocol clearly and early, and separating them from minor notational conventions.

  5. The notation for the set of experts is introduced abruptly, without describing what the experts are or what purpose they serve. A short explanation of the idea, meaning experts with different effective memory lengths tailored to different possible discounts, would make the algorithm much easier to follow.

  6. The technical sections refer to results out of order. For example, the beginning of Section 5.1 refers to a "grid transfer lemma," which is meaningless to a reader at that point. A brief roadmap of the analysis should introduce any results important enough to name.

  7. More generally, I encourage the authors to revise the manuscript with a reader in mind who is less familiar with this specific line of work. The paper would be much stronger if it took more space to situate the problem, motivate it, and explain the main ideas, even at the cost of moving some technical detail to the appendix.

4 comments

We thank the reviewer for recognizing that the upper and lower bounds essentially match and that the numerical study supports the theory. The paper studies a concrete question that arises whenever one trajectory is evaluated after deployment with a memory length chosen later. We address each point separately.

Motivation of the setting

The discount is an evaluation parameter. It determines how much weight the evaluator assigns to recent and old rounds. The learner does not know this parameter and cannot replay the trajectory after the evaluation rule is chosen.

This situation occurs when a logged trajectory is audited with several memory windows, when a deployed optimizer is inspected with different decay rates, or when a reinforcement-learning trajectory is scored with different horizons. The same decisions must serve all these evaluations. A learner that knows the evaluation discount can tune its memory. A learner that does not know it faces a genuine adaptation problem.

The main question is the cost of this missing evaluation information. The answer depends on when the trajectory will be evaluated. If one fixed endpoint is used, the cost is Θ(log⁡log⁡N)\Theta(\log\log N). If every prefix must be valid, the cost is Θ(log⁡N)\Theta(\log N). The matching full-feedback lower bounds show that this difference comes from the evaluation requirement itself.

Why the question is theoretically important

The paper separates three effects that are usually combined. Curvature controls the base learning rate. Discounting controls the evaluation weights. The evaluation quantifier controls which histories the same trajectory must serve.

This separation yields a sharp result. The learner uses one subgradient per round and no function values. Sharp-BDF preserves the leading coefficient of the known-discount OGD comparator for every discount on one trajectory. The lower bounds then show that the remaining adaptation cost has two different optimal orders. This is a structural characterization of unknown evaluation parameters in curved online optimization.

Exposition and the central picture

The setting can be summarized in four lines. At round tt, the learner chooses xtx_t before seeing ftf_t. It receives one subgradient at xtx_t. The discount λ\lambda is never revealed and affects no update. After the run, an evaluator chooses TT, λ\lambda, and a comparator uu.

The algorithm runs base learners with different forgetting rates. Each base learner represents one possible effective memory. The master combines them without knowing which memory the evaluator will use. Prefix evaluation requires all historical endpoints. Endpoint evaluation requires only the final endpoint, so it allows a smaller adaptation cost.

Relation to Yang et al. [1]

Yang et al. [1] study unknown discounts over a continuous interval for general convex losses. Their result identifies curvature as an open direction. Our work resolves that direction under strong convexity and nonsmooth first-order feedback.

The new elements are fourfold. First, we identify the coefficient-sensitive benchmark BTor(λ)=G2KT(λ)/(2μ)B_T^{\mathrm{or}}(\lambda)=G^2K_T(\lambda)/(2\mu). Second, Sharp-BDF preserves this coefficient with one genuine subgradient and zero function values. Third, we distinguish fixed-endpoint and prefix-uniform evaluation and prove matching Θ(log⁡log⁡N)\Theta(\log\log N) and Θ(log⁡N)\Theta(\log N) lower bounds. Fourth, the lower bounds hold for randomized full-feedback algorithms and remain true after subtracting the true minimax value on the steady-state discount set.

The relation to discounted expert aggregation [2] is also direct. Those methods receive the discount as an input. Here the discount is hidden from the learner and selected only for evaluation. That missing input changes the minimax problem.

Meaning of the comparison table

The queries column counts genuine loss-oracle calls per round. A gradient query means one subgradient evaluation at the played point. A value query means evaluating the loss away from the played point. Methods described only with gradients have zero value queries. The proposed method uses one gradient query and zero value queries.

The excess column is an additive worst-case excess over the comparator stated for that row. For this paper, the comparator is the known-discount benchmark BTorB_T^{\mathrm{or}}. For prior work, the comparator is the one used in that work. The table is a map of problem settings and guarantees, not a ranking of incomparable numbers.

Discounting versus algorithmic choices

A step size is chosen by the learner and changes how the learner updates. The discount is chosen by the evaluator and changes how the realized trajectory is scored. They are different objects.

The algorithm may run many forgetting scales internally, but it produces one decision sequence. The evaluator may later apply any λ\lambda to this same sequence. The learner never selects λ\lambda, and the evaluation discount never enters the update.

Why both protocols matter

The two protocols correspond to two common uses of a logged trajectory. A fixed endpoint models one audit date. Prefix evaluation models a system that must be auditable at every stopping time. The latter is strictly stronger because the evaluator can select both the endpoint and the memory after seeing the trajectory.

The bandit analogy is useful only at the level of information structure. Endpoint evaluation resembles selecting one history scale after observing the run. Prefix evaluation must protect all time positions as well. The mathematical problem is different from best-arm identification because there are no stochastic arms and no feedback-dependent evaluation choice during learning. The distinction matters because it produces different minimax orders for the same trajectory and the same feedback model.

Abstract terminology

The benchmark is simply the regret guarantee of a learner that is told λ\lambda before round 1. The fixed-endpoint protocol means that only T=NT=N is evaluated. The prefix protocol means that every T≤NT\le N must be valid. An effective memory Hλ=min⁡{N,(1−λ)−1}H_\lambda=\min\{N,(1-\lambda)^{-1}\} is the number of recent rounds that receive substantial evaluation weight. Scale extremes mean bounded HλH_\lambda or bounded N/HλN/H_\lambda. Constant adaptation means an additive excess bounded independently of NN in those regimes.

Role of strong convexity

Strong convexity and discounting are independent parts of the setting. Strong convexity gives the fast base rate and makes the surrogate recycling identity useful. Discounting defines the post-run evaluation. The paper does not use discounting to create curvature, and it does not use curvature to define discounting.

The role of log⁡Hλ\log H_\lambda

The quantity log⁡Hλ\log H_\lambda is a coarse orientation used in prior discounted and adaptive-regret analyses [1, 2]. It describes the effective history scale. The coefficient-sensitive quantity in this paper is instead $ K_T(\lambda)=\sum_{t=1}^T\frac{\lambda^{T-t}}{S_t(\lambda)}. $ The distinction is central. log⁡Hλ\log H_\lambda hides initialization effects and cannot preserve the oracle coefficient. KT(λ)K_T(\lambda) captures both initialization and steady state. This is why the paper first introduces the interaction protocol and then defines KTK_T as the exact benchmark quantity.

Interaction protocol and notation

The interaction is causal. The learner selects xtx_t, observes one vector gt(xt)g_t(x_t), and updates all internal experts from this shared vector. It never receives the evaluation discount. The full-feedback model used in the lower bounds is strictly richer because it may reveal the full loss function. Thus the lower bounds do not rely on the single-gradient restriction.

Meaning of the expert set

Expert ii uses γi\gamma_i and therefore tracks a different forgetting scale. A long-memory expert is suitable when λ\lambda is close to 1. A short-memory expert is suitable when λ\lambda is small. The master uses their predictions to form one decision.

The compensation coefficient ct,i=1−1/St,ic_{t,i}=1-1/S_{t,i} appears in both the prediction weights and the potential update. The identity $ |g_t+\mu(z-x_t)|^2 =|g_t|^2+2\mu\ell_t(z) $ lets the master recycle the surrogate surplus instead of paying a constant-factor loss for each expert. This is the mechanism behind the coefficient-preserving guarantee.

Proof roadmap

The logical order is short. First, the known-discount OGD analysis defines KTK_T and proves attainability. Second, the compensated master controls all grid experts with one gradient. Third, a signed transfer identity moves the grid guarantee to every continuous discount. Fourth, time-block and history-scale constructions give the two lower bounds. Finally, the true-minimax comparison removes benchmark slack on the steady-state set.

Overall significance

The paper gives a complete answer to a previously unresolved curved-loss version of unknown-discount adaptation. It combines a one-gradient algorithm, exact coefficient preservation, continuous-discount transfer, and matching lower bounds that separate evaluation protocols. The result is useful both as an algorithmic guarantee and as a characterization of what post-run evaluation can cost.

References

[1] Wenhao Yang, Sifan Yang, and Lijun Zhang. Discounted Online Convex Optimization: Uniform Regret across a Continuous Interval. ICLR, 2026.

[2] Alexey Chernov and Fedor Zhdanov. Prediction with Expert Advice under Discounted Loss. ALT, 2010.

[3] Elad Hazan, Amit Agarwal, and Satyen Kale. Logarithmic Regret Algorithms for Online Convex Optimization. Machine Learning, 2007.

Thanks for your reply and additional clarifications. Many of these points will improve a future revision. As is stands, the manuscript does not seem ready for publication, and I will keep my score.

Reviewer_dwzCOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies strongly convex online convex optimization with an unknown evaluation discount, requiring a single decision sequence to accommodate all discounts. With a known horizon and curvature parameter and only one subgradient observed per round, Sharp-BDF uses compensation based on the quadratic term of the surrogate loss to preserve the coefficient of the known-discount benchmark BTor(λ)=G2KT(λ)/(2μ)B_T^{\mathrm{or}}(\lambda)=G^2K_T(\lambda)/(2\mu) and extends guarantees from a finite grid to a continuous interval of discounts. The paper establishes normalized adaptation costs of Θ(log⁡N)\Theta(\log N) when every prefix must be evaluated and Θ(log⁡log⁡N)\Theta(\log\log N) at a fixed endpoint. It also provides a hybrid method with constant adaptation cost in both the short-memory and nearly full-history regimes.

Critical strengths
  1. The separation in adaptation costs between the two evaluation protocols is valuable. The matching lower bounds use uncertainty about temporal location and history scale, respectively, and apply even to randomized algorithms with full feedback, showing that the difference stems from the evaluation requirements themselves. The same rates hold after subtracting the true minimax value on the steady-state discount set, further ruling out a separation caused solely by slack in the benchmark.

  2. The method preserves the benchmark coefficient with one gradient per round through a concrete and effective technical design. The identity for the squared surrogate gradient, together with the use of the compensation coefficient in both the prediction weights and the potential, avoids the constant-factor loss incurred by directly bounding the surrogate gradient. The transfer to a continuous interval of discounts also preserves the coefficient of the benchmark term. The supporting proofs are fairly complete.

Critical weaknesses
  1. The choice of benchmark and the interpretation at finite horizons remain substantial limitations. The guarantees over the full discount interval use the attainable upper bound BTorB_T^{\mathrm{or}} as the benchmark, while Theorem 5 establishes only a constant-factor comparison with the true minimax value. The matching results relative to the true minimax value are restricted to KT(λ)≤2K_T(\lambda)\le 2. Although the paper acknowledges this distinction, the analysis does not sufficiently quantify the benchmark slack when KTK_T grows with the horizon. Preserving the coefficient of BTorB_T^{\mathrm{or}} therefore does not directly establish an equally tight approximation to optimal performance with a known discount. Moreover, the explicit lower bounds in Theorems 2 and 3 require log⁡N≥16384\log N\ge16384 and log⁡log⁡N≥8192\log\log N\ge8192, respectively, and provide no informative numerical separation at the horizons used in the experiments. I recognize the value of the asymptotic separation, but the scope of this refinement and its limited implications for finite horizons weaken the overall case for the contribution.

  2. The experiments do not sufficiently isolate the gains from the core mechanism. Section 6.2 attributes the advantage of the hybrid over BDF-Curv to compensation, but Table 2 reports 20.120.1 and 13.013.0 projections per round on average, respectively, and the two methods also differ in their expert families and activation schedules. Furthermore, the experimental domain satisfies D=G/μD=G/\mu, so the naive surrogate gradient admits a 2G2G bound, yet the baseline still uses the conservative learning rate μ/(9G2)\mu/(9G^2) based on 3G3G. The comparison thus mixes differences in algorithmic structure with the effects of parameter tuning. The existing comparison between the prefix and naive variants and the prior ablations are useful, but a compensation ablation with the same structure, priors, and appropriately calibrated learning rates is still needed. In addition, the gap in Appendix H.1 subtracts the actual regret of the algorithm that knows the discount, whereas Equation (4) subtracts the analytical benchmark. Both quantities should be reported separately, and Figure 3 and Table 3 should specify which one they use. Checking the former against the certificate provides a conservative verification of the latter, but its numerical values cannot be directly interpreted as the adaptation cost characterized by the theory.

Questions for authors
  1. In the long-memory regime where KT(λ)>2K_T(\lambda)>2, could the authors quantify the gap between BTorB_T^{\mathrm{or}} and the true minimax value more precisely, or explain what additional performance improvements are guaranteed by preserving this benchmark coefficient? Can the existing lower bounds be expressed in a more informative form for finite horizons? These points would directly affect my assessment of the significance of the theoretical contribution.
  2. Could the authors provide a compensation ablation within the same hybrid structure, using identical priors and activation rules and calibrating the baseline learning rate to the actual 2G2G bound, while separately reporting excess relative to the analytical benchmark and to the actual regret of the known-discount algorithm? This would help determine how much of the observed advantage comes from compensation itself.
2 comments

We thank the reviewer for highlighting the value of the protocol separation and the technical role of exact surrogate recycling. The two lower bounds use different sources of uncertainty, temporal location for prefix evaluation and history scale for endpoint evaluation. They hold for randomized full-feedback algorithms and remain valid after subtracting the true minimax value on the steady-state set. We address the two concerns and both questions below.

W1 and Q1: Benchmark slack and finite-horizon meaning

The benchmark gap can be quantified directly on the normalized one-dimensional class. Let

\qquad b_T(\lambda)=\frac12K_T(\lambda).$$ The lower bound in Theorem 5 gives $v_T\ge K_T/48$. The virtual-target forward predictor in the question gives the sharper upper bound $v_T\le K_T/8$. Therefore $$\frac{K_T}{48}\le v_T\le\frac{K_T}{8}, \qquad \frac{3K_T}{8}\le b_T-v_T\le\frac{23K_T}{48}. \tag{1}$$ Thus, when $K_T$ grows, the gap between the analytical benchmark and the true minimax value is itself of order $K_T$. The coefficient claim has a precise interpretation. With a known discount, the general-domain OGD comparator is $B_T^{\mathrm{or}}$. With an unknown discount, Sharp-BDF satisfies \$ R_T^\\lambda(u) \\le B_T^{\\mathrm{or}}(\\lambda) +\\frac{G^2}{\\mu}C_N(\\lambda), \$ on one trajectory for all discounts. The unknown discount adds only the additive term $C_N(\lambda)$. It does not multiply the leading $K_T(\lambda)$ term. For the hybrid, $C_N(\lambda)$ is constant when $H_\lambda=O(1)$ or $N/H_\lambda=O(1)$, and is $O(\log\log N)$ at intermediate scales. Equation (1) also makes the finite-horizon interpretation explicit. Relative to the exact minimax value, the total excess is bounded by \$ R_T^\\lambda(u)-V_T(\\lambda) \\le \\frac{G^2}{\\mu} \\left(\\frac{23}{48}K_T(\\lambda)+C_N(\\lambda)\\right). \$ The term proportional to $K_T$ is comparator calibration. The term $C_N$ is the price of not knowing the discount. The steady-state results isolate the second term. On $K_T\le2$, Theorems 10 and 11 subtract the true known-discount minimax value and prove the matching $\Theta(\log\log N)$ endpoint cost and $\Theta(\log N)$ prefix cost. The protocol separation therefore survives exact benchmark calibration. The existing change-of-measure construction also gives more informative finite-horizon bounds when its exact geometric weights are retained. For a selected block $I$, let $$W=\sum_{t\in I}\lambda^{T-t}, \qquad J_I=\sum_{t\in I}\lambda^{2(T-t)}(1+\varepsilon^2)^{t-s}, \qquad E_I=\sum_{t\in I}\mathbb E_0 Z_t^2.$$ The exact loss expansion gives the normalized inequality \$ d\\ge \\frac{\\varepsilon^2W^2}{8S_T(\\lambda)} -\\frac{\\varepsilon}{4}\\sqrt{E_IJ_I} -\\frac12K_T(\\lambda). \\tag{2} \$ For prefix evaluation, one of the time blocks satisfies $E_I\le(4\mathsf H_N+8d)/k$. Setting $N=2^{31}$, $h=38$, $m=49$, and $\varepsilon=1/2$ in (2) yields \$ d\\ge0.1316047-0.0325416\\sqrt{11.2438+d}, \$ which implies \$ \\Delta_N^{\\mathrm P,\\star}\\ge0.022. \$ For endpoint evaluation, one history annulus satisfies $E_I\le16(1+d)/k$. Using $h\varepsilon^2=76$ gives \$ d\\ge0.0137285-0.0133021\\sqrt{1+d} \$ when $\log\log N\ge84$, and hence \$ \\Delta_N^{\\mathrm E,\\star}\\ge4\\times10^{-4}. \$ These are sufficient finite-horizon bounds from the same lower-bound constructions. They substantially improve the displayed sufficient thresholds while preserving the asymptotic orders.

W2 and Q2: Isolating compensation from hybridization

We ran the requested controlled ablation. The ablation uses exactly the hybrid expert family, the same priors, the same activation times, the same base learners, the same one-gradient feedback, and the same number of projections per round. It removes only the compensation mechanism. The baseline mixes with vt,iv_{t,i} instead of vt,ict,iv_{t,i}c_{t,i}, updates with exp⁡(−αℓt,i)\exp(-\alpha\ell_{t,i}) instead of exp⁡(−αct,iℓt,i)\exp(-\alpha c_{t,i}\ell_{t,i}), and uses $ \alpha=\frac{\mu}{8G^2}, $ which is calibrated to the experimental bound ∣∇ℓt(z)∣≤2G\\|\nabla\ell_t(z)\\|\le2G when D=G/μD=G/\mu.

The table reports two different quantities. Analytical excess subtracts BTorB_T^{\mathrm{or}}. Oracle gap subtracts the regret of the known-discount algorithm on the same instance.

MethodWorst-case regretExcess over BTorB_T^{\mathrm{or}}Gap to known-discount oracleProjections per round
Hybrid without compensation8.487.938.3520.12
Sharp-BDF hybrid1.841.331.7120.12

The controlled ablation reduces the oracle gap from 8.35 to 1.71 and the analytical excess from 7.93 to 1.33. The improvement is therefore caused by compensation under the same hybrid structure, not by expert-family or activation changes.

The existing prefix comparison gives the same conclusion with an independent control. BDF-Curv and Sharp-BDF prefix share the grid, prior, activation schedule, base update, feedback, and projection count. The oracle gap decreases from 12.04 to 5.18, a 57.0% reduction. Hybridization then reduces the gap from 5.18 to 1.71. These are successive controlled comparisons.

The uniform-prior endpoint variant has worst-case regret 2.32, oracle gap 1.80, and certificate 57.22 on the same instance family. The hybrid has the smallest measured regret and oracle gap, while its theorem additionally gives constant adaptation at both scale extremes on one trajectory.

Separate reporting of the two excess measures

For every experiment, we distinguish

=\sup_{\lambda,T} \left[\frac{\mu}{G^2}R_T^\lambda(u^\star)-\frac12K_T(\lambda)\right]_+$$ from $$E_{\mathrm{oracle}} =\sup_{\lambda,T} \frac{\mu}{G^2} \left(R_T^\lambda(u^\star)-R_{T,\mathrm{known}\text{-}\lambda}^\lambda(u^\star)\right).$$ The first quantity is the theoretical certificate target. The second measures the practical price against the realized known-discount trajectory. The two quantities are not interchangeable. Reporting both gives the direct link between the theory and the observed performance. **Why the contribution remains significant** The paper establishes three facts together. It gives a domain-uniform one-gradient upper bound with no multiplicative loss in the attainable benchmark. It proves that the evaluation quantifier changes the optimal adaptation order. It shows that this order difference survives full feedback, randomization, and subtraction of the true minimax value on the steady-state set. The finite-horizon form in (2) and the controlled ablation quantify the two points that are not visible from the simplified asymptotic statements alone.
Reviewer_M4ZzOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper characterizes adaptation to an unknown discount in strongly convex online optimization: Θ(log⁡N)\Theta(\log N) excess under prefix-uniform evaluation versus Θ(log⁡log⁡N)\Theta(\log\log N) at a predetermined endpoint. Sharp-BDF achieves these orders relative to an attainable known-discount benchmark using one subgradient per round. Matching lower bounds allow randomized full-feedback algorithms.

Critical strengths
  • S1. A matching separation between evaluation protocols. The logarithmic versus doubly logarithmic adaptation costs reveal a meaningful consequence of fixing the evaluation endpoint. Full-feedback lower bounds show that this distinction is intrinsic to the task.

  • S2. Exact recycling of the surrogate surplus. The compensation mechanism preserves the chosen benchmark’s coefficient using one genuine subgradient. The signed grid-transfer identity then extends the guarantee to every discount on the same trajectory.

Critical weaknesses
  • W1. The benchmark leaves substantial oracle slack. On the normalized one-dimensional class, Assumption 1 implies ∣gt(x)−μx∣≤G/2|g_t(x)-\mu x|\le G/2. Virtual targets yt=xt−gt(xt)/μy_t=x_t-g_t(x_t)/\mu and discounted forward prediction yield a known-discount bound of G2KT(λ)/(8μ)G^2K_T(\lambda)/(8\mu), one quarter of the proposed benchmark. The paper acknowledges that its benchmark differs from the minimax value, but this gap limits the significance of preserving its particular coefficient outside the steady-state regime.

  • W2. The separation offers limited quantitative guidance at finite horizons. The explicit lower bounds require log⁡N≥16384\log N\ge16384 or log⁡log⁡N≥8192\log\log N\ge8192. They establish asymptotic orders but leave the unavoidable adaptation penalty unclear at the reported experimental budgets.

  • W3. The attribution of the empirical gains is overstated. Section 6.2 attributes the hybrid–BDF-Curv improvement to compensation, although hybridization also changes the expert families, priors, and activation schedule. Table 2 already provides the more controlled prefix–BDF-Curv comparison; the mechanistic claim should use that comparison. The uniform-prior endpoint variant, whose certificate is approximately 57.257.2, is also omitted.

Questions for authors
  • Q1 (W1). Consider A0=0A_0=0, xt=λAt−1/St(λ)x_t=\lambda A_{t-1}/S_t(\lambda), and At=λAt−1+ytA_t=\lambda A_{t-1}+y_t. Given the resulting G2KT(λ)/(8μ)G^2K_T(\lambda)/(8\mu) guarantee on the normalized class, what justifies calibrating adaptation against the larger benchmark? How should coefficient preservation be interpreted outside the steady-state regime?

  • Q2 (W2). What is the strongest finite-horizon lower bound implied by the existing constructions before simplifying the constants, and at what horizon does it become nonvacuous?

  • Q3 (W3). How much of the hybrid’s additional improvement comes from compensation versus hybridization? Please base the compensation claim on the available prefix–BDF-Curv comparison and clarify how the uniform-prior endpoint algorithm performs.

Required Corrections

  • Algorithm initialization (lines 273, 289). Initialize z1,iz_{1,i} for every expert; the current inactive-expert update reads undefined states.

  • Roundwise regret wording (lines 92–94, 124, 210–213). G2/(2μSt)G^2/(2\mu S_t) is an amortized analysis term, not a roundwise regret bound.

  • Missing counterexample (lines 151–152, 306–307). Supply the claimed counterexample establishing the necessity of both compensation placements, or qualify the claim.

  • Numerical reporting (lines 430–431, 1811–1813). The endpoint slope is approximately 21.821.8 against log⁡log⁡N\log\log N; 24.124.1 corresponds to fitting against log⁡(M+1)\log(M+1). Also qualify 8log⁡28\log2 as the asymptotic prefix increment. Cite Theorem 6 for the hybrid certificate in lines 1796–1798.

  • Textual errors. Resolve the conflicting baseline feedback description (line 247); replace “three protocols” with “three algorithm variants” (line 308), “last equality” with “last inequality” (line 1046), and remove “eq. equation” (lines 1863–1864).

3 comments

We thank the reviewer for identifying the two central contributions of this work: the matching separation between prefix and endpoint evaluation, and exact recycling of the surrogate surplus with one genuine subgradient per round. We address every concern below.

W1 and Q1: Benchmark calibration

The reviewer’s sharper bound is correct on the normalized one-dimensional class. The endpoint gradient constraints imply $ |g_t(x)-\mu x|\le G/2, $ so the virtual targets remain in the interval. The forward predictor therefore gives $ \frac{G^2}{8\mu}K_T(\lambda). $ This restricted-class result and our benchmark serve different purposes. We use $ B_T^{\mathrm{or}}(\lambda) =\frac{G^2}{2\mu}K_T(\lambda) $ because it is the pathwise known-discount OGD guarantee under the full assumptions of the paper. It holds for every compact convex decision set, arbitrary nonsmooth strongly convex losses, and one observed subgradient per round. It is therefore a common domain-uniform comparator for the unknown-discount problem.

The main algorithm preserves the coefficient of this attainable comparator on one trajectory for every discount. This is a meaningful statement outside the steady-state regime. It means that unknown discount adaptation causes no additional multiplicative loss relative to the general-domain OGD guarantee.

The sharper restricted-class oracle does not affect the protocol separation. On the steady-state set KT(λ)≤2K_T(\lambda)\le2, Theorems 10 and 11 subtract the true known-discount minimax value and still give matching $ \Theta(\log\log N) \quad\text{and}\quad \Theta(\log N) $ lower bounds for endpoint and prefix evaluation. Thus the separation is not caused by slack in BTorB_T^{\mathrm{or}}. Using the smaller oracle on the normalized class only increases the additive excess, so the lower bounds remain valid.

W2 and Q2: Finite-horizon lower bounds

The asymptotic statements use simple constants. Keeping the exact geometric weights and likelihood-ratio moments in the existing construction gives a stronger finite-horizon inequality. Let dd be the normalized worst-case excess and let II be the selected block. Define $ w_t=\lambda^{T-t}, W=\sum_{t\in I}w_t, $ $ E_I=\sum_{t\in I}\mathbb E_0 Z_t^2, J_I=\sum_{t\in I}w_t^2(1+\varepsilon^2)^{t-s}. $

The exact loss expansion and weighted Cauchy–Schwarz give $ d\ge \frac{\varepsilon^2W^2}{8S_T(\lambda)} -\frac{\varepsilon}{4}\sqrt{E_IJ_I} -\frac12K_T(\lambda). \tag{1} $ For prefix evaluation, one of the disjoint time blocks satisfies $ E_I\le\frac{4\mathsf H_N+8d}{k}. $ For endpoint evaluation, one of the disjoint history annuli satisfies $ E_I\le\frac{16(1+d)}{k}. $ These bounds retain the finite terms that were removed when deriving the simpler theorem constants.

For prefix evaluation, setting N=231N=2^{31}, h=38h=38, m=49m=49, and ε=1/2\varepsilon=1/2 in (1) gives $ d\ge0.1316047-0.0325416\sqrt{11.2438+d}, $ and hence $ \Delta_N^{\mathrm P,\star}\ge0.022. $ For endpoint evaluation, the same annulus construction with hε2=76h\varepsilon^2=76 gives $ d\ge0.0137285-0.0133021\sqrt{1+d} $ when log⁡log⁡N≥84\log\log N\ge84, and therefore $ \Delta_N^{\mathrm E,\star}\ge4\times10^{-4}. $ These are sufficient finite-horizon thresholds from the existing construction. The upper bounds in Theorem 1 hold for every NN, including the experimental budgets.

W3 and Q3: Compensation versus hybridization

The prefix comparison isolates compensation. BDF-Curv and Sharp-BDF prefix use the same grid, priors, activation schedule, base learner, projections, and one-gradient feedback. They differ in the compensated master update and its admissible meta rate. The worst-case oracle gap changes as follows: $ 12.04 \longrightarrow 5.18, $ a 57.0% reduction. The hybrid then adds the endpoint expert family and reduces the gap from 5.18 to 1.71, a further 67.0% reduction. These two comparisons separate the effect of compensation from the additional benefit of hybridization.

The uniform-prior endpoint variant was also evaluated on the same ten instances and the same discount set. Its worst-case results are:

MethodWorst-case regretOracle gapCertificate
BDF-Curv12.1612.04273.07
Sharp-BDF prefix4.645.18118.09
Sharp-BDF endpoint, uniform2.321.8057.22
Sharp-BDF endpoint, scale-local4.934.4288.57
Sharp-BDF hybrid1.841.7178.09

The uniform endpoint variant has the smallest certificate in this table. The hybrid has the smallest measured regret and oracle gap, and its theorem gives constant adaptation at both scale extremes on one trajectory.

Algorithm initialization

Initialize z1,i=x∘z_{1,i}=x_\circ for every expert. Inactive expert states remain fixed until activation. Thus every state used by the update is defined and feasible.

Roundwise regret wording

The quantity G2/(2μSt)G^2/(2\mu S_t) is an amortized contribution from the distance-potential analysis. It is not a standalone bound on the regret in round tt. The discounted distance terms telescope, giving the cumulative known-discount guarantee $ \frac{G^2}{2\mu}K_T(\lambda). $

Counterexamples for both compensation placements

Set μ=G=1\mu=G=1, X=[−1/2,1/2]\mathcal X=[-1/2,1/2], α=1/4\alpha=1/4, v1=v2=1/2v_1=v_2=1/2, (z1,z2)=(−1/2,1/2)(z_1,z_2)=(-1/2,1/2), and (c1,c2)=(0,1/3)(c_1,c_2)=(0,1/3).

With compensation only in the prediction, x=1/2x=1/2. The valid loss f(x)=(x+1/2)2/2f(x)=(x+1/2)^2/2 gives g=1g=1, ℓ(z1)=−1/2\ell(z_1)=-1/2, and ℓ(z2)=0\ell(z_2)=0. The exponent without compensation gives $ \sum_iq_i=\frac12(1+e^{1/8})>1=\sum_iv_i. $ With compensation only in the exponent, the prediction is x=0x=0. The valid loss f(x)=(x−1/2)2/2f(x)=(x-1/2)^2/2 gives g=−1/2g=-1/2 and ℓ(z2)=−1/8\ell(z_2)=-1/8. The resulting mass is $ \sum_iq_i=\frac12(1+e^{1/96})>1=\sum_iv_i. $ Both examples satisfy the stated curvature and gradient assumptions. Hence both placements are needed for the universal mass inequality used in the proof.

Numerical reporting

The endpoint certificate has slope 21.8 against log⁡log⁡N\log\log N and slope 24.1 against log⁡(M+1)\log(M+1). The latter is the parameterization used by the displayed certificate. The prefix increment approaches 8log⁡28\log2 per grid level asymptotically. At finite horizons, the 16log⁡(M+1)16\log(M+1) term and prior normalization also contribute. The hybrid certificate is the one stated in Theorem 6.

Textual consistency

All experimental baselines use one genuine subgradient and zero function values per round. Algorithm 1 contains three algorithm variants across the two evaluation protocols. The final step of Lemma 4 is an inequality. Equation references use a single equation prefix. These local consistency points do not change any algorithm, theorem, or numerical result.

Thank you for your detailed response to my review. As you explicitly demonstrated, the oracle slack is on the order of KTK_T, meaning that coefficient preservation does not guarantee a tight approximation of the true minimax value. While the finite-horizon numerical value for the prefix evaluation was helpful, the endpoint evaluation still requires the extreme condition of log⁡log⁡N≥84\log \log N \ge 84. Additionally, the provided prefix comparison and uniform-prior endpoint results partially address my empirical questions. I will maintain my score of 2.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.