PaperlayerView exact revision on arXiv

Source-linked AI summary

The cost of useful natural gradient updates

Subhransu S. Bhattacharjee, Dylan Campbell, Rahul Shome

arXiv:2609.33499v1cs.LGcs.ITmath.ITmath.OC

TL;DR

An exact natural-gradient direction may not provide enough information to choose a useful finite update under a population KL budget. The paper analyzes calibration through four-state laws, event tilts, logistic models, and classifier heads. Its results show rare-event sample costs and computational hardness for selecting useful steps, while a KL margin improves classifier-head joint success.

  • Problem

    An exact natural-gradient direction does not determine a useful finite step, and the information and cost required to calibrate its length remain under-explored.

    Source: §1 · pp. 1–2

  • Method

    The paper constructs indistinguishable-local-information laws and analyzes calibration, computational hardness, sampling bounds, and KL certification across several model settings.

    Source: §1 · p. 2

  • Results

    The four-state family’s calibration sample complexity is Θ(log(1/δ)/(pMε^2)), and a 10% KL margin raises joint success in classifier heads from about 50% to over 93%.

    Source: §1 · p. 2

  • Takeaways & Limitations

    Calibration can carry a substantial cost even when the natural-gradient direction is known exactly.

    Source: §5 · p. 9

    The bounds are worst case for single updates under stated access and output restrictions, and the experiments do not test generalization or training trajectories.

    Source: §5 · p. 10

Abstract

from arXiv · show

What information is needed to turn a natural-gradient direction into a useful finite update? Under a population Kullback-Leibler (KL) budget, we call a step useful if it is feasible and loses at most a fraction $\varepsilon$ of the best feasible gain along the direction. We construct a four-state exponential family whose laws share their initial gradient, scalar Fisher information and natural gradient, yet two laws have disjoint useful-step sets. With these quantities supplied exactly and the law otherwise known only through draws, the family's worst-case sample complexity is $\Theta(\log(1/\delta)/(p\varepsilon^2))$ for small $\varepsilon$, where $p$ scales rare-state probabilities and $\delta$ is the failure probability. The budget is fixed and the optimal gain stays bounded away from zero, so the step length, not the direction, carries this cost. For succinctly described event-tilt models, returning a useful step is NP-hard even with the exact natural gradient and efficient exact sampling. Recovering the unit natural gradient to constant error is also NP-hard even in a two-parameter logistic family with Fisher condition number at most 3. We also give matching sample bounds for event tilts, sample bounds for damped Fisher solves and a population-KL certificate for affine classifiers. In frozen-feature classifier heads, stopping at a sampled KL boundary succeeds in about half of the trials, and a 10% KL margin raises joint success above 93% at a KL budget of 0.01. Thus, knowing where to move is not enough: how far to move can carry an update's entire cost.

1 Introduction

An exact natural-gradient direction does not determine a useful finite step: the step length must also be calibrated to the population KL budget. The paper shows that local information can leave useful lengths ambiguous, calibration can inherit rare-event sampling costs, and useful-step selection can be computationally hard.

1 Introduction

  • The paper asks what information beyond an exact direction is needed to choose a useful length and what acquiring that information costs.The quadratic step can exceed feasible length by over 450 times and incur about 8.6 × 10^3 nats of KL against a 1/10 budget.Source: §1 · p. 2
  • With exact local information, four-state laws can share their initial gradient, scalar Fisher information, and natural gradient yet have disjoint useful-step intervals.The family is a softmax distribution over statistic values 0, 1, 2, and 3; its parameter shifts probability mass to a rare top state.Source: Figure 1 · p. 1, §1 · p. 2
  • The four-state family’s worst-case calibration sample complexity is Θ(log(1/δ)/(pMε^2)), matching the cost of estimating a rare probability.At fixed KL budget, the optimal gain stays bounded away from zero as pM decreases.Source: §1 · p. 2
  • Selecting a useful event-tilt parameter is NP-hard despite an exact natural gradient and efficient exact sampling, and recovering a logistic model’s unit natural gradient is also NP-hard.The logistic result holds with Fisher condition number at most 3; the paper also reports matching event-tilt sample bounds and damped Fisher-solve bounds.Source: §1 · p. 2
  • A 10% KL margin raises joint success in classifier heads from about 50% to over 93%.The introduction also reports similar calibration success across event probabilities and exact-KL calibration meeting the logistic gain target despite inaccurate directions.Source: §1 · p. 2

