Formalization: Chebyshev Rollout Schedules for Polynomial Extrapolation under Low-Order Interference

Under static rollout consistency and the β-order polynomial identity, τ_P = m_P(1) - m_P(0) = ∑_{ℓ=1}^β a_{P,ℓ} (polynomial endpoint evaluation). Inherited setup from CortezEichhornYu2022; recalled only to reduce τ_P to a degree-β endpoint functional.

ℓ¹/ℓ∞ duality: for a schedule p with distinct nodes and nonempty W_β(p), the minimal total-variation norm of a representing weight vector equals the dual (Chebyshev) norm sup{ |r(1)-r(0)| : deg r ≤ β, max_j |r(p_j)| ≤ 1 }, and A_β(p) is its square. Matching the note, the only premises are that the nodes are distinct and that W_β(p) is nonempty (feasibility of the primal); there is no β ≤ k side-condition on the statement.

Lagrange endpoint weights on any k+1 distinct nodes reproduce the endpoint contrast for all polynomials of degree at most β when β ≤ k, hence satisfy the moment equations for W_β(p).

For β ≥ 1 and k ≥ β, the linear-unbiased weight set W_β(p) is nonempty for every budgeted schedule p ∈ S_{k,q}: distinct nodes make the (β+1)×(k+1) moment matrix full row rank (a nonzero degree-≤β polynomial cannot vanish at k+1 ≥ β+1 distinct points), so w ↦ Bw is surjective onto the target moment vector.

Closed form for the Chebyshev polynomial outside its oscillation interval: at any point x ≥ 1, writing λ = x + √(x² - 1) for the associated growth factor, the degree-n Chebyshev polynomial satisfies T_n(x) = (λⁿ + λ⁻ⁿ)/2. Equivalently, setting x = cosh a gives T_n(x) = cosh(n a) and λ = eᵃ.

The endpoint growth factor is larger for tighter budgets: writing λ(q) = x_q + √(x_q² - 1) with x_q = 2/q - 1, one has λ(q_max) ≤ λ(q) whenever 0 < q ≤ q_max < 1.

Upper envelope for the endpoint value: for a growth factor λ ≥ 1 and an order n ≥ 1, (λⁿ + λ⁻ⁿ)/2 + 1 ≤ 2 λⁿ.

Matching lower envelope for the endpoint value, with a constant that depends only on a floor for the growth factor: if λ ≥ λ₀ > 1 and the order satisfies n ≥ 1, then (λⁿ + λ⁻ⁿ)/2 - 1 ≥ ½ (1 - λ₀⁻¹)² λⁿ.

Endpoint growth: writing x_q = 2/q - 1, λ(q) = x_q + √(x_q² - 1), for every degree-β polynomial R with sup_{[-1,1]} |R| ≤ 1 the endpoint contrast obeys the uniform upper bound |R(x_q) - R(-1)| ≤ C(q_max) λ(q)^β, and the Chebyshev polynomial T_β supplies the matching lower order T_β(x_q) - 1 ≥ c(q_max) λ(q)^β, both uniform over q ∈ (0, q_max] (via x_q = cosh a, T_β(x_q) = cosh(β a), λ(q) = eᵃ). Uses chebyshev_exterior_extremal.

A real number of absolute value at most one remains at most one after multiplication by a sign (-1)ⁱ. Arithmetic step in the alternation argument, where polynomial values at the Chebyshev extremal nodes are compared against the alternating signs carried by those nodes.

Sign pattern of Lagrange interpolation coefficients at an exterior point: interpolating on the n + 1 Chebyshev extremal nodes of [-1, 1], the i-th Lagrange basis polynomial evaluated at any point x₀ > 1 agrees in sign with (-1)ⁱ, i.e. (-1)ⁱ ℓ_i(x₀) ≥ 0 for every index i ≤ n.

