acceptodds
Under review as a conference paper at ICLR 2027

The Statistical Price of Unknown Transient Amplitude in Best-Asymptote Identification

Abstract

When several learning or optimization runs share a budget of updates, the run with the smallest current loss need not be the run with the smallest limiting loss because the runs are still improving. We study how to identify the run with the best limit (best-asymptote identification) when the th update of run produces with Gaussian noise: each pull advances only the arm it is spent on, the decay exponent and the noise variance are known, and the limits and the transient amplitudes are not. The question is how much not knowing the amplitudes costs compared with an oracle that reveals them. We give three exact answers. For a single arm, the sharp asymptotic variance for estimating is instead of the oracle's , where for and for ; unknown amplitude, therefore, has a first-order cost only when the transient decays slowly. For two arms whose limits differ by , with amplitudes in any fixed compact subinterval of and a budget cap almost surely, the exact local asymptotic minimax misidentification error over all parameter-free policies with predictable, history-dependent allocation and adapted stopping is ; it is attained by deterministic balanced sampling with full-prefix least squares, and the oracle value is the same formula with . Hence, no adaptive allocation or stopping rule can remove the nuisance penalty: matching the oracle requires times as much first-order budget. For arms, when at most one challenger may approach the best arm at the scale and every other arm keeps a fixed margin, a sublinear screening pilot followed by an independent-suffix comparison attains the two-arm value, and the optimized deterministic all-arm-prefix budget is times larger. Exact finite-prefix risk calculations and Gaussian simulations illustrate the boundary at and the screening mechanism.

Primary area:
learning theory
Keywords:
Best-arm identification, functional multi-armed bandits, learning curves, adaptive experimental design

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 4 reviews, above 27% of the others.
Reviewer_RNWfOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

the paper studies the problem on identifying the best limiting loss, or say in a different way, identifying the best learning / optimization process that can lead to smallest loss in the end. specifically, the core interest is not on proposing new algorithms, but for the specific model, what the price gap we need to pay when we dont know the amplitude. the discussion covers three cases, single arm, two arms and more than two arms, with different results.

Critical strengths

the paper comes with very strong theoretic contribution on the problem of best asymptote identification, where the amplitude is unknown. as a major contribution it quantifies the cost of the unknown quantity and show that the cost is likely necessary as well, in different cases. the cost itself looks reasonable and good addition to existing works. additionally, the paper is structured in a stepwise way from one arm to two arms then multi arms, which helps a bit to get some general idea quickly despite it being very theoretical paper.

Critical weaknesses

frankly it is very hard at least for me to read with such heavily loaded notations. And many of the notations seem to be unnecessarily complicated i believe. for example, R^{pi_T,B}_{T,M}(c;r) in line 229, with 6 arguments essentially in the formula, and bottom T can be totally removed as there is already a T. also there are many notations undefined or used before defined, such as big C in the abstraction, tho this one isnt difficult to guess what it means, but there is also small c in the abstraction. overall, the notation issues have made the paper hard in reading with many cognitive efforts on digesting the meanings.

Questions for authors

to the best of my knowledge, coming from more adaptive bandit algorithm design background, it seems to be a classic result that in the two arms setting, equally sampling is nearly optimal or say in a different way, adaptivity doesn't help gain much further, while in multi-armed settings (K>2), adaptivity does make a difference. this seems to be in analogy to one of the messages this paper delivers. I first wonder if the authors can clarify if this statement is true, and if true, can the authors make this connection clear / strong with the results of this paper? especially what this paper presents beyond that?

1 comment

Simplifying the error notation and defining cc and CC

Equation (14) now uses RT(π,M)R_T(\pi,M). This is the smallest worst-case error attainable by a final recommendation after sampling according to policy π\pi, over the stated parameter window of radius MM. The exponent rr, rescaled gap cc, budget multiplier CC, and amplitude interval are fixed in that section and are suppressed in the notation. The policy symbol π\pi denotes the sequence of rules used at different budgets, so TT appears only once in RT(π,M)R_T(\pi,M) as the budget index.

