- 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 , when candidate parameters are coupled through . Queries return noisy values and gradients and trigger prescribed projected updates without resets. The paper characterizes identifiability through the access matrices , 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 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
-
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.
-
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, , so the singular-access impossibility does not apply. Furthermore, when , the geometry-scaled step gives , independent of . 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.
-
The upper and lower bounds do not match in general. Corollary 1 establishes the rate with fixed and the curvature, access, gains, noise, and initial and transformed anchor radii uniformly controlled. The dependence on geometry is not confined to ; it also enters the stopping phase . In Corollary 3, the bounded-radius construction requires , 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
Part 2
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 and error tolerances bounded away from one half, they have the same order, allowing constants and the logarithm used to control errors across the alternatives.
Corollary 1 bounds expected cost by an inverse-squared-gap rate, up to logarithms, for a broader class with 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 , and the phase at which the intervals separate. Appendix A.3.2 sharpens the distance estimate by removing an unnecessary factor ; 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 before the observations become informative, even at fixed gap and distance. When access varies, Corollary 3 keeps the rescaled distance bounded by taking . 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.
Part 1
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).
For complete sharing, Si=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”).
When all coefficients of model i are shared equally, projection reduces every direction by the same factor si. For Si=siI, the allowed gradient multiplier 2/[si(μi+Li)] 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).