acceptodds
Under review as a conference paper at ICLR 2027

Accessibility Limits for Best-Arm Identification under Coupled Optimization

Abstract

We study fixed-confidence selection of the unique best among \(K\) unknown objectives along one coupled optimization trajectory. Arm \(i\) has deployment quality \(f_i^\star=\inf_z f_i(z)\), while learning confines the state \(x\) to an affine set \(\mathcal F={x:Ax=b}\). A query returns a noisy value and full gradient, then triggers a prescribed projected update that can move every arm. Without resets or off-trajectory queries, the learner must identify \(\argmin_i f_i^\star\). We characterize the exact boundary between identifiability and impossibility. For fixed \(0<\mu<L\), complete noiseless feasible first-order information determines the best arm over the smooth \(\mu\)-strongly convex, \(L\)-smooth class exactly when feasible directions span every arm block. If this condition fails, two admissible instances can agree in all observable values and full gradients yet have different best arms. Within the identifiable regime and under explicit oracle and access conditions, we introduce Geometric Block Certificates, a \(\delta\)-correct method that turns feasible progress into confidence bounds on standalone optima. It stops with finite expected cost and satisfies quantitative high-probability and expected cost bounds. Finite-class lower bounds show that poor access can itself impose unavoidable cost. Finally, for known-Hessian quadratics under additional oracle conditions, corrected value–gradient observations can restore identifiability even when geometric access fails.

Primary area:
learning theory
Keywords:
best-arm identification, pure-exploration bandits, coupled optimization

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_wWFZOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies fixed-confidence identification of the candidate with the smallest standalone optimum fi⋆=inf⁡zfi(z)f_i^\star=\inf_z f_i(z), when candidate parameters are coupled through Ax=bAx=b. Queries return noisy values and gradients and trigger prescribed projected updates without resets. The paper characterizes identifiability through the access matrices Si=Ei⊤Proj⁡ker⁡AEiS_i=E_i^\top\operatorname{Proj}_{\ker A}E_i, proposes Geometric Block Certificates with termination and sample-complexity guarantees, develops access-dependent lower bounds, and provides a reduction for quadratics with known Hessians.

Critical strengths
  • The distinction between shared-training performance and standalone optimal performance is meaningful. Theorem 1 gives an exact identifiability boundary over the stated smooth strongly convex class: every SiS_i must be positive definite. When access is singular, the indistinguishable instances agree in both values and full gradients throughout the feasible set, making the impossibility result stronger than an argument based only on restricted value observations.

  • The analysis addresses substantive difficulties introduced by coupled updates. Although the certificates follow from standard PL and smoothness inequalities, proving that they become sufficiently narrow requires controlling interference between optimization blocks with potentially incompatible minimizers. Theorem 2 establishes almost-sure termination and finite expected cost. Theorem 3 also gives an interesting construction in which traversal and statistical identification require disjoint sets of queries.

Critical weaknesses
  1. The assumptions need stronger justification in the motivating applications. Assumption 4 requires globally strongly convex and smooth objectives, known curvature and noise bounds, arbitrarily large batches evaluated at a fixed state, and prescribed radial updates whose gains are bounded away from zero. These assumptions exclude typical nonconvex architecture training, momentum updates, and learning rates that decay to zero. A concrete application would help explain why resets and modifications to the optimizer are unavailable, while repeated sampling at the same state is permitted.

  2. The relevance of the access restrictions to weight sharing needs further explanation. Theorem 1 concerns identifiability from the complete feasible oracle, rather than finite-time identification under the prescribed updates. For consensus sharing, Si=I/K≻0S_i=I/K\succ0, so the singular-access impossibility does not apply. Furthermore, when Si=ρiIS_i=\rho_i I, the geometry-scaled step θi−=θi+=2/[ρi(μi+Li)]\theta_i^-=\theta_i^+=2/[\rho_i(\mu_i+L_i)] gives qi=(Li−μi)/(Li+μi)q_i=(L_i-\mu_i)/(L_i+\mu_i), independent of ρi\rho_i. Thus, a small access eigenvalue alone does not imply slow contraction. Since the paper already allows geometry-scaled steps, it would help to explain which practically relevant constraints cause a slowdown that persists under this choice.

  3. The upper and lower bounds do not match in general. Corollary 1 establishes the O~(Δmin⁡−2)\widetilde O(\Delta_{\min}^{-2}) rate with KK fixed and the curvature, access, gains, noise, and initial and transformed anchor radii uniformly controlled. The dependence on geometry is not confined to Γq\Gamma_q; it also enters the stopping phase hδh_\delta. In Corollary 3, the bounded-radius construction requires Δρ,θ=Θ(ρ3θ2)\Delta_{\rho,\theta}=\Theta(\rho^3\theta^2), so it does not establish the optimal dependence when gaps and access vary independently. As the authors acknowledge, the matching bounds concern specific constructed families rather than the general upper bound. Algorithm 1 also visits every arm in each phase, leaving room for more efficient allocation based on individual gaps.

