Source
Chowdhury, Dubey, Beirami, Kidambi, Monath, Ahmed and Chaturvedi (2025), LIT-963, AISTATS 2025, read in full in NOTE-820: Lemma 3.3 with its proof (A.2), Definition 4.1 with its justification (A.3), and Method 4.2 with its justification (A.4). The bounds build on Calmon et al. (2015, 2017), not held here.
What was actually shown
- The cap. For any erasure Z = f(X), possibly stochastic, with A → X → Z, the chain rule gives I(Z;X) = I(Z;A) + I(Z;X|A) − I(Z;A|X). With I(Z;A) = 0 and I(Z;A|X) = 0 this is I(Z;X|A) ≤ H(X|A), with equality iff H(X|Z,A) = 0. Nothing else is assumed.
- Deterministic attainment. Under finite supports and disjoint group supports (A2–A4), a deterministic piecewise map attains the cap iff the groups’ conditional distributions have equal support sizes and are permutations of each other. Equality forces each group’s map to be one-to-one. Zero leakage forces equal output distributions across groups (strict concavity of entropy). Mapping each group bijectively onto a common Q achieves both.
- Positive utility is possible. With |𝒳| > |𝒜|, zero leakage is compatible with positive utility (Lemma 3.2, via Calmon et al.). A constant map is always perfectly erasing and useless.
The cap could have failed only through an error in the chain rule. The attainment condition could have failed: A.3 is an argument that a weaker condition does not suffice for deterministic maps, and it holds.
What this does not say
- Not that unequal groups put the cap out of reach. The paper says so (§4), but its necessity argument covers deterministic maps only. Stochastic maps can reach the cap whenever each group’s distribution is a coarsening of one common Q. Under disjoint supports a quantile common refinement always supplies such a Q; NOTE-820 gives the construction and a numerical check. The cost is a larger output support. The paper’s own algorithm for unequal groups is stochastic and does not use this.
- Not a statement about tasks. Utility is I(Z;X), information about the whole representation. The task-level consequence, I(Z;B) ≤ H(B|A) for any B, follows by the same chain rule but is this record’s step, not the paper’s.
- Not about overlapping concept groups. Disjoint supports make A a function of X. Then the cap is H(X) − H(A): perfect erasure costs at least the concept’s entropy. With overlap, the attainment analysis does not apply.
- Not about relaxed erasure. For leakage ε > 0 the paper has only Calmon et al.’s bracket max{0, u − H(X|A)} ≤ ε(u) ≤ u·I(A;X)/H(X), and defers the attaining functions.
- Not that PEF is the best erasure in practice. Its empirical lead rests on known or KDE-estimated distributions, V-information lower bounds and two real datasets. That comparison is ML practice and belongs to the anthology.
Connections
- QUESTION-010. A one-step partial answer. A representation can be made to carry nothing about one variable while keeping everything about the rest that is not shared with it, and no more. So one task family can be destroyed while another is kept, exactly to the extent the second does not run through the first. Like THEORY-199, it is single-step and about an ideal procedure that knows the distributions. It says nothing about chains or about relations as opposed to a categorical label.
- THEORY-199. The same shape of answer by a different route. There, noise destroys a top-level class while low-level features survive. Here, a designed map destroys a chosen label at a known information price.
Note of 2026-10-20: the cap and its attainment, re-derived
Re-derived for the promotion audit (batch 051, ADR-047 v2). X has finite support; A is the concept; Z is produced from X alone, possibly with independent randomness, so A → X → Z.
- The cap. I(Z; X, A) expands two ways, as I(Z;X) + I(Z;A|X) and as I(Z;A) + I(Z;X|A). The Markov condition gives I(Z;A|X) = 0, and perfect erasure gives I(Z;A) = 0. So I(Z;X) = I(Z;X|A) = H(X|A) − H(X|Z,A) ≤ H(X|A), with equality iff H(X|Z,A) = 0, that is, iff X is a function of (Z, A).
- Deterministic necessity. Let Z = f(X). Equality forces f to be one-to-one on the support of each group’s distribution p_a. Zero leakage forces Z given A = a to have one law Q for every a. A one-to-one image of p_a is p_a relabelled, so every p_a has the point masses of Q: the groups’ distributions are permutations of one another. This direction uses neither disjoint groups nor strict concavity of entropy.
- Deterministic sufficiency. Under disjoint group supports, if the p_a are permutations of a common Q, map each group’s support one-to-one onto Q’s support, matching masses. Then Z given A = a is Q for every a, and f is one-to-one on each group, so both conditions in 1 hold.
- Stochastic attainment. H(X|Z,A) = 0 means x = g_a(z) on group a, so each p_a is a deterministic coarsening of the common law Q of Z. Conversely, given such a Q and g_a, draw Z from Q conditioned on g_A(Z) = X. Under disjoint finite supports, the common refinement of the groups’ cumulative partitions of [0, 1] supplies Q. This is the correction the body makes to the paper’s §4.