- 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
- 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.
- The paper includes a numerical experiment, which helps ground the theory.
Critical weaknesses
- 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.
- 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:
-
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?
-
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:
-
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.
-
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.
-
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?
-
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.
-
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.
-
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.
-
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
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 to this same sequence. The learner never selects , 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 before round 1. The fixed-endpoint protocol means that only is evaluated. The prefix protocol means that every must be valid. An effective memory is the number of recent rounds that receive substantial evaluation weight. Scale extremes mean bounded or bounded . Constant adaptation means an additive excess bounded independently of 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
The quantity 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. hides initialization effects and cannot preserve the oracle coefficient. captures both initialization and steady state. This is why the paper first introduces the interaction protocol and then defines as the exact benchmark quantity.
Interaction protocol and notation
The interaction is causal. The learner selects , observes one vector , 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 uses and therefore tracks a different forgetting scale. A long-memory expert is suitable when is close to 1. A short-memory expert is suitable when is small. The master uses their predictions to form one decision.
The compensation coefficient 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 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.
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 Θ(loglogN). If every prefix must be valid, the cost is Θ(logN). 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 t, the learner chooses xt before seeing ft. It receives one subgradient at xt. The discount λ is never revealed and affects no update. After the run, an evaluator chooses T, λ, and a comparator u.
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μ). 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 Θ(loglogN) and Θ(logN) 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 BTor. 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.