Classical exterior-point Chebyshev extremal inequality (Rivlin1974): every real polynomial P of degree ≤ β with sup_{[-1,1]} |P| ≤ 1 satisfies |P(x₀)| ≤ T_β(x₀) for every x₀ > 1. The formal proof uses the equivalent Lagrange-interpolation form of the alternation argument: the exterior evaluation functional has the Chebyshev alternating signs on the extremal nodes.

For every integer k ≥ 1 and q ∈ (0,1], the shifted Chebyshev-Lobatto schedule p^Ch(k,q) belongs to S_{k,q}: endpoints 0 and q, with strict monotonicity from the strict decrease of cosine on [0,π]. This lemma is the load-bearing member that pins the Chebyshev schedule's core space p^Ch(k,q) ∈ [0,1]^(k+1): its conclusion BudgetedSchedule has as first conjunct ∀ j, p^Ch(k,q) j ∈ Set.Icc 0 1, i.e. the [0,1]^(k+1) range, holding exactly under the admissibility hypotheses k ≥ 1 and q ∈ (0,1]. The range predicate hq : 0 < q ∧ q ≤ 1 realizes the core space q ∈ (0,1]. @realizes p^Ch(k,q)(range [0,1]^(k+1): BudgetedSchedule Icc conjunct; k≥1, q∈(0,1]) @realizes q(carrier ℝ; range 0 < q ≤ 1 via hq — the p^Ch admissibility range)

The local gate proposition is discharged by the reusable substrate implementation.

Gate consumer: for c > 1, there is a finite constant K(c) (namely sec(π/(2c))) such that for every β ≥ 1, every integer k ≥ c·β, and every degree-≤β polynomial R, sup_{[-1,1]} |R| ≤ K(c) · max_{0≤j≤k} |R(-cos(π j / k))|. Its only hard step is the gated Ehlich–Zeller mesh inequality (threaded as hmesh); the rest is sec monotonicity from β/k ≤ 1/c. Proved conditional on the gate.

The equal-spacing benchmark schedule p^eq(β,q) = (0, q/β, 2q/β, ..., q) has distinct nodes: whenever the order satisfies β ≥ 1 and the budget q is positive, distinct round indices give distinct treated fractions. Node distinctness is the premise under which Lagrange interpolation on this grid — and hence the dual description of the amplification — is available.

Size of the Lagrange basis at full treatment on the equal grid: for order β ≥ 1 and budget q ∈ (0,1], the j-th Lagrange basis polynomial for the equal-spacing schedule p^eq(β,q) obeys |ℓ_j(1)| ≤ (β/q)^β / (j! (β - j)!) at the extrapolation point 1.

Equal-spacing benchmark: A_β(p^eq(β,q)) ≤ 9 (β/q)^{2β} for every integer β ≥ 1 and every q ∈ (0,1] (the universal constant C_eq = 9). Constructed via Lagrange-basis weights on the equal grid with the ℓ¹ bound ∑|w_j| ≤ 3 (β/q)^β, plus the endpoint case at q = 1. The leading conjunct ∀ j, p^eq(β,q) j ∈ [0,1] realizes the schedule's core space p^eq(β,q) ∈ [0,1]^(β+1) (the range clause the note states for the benchmark grid); the second conjunct is the amplification bound proper. The range predicate hq : 0 < q ∧ q ≤ 1 realizes the core space q ∈ (0,1]. @realizes p^eq(beta,q)(range [0,1]^(β+1): Icc conjunct on conclusion; β≥1, q∈(0,1]) @realizes q(carrier ℝ; range 0 < q ≤ 1 via hq)

On the integer grid {0, 1, ..., β}, the product of the distances from a fixed index i to all the other indices equals i! (β - i)!.

For every natural number n ≥ 1, 2ⁿ ≤ 2 · n!. Arithmetic step that converts the binomial total 2^β arising in the equal-spacing weight bound into a factorial denominator.