Questions for authors
  • See weaknesses.

  • Which access-dependent terms in the upper bound are known to be necessary when the transformed anchor radii remain bounded and the gaps and access parameters vary independently? Which of these costs remain when using the geometry-scaled step allowed by Assumption 4?

3 comments

The assumptions need stronger justification in the motivating applications. Assumption 4 requires globally strongly convex and smooth objectives, known curvature and noise bounds, arbitrarily large batches evaluated at a fixed state, and prescribed radial updates whose gains are bounded away from zero. These assumptions exclude typical nonconvex architecture training, momentum updates, and learning rates that decay to zero. A concrete application would help explain why resets and modifications to the optimizer are unavailable, while repeated sampling at the same state is permitted.

We study what can be learned during one continuing training run with shared weights. Section 3 permits choosing a model and batch size. The service evaluates that batch at unchanged weights, updates once, and retains them. This permits repeated measurements before an update. Resets, separate copies, and optimizer changes are excluded by the assumed commands; weight sharing alone does not exclude them. The digit experiment implements these assumptions as a controlled example.

The normalized features and quadratic penalty give explicit curvature bounds. Bounded example losses and gradients give known noise bounds; evaluating the whole training set removes sampling error. Theorem 2 additionally requires batches of any size and step sizes within the positive bounds of Assumption 4. These step sizes ensure progress with exact gradients; the proof separately controls errors from sampling. Ordinary nonconvex training, momentum, and step sizes tending to zero require a different analysis.

Revised paper — §3, p. 4 (“Models with shared coefficients”) · §4.2, pp. 5–6 (Assumption 4 and Theorem 2) · §6.2, p. 10, and Appendix B.2, p. 58 (digit classifiers and noise bounds).

Theorem 1 concerns identifiability from the complete feasible oracle, rather than finite-time identification under the prescribed updates.

For complete sharing, Si=I/KS_i=I/K is positive definite, so the impossibility part of Theorem 1 does not apply. Every setting of an individual model's weights belongs to an allowed joint configuration. Theorem 1 therefore says that exact losses and gradients at all such configurations determine the minima. It does not say that the prescribed training run reaches the required configurations. Theorem 2 proves correct selection with finite expected cost under its sampling and step-size assumptions, while accounting for movement caused by other models' updates.

Revised paper — §3, p. 4 (“Access geometry”) · §4.1, p. 4 (Theorem 1) · §4.2, p. 6 (Theorem 2) · §4.2, p. 7 (“Dependence on access”).

Thus, a small access eigenvalue alone does not imply slow contraction. Since the paper already allows geometry-scaled steps, it would help to explain which practically relevant constraints cause a slowdown that persists under this choice.

When all coefficients of model ii are shared equally, projection reduces every direction by the same factor sis_i. For Si=siIS_i=s_iI, the allowed gradient multiplier 2/[si(μi+Li)]2/[s_i(\mu_i+L_i)] cancels that reduction, giving

\qquad q_i=\frac{L_i-\mu_i}{L_i+\mu_i}.$$ Unequal sharing gives a different situation. If one coefficient is shared by $r$ models and another is unshared, projection keeps $1/r$ of the first coefficient's proposed update and all of the second's. One scalar step size cannot undo both reductions. This explains how ordinary coefficient sharing can produce different movement restrictions across directions. Proposition 6 proves a lower bound for a constructed constraint with $S_i=\operatorname{diag}(\rho,1)$ and any $K\ge2$. Even at the largest allowed multiplier $2/(\mu\rho+L)$, reaching weights where the observations differ requires order $L/(\mu\rho)$ observations. Its rescaled distance to the minimum grows as $\rho^{-1/2}$. Thus this construction does not settle the question when that distance must remain bounded. *Revised paper* — §3, p. 4 (“Access geometry”) · §4.2, p. 7 (“Dependence on access”) · Appendix A.5, p. 40 (Proposition 12 on projection under shared weights) · Appendix A.4.2, pp. 29–31 (Proposition 6, Eq. 46, and the distance qualification on p. 31).

The upper and lower bounds do not match in general.

