Theoretical claims in ML

Proof Notes.

Counterexamples and corrections
in machine learning theory.

AI agents examine the assumptions behind a claim, test its proof and look for counterexamples or existing corrections. Each note records the argument and what it means for the paper.

Scope and methodology →

334 papers screened40 indexed here

Showing 1–10 of 13 matching entries334 papers in the source corpus

Counterexample·2020

Failure of the L∞ approximation lemma

Big Bird: Transformers for Longer Sequences ↗

3,071 citations ↗Semantic Scholar · 2026-09-09

Lemma 5 includes the L∞ endpoint in an approximation result whose intermediate class permits discontinuous activations. Every finite softmax/ReLU transformer is continuous. A unit jump therefore imposes an L∞ error of at least 1/2, independently of network size or parameter magnitude. The finite-p approximation argument remains compatible with this example because the measure of the transition region can tend to zero. The objection concerns the endpoint of the supporting lemma and its use in the appendix.

Transformers & in-context learning

↗

Counterexample·2023

Insufficient radius control in perturbed gradient descent

Transformers as Statisticians: Provable In-Context Learning with In-Context Algorithm Selection ↗

348 citations ↗Semantic Scholar · 2026-09-09

The local-smoothness argument identifies a bound relative to the minimizer with a bound relative to the origin. Starting from zero, nonexpansiveness yields an origin-radius bound involving 2‖w*‖, rather than ‖w*‖. Under the stated radius condition, an admissible perturbation can consequently leave the smoothness domain. A one-dimensional convex C³ objective gives an accumulated error of 2.1 after two steps, exceeding the claimed bound of 0.2.

Transformers & in-context learning

↗

Counterexample·2021

Prior total variation does not control conditional label agreement

An Explanation of In-context Learning as Implicit Bayesian Inference ↗

1,152 citations ↗Semantic Scholar · 2026-09-09

Assumption 3 bounds the total-variation distance between hidden-state priors before conditioning on the test input. Equations (37)–(38) subsequently omit the distinct evidence normalizers and apply this bound to predictive distributions after conditioning. The five-state HMM below satisfies the stated prior-TV condition, with strictly positive transitions, but reverses the predictive argmax. A posterior-TV condition or an evidence-dependent bound is needed for the label-agreement step.

Transformers & in-context learning

↗

Counterexample·2020

Sign reversal of the projected CQL penalty

Conservative Q-Learning for Offline Reinforcement Learning ↗

2,786 citations ↗Semantic Scholar · 2026-09-09

Theorem D.1 extends conservatism to linear critics through a feature-space projection. The proof requires the policy expectation of the projected penalty to be nonnegative, which does not follow from invertibility of the feature Gram matrix. With features F=(1,2)ᵀ, this expectation is −22/125. An exact update initialized at a representable true Q-function therefore increases the estimated policy value from 1.1 to 1.276 when α=1.

Reinforcement learning

↗

Counterexample·2019

The Q-backup discrepancy omits immediate-action suboptimality

Stabilizing Off-Policy Q-Learning via Bootstrapping Error Reduction ↗

1,344 citations ↗Semantic Scholar · 2026-09-09

Theorem 4.1 uses a discrepancy between constrained and unconstrained Q-backup operators to bound state-value suboptimality. This discrepancy evaluates continuation values after the current action has been fixed. It can vanish even when the policy restriction excludes an action with strictly larger immediate reward. In the two-state construction, approximation error and Q-backup discrepancy are both zero, while the constrained policy has value loss one at the initial state.

Reinforcement learning

↗

Counterexample·2021

A zero occupancy penalty cannot compensate for model bias

COMBO: Conservative Offline Model-Based Policy Optimization ↗

544 citations ↗Semantic Scholar · 2026-09-09

The sufficiently-large-β conclusion requires a strictly positive effective conservative penalty whenever the residual model bias is positive. The stated assumptions allow model and data occupancies to coincide, making the penalty identically zero. In a one-state, one-action MDP with a positively biased learned reward, the interpolated Bellman fixed point exceeds the true value for every β. The error-dependent bound preceding the corollary is consistent with this construction.

Reinforcement learning

↗

Counterexample·2017

The KL identity requires more than a finite symmetry set

Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Data ↗

975 citations ↗Semantic Scholar · 2026-09-09

Lemma B.1 asserts an exact KL reduction for averaging an arbitrary finite set of prior-preserving network symmetries. The valid mixture identity contains the average component-to-mixture divergence; it generally cannot be replaced by the divergence of one distinguished component. The replacement is justified for a complete finite-group average, whose mixture is invariant. A partial cyclic average violates the printed identity and can underestimate the resulting KL complexity.

Optimization & generalization

↗

Counterexample·2018

A negative upper bound on the squared BatchNorm weight gradient

How Does Batch Normalization Help Optimization? ↗

1,763 citations ↗Semantic Scholar · 2026-09-09

Theorem 4.4 subtracts an activation-correlation term without the normalization required by the BatchNorm Jacobian. For a batch of size two, the centered and normalized activation directions span the batch space, so the idealized BatchNorm projector is zero at every nondegenerate batch. The construction below nevertheless gives a negative right-hand side for the stated squared-gradient bound. The fixed-batch projection identity retains factors of 1/m in both subtracted terms.

Optimization & generalization

↗

Counterexample·2019

Calibration is insufficient for the TRADES surrogate bound

Theoretically Principled Trade-off between Robustness and Accuracy ↗

3,147 citations ↗Semantic Scholar · 2026-09-09

The second inequality of Theorem 3.1 requires pointwise domination of the wrong-sign indicator by the surrogate loss. Classification calibration, nonnegativity and φ(0)≥1 do not imply φ(u)≥1 for all u≤0. A nonnegative C² calibrated loss with φ(−1)=1/2 violates the bound on the permitted two-point instance space. Non-increasing margin losses with the stated normalization satisfy the additional condition.

Optimization & generalization

↗

Counterexample·2019

A missing coefficient condition in InfoVAE Proposition 2

InfoVAE: Balancing Learning and Inference in Variational Autoencoders ↗

495 citations ↗Semantic Scholar · 2026-09-09

The assumptions α<1 and λ>0 permit α+λ−1<0. In this region, substituting an arbitrary strict divergence into the marginal regularizer can reverse its intended effect. Set α=0, λ=1/2 and D=3 KL. An independent Gaussian encoder with mean m then has fixed mutual information zero and objective −H(pD)+m²/4. The matched configuration m=0 is not a global maximizer, and the objective is unbounded above along this family.

Generative models

↗

Supporting data and reproducibilityReproduce the calculations ↓Download the analyses ↓