For every order β ≥ 1, the reciprocal-factorial sum ∑_{j=0}^{β} 1 / (j! (β - j)!) is at most 2; the sum in fact equals 2^β / β!, and the bound follows from 2^β ≤ 2 · β!.

Rate-feasibility of the Chebyshev-Lobatto schedule for the exact risk: for c > 1, β ≥ 1, k = ⌈c·β⌉, and q ∈ (0, q_max], the fixed-Chebyshev exact risk obeys inf_{w∈W_β(p^Ch)} sup_{P∈P_β} w'Γ_P(p^Ch)w ≤ (σ₀²/n) C₊(c,q_max) (ρ(q)/q)^{2β}, hence R_exact(β,k,q) ≤ (σ₀²/n) C₊(c,q_max) (ρ(q)/q)^{2β}. Pure composition of exact_risk_envelope_upper (applied to the admissible p^Ch via chebyshev_schedule_admissible) with the Chebyshev upper half of chebyshev_minimax. The range predicate hc : 1 < c realizes the core space c ∈ (1,∞); hq : 0 < q with hcap : LowBudgetCap q qmax realizes q ∈ (0,1]. @realizes c(carrier ℝ; range 1 < c via hc) @realizes q(carrier ℝ; range 0 < q ≤ q_max < 1 via hq + hcap)

The endpoint growth factor written directly in terms of the budget: for 0 < q < 1, (2/q - 1) + √((2/q - 1)² - 1) = (1 + √(1 - q))² / q.

The total-variation amplification of a rollout schedule is never negative, being an infimum of squared total-variation norms of unbiased weight vectors. The bound also holds vacuously when no unbiased weights exist for the schedule, since an infimum over an empty set of reals is 0.

Exhibiting one admissible design bounds the minimax value: if p is a budgeted rollout schedule with budget q on k + 1 rounds, then the minimax amplification M_{β,k,q} is at most that schedule's own amplification A_β(p). This is the direction used to convert an explicit design, such as the shifted Chebyshev–Lobatto grid, into an upper bound on the minimax value.

A lower bound holding for every admissible design is a lower bound on the minimax value: if at least one budgeted schedule with budget q on k + 1 rounds exists, and every such schedule p satisfies B ≤ A_β(p), then B ≤ M_{β,k,q}.

The budget is respected at every round: in a budgeted rollout schedule the treated fraction increases across rounds and equals q at the final round, so every round j has p_j ≤ q. This is what confines all schedule nodes to the budget window [0, q].

The change of variables carrying the budget window onto the Chebyshev interval is well-defined: with a positive budget q, any treated fraction u with 0 ≤ u ≤ q is mapped by u ↦ 2u/q - 1 into [-1, 1]. Under this reparametrisation the rollout schedule's nodes become points of the standard interval on which Chebyshev polynomials are bounded by one.

Composing the degree-β Chebyshev polynomial with the affine rescaling u ↦ (2/q) u - 1 again yields a polynomial of degree at most β. Degree bookkeeping for the test polynomial used in the minimax lower bound, which must remain admissible for the degree-β dual problem after being transported from the standard interval to the budget window.

No rollout design can beat the Chebyshev exponential base. Granted an endpoint growth bound for the Chebyshev polynomial with a positive constant c — that T_β(2/q - 1) - 1 ≥ c λ(q)^β uniformly over orders β ≥ 1 and budgets q ∈ (0, q_max] — EVERY budgeted rollout schedule p with budget q ≤ q_max < 1 on k + 1 rounds, where the number of rounds satisfies k ≥ β, has total-variation amplification at least c² · ((1 + √(1 - q))² / q)^{2β}.

Composing a polynomial of degree at most β with the affine map x ↦ (q/2)(x + 1), which carries the standard interval [-1, 1] onto the budget window [0, q], leaves the degree at most β. Degree bookkeeping for moving a dual test polynomial between the two parametrisations in the amplification upper bound.

