- Rating
- 2
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 1
- Soundness
- 2
Read review
Paper summary
The paper studies unbiased sparsification of a probability vector in by a random vector with support while preserving prescribed linear statistics on every realization. Building on previous results on unprotected sparsification and protected rounding, it establishes a sharp worst-case covariance bound for every support budget , where measures the effective number of protected directions, stated as . The construction repeatedly moves the current probability vector to the boundary of its protected affine slice, reducing its support while preserving its conditional expectation. The paper then constructs an exact-rational sampler attaining this bound within a factor of . Finally, the paper shows the multiplicative factor in the Loewner-order bound is tight by a reduction from minimum cut.
Critical strengths
-
Sparsifying a distribution while preserving unbiasedness and specified linear statistics is an important problem that has potential applications in simplifying the attention mechanism. The paper improves previous protected rounding guarantees and extends the sharp unprotected bound from concurrent work to the harder protected setting.
-
The matching worst-instance lower bound establishes the optimality of the universal tradeoff, giving a substantial conceptual contribution to understanding the cost of exact protection. The reduction from Minimum Uncut is elegant.
-
Small synthetic experiments illustrate the covariance guarantee and the benefit of the paper's construction.
Critical weaknesses
The presentation is a substantial barrier to assessing the paper’s contributions and technical guarantees.
-
The improvement over the previous work is not clearly compared. For instance, although Section 2 and Table 1 quote [Haverbeck et al., 2026]’s guarantee, the comparison uses different support parameters and covariance comparators, leaving readers to reconstruct the error term. The paper should express the results (e.g., in Table 1) using the same total support budget, explicitly state the multiplicative factor in the Loewner bound, and clearly explain its improvements. Also, I think the comparison could be moved to the main body, after presenting the results.
-
The cohesion of the introduction could be largely improved. Currently, transitions between claims or sentences sometimes look abrupt. Specialized terms such as “quadratic query” and “explicitly represented optimal law” receive insufficient explanation.
-
The technical exposition is difficult to verify, particularly the rational-sampler analysis, because formal statements and proofs receive insufficient intuitive explanation. A technical overview describing the construction, obstacles, and key ideas would help.
I believe the technical contribution is important. However, I currently lean toward weak rejection because the write-up makes the contributions difficult to assess and the technical sections hard to verify. I would raise my evaluation if the authors substantially improve the presentation.
Questions for authors
-
In the class-balanced example, for classes of equal total mass, independent sampling within each class gives at $ m=c$, while the universal coefficient is . So this seems to contradict your claim that the covariance cannot be pushed down lower (line 94). Do you refer to a worst-case guarantee over all instances, or am I misunderstanding anything?
-
Could the authors explain the experimental setup and its connection to the theoretical algorithm more clearly? In particular, the experiments use multiplicative weights with a fixed number of rounds, which seems different from the minimax step in Algorithm 1. Which components of the theoretical construction are implemented or approximated, and which guarantees are the experiments intended to validate?