acceptodds
Under review as a conference paper at ICLR 2027

The Price of a Blind Jump: How Rounds and Distributions Create Learning Paths

13 views

Abstract

How do adaptive rounds and input distributions change the cost of learning hierarchical structure? We answer this question through the blind-jump width, the number of unknown coordinates a learner must locate together. For fixed-link product juntas with square-integrable likelihood ratios and full detectability, we identify the exact ambient exponent of -batch full statistical-query (SQ) cost as the -wave carrier-closure width . Equal nonadaptive and sequential endpoints can nevertheless yield reversed difficulty rankings at intermediate rounds. A hidden-rung block staircase exhibits three regimes for the same support-recovery task. Under Rademacher inputs, depth and block width give exponent , with explicit binomial bounds for growing structural parameters. Bounded amplitude perturbations at dispersion create unary response-energy witnesses: nonadaptive full SQs recover the support, with an IID implementation using rows and arithmetic at fixed signal-to-noise ratio. Every fixed symmetric standardized nonconstant-modulus law instead requires exponentially many passive samples in , at fixed depth and signal-to-noise ratio. These results quantify how rounds build useful carriers and how distribution design supplies them immediately. Lean 4 formalizations accompany the carrier calculus, lower-bound success estimates, and selected analytic identities.

Primary area:
learning theory
Keywords:
statistical query learning, adaptivity, sparse function learning, hierarchical learning, distribution design, sample complexity, computational-statistical tradeoffs

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

The paper considers learning sparse parity functions of special block-wise structure (given by equation (3)). The results concern the complexity of learning of such functions by statistical queries. The paper is purely theoretical. Some of the results are formalized in Lean.

Critical strengths

The paper probably develops a coherent mathematical theory with some new results, but it is hard to assess and appreciate this theory for a human reader.

Critical weaknesses

Very poor exposition

The paper is extremely hard to read. It reads like written by AI and for AI. I'm not an expert in the narrow topic of the paper, but I'm familiar with some of the publications in the reference list, and they are by a large margin more readable.

The paper essentially assumes that the reader knows very well a very specialized line of previous research on hierarchical parity learning by statistical queries. The exposition is extremely dense and from the very beginning full of narrow terminology, which is never clarified ("parity characters", "rounds", "immediate interactions", "carrier", "unary witness", etc). Already the first equation (1) contains objects χS\chi_S that are never formally defined in the main text. No broad context is explained. Motivation, state of the art, specific challenges to be addressed are very poorly explained. No heuristics, simple examples, practical experiments, graphical illustrations are provided. The contributions are stated in section 1.1 in an equally unclear form, with Theorem 1.1 being both informal and vague.

This lack of clarity cannot be justified. For example, the cited paper Cornacchia and Mossel (2023) is on the same topic of parity learning, but is perfectly readable even by non-experts, has a gentle, highly informative introduction, a clear contribution, helpful heuristics, examples and experiments.

I believe that the paper needs a major revision performed with a human reader in mind.

Questions for authors

N/A

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

This paper studies how rounds and input distribution affect learning hierarchical structures. It measures the complexity by a quantity termed blind-jump width, i.e. the number of coordinates that the algorithm searches in replacement of a carrier. The result extends the detectable-set framework of Joshi et al. (2024) to a fixed number of frozen batches.

Critical strengths

The paper extends prior results on learning sparse functions to learning of hierarchical structures. It identifies a quantity termed blind-jump width that can capture the effort an algorithm needs to pay for identify hidden structures like rungs.

Critical weaknesses

The paper could have done a better job to introduce the problem studied to more general audience. For example, the paper can introduce what kinds of hierarchical structures are considered here. Are they neural networks? How large these networks are? What kinds of hidden rungs are allowed in such a structure? Why are intermediate interactions important for identifying the structures? The paper can even construct solid examples to clearly illustrate such ideas, instead of assuming all audiences are familiar with the exact literature (for example, Equation (1) was not even explained and χ\chi was not defined until the appendix).

Questions for authors

See weaknesses.

Reviewer_TRrXOpenReview ↗
Rating
2(−1)
Confidence
2
Informativeness
1(−1)
Presentation
1(−1)
Soundness
3
Read review
Paper summary

The paper studies how adaptive rounds and input distributions affect the complexity of recovering the support of a structured target. Its main result characterizes the fixed-parameter ambient exponent of full statistical-query cost, measured by q/τ², for any fixed number of frozen query batches. The exponent is given by a repeated closure of the detectable-set family. This extends the nonadaptive and fully adaptive endpoint characterizations and shows that problems with identical endpoints can have different, and even reversed, difficulty rankings at intermediate round budgets. The paper also provides explicit recovery procedures, sample-reuse guarantees, synthetic experiments, and a reported Lean formalization of selected proof components.

Critical strengths
  1. Theorem 2.2 gives an exact ambient exponent for every fixed frozen-batch budget and applies to general fixed detectable-set systems. The equal-endpoint reversal provides a clear example of information that is absent from the nonadaptive and fully adaptive characterizations. This is the paper’s strongest contribution: it identifies precisely how limited adaptivity changes the support-recovery problem.

  2. The paper combines an explicit unary recovery guarantee at degree-dependent critical dispersion with an exponential passive-information lower bound for every fixed nonconstant-modulus law. The exact moment calculations and the fractional-moment argument explain why magnitude variation can reveal useful information at one scale and concentrate that information on rare events at another. This gives the distributional comparison both an algorithmic and an information-theoretic foundation.

Critical weaknesses
  1. Although the general finite-round theorem applies beyond the staircase example, the sharp hierarchy in the main model relies on selecting a fresh hidden rung for every observation. Proposition 2.3 shows that replacing this observation rule with a deterministic sum of the same staircase terms exposes cross-rung interactions through squared-label queries and permits one-batch width-b screening. This is an informative distinction, but it also makes the hierarchy sensitive to the observation model. The paper’s significance is therefore strongest as a characterization of structured SQ support recovery; the implications for stages of representation learning or optimization are less firmly established.

  2. The general theorem identifies an ambient exponent with the link and latent dimension fixed; the concise critical sample bound fixes depth and signal-to-noise ratio; and the n-query unary result has a parameter-dependent tolerance. These qualifications are stated, but they are distributed across the main text and appendices. Bringing the assumptions and resource measures together would make it clearer which comparisons hold uniformly and which are restricted to fixed-parameter regimes. This currently limits the accessibility of an otherwise careful theoretical contribution.

Questions for authors
  1. How should the finite-round hierarchy be interpreted in relation to the motivating discussion of intermediate representations? In particular, Proposition 2.3 shows that a deterministic staircase sum admits a one-batch squared-label shortcut, while the main example avoids this through a fresh hidden selector. Please clarify which conclusions are intended to apply to broader learning settings and which depend specifically on the frozen full-SQ observation model.

  2. Compared with Assumption 2.1 of Joshi et al. (2024), Theorem 2.2 appears to require square integrability only relative to the fully decoupled product reference, rather than relative to every truncated link. Does this strictly enlarge the admissible class of links? Please clarify this relationship and the role of the conditional-projection argument, since it could strengthen the assessment of the theorem’s contribution beyond the finite-round characterization.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.