Before the equation, Section 5 defines CTCT as the maximum total number of updates and c/Tc/\sqrt{T} as the minimum separation between the limiting losses under comparison. It explains why this separation is comparable to the uncertainty in the estimated difference. Neither cc nor CC appears in the revised abstract. The abstract and introduction define a training run, observed loss, and limiting loss before introducing the mathematical notation.

Is the two-arm versus multi-arm distinction classical, and what is added here?

Yes, for two stationary Gaussian arms with equal known variance, balanced sampling attains the optimal fixed-budget error exponent. With unequal known variances, the allocation attaining this exponent assigns updates in proportion to the standard deviations (Kaufmann, Cappé and Garivier, 2016). Revealing the transient amplitudes in our model recovers the equal-variance stationary comparison because the remaining improvement can then be subtracted from every loss. Section 2 makes this connection explicit.

Our additional result concerns the exact nonzero limiting error for increasingly close limits when the amplitudes are unknown. The variance ratio for fitting rather than knowing the amplitude is κ(r)=(1−r)2/r2\kappa(r)=(1-r)^2/r^2 for 0<r<1/20<r<1/2 and one for r≥1/2r\ge1/2. Theorem 2 proves that this is also the exact limiting budget ratio after optimizing over allocation and stopping under the stated total budget cap. The proof must account for the dependence of the final sample counts on earlier noise. Section 5 bounds the information about which limit is smaller in the observations collected by an adaptive policy. Equal sampling and least squares attain the bound.

For more than two arms, Section 6 makes the adaptive advantage precise on a restricted class. The number of arms KK is fixed, only one competitor can have a limit close to the best arm’s, and all other limits exceed both by a fixed margin. An initial screening stage identifies the pair with probability tending to one while using a fraction of the budget that tends to zero. Almost all remaining updates go to that pair. For a schedule fixed in advance, the competitive pair might consist of the two least-sampled arms, which together receive at most 2/K2/K of the budget. On this class, screening saves a factor K/2K/2 in first-order budget over the optimal deterministic allocation. The cost κ(r)\kappa(r) of estimating each amplitude persists.

The optimal unrestricted adaptive allocation with several simultaneously close competitors remains open.

Reviewer_TRLEOpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

The paper studies the problem of "best-asymptote identification": think best-arm identification except that the "arms" decay exponentially to some constant values, and the "best arm" is the one with the highest such constant. In this highly stylized problem, they characterize various statistical costs involved.

Critical strengths

None.

Critical weaknesses
  1. Extremely poorly written, to the point where it is impossible to understand the exact problem setting, or its motivation or the solution that the paper proposes. It is impossible to judge and review the paper's contributions with such a presentation.
  2. From what I do understand, the paper studies an extremely artificial and heuristically motivated problem. It is unclear what such an analysis is supposed to tell us beyond just being a mathematical curiosity.
Questions for authors

Unless the authors are willing to use human-understandable language to elaborate on the problem and their results, I do not think that answers to any specific questions will change my opinion of the paper.

5 comments

We rewrite the paper, must be better now.

What is the problem, why does it arise, and what procedure solves it?

We want to choose a training setting that gives the smallest prediction error after a long period of training. One such setting is the learning rate, which controls the size of each update to the model. To compare candidate learning rates, we train a separate copy of the model at each rate and call each such training process a run. After an update, we observe the selected run’s loss, which measures prediction error. Only that run advances. The runs share a limited number of updates, so the decision must be made before all of them have been trained for a long time.

An early comparison can favor the wrong setting. To see the difficulty, consider two of the candidate learning rates. Suppose their runs have expected losses after ss updates of 0.1+0.3s−1/40.1+0.3s^{-1/4} and 0.2+0.1s−1/40.2+0.1s^{-1/4}. After the first update, the second run leads with expected loss 0.30.3 versus 0.40.4. At 16 updates each, both expected losses are 0.250.25. The first run eventually has the smaller limiting loss, 0.10.1 versus 0.20.2. Choosing by the initial ranking would favor the wrong run.