2 Background & Related Work

The background defines the distributional and complexity concepts used in the paper, then distinguishes its targets from prior work on inference, step selection, rare-event estimation, and certification.

Preliminaries

  • Exponential tilting reweights a base law using statistics, while the Fisher matrix is their covariance under the tilted law.The paper defines the KL budget using the forward divergence from the initial reference law and distinguishes population from empirical Fisher information.Source: §2 · p. 3

A primer on complexity theory

  • The paper’s sample lower bounds use two-point testing, while its computational reductions connect useful-output algorithms to deciding SAT.The discussion defines procedure success uniformly over considered laws and relates randomized polynomial-time success to NP ⊆ BPP.Source: §2 · p. 3

Inference and sampling access

  • The cited inference literature studies expected Fisher computation and Bayesian-network inference, whereas these reductions target the returned direction or step despite efficient exact sampling.Arithmetic-circuit compilation can make inference linear in circuit size, but the circuit may be exponential in the network description.Source: §2 · p. 3

Step selection

  • Prior step-selection work includes lower-bound improvement methods, noisy line searches, and stochastic trust-region analyses with probabilistic accuracy conditions.The paper contrasts its focus on calibration information with these analyses and cites Jin et al. (2025) on oracle and sample costs.Source: §2 · p. 3

Rare events and certification

  • Rare-Bernoulli estimation has sample order log(1/δ)/(pε^2), which the paper transfers to calibration; empirical Bernstein bounds are used to certify population KL.Prior KL estimation and policy-value certification address related but distinct targets.Source: §2 · pp. 3–4

3 Complexity of Useful Updates

Section 3 shows that exact local information, efficient sampling, or a well-conditioned Fisher matrix does not always make useful updates cheap, while draws still support guarantees for damped solves and KL feasibility.

3.1 Calibration complexity with exact gradient and scalar Fisher information

  • Four-state laws with identical first two moments and exact local information can have disjoint useful-step intervals; calibration requires Θ(log(1/δ)/(p_M ε^2)) draws.The bound holds with the exact initial gradient, scalar Fisher information, and natural gradient supplied.Source: §3.1 · pp. 4–5

3.2 Complexity of computing useful steps at a fixed KL budget

  • For event tilts, matching sample bounds show that selecting a useful step requires Θ(log(1/δ)/(p ε^2)) draws.The upper bound uses a confidence interval for event mass and chooses a step feasible across that interval.Source: §3.2 · p. 5
  • Selecting a useful event-tilt step is NP-hard despite an exact natural gradient and efficient exact sampling.The hardness applies to returning a feasible step attaining at least three quarters of the optimal feasible gain.Source: §3.2 · p. 6

3.3 Complexity of natural-gradient direction recovery

  • Recovering the unit natural gradient to error 1/32 is NP-hard from a succinct model description, and sample-only recovery needs at least D_L/6 draws.The construction uses rare informative observations, which can leave both Fisher eigenvalues small despite a bounded condition-number ratio.Source: §3.3 · pp. 6–7
  • At KL budget 1/(100D_L), finding a feasible update within 1/200 of the constrained query optimum is NP-hard.From draws alone, success probability 2/3 requires at least D_L/6 draws.Source: §3.3 · p. 7

3.4 Damped estimation and KL certification

  • For damped Fisher solves, the upper sample bound scales as (1 + d/λ) ε^-2 log(2d/δ), while a matching lower bound scales as d/(λ ε^2).The bounds apply to estimating the damped direction under the stated parameter ranges.Source: §3.4 · p. 8
  • For affine-logit softmax classifiers, a simultaneous population-KL certificate makes any candidate with bound at most η feasible with probability at least 1 − δ.The certificate controls feasibility, not gain; its slack shrinks with sample size and grows at most logarithmically in the number of candidates divided by δ.Source: §3.4 · p. 8