The shifted Chebyshev–Lobatto rollout design attains the exponential base, matching the lower bound. Granted two inputs — an endpoint upper bound with constant C, namely |R(2/q - 1) - R(-1)| ≤ C λ(q)^β for every polynomial R of degree at most β bounded by one on [-1, 1]; and a norming-set inequality with constant K, valid once the number of rounds satisfies k ≥ c β, controlling the largest value of such an R on all of [-1, 1] by K times its largest value on the k + 1 Chebyshev–Lobatto nodes — the Chebyshev–Lobatto schedule p^Ch(k,q) has total-variation amplification at most (K C)² · ((1 + √(1 - q))² / q)^{2β} for every order β ≥ 1 with β ≤ k and every budget q ≤ q_max < 1.

No-extrapolation boundary at the full-budget point q = 1: the endpoint rule w₀ = -1, w_β = 1, wⱼ = 0 for 1 ≤ j ≤ β-1 lies in W_β(p^eq(β,1)), hence A_β(p^eq(β,1)) ≤ 4. Marks the limit where node optimization becomes trivial (a β-uniform lower bound cannot extend to q = 1).

Total-variation variance envelope and its sharpness: if the round statistics X₀,...,X_k satisfy the per-round envelope Var_pi(X_j) ≤ σ₀²/n (the threaded assumption RoundMeanVarianceEnvelope), then Var_pi(∑ⱼ wⱼ Xⱼ) ≤ (σ₀²/n)(∑ⱼ|wⱼ|)² for every real w, via the L²(π) triangle inequality.

Order bookkeeping for taking an infimum after a uniform multiplicative comparison.

Envelope-to-exact-risk bridge: for β ≥ 1, k ≥ β, q ∈ (0,1], and every budgeted schedule p ∈ S_{k,q}, the fixed-schedule exact risk is dominated by the amplification envelope, inf_{w∈W_β(p)} sup_{P∈P_β} w'Γ_P(p)w ≤ (σ₀²/n) A_β(p) (the same L² triangle argument as variance_envelope_sharpness applied to the exact covariance Γ_P(p)); consequently R_exact(β,k,q) ≤ (σ₀²/n) M_{β,k,q}.

Headline theorem (Chebyshev-Lobatto matched minimax). Fix q_max ∈ (0,1) and let ρ(q) = (1 + √(1-q))². There is a positive constant C₋(q_max) — chosen UNIFORMLY IN c, depending only on q_max — and, for every oversampling ratio c > 1, a positive constant C₊(c,q_max), such that (both uniform in β, k, q) for every β ≥ 1, every integer k ≥ c·β, and every q ∈ (0, q_max]:

Range realization for ρ_Ch(c,q_max) ∈ [1,∞): the minimal-base infimum is ≥ 1, pinning the symbol's declared space [1,∞) VALUE-wise (not merely element-wise). The defining set {ρ | 1 ≤ ρ ∧ ∃ M, …} has 1 as a lower bound (every member satisfies the 1 ≤ ρ conjunct) and is nonempty: the Chebyshev upper half gives A_β(p^Ch) ≤ C₊·(((1+√(1-q))²)/q)^{2β}, so after multiplying by q^β the base is bounded by 4^β. Thus ρ = 4 is a finite witness, and le_csInf gives 1 ≤ sInf. @realizes rho_Ch(c,q_max)(range [1,∞): 1 ≤ rhoCh established value-wise via nonempty witness)

Main deliverable 1 (TV-envelope rollout design theorem). Assume β ≥ 1 and k ≥ β. For every budgeted schedule p ∈ S_{k,q} and every law P ∈ P_β (bundled as RolloutLawClass), the unbiased weight set is nonempty, and for every w ∈ W_β(p) the linear rollout estimator hat_τ_{w,p} = ∑ⱼ wⱼ bar_Y_j is design-unbiased for τ_P = m_P(1) - m_P(0) and satisfies the sharp total-variation variance bound Var_pi(hat_τ_{w,p}) ≤ (σ₀²/n)(∑ⱼ|wⱼ|)².