The model expresses remaining improvement as a power law, βis−r\beta_i s^{-r}. Here ss counts the updates of run ii, r>0r>0 is a known decay exponent, and βi>0\beta_i>0 is an unknown amplitude that determines how much improvement remains after the first update. Observations have independent Gaussian noise of known positive variance. For two runs, the procedure divides the budget equally and fits a limiting loss and amplitude to each run. The fit minimizes the sum of squared differences between predicted and observed losses; this is least-squares fitting. We then select the run with the smaller fitted limit. When amplitudes lie between fixed positive bounds, Theorem 2 proves that this procedure attains the smallest limiting worst-case error for pairs whose limits are separated on the scale of the estimation error. The abstract, introduction, and Section 5 now introduce the problem and procedure in this order.

What does this analysis tell us about training decisions, and what are its limits?

The result measures the extra observations needed when both the limiting loss and the amount of remaining improvement must be estimated. A benchmark given the amplitudes can subtract the remaining improvement from each observation. Without them, both the limit and the remaining improvement must be inferred from the losses.

The crossing example has a fixed gap of 0.10.1. Theorem 2 examines closer comparisons, with gaps on the scale of the estimation error. At r=1/4r=1/4, matching the known-amplitude benchmark’s limiting worst-case error requires nine times as many updates to first order. Allowing the next update and the decision to stop to depend on earlier losses does not remove this cost. For r≥1/2r\ge1/2 the first-order ratio is one. The power-law and noise assumptions limit this conclusion.

For increasingly close limiting losses, Section 8 shows that fitting the wrong exponent can make the probability of an incorrect choice tend to one, even when both true curves are power laws. The theorem therefore does not provide an accuracy guarantee for arbitrary training trajectories.

Section 7 evaluates screening by replaying recorded LCBench curves from 35 tasks. The procedure first compares all candidates briefly, retains the two with the lowest fitted limits, and spends the remaining budget on them. It has lower mean normalized epoch-50 regret than balanced least-squares fitting in 11 of 12 combinations of budget and assumed exponent, while successive halving has lower regret than screening in all 12. Here normalized regret measures excess epoch-50 loss over the best configuration, divided by the group’s median-to-best loss difference. Since these data do not reveal limiting losses or true amplitudes, this experiment assesses finite-budget selection at epoch 50, but cannot validate the theoretical multiplier.

My understanding is still that this is a highly stylized model that serves as a proxy for the phenomenon they wish to investigate. I am certainly not going to re-read the paper to see if it is better now, as that defeats the purpose of the whole initial review stage. I also find the above response hard to read and follow. I maintain my score.

"I am certainly not going to re-read the paper to see if it is better now, as that defeats the purpose of the whole initial review stage. I also find the above response hard to read and follow. I maintain my score."

Rewriting the paper is a new and proper instrument introduced for this year rebuttal process. It is Ok, that you found this instrument troublesome because it requires to re-read the paper, i.e. burn much time. Well, we understand you well, because authors are in the same situation - we also must read new papers since we all serve as a reviewers. But I think that decision is not a good one, because, in short, you do not plan to properly do your work as a reviewer. If you do not plan to read new text or read rebuttal (what so cryptic here or hard to read?), then you just don't give us a chance for rebuttal.

That is especially the case since your whole review could be summarize as "the paper is poorly written" and "the setting is a highly stylized model". We rewrite the paper, i.e. address your main concern, but you refuse to check.

"the setting is a highly stylized model"

We do not agree. It is indeed stylized model, but it is practical. The same type of models are usually used as scaling laws models.

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

This paper studies best-asymptote identification, where multiple learning algorithms exhibit improving loss trajectories and share a limited training budget. The authors characterize the statistical cost of unknown transient amplitudes, establish sharp asymptotic minimax identification bounds under adaptive allocation and stopping, and extend the analysis to multiple arms through a screening-based strategy.

Critical strengths

The paper establishes sharp minimax bounds and precisely quantifies the statistical efficiency loss caused by unknown transient amplitudes, including a critical transition at the decay exponent (r=1/2).

