acceptodds
Under review as a conference paper at ICLR 2027

Compress Now, Contaminate Later: One Quantizer for Every Huber Level

Abstract

In binary hypothesis testing with compressed observations, the encoder may have to be fixed before anyone knows a bound on the contamination. We study this setting where the decoder learns a common Huber contamination bound only after encoding, and can then choose its test but not undo the encoder's merges. For known finite laws, output symbols suffice to keep a constant fraction of robust Hellinger information at every feasible level, where is comparable to clean squared Hellinger distance. We also characterize the cost of using fewer symbols, which can be steep. On a geometric family with evidence scales, the best uniform sample overhead satisfies , even though a bit selected separately for each level has constant overhead. An adjustable-growth version of our construction attains this order. The exponential penalty applies to one identical memoryless channel where a known schedule of different one-bit encoders has overhead on the same family. Learning the encoder from clean observations is harder still. No finite training budget depending only on clean difficulty preserves every raw-feasible level with a fixed output budget. A fitted test does succeed above an estimation-error threshold, and independent calibration certifies tests through simultaneous moment bounds. Experiments measure the alphabet–information trade-off, compare designs that target clean information, and quantify what certification costs.

Primary area:
learning theory
Keywords:
information-preserving quantization, robust hypothesis testing, Huber contamination, communication-constrained inference

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_e6wEOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

As far as I am able to understand, to the best of my abilities: The paper studies the problem of robust hypothesis testing: the goal is not to test whether samples come from distribution P versus Q, but rather, from the composite classes H_eps(P) versus H_eps(Q), where H_eps(P) is the set of distributions of the form (1-eps) P + eps R, over all distributions R. This is a fairly well-studied problem in statistics and information theory, the twist in this paper is that the test is performed not directly but through a noisy version of the observation. They show, among other things, that the number of samples needed to get to the same error level only changes by a "constant factor" [this comes with qualifications that are unclear, see below].

Critical strengths

None.

Critical weaknesses
  1. The paper is extremely poorly written: there is no clear problem description, most sentences do not make any sense and are poorly contextualized. The related work section is just a list of references with no effort made to situate those papers in relation to this.
  2. There is no attempt to motivate or provide reasonable background for the problem. It is unclear what the goal of the paper is, why it is interesting

I do not like or want to make assumptions but it is abundantly clear to me that this paper is the unedited output of a large language model (likely not a very good one at that). Sentences appear to make sense if the goal is simply to read through aimlessly but any attempt at understanding what anything means is futile, starting from the very first sentence of the paper.

Questions for authors

I would need the authors to actually attempt to write or edit the paper themselves to change my opinion. I could ask a list of specific questions that make their results unclear, but there are far too many to list. For example, what is this "growth factor" that is mentioned in Theorem 1 but is not defined anywhere else?

Reviewer_fmZMOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper focuses on the problem of binary hypothesis testing where each observation passes through a fixed memoryless encoder (channel). The encoder is chosen first and then a Huber contamination bound ε\varepsilon is revealed to the decoder. The decoder then selects the robust test for that level to decide between PP and QQ, but cannot recover distinctions between inputs that the encoder merged. The goal is to have a single encoder that for every feasible ε\varepsilon, increases the required sample size by at most a constant factor relative to uncompressed robust testing.

Critical strengths

The problem tackled is novel and well motivated from information theoretic viewpoint.

Theorem 1 (and Lemma 2) is one of the main technical strengths of the paper, a single binning preserves clipped moments at all thresholds at once, so O(1+log⁡(1/J))O(1+\log(1/J)) outputs keep a constant fraction of robust information at every feasible ε\varepsilon.

Another strength is theorem 3 which discusses the trade-off between alphabet size and the cost of reuse. A matching lower bound shows that any single fixed encoder pays a sample overhead exponential in the number of evidence scales per output symbol, and the construction achieves this. By contrast, encoders chosen per level or scheduled across observations pay only constant or linear overhead, so the penalty comes specifically from requiring one identical encoder.

Synthetic experiments with 80-digit precision, including the optimality of the clean-MI baseline is confirmed by a second, independently written solver. Detailed specifications and seeds are provided.

Critical weaknesses

My main concern is whether the paper is actually relevant/significant to ICLR. The paper is primarily dealing with information theory problem and is only tangentially related to learning theory at best. This is also evident from the cited works. Even though the synthetic experiments strengthen the paper, however real data is not used and applications to machine-learning use cases have not been discussed. I believe a better fit would be an information theory venue or perhaps maybe a conference with a primary focus on statistics.