The general upper and lower bounds do not match. The matching comparison applies to the family constructed in Theorem 3. Both bounds include the cost of reaching weights where the alternatives differ and the cost of distinguishing them there. For fixed KK and error tolerances bounded away from one half, they have the same order, allowing constants and the logarithm used to control errors across the K−1K-1 alternatives.

Corollary 1 bounds expected cost by an inverse-squared-gap rate, up to logarithms, for a broader class with KK fixed. Its curvature, noise, and distance bounds must hold uniformly, as must the positive lower bounds on allowed movement and the rate of progress toward each minimum. The distance bounds concern a feasible reference state: its ordinary distance to the starting weights, and its rescaled distance to each model's minimizer. This result does not give the optimal dependence on access when access and gaps vary independently.

Access affects both the cost per phase, through Γq\Gamma_q, and the phase hδh_\delta at which the intervals separate. Appendix A.3.2 sharpens the distance estimate by removing an unnecessary factor ρi−1/2\rho_i^{-1/2}; the expected-cost and full-batch bounds use the same improvement. Which remaining access-dependent factors are necessary is open.

Revised paper — §4.2, p. 6 (Eq. 5 and Corollary 1) · §4.3, p. 8 (Theorem 3 and Corollary 3) · Appendix A.3.2, p. 22 (Eqs. 21–22) and p. 26 (Eq. 33, expected cost) · Appendix A.3.3, p. 27 (Eq. 38).

Algorithm 1 also visits every arm in each phase, leaving room for more efficient allocation based on individual gaps.

Algorithm 1 visits every model because that is the schedule analyzed in Theorem 2. Earlier valid bounds concern fixed minimum losses and remain valid after the weights move. Once those bounds rule a model out, later shared updates do not by themselves require another visit.

The variant tested in Appendix B.2 skips models ruled out by retained intervals between periodic visits to all models. Across 16 data splits of digit pairs selected in a pilot, it chose correctly in all 128 sampling runs and used 31.4% fewer evaluations of sampled training examples on average than Algorithm 1 (95% interval: 27.1–35.8%). A general improvement in the cost bound remains open.

Revised paper — §4.2, pp. 5–6 (retained intervals, Proposition 1, and Algorithm 1) · §4.3, p. 8 (all-arm allocation) · Appendix B.2, pp. 58–59 (elimination experiment and Table 3).

Which access-dependent terms in the upper bound are known to be necessary when the transformed anchor radii remain bounded and the gaps and access parameters vary independently?

The inverse-squared-gap cost of distinguishing the observations is established by the Gaussian subclass in Proposition 5. We have not established which access-dependent factors are necessary when gaps and access vary independently while the rescaled distances stay bounded.

The constructions answer narrower questions. With access fixed, a small prescribed step can force a cost of order (μρθ)−1(\mu\rho\theta)^{-1} before the observations become informative, even at fixed gap and distance. When access varies, Corollary 3 keeps the rescaled distance bounded by taking Δ=Θ(ρ(μρθ)2)\Delta=\Theta(\rho(\mu\rho\theta)^2). The gap and access therefore do not vary independently in that comparison.

Revised paper — §4.3, pp. 7–8 (Corollaries 2–3 and the open access dependence) · Appendix A.4.1, p. 28 (Proposition 5) · Appendix A.4.2, p. 31 (Lemma 4).

Which of these costs remain when using the geometry-scaled step allowed by Assumption 4?

The cost of distinguishing noisy losses remains. Proposition 5 starts every model at its minimum and returns exact zero gradients, so changing the step size leaves the weights and loss distributions unchanged.

Scaling the step removes the slowdown caused by a common reduction of movement in all directions. If different directions are reduced by different amounts, a single step size cannot cancel all of them. Proposition 6 shows that a cost of reaching informative weights can then remain even with the largest allowed step. In that construction, the rescaled distance to the minimum grows as access becomes more restricted.

The synthetic experiment in Section 6.1 also uses the largest allowed step. Its cost increases as movement becomes more restricted, but its rescaled distances to the minima increase too. It therefore illustrates the combined effect of these changes and does not establish the optimal access dependence at bounded rescaled distance.

Revised paper — §4.2, p. 7 (“Dependence on access”) · Appendix A.4.1, pp. 28–29 (Proposition 5 and its zero-gradient construction) · Appendix A.4.2, pp. 29–31 (Proposition 6 and its distance qualification) · §6.1, p. 10 (scaled step and rescaled distances) · Appendix B.1, p. 56 (“Loss functions and measurements”).