The analysis goes beyond fixed allocation and shows that adaptive budget allocation and stopping cannot eliminate the statistical penalty in the considered two-arm setting.

Critical weaknesses
  1. The underlying problem of allocating training budgets among improving learning algorithms has been extensively studied in prior work, including Cella et al. (2021) and Takemori et al. (2024). Moreover, the key variance inflation factor for slowly decaying curves is already implicit in existing inverse-Gram analyses. The main novelty therefore lies in refining the theoretical characterization rather than introducing a fundamentally new problem.

  2. The theoretical results rely on a specific power-law learning curve with known decay exponent and Gaussian noise variance. These assumptions may not hold in practical training processes, limiting the generality of the conclusions.

  3. The experiments are conducted entirely under the assumed Gaussian learning-curve model, without real-world training tasks. Furthermore, the main statistical penalty is established in a local asymptotic regime, leaving its practical significance under finite budgets and realistic learning curves unclear.

Questions for authors
  1. Given that previous studies have already investigated budget allocation for improving learning curves and derived related statistical bounds, what are the most important new insights enabled by the exact minimax characterization beyond existing results?

  2. How sensitive are the theoretical conclusions to misspecification of the learning-curve model, particularly when the decay exponent (r) is unknown or the actual convergence pattern deviates from a power law?

  3. Can the authors provide experiments using real learning or optimization trajectories to demonstrate the practical significance of the identified statistical penalty and the proposed screening strategy under realistic computational budgets?

3 comments

1. What does the exact minimax characterization add to earlier work?

The allocation problem is established, and the variance coefficient is already implicit in earlier inverse-Gram analyses. Our contribution is to determine the smallest possible limiting worst-case error when allocation and stopping may depend on previous losses. This establishes when the coefficient is an unavoidable budget cost, even for adaptive procedures, and when that leading cost disappears. A variance calculation at predetermined sample counts alone does not establish this conclusion.

Cella et al. (2021) use the same inverse-power mean curve and evaluate the chosen arm at the loss it has reached when the budget expires. Specializing the inverse-Gram calculation of Takemori et al. (2024) to a single inverse power gives the variance coefficient κ(r)=(1−r)2/r2\kappa(r)=(1-r)^2/r^2 for 0<r<1/20<r<1/2. Their Theorem 6.3 gives an exponential lower bound on worst-case error for a finite target horizon. It requires every arm to receive a positive fraction of that horizon, worst-case error at most one half, and conditions on the budget and problem class. Section 2 now states these connections and distinctions.

Our theorem gives the exact limiting error for nearly equal limiting losses, where the error remains nonzero. It allows each update and the decision to stop to depend on past observations, provided the total number of updates stays within the budget with probability one. The rule cannot use the unknown parameters. No convergence assumption is imposed on the sampling proportions. Equal sampling followed by least squares attains the bound. With amplitudes between fixed positive bounds, matching the accuracy of the known-amplitude benchmark requires a budget ratio tending to κ(r)\kappa(r) below r=1/2r=1/2 and to one for r≥1/2r\ge1/2.

Section 5 gives a numerical example. Fix the decay exponent at r=1/4r=1/4 and the noise variance at one. With a total budget of TT updates and a gap of 2/T2/\sqrt{T}, the smallest limiting worst-case error is approximately 0.369 with unknown amplitudes and 0.159 with revealed amplitudes. Keeping this gap, increasing the unknown-amplitude budget to 9T9T matches the revealed-amplitude error at budget TT.

2. How sensitive are the conclusions to an unknown exponent or a different curve shape?

An incorrect exponent can make the probability of choosing the worse run tend to one. Theorem 2 assumes a specified power law, a known exponent, and independent Gaussian noise of known positive variance. It does not establish the same guarantee when the exponent or variance is estimated, or when the noise is dependent or non-Gaussian. Section 8 and Appendix L examine curve misspecification under the stated noise model.