4 Empirical Illustrations

The experiments show that conservative KL calibration improves joint success in learned classifier heads, while direction accuracy alone does not predict finite-step gain. Across calibration rules, stopping at an estimated KL boundary often fails feasibility, whereas a margin largely avoids those failures.

Experimental setup

  • The experiments score each returned update by exact reference-law KL feasibility and gain relative to the feasible-gain benchmark.Joint success means the update is feasible and meets the gain tolerance; infeasible updates receive zero feasible gain.Source: §4 · p. 8

Calibration sample scales

  • At m p_M ε^2 = 16, the binary confidence rule has 95.8%–97.1% joint success as p varies from 10^-6 to 2^-11.For the four-state family, conservative calibration reaches 100% at the largest sample budget, while plug-in calibration remains near 50%; its KL excess is tiny but crosses the boundary.Source: §4 · p. 8

Direction accuracy and finite gain

  • 99.5% average optimal gain and the 90% gain target in every trial follow population-KL calibration, despite only 31.9% of estimated directions meeting the Euclidean tolerance.The mean cosine between estimated and population rays in Fisher geometry is 99.46%; at 16D_L draws, confidence calibration along the exact direction succeeds in 1.1% of trials.Source: §4 · pp. 8–9

Calibration in learned classifier heads

  • 99.53% on CIFAR-10 and 93.75% on SST-2 joint success with a 10% KL margin, versus 48.59% and 50.94% at the full budget.At the same setting, every margin update also meets the stricter 90% gain target; remaining failures are KL violations.Source: §4 · p. 9, Figure 2 · p. 9

5 Discussion

The discussion frames useful natural-gradient updates as having separate direction and length costs, with calibration potentially costly even when the direction is known. The appendices lay out proof tools and constructions, while the paper limits its claims to specified single-update settings and identifies open questions.

5 Discussion

  • Calibration can require rare-state information absent from local quantities, and its sample cost can match rare-probability estimation even when local information is supplied exactly.The results also establish computational intractability for useful-step selection despite efficient exact sampling.Source: §5 · pp. 9–10
  • The bounds are worst-case, concern single updates, and depend on stated access and output restrictions.The experiments use fixed checkpoints, representations, and queries under a finite reference law; they do not test generalization or training trajectories.Source: §5 · p. 10
  • Future questions include accumulation over training runs, selecting direction and length from reused draws, and reducing sample needs through rare-state importance sampling.The discussion also recommends reporting KL budget, gain benchmark, and success probability together.Source: §5 · p. 10

Appendix

  • The appendices proceed from theoretical proofs to reproducibility details and experiments, covering calibration, hardness, direction recovery, damping, and a population-KL certificate.Experiments include count simulations, logistic controls and damping simulations, and learned classifier heads.Source: Appendix · p. 13

A Procedures and lower-bound tools

  • The lower-bound procedure model permits stopping after at most m independent draws, with supplied quantities fixed across compared laws.Padding and two-point testing convert disjoint sets of successful outputs into sample lower bounds regardless of computational resources.Source: A Procedures and lower-bound tools · p. 13

B Fixed-budget calibration with an exact natural gradient

B.1 Calibration with exact gradient and scalar Fisher information

This section examines why calibrating a useful step can require more than an exact supplied direction, including computational and sample complexity for event tilts. It also qualifies the nonvanishing-gain result under alternative divergence constraints.

B.1 Calibration with exact gradient and scalar Fisher information

  • Four-state laws with identical supplied gradient and scalar Fisher information can have disjoint useful-step intervals, so exact local quantities do not determine a useful finite step.Four statistic values are the minimum support needed to vary the law while preserving its first two moments; the construction changes the finite-step KL boundary while keeping those moments fixed.Source: §B.1 · pp. 14–17