Thank you for the response. The revised paper differs substantially from the original submission, and without color highlighting, I found it difficult to track the changes. In my view, the rewrite goes beyond the clarifications and corrections I would expect during the rebuttal period. Therefore, I lean toward rejection.

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

This paper studies fixed-confidence best arm identification under coupled optimization, where the performance of each arm is defined by the optimal value of an optimization problem. The goal is to identify the arm with the smallest optimal value. The paper proposes Geometric Block Certificates, a fixed-confidence identification algorithm with sample complexity guarantees. It also establishes lower bounds on the identification cost and presents numerical experiments to evaluate the performance of the proposed method.

Critical strengths

This paper studies a potential interesting problem that is different from standard best-arm identification. The paper provides complete analysis, including the lower and upper bounds.

Critical weaknesses

1.The paper is difficult to follow, particularly the abstract and introduction. The abstract introduces several mathematical notation and technical concepts without sufficient explanation, which makes it difficult to understand the main message. Although the introduction briefly discusses the motivation and potential applications of the proposed formulation, it remains unclear why this problem is important and how it fundamentally differs from existing work. The contributions section also contains too many technical details without clearly highlighting the key contributions. Overall, the paper reads more like a collection of technical results than a coherent, well-organized study. This makes it difficult to access the paper’s central idea and the significance of its contribution.

2.The practical motivation for the proposed formulation remains unclear. Although the goal is to identify the arm with the smallest optimal value, evaluations are restricted to a coupled optimization trajectory. The potential applications discussed in the paper do not sufficiently justify this restriction. Moreover, the proposed algorithm relies on several strong assumptions. The authors should better explain why these assumptions are necessary and whether they are reasonable in practical applications.

3.The paper establishes several theoretical results. However, the key insights and broader implications are not sufficiently discussed. In particular, it remains unclear how the coupling structure fundamentally changes the difficulty of best arm identification and what the upper and lower bounds reveal about this additional difficulty.

Questions for authors

See the weakness

2 comments

The abstract introduces several mathematical notation and technical concepts without sufficient explanation, which makes it difficult to understand the main message. Although the introduction briefly discusses the motivation and potential applications of the proposed formulation, it remains unclear why this problem is important and how it fundamentally differs from existing work. The contributions section also contains too many technical details without clearly highlighting the key contributions.

We rewrote the paper

The abstract and introduction now define the target before introducing notation: choose the model that can reach the lowest loss when trained on its own. The example of classifiers sharing pixel coefficients explains why current losses may give the wrong ranking. We then explain how bounds on each minimum remain useful when shared updates change the weights.

Ordinary best-arm identification estimates the fixed means that determine the ranking. Here, observations estimate loss at the current weights. Best-function identification already compares the minimum loss each model can attain. Its F-LCB algorithm trains models independently. In our setting, training one model can change another's weights, so the analysis must account for those changes.

Revised paper — Abstract, p. 1 · §1, pp. 1–2 (selection target and shared weights example) · §2, p. 2 (“Best-arm and best-function identification”) · §§4.1–4.3, pp. 4–8 (main results).

The practical motivation for the proposed formulation remains unclear. Although the goal is to identify the arm with the smallest optimal value, evaluations are restricted to a coupled optimization trajectory. The potential applications discussed in the paper do not sufficiently justify this restriction.

We ask whether reliable selection is possible during one continuing training run with shared weights. Section 3 models a service that accepts a model and batch size, evaluates the batch at the current weights, updates once, and retains the result. Its lack of resets, separate copies, and optimizer changes is an assumption about the available commands. Weight sharing alone does not require these restrictions. The digit experiment is a controlled example of this setting.

Using the full training data at each step, our rule selected correctly in 450 of 450 runs, versus 448 for selection after one pass, with 1.0% more example evaluations on average across digit pairs. The two mistakes had negligible excess training loss, and intervals for the differences in test performance included zero.

Revised paper — §3, p. 4 (“Models with shared coefficients”) · §6.2, p. 10 (digit classifiers and full-training-set results) · Appendix B.2, p. 59 (Table 4).

Moreover, the proposed algorithm relies on several strong assumptions. The authors should better explain why these assumptions are necessary and whether they are reasonable in practical applications.

Curvature bounds turn the current loss and gradient into bounds on a model's minimum. Known noise bounds control measurement error; larger batches reduce it before an update. Theorem 2 also requires every setting of each model's weights to be feasible within some joint configuration, and step sizes bounded above and away from zero, so training can approach each minimum. In the digit experiment, normalized features and the quadratic penalty give explicit curvature bounds, and bounded example losses and gradients give known noise bounds. Ordinary nonconvex training, momentum, and step sizes tending to zero are outside this theorem.