Suppose the true exponent is 1/41/4 and we fit 1/21/2. For a run with amplitude β>0\beta>0, the fitted limit has an upward bias asymptotic to (4β/3)n−1/4(4\beta/3)n^{-1/4} after nn observations. Here the amplitude sets the amount of improvement remaining after the first update. Let the two limits be μ1\mu_1 and μ2\mu_2, with μ2−μ1=c/T\mu_2-\mu_1=c/\sqrt{T}, and give each run ⌊T/2⌋\lfloor T/2\rfloor observations. For fixed amplitudes β1>β2\beta_1>\beta_2, the better run has the larger upward bias. Its excess bias eventually exceeds both the true gap and the statistical error. The probability of choosing the worse run then tends to one. Figure 3 illustrates this effect: at 8,192 observations per run, the error is 0.3730.373 with the correct exponent and 0.9620.962 with the wrong one.

Appendix L also treats deterministic deviations from the assumed mean curve. For fixed observation counts, it gives the exact bias of each least-squares estimate. If each run receives a positive limiting share of the budget, a difference between these biases that is negligible relative to T−1/2T^{-1/2} leaves the limiting comparison error unchanged. This is a condition on the effect of the deviations, not a guarantee for arbitrary learning curves. Estimating the exponent from the same observations makes the fitting weights random and requires a separate analysis; its minimax cost remains open. Appendix B extends the single-run estimation analysis to other curve shapes specified in advance.

3. What do real training trajectories and finite budgets show?

The revision adds a replay of measured LCBench curves from all 35 tasks. Screening improves mean normalized regret over balanced least-squares fitting in 11 of the 12 budget/exponent settings, but successive halving performs better than screening in all 12. These results assess the screening procedure under finite budgets. The real-data penalty for unknown amplitudes remains unmeasured because the true amplitudes and limiting losses are unavailable.

We use the Auto-PyTorch data (Zimmer et al., 2021) in their Syne Tune conversion (Salinas et al., 2022). Screening first trains every candidate briefly, retains the two with the lowest fitted limits, and splits the remaining updates between that pair. The final fits use only observations collected after screening. For each task, we sampled 100 groups of eight training configurations and gave every method the same groups. Table 1 reports total budgets of 48, 64, 96 and 128 epoch updates across each group. Screening and balanced ordinary least squares (OLS) use the same fixed exponents 0.250.25, 0.50.5 and 11. An epoch is one pass through the training data. Methods receive equal epoch budgets, though computation time per epoch varies by configuration.

We score each choice by its excess epoch-50 validation loss over the best configuration in its group. Normalized regret divides this excess by the difference between the group’s median and best losses. At budget 128 and assumed exponent 1, mean normalized regret is 0.06609 for screening, 0.09133 for balanced OLS, and 0.03322 for successive halving. Screening selects the epoch-50 best configuration more often than balanced OLS in 6 of the 12 settings. At budget 128, the screening stage has already discarded the epoch-50 best configuration in 17.1% to 30.1% of groups, depending on the assumed exponent.

Appendix M gives the schedules, variation across tasks, other error measures, and secondary test-loss results.

The Gaussian experiments allow a direct finite-budget comparison with revealed amplitudes. On the eight-run instance in Appendix K.1, with r=1/2r=1/2, gap 0.025, noise variance one, and target error 0.10, screening first reaches the target at 29,904 updates with unknown amplitudes and 10,848 with revealed amplitudes, a ratio of 2.76. These errors were computed by Gaussian integration, searching budgets divisible by eight. The supplementary file finite_budget_table.csv reports both budget thresholds and the errors at the preceding grid points. This compares the specified screening procedures on one instance, rather than an optimal finite-budget ratio over all procedures. Thus a substantial cost can remain at finite budgets even where the asymptotic ratio is one.

Reviewer_hkvNOpenReview ↗

Response to authors

Thank you for the detailed response. I appreciate the authors' efforts

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