Questions for authors

Why in introduction no motivation for real-world use cases is skipped? Can the authors provide use cases with real data and supporting experiements which follows the paper's setup of binary hypothesis testing?

Reviewer_487NOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
1
Soundness
3
Read review
Paper summary

This paper studies binary hypothesis testing under Huber contamination, where observations are compressed by a fixed encoder before the contamination bound ε\varepsilon is known. Once ε\varepsilon is revealed, the decoder can choose an appropriate test, but the encoder must remain unchanged. The goal is to design an encoder with a small output alphabet that preserves the sample complexity of robust hypothesis testing simultaneously for all feasible contamination levels.

For known distributions (P,Q)(P,Q), the authors first construct a quantizer with O(1+log⁡(1/J))O(1+\log(1/J)) output symbols, where JJ is comparable to the squared Hellinger distance between PP and QQ. The quantizer guarantees that, for every feasible contamination level, the sample complexity of robust hypothesis testing increases by at most a constant factor compared to testing on the original, uncompressed observations. To achieve this, the construction separates symbols ii according to whether Pi>QiP_i>Q_i or Pi<QiP_i<Q_i, and then further partition them based on the quantity Ai:=∣Pi−Qi∣/(Pi+Qi)A_i := |P_i - Q_i| / (P_i+Q_i). The goal is to preserve distinctions between symbols that may become important at different contamination levels. In particular,

  • for symbols with large AiA_i, the construction groups them into geometrically spaced bins [a,2a),[2a,4a),…[a,2a),[2a,4a),\ldots.
  • for symbols with small AiA_i, it instead groups them so that the total probability mass of successive bins grows geometrically, with the probability mass measured under the mixture distribution (P+Q)/2(P+Q)/2.

The authors show that this construction preserves the first and second moments of the clipped quantity min⁡(Ai,t)\min(A_i,t), simultaneously for all clipping thresholds tt. Since the optimal robust test involves clipping the likelihood ratio (at thresholds determined by ε\varepsilon), this allows the same quantizer to preserve testing quality across all ε\varepsilon.

The paper also studies the trade-off between the number of output symbols KK and the worst-case increase in sample complexity RKR_K. They prove an upper bound of log⁡(1+RK)=O(1+log⁡(1/J)/K)\log(1+R_K)=O(1+\log(1/J)/K) for all distributions and show that this bound is tight on a family of distributions. Additionally, the paper gives impossibility result for learning the encoder from noise-free training observations.

Critical strengths
  • I think designing an encoder with a small output alphabet that works simultaneously for all contamination levels as a problem is theoretically interesting. From my reading of the related work section, this appears to be a new problem formulation, as previous work on robust quantization generally assumes that the contamination level is known when designing the encoder.

  • The paper establishes a nontrivial theoretical guarantee. The underlying idea of the construction and its analysis through clipped-moment inequalities is clean and effective.

Critical weaknesses

Although the problem and the idea are not particularly complicated, I found the paper unusually difficult to read. The authors frequently introduce terminology that may be technically meaningful but is not immediately intuitive, and then use that terminology throughout the paper without much explanation. Examples include "raw-feasible", "identity fallback", and "evidence scales". For a theoretical paper, I think it would be clearer to refer directly to the mathematical objects rather than introduce nonstandard terminology.

Another issue is that parts of the construction and proofs are explained in highly compressed sentences that are difficult to parse. E.g.,

  • construction: in Section 3, the construction is described in a dense paragraph that mixes intuition with technical details (without a formal algorithm or a clear presentation of the steps in the main text).

  • proof: the paragraph following Lemma 2 jumps between "at most one lower bin straddles tt (a clipping threshold)", a "slack covers the straddling bin", and an argument that a lower bin "is charged to the predecessor", all within a few sentences. I found it difficult to follow the reasoning without reconstructing the intermediate steps myself.

Similar issues appear throughout the nine-page main text, so I am concerned that the paper, in its current form, is not presented clearly enough for the broader ICLR audience. It requires substantial effort to understand the constructions and how the different ingredients of the proofs fit together. For a theoretical paper, clearly communicating the main ideas and arguments is an important part of the contribution. In my view, the paper would require a substantial revision of its exposition and organization before it is ready for publication.


While I find the problem formulation theoretically interesting, its practical relevance is bit unclear. The paper motivates the setting in one sentence: "the encoder may have to be fixed before anyone knows a bound." But it is unclear in what applications the contamination bound would be (1) unknown when designing the encoder but (2) become available later when choosing the test.

Questions for authors

NA

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.