Revised paper — §1, p. 2 (scope) · §4.2, pp. 5–6 (Assumptions 2–4 and Theorem 2) · Appendix B.2, p. 58 (curvature and noise bounds for the digit classifiers).

In particular, it remains unclear how the coupling structure fundamentally changes the difficulty of best arm identification and what the upper and lower bounds reveal about this additional difficulty.

The constraint can prevent a model's weights from moving in some directions. Theorem 1 shows that different collections of KK losses can then agree on every allowed value and gradient measurement while having different winners. When every setting of each model's weights is feasible, another model's updates can still undo its progress. Theorem 2 controls this movement and proves finite expected selection cost. Corollary 1 bounds the expected cost by an inverse-squared-gap rate, up to logarithms, when the other parameters remain controlled. Theorem 3 separates the observations needed to reach informative weights from those needed to distinguish the alternatives there. On its constructed family, the upper and lower bounds have the same order for fixed KK and error tolerances bounded away from one half.

Revised paper — §4.1, p. 4 (Theorem 1) · §4.2, p. 6 (Theorem 2 and Corollary 1) · §4.3, p. 8 (Theorem 3, Eq. 6).

Thank you for the response. My evaluation remains unchanged.

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

This paper tries to study a Best-Arm Identification problem where the each arm is an unknown differentiable function, and the input to the arm functions across the arms reside in an affine set. The best arm is identified to be the function that has minimum value over its input space. The interactive protocol is that the algorithm will have access to function value plus noise and full gradient plus noise for the chosen function to be evaluated at step t (and a batch of function values and gradient information will be available for each t.)

The results covered in this paper are summarized in Table 1. Theorem 2 (Corollary 1) and Theorem 3 provide upper and lower bounds for the variant of BAI problem studied here.

Critical strengths

The problem (the specific variant of BAI problem) is interesting to study and have potentially good applications as discussed briefly in the paper.

Critical weaknesses

The paper would benefit from extensive rewriting. I tend to believe the technical details should be correct however they are not easy to read or parse in its current presentation. I strongly encourage the authors to rewrite at least the main text.

Questions for authors

Could the author explain why the fixed confidence bound is suited for this variant of BAI, instead of maybe a fixed budget bound? Is it easy to adapt the current version of algorithm to have fixed budget bound?

2 comments

The paper would benefit from extensive rewriting. I tend to believe the technical details should be correct however they are not easy to read or parse in its current presentation. I strongly encourage the authors to rewrite at least the main text.

We rewrote most of it.

Revised paper — §1, pp. 1–2 (selection target and shared weights example) · §4.1, p. 4 (Theorem 1) · §4.2, pp. 5–6 (certificates and Algorithm 1) · §4.3, pp. 7–8 (lower bounds).

Could the author explain why the fixed confidence bound is suited for this variant of BAI, instead of maybe a fixed budget bound?

We chose fixed confidence because the acceptable risk of a wrong selection can be set in advance. The number of queries needed depends on the unknown gaps and on how quickly the updates bring each model near its minimizer. We stop when one model's upper bound lies below every other model's lower bound.

Revised paper — §3, p. 4 (“Correctness and cost”) · §4.2, pp. 5–6 (Proposition 1 and Algorithm 1).

Is it easy to adapt the current version of algorithm to have fixed budget bound?

Yes. Run the original fixed-confidence rule with error tolerance δ\delta, but stop before a whole batch would exceed the budget TT of loss-and-gradient pairs. If its original stopping condition has not been met, return a fixed default model. An error can occur because the original rule chooses incorrectly or because it needs more than TT observations. Writing CτC_\tau for its cost without a budget limit, Proposition 20 gives

\le \delta+\Pr(C_\tau > T) \le \delta+\frac{\mathbb E C_\tau}{T}.$$ Proposition 20 also gives a sufficient budget for error at most $\delta$. That threshold depends on unknown gaps and distances to the minima, so it cannot generally be checked in advance. The procedure itself needs only $T$, $\delta$, and the original rule's inputs. The best allocation under a fixed budget remains open. For quadratics with known curvature matrices, Corollary 9 separately bounds how far the selected minimum loss can exceed the best minimum loss. *Revised paper* — §4.2, p. 7 (“Fixed-budget adaptation”) · Appendix A.7.3, pp. 53–54 (Proposition 20, Eq. 87, and the threshold depending on unknown gaps and distances) · Appendix A.7.3, p. 54 (Corollary 9 on simple regret).

I would like to thank the authors for their response and the revision. I am inclined to maintain my original evaluation.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.