The paper studies a non-stationary (asymptotic) best-arm identification problem in which the means of the arm evolve accordingly to an amplitude based update Yi,s=μi+βis−r+ϵi,sY_{i,s}= \mu_{i} + \beta_{i}s^{−r} + \epsilon_{i,s} where βi\beta_i is unknown. The paper asks what the statistical price of not knowing the βi\beta_i in various settings. The first result uncovers the variance of estimating a single μi\mu_i which shows that this becomes difficult only if the trajectory decays slowly.

Critical strengths

Potentially, this paper has non-trivial and important technical contributions. However I’m not able to weight those as they are obfuscated by very poor exposition. However, I cannot exclude the situation in which a substantial rewrite might uncover some interesting technical contributions. I find interesting that the penalty disappears when r≥1/2r\ge 1/2.

Critical weaknesses

I find the paper comically badly written. I found it hard even to understand what the setting was (even at the high level). I’m not an expert in non stationary bandits, or best-arm identification but I’m an expert in online learning and I think I’m supposed to be able to understand the premises of the paper without so much effort. Most of the jargon is impenetrable and does not add anything to the intuition. Few examples are (far from this being a complete list): fixed-arm geometry, prefixes, challenger, oracle envelopes, independent-suffix comparison. The abstract is absurdly overloaded with exact statements.

Questions for authors

The two-arm problem needs the assumption that the two arms differ in the limit by 1/T1/\sqrt T. How does this make sense in general? Moreover, I read this from the abstract but not in section 5.

2 comments

Clarity of the setting, terminology, and abstract

We rewrite part of the paper

We compare settings for training a prediction model, such as different learning rates. Each setting trains a separate copy of the model; we call that training process a run. After an update, we observe its loss, a measure of prediction error on held-out data. The runs share a limited budget of updates. We want to select the setting whose mean loss approaches the lowest limit, although a different setting may have the lower loss early in training. The paper assumes a known shape for the decrease in each run’s mean loss. The unknown amplitude sets the size of its remaining improvement. The revised abstract and introduction define these objects before introducing bandit terminology or stating the results.

The terms identified in the review refer to the following estimation problems and operations:

  • “Fixed-arm geometry” concerns estimating one run’s limiting loss while also fitting its remaining improvement.
  • A “prefix” consists of the first specified number of observations from a run.
  • A “challenger” is a competing run; in the screening theorem, only the second-best run can have a limit close to the best one.
  • The “oracle envelopes” are the lower and upper limiting errors for a benchmark given the amplitudes. Section 5 defines both and proves that they agree.
  • An “independent-suffix comparison” fits the retained runs using only observations collected after screening. The final fits do not reuse the observations that selected the pair.

Sections 3, 5, and 6 now explain the estimation problem, the known-amplitude benchmark, and the screening procedure in these terms. The abstract introduces the model and the budget penalty without the local parameter class, the exact error formula, or the previously unexplained constants cc and CC. Those definitions and exact statements appear in Section 5.

Why compare limiting losses separated by c/Tc/\sqrt{T}?

The limiting losses of a given pair stay fixed throughout training. The scale c/Tc/\sqrt{T} describes which pairs we compare as the available budget grows: larger budgets allow us to distinguish closer limits. Write CTCT for the maximum total number of updates, where C>0C>0 is fixed and TT grows. With equal sampling, the standard error of the estimated difference is of order 1/T1/\sqrt{T}. A gap of c/Tc/\sqrt{T}, with c>0c>0 fixed, remains comparable to that uncertainty and therefore leaves a nonzero probability of choosing the wrong run.

Section 5 now introduces this comparison before equation (14). Its parameter class allows either run to be better and includes every gap of at least c/Tc/\sqrt{T} within the stated parameter bounds. The largest limiting error occurs at the smallest allowed gap. Training the two runs equally and choosing the smaller fitted limit attains the bound without knowing cc.

For a gap held fixed as the budget grows, the smallest worst-case error tends to zero. Under the parameter bounds of Proposition 6, this optimal error has the same exponential decay rate with known and unknown amplitudes. The additional budget factor in Theorem 2 concerns increasingly close pairs whose separation remains comparable to the estimation error.

Thank you for your response, but I believe that most of my concerns remain valid. Therefore, I will maintain my original score.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.