acceptodds
Under review as a conference paper at ICLR 2027

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

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.

Then back it, or bet against it.

Related papers

Open the market on this paper to see 7 more related papers.