The Setting
How large can the variance of a conditional coordinate sum be relative to a common Fourier degree bound for the observation’s cells?
For a finite coordinate set , the sign cube is , equipped with the uniform distribution.✦ For a real function , a subset and a point , the uniform mean, Fourier characters and real Fourier-Walsh coefficients are defined by (1). (1) The degree in (1) is ordinary real multilinear Fourier degree, with degree zero for constants and the zero function.
A finite observation is a map to a finite report set . For a finite observation and a report , the fiber indicator is the function on that equals one on the fiber of and zero elsewhere.✦ The fiber probability , restricted moment and fiber conditional mean of a real observable are given in (2); the conditional expectation evaluates this mean at the observed report. (2) The fiber conditional mean on an empty fiber is zero. The coordinate sum , conditional score and retained variance are defined by (3); the score is centered. (3)
A degree-controlled observation is a finite observation with positive retained variance and an assigned positive natural cell cost bounding the Fourier degree of every fiber indicator.✦ Write for these observations and for their ratio of retained variance to cell cost, as in (4). (4) The one-bit observation is the identity map with assigned cost .✦
Deterministic Switching Tables
For a finite block index set , the independent observation blocks of form the map in (5).✦ A point of this cube is identified with its family of blocks .✦ (5) This identification is called the block coordinate equivalence.
Let be a finite leaf index set. For a block input space , the selector and leaf input space is , and the full input space is ✦; the last coordinate is the fallback block. For , these spaces are identified with cubes on disjoint copies of . Write a full input as . For a full input to the event-switched observation of , the old report is . For an event , the event-switched observation is the map in (6), whose two report sets are disjoint. (6) The switching block index set consists of one selector index , one leaf index for each , and one fallback index . The switching block equivalence is the bijection from to that sends a family to its selector block, its family of leaf blocks and its fallback block; its inverse reads the corresponding block at each index. The switching cube equivalence is the bijection from to obtained by the block coordinate equivalence followed by the switching block equivalence.
A selector table chooses a leaf from the selector report, and a leaf table assigns a pass or fail value to each leaf report. For a selector table and a leaf table , the unique failing leaf event is the subset given in (7); the table-switched observation is . (7)✦
The Fixed Gaussian Parameters
The grid half-size , radius , spacing and tent width are the constants in (8). The leaf set is , with middle index and leaf centers given there. (8) The clipping function takes values in . The grid ramp differences define the selector weights , and the tent functions define the leaf tests , by (9). The selector tests are . (9)
For a measure , a real observable and weights , the weighted moments are the integrals in (10), for .✦ With the standard normal law, the Gaussian leaf and selector moment arrays are and , respectively. (10) For moment arrays , the weighted means , weighted variances and moment gain are defined by (11); quotients with zero denominator are assigned value zero. (11) The gain threshold is half the moment gain of the Gaussian arrays in (10), as specified in (12). (12)✦
Definition 1. The amplification cost factor is the positive natural number in (13), and the amplification factor is the real number in (14). (13)✦ (14)✦
The Claim
Theorem 1. Let and be finite sets, and let have . For a positive integer , write and let denote the block map in (5) for . There are such an integer , a selector table and a leaf table satisfying (15). (15)✦ The fixed amplification factor satisfies (16). (16)✦ Each degree-controlled observation admits a degree-controlled observation satisfying (17). (17)✦ The one-bit observation has the ratio in (18). (18)✦ At each nonnegative integer , some degree-controlled observation satisfies (19). (19)✦ The ratio of retained variance to cell cost exceeds any prescribed real bound for some degree-controlled observation , as in (20). (20)✦
In the paper, the result reads: if integers and a measurable observation rule on real inputs have every output indicator, on every product of finite input alphabets, expressible as a finite linear combination of functions of at most coordinates, and there is such that for every centered variance-one sequence converging weakly to a standard normal with uniformly bounded fourth moments, independent copies eventually satisfy , then finite observations have arbitrarily large , and Theorem 1.1 follows.
What Is Checked
The variance statements concern uniform finite sign cubes and deterministic selector and leaf tables; the ratio statements concern observations with positive retained variance and assigned positive natural cell costs bounding every fiber indicator’s Fourier degree.