B.2 Calibration bounds and computational reduction

  • For 0 < p ≤ p0/2, 3/4-useful calibration requires m ≥ log(1/(2δ))/[-log(1 − p)], while confidence calibration succeeds with m ≥ (2048/p) log(8/δ).The lower bound holds regardless of computational power; the upper-bound rule uses Bernoulli-KL confidence intervals to return a feasible step.Source: §B.2 · p. 18
  • The benchmark optimizes event-probability gain over all distributions on the base support, and the event tilt’s optimal gain equals that unrestricted event-probability optimum.Source: §B.2 · p. 18
  • The SAT reduction encodes a formula as an event with mass p = (1 + #SAT(φ))/2^(n+11), using tag bits to separate satisfying assignments from one additional accepted state.The tag-bit count keeps the event mass below p0 = 2^-10, within the calibration bounds’ stated range.Source: §B.2 · p. 20
  • A polynomial-time calibration procedure would yield a randomized satisfiability decision via a constructible predicate and sampler, although the supplied natural gradient is one for every formula.Useful steps of polynomial bit length exist, and the reduction simulates draws with fresh fair bits.Source: §B.2 · p. 20
  • m≥10394/p draws suffice at δ=0.05; at p=10^-5, this is about 1.04 × 10^9 draws.Source: §B.2 · p. 21
  • At a fixed KL budget, the nonvanishing-gain conclusion does not extend to the examined alternative divergence constraints, whose optimal calibration sample rates remain undetermined.For update-to-base KL, feasibility forces event probability toward zero as p decreases.Source: §B.2 · p. 21

B.3 Dependence on the required improvement

  • At fixed confidence, the matching worst-case rate corresponds to expected event count mp=Θ(ε^-2), even with the exact natural gradient supplied; the testing lower bound has the constructive upper bound’s logarithmic confidence dependence.Source: §B.3 · pp. 21–22
  • Changing event mass by a factor of 1 + 4ε separates useful steps at p from feasible steps at the changed mass, enabling a testing lower bound.The useful-step interval shifts by more than its width; thresholding an output then distinguishes the two masses.Source: §B.3 · p. 22
  • The confidence-based upper bound converts mass-estimation error into gain loss and budgets additional loss for downward rounding, which preserves feasibility.The rounding allowance must scale with ε to preserve the stated accuracy.Source: §B.3 · p. 22

C Quadratic rescaling and finite KL

A quadratic Fisher model can substantially misestimate the finite-step KL cost, even when the scalar Fisher information is exact. In the examples given, modest quadratic-budget margins do not ensure feasibility.

C Quadratic rescaling and finite KL

  • The scalar example isolates finite-step approximation error from sampling error in learned-head KL estimates.The analysis distinguishes error in estimating the Fisher matrix from error in the quadratic approximation to finite-step KL.Source: C Quadratic rescaling and finite KL · p. 22
  • Targeting a fraction of the KL budget scales the quadratic-cost ratio by that fraction; scaling both budgets equally leaves the ratio unchanged.This identity describes error within the quadratic approximation.Source: C Quadratic rescaling and finite KL · p. 23
  • At p=1/2048 and budget 0.1, the quadratic step has true KL 12.609; scaling it by 0.9 still gives KL 11.571.The 10% quadratic-budget margin therefore does not ensure finite-KL feasibility in this binary-tilt example.Source: C Quadratic rescaling and finite KL · p. 23

D Direction recovery in logistic models

The logistic-model section reduces direction recovery and finite KL-constrained improvement to satisfiability, including when the Fisher matrix is well-conditioned. The following section establishes bounds for damped natural-gradient estimation and quantifies damping bias.

D Direction recovery in logistic models

  • Recovering a unit natural-gradient direction to constant accuracy is NP-hard, although the two-parameter logistic construction has Fisher condition number at most 3.A coordinate of the normalized direction separates unsatisfiable from satisfiable formulas; the construction's sampler uses polynomially many random bits and formula evaluation.Source: D Direction recovery in logistic models · pp. 23–24
  • A finite KL-constrained update also distinguishes satisfiability: valid outputs have first coordinate above 43/200 for K=1 and at most 1/5 for K≥2.Thresholding the returned coordinate decides satisfiability without evaluating the output's KL cost or objective value.Source: D Direction recovery in logistic models · pp. 24–25
  • With sample-only access, at least D_L/6 draws are required to distinguish the K=1 and K=2 logistic laws, regardless of computational power.The lower bound follows by testing the two observation laws using the separation in successful outputs.Source: D Direction recovery in logistic models · p. 25

E Damped natural-gradient estimation and lower bounds

  • The section also establishes upper and lower bounds for damped natural-gradient estimation and quantifies when damping makes the rare-event contribution negligible at the requested accuracy.Source: E Damped natural-gradient estimation… · p. 26

E.1 Fisher matrix estimation

This section gives sample guarantees for estimating damped Fisher solves and identifies when fixed damping makes estimation easier. It also shows that accurate direction estimates do not by themselves control finite-step KL.

E.1 Fisher matrix estimation

  • A damped Fisher solve can be estimated from paired independent draws using covariance concentration and spectral bounds on the estimated inverse.The estimator does not require the population matrix, and the same right-hand side isolates error from estimating the Fisher matrix.Source: §E.1 · p. 26
  • The scalar damped inverse requires at least 1/(360λρ²) Bernoulli observations for relative error ρ, and the vector lower bound scales as d/(360λ ε²).The vector result embeds the scalar problem along a known direction.Source: §E.1 · pp. 26–27
  • Damping reduces sensitivity to matrix error, but these direction-error bounds do not control finite-step KL.The bias relative to the undamped natural gradient also depends on gradient components in the Fisher eigenbasis and its eigenvalues.Source: §E.1 · p. 27

E.2 Resolution under fixed damping

  • For an event indicator with variance I ≤ ρλ, 1/λ approximates the damped inverse within relative error ρ; sampling achieves that accuracy with m ≥ 10 log(2/δ)/(ρ²λ).The stated bound also applies when the event mass is at most ρλ.Source: §E.2 · p. 28

F Population-KL certification for finite candidate sets

The section provides a population-KL certificate for selecting among finitely many affine-classifier updates. Simultaneous cost bounds permit data-dependent selection, while sequential validation certifies feasibility rather than objective gain.

F Population-KL certification for finite candidate sets

  • For finitely many candidate steps with bounded per-input KL, empirical Bernstein bounds certify that any selected candidate has population KL at most η with probability at least 1−δ.The zero step ensures the accepted set is nonempty, and selection may use the calibration observations.Source: F Population-KL certification for… · p. 28
  • The per-input KL envelope is bounded by the smaller of R_logit(t) and R_logit(t)²/8, enabling a known cost bound before sampling.The logit range is bounded using the feature norm and differences between direction rows.Source: F Population-KL certification for… · pp. 28–29
  • When candidate gains are known, a strengthened simultaneous bound selects a feasible candidate whose gain is at least the best among candidates satisfying K_j+2r_j≤η.The comparison uses a larger logarithmic confidence term than basic feasibility certification.Source: F Population-KL certification for… · p. 29
  • Fresh independent batches can validate successive proposals with an overall failure probability controlled by allocating δ/[r(r+1)] to attempt r.The sequential guarantee permits stopping after any completed attempt, but controls KL feasibility, not objective gain.Source: F Population-KL certification for… · p. 30

G Reproducibility details

The reproducibility appendix specifies reporting conventions, computational environments, randomization, and numerical tolerances. It also describes count-based calibration experiments that vary rarity and gain requirements.

G Reproducibility details

  • Learned-head intervals use paired query bootstrap resampling, while logistic and damping means use replicate standard errors and success rates use Wilson intervals.The grids, endpoints, seeds, and confidence rules in Appendices H.2 and I.2 were fixed before evaluation.Source: G Reproducibility details · p. 30
  • Learned-head studies ran with Python 3.12 and PyTorch 2.8 on RTX GPUs, while logistic, damping, and count studies used Python 3.14 on an Apple M2.The text-head experiment specifies a DistilBERT checkpoint and SST-2 dataset revisions.Source: G Reproducibility details · p. 30
  • Fixed seeds keyed learned-head draws by study, model, query, repetition, and sampling stream, with smaller-budget samples taken as prefixes of larger-budget samples..Source: G Reproducibility details · p. 30
  • Learned-head Fisher and KL computations used float64, conjugate gradients had a 10^-8 residual tolerance, and scalar searches bracketed and bisected the KL boundary.Scalar searches included the zero step because query gain may peak before the boundary.Source: G Reproducibility details · p. 30

H Count-based calibration experiments

  • Count-based experiments varied event rarity and allowed gain loss, using independent simulated counts to examine calibration sample scales.Methods received counts and the specified information; implementation and reporting conventions are given in Appendix G.Source: H Count-based calibration experiments · p. 30

H.1 Calibration in the four-state family

The four-state experiments compare calibration rules when local information is shared, while event-tilt experiments vary rarity and gain tolerance. The logistic-control section outlines comparisons of direction accuracy, KL estimation, damping, and higher-dimensional recovery.

H.1 Calibration in the four-state family

  • At normalized budget m p_M ε²=220, the conservative rule succeeds in all 2,048 trials at every family setting, while the plug-in rule succeeds in 49.32–51.71% for ω∈{1.25,1.5} and 100% at ω=1.The conservative rule's uniform 95% theorem guarantee applies only above approximately 442,666, which only the final grid budget exceeds.Source: §H.1 · p. 33
  • At normalized budget 212, every offset/rounding variant meets the gain target in every trial, so their success-rate differences measure feasibility; rounding can reduce joint success at smaller budgets.Both the positive offset and downward rounding contribute, and rounding alone ranges from 77.44% to 100% at the largest budget.Source: Table A3 · p. 32, §H.1 · p. 33

H.2 Event tilts: rarity and required gain

  • At p=10^-5 and m p ε²=16, the event-count confidence rule achieves 96.4–99.1% joint success across ε∈{1/4,1/8,1/16,1/32}.Expected event counts range from 256 to 16,384; at ε=1/32, success is 95.8–97.1% across event rarities at the same normalized budget.Source: §H.2 · p. 33

I Logistic controls and damped estimation

  • The logistic-control experiments compare direction accuracy with finite gain under exact KL calibration, then examine sampled KL estimation, damping, and higher-dimensional direction recovery.The supplied passages describe the study sequence but do not report its outcomes.Source: I Logistic controls and damped… · p. 33

I.1 Finite-step improvement with a sampled Fisher matrix

The experiments separate direction quality from finite-step calibration, testing sampled Fisher directions and KL-based step selection across logistic models, higher dimensions, and fixed-feature classifier heads. They find that useful gain can remain high despite inaccurate directions, while reliable feasibility depends on calibration and sampling conditions.

I.1 Finite-step improvement with a sampled Fisher matrix

  • At m/DL = 16, pseudoinverse and lightly damped directions achieve 99.5% and 99.6% gains, although only 31.9% of pseudoinverse directions meet the Euclidean tolerance.At K = 1, DL = 65,536 and scaled budget 0.05, sampled Fisher matrices are singular in 28.8% of trials; across 840 settings, Fisher cosine and finite-gain fractions differ by at most 6.08 percentage points.Source: §I.1 · pp. 35–36, Table A4 · p. 36
  • At K = 1, DL = 65,536 and scaled budget 0.05, methods differ in gain despite sharing a reference-KL line search; Fisher cosine closely tracks finite gain across the tested settings.At m/DL = 16, the mean Fisher cosine is 99.46% and mean finite gain is 99.54%, despite the low Euclidean pass rate.Source: §I.1 · pp. 35–36, Table A4 · p. 36

I.2 Sample-based logistic updates

  • With pseudoinverse directions and empirical calibration, feasibility ranges from 43.2% to 49.2% as m/DL rises from 16 to 1,024, while the 95th-percentile KL ratio falls from 1.411 to 1.039.At K = 1, the gradient ray reaches at most 88.3% of global optimal gain, below the 90% target.Source: §I.2 · pp. 36–37

I.3 Sample dependence on the damping scale

  • At sλ = 128, estimating reciprocal damped scalar Fisher information succeeds in 95.6–97.5% of trials across six scales, compared with 84.1–88.6% at sλ = 64.The larger setting uses 2,560–853,334 observations.Source: §I.3 · p. 37, Figure A6 · p. 37

I.4 Direction recovery in higher dimensions

  • The higher-dimensional construction retains the direction-recovery obstruction while allowing polynomial-time exact sampling for power-of-two block counts.A known projection recovers the two-dimensional SAT test from any sufficiently accurate high-dimensional output.Source: §I.4 · pp. 37, 39
  • At d = 256 and m/(nblk DL) = 16, direction success is zero for both K values despite gains of 97.60% and 98.63%; at fixed m = 16DL, pooling yields 99.55% gain versus 29.59% for separate estimation.Gradient gains remain 88.28% and 94.87% for K = 1 and 2, independent of dimension.Source: §I.4 · p. 39, Table A7 · p. 39

J.1 Models and fixed interventions

  • The classifier-head experiments update an affine softmax head for one query while keeping the learned representation fixed, using class-stratified selections of initially misclassified queries.The models include a ResNet-18 on CIFAR-10 and a DistilBERT checkpoint on SST-2.Source: §J.1 · p. 40

J.2 Directions, step selection and outcomes

  • At a positive KL boundary with a centered, nondegenerate normal estimation error, strict feasibility violations approach one half even as their magnitude vanishes.The result concerns exact feasibility before numerical tolerances; inactive constraints, caps, or directions estimated from calibration data need not satisfy the stated conditions.Source: §J.2 · p. 41

J.3 Full-budget experiment

The full-budget experiment compares empirical and reference KL calibration while separating calibration effects from direction estimation. Empirical calibration along the reference direction often violates the population budget, leaving joint-success failures attributable to KL violations.

J.3 Full-budget experiment

  • The primary comparison subtracts raw gain under empirical calibration from reference calibration, using the reference direction at m = 1,024, η = 0.01, and λ = 0.001.The methods use independent batches for Fisher estimation and calibration; each condition has 20 repetitions for each of 32 queries.Source: §J.3 · p. 41, Table A9 · p. 41
  • 47.50% of CIFAR interventions and 45.63% of SST interventions achieve joint success along the reference direction; all failures are KL violations.Joint success requires feasibility and at least 90% of the ray benchmark at the primary setting.Source: §J.3 · pp. 41–42
  • Empirical calibration along the reference direction exceeds 1.1η in 27.34% of CIFAR and 37.19% of SST interventions.Raw gains include infeasible steps and can exceed the reference-budget optimum.Source: §J.3 · pp. 41–42

J.4 Margin experiment and outcomes

The margin experiment tests whether reserving 10% of the empirical KL budget reduces boundary crossings while retaining useful gain. Empirical-margin joint success increases with sample size, though the reported uncertainty is conditional on the selected queries and fixed checkpoints.

J.4 Margin experiment and outcomes

  • The exact-law margin bound ensures that using a fraction χbud of the KL budget retains at least χbud of the full-budget ray-optimal gain.The bound applies to affine-logit softmax classifiers along a fixed direction and does not require either supremum to be attained.Source: §J.4 · p. 42
  • At η = 0.01 and m = 16,384, empirical-margin joint-success failures are 3/640 on CIFAR and 40/640 on SST; every update meets the 90% gain target.The remaining failures are KL violations; the mean decline in training-reference accuracy stays below 0.15 percentage points under both empirical rules.Source: §J.4 · p. 42
  • At η = 0.001 and the largest sample size, empirical-margin joint success reaches 98.13% on CIFAR and 91.56% on SST.The SST interval is [88.13, 94.84], and the 90% gain target lowers success at some smaller sample sizes.Source: §J.4 · p. 43

J.5 Sampling cost and uncertainty

  • Uncertainty intervals quantify variation across the selected queries, conditional on the checkpoints and query selection.Empirical updates along estimated directions use independent batches for Fisher estimation and calibration.Source: §J.5 · p. 43

Related papers

Loading 2609.33499v1…