acceptodds
Under review as a conference paper at ICLR 2027

Protected Unbiased Sparsification: A Sharp Loewner Curve

Abstract

Many learning systems replace a probability vector —token attention, data weights, expert gates—by a random vector supported on at most coordinates. Such a replacement is trustworthy only if it is unbiased, preserves prescribed linear statistics on every realization (class proportions, group masses, control variates), and remains reliable for downstream responses that are not known when is drawn. We give a complete answer to this problem in Loewner order. Writing for the effective number of protected directions, , and for the covariance of a categorical draw that remains after regressing on the protected statistics, we construct, for every budget , an unbiased exactly protected -sparse with and we prove that the coefficient cannot be improved uniformly over instances at any budget. The result lifts a concurrent unprotected coefficient to arbitrary pathwise protection through a new residual-covariance bridge: the protected problem on coordinates with budget behaves exactly like the unprotected problem on coordinates with budget . For rational inputs, an exact-rational Las Vegas sampler draws in expected polynomial time and attains the curve within a factor . Finally, the universal guarantee is essentially the strongest constructible one: optimizing a law for a single revealed quadratic query already encodes Minimum Uncut exactly, so no polynomial-time approximation scheme outputs an explicitly represented optimal law unless . A small numerical study confirms that the constructed law tracks the curve and that the minimax step is necessary.

Primary area:
optimization
Keywords:
unbiased sparsification, Loewner order, covariance bounds, exact linear constraints, randomized rounding, learning theory

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_r3baOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

The paper studies unbiased sparsification of a probability vector in Δk\Delta_k by a random vector QQ with support mm 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 d+1≤m≤kd+1\le m\le k, where d=rank⁡(ACpA⊤)d=\operatorname{rank}(AC_pA^\top) measures the effective number of protected directions, stated as Cov⁡(Q)⪯k−m(m−d)(k−d−1)Cp∣A\operatorname{Cov}(Q) \preceq \frac{k-m}{(m-d)(k-d-1)} C_{p \mid A}. 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 1+ε1+\varepsilon. Finally, the paper shows the multiplicative factor in the Loewner-order bound is tight by a reduction from minimum cut.

Critical strengths
  1. 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.

  2. 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.

  3. 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.

  1. 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.

  2. 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.

  3. 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
  1. In the class-balanced example, for cc classes of equal total mass, independent sampling within each class gives Cov⁡(Q)=Cp∣A/c\operatorname{Cov}(Q)=C_{p\mid A}/c at $ m=c$, while the universal coefficient is 11. 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?

  2. 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?

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

Given a probability vector p∈Δkp\in \Delta_k, this paper proposed how to construct a sparse random vector QQ with ∣∣Q∣∣0≤m||Q||_0 \leq m, such that E(Q)=p\mathbb{E}(Q) = p and it satisfies AQ=ApAQ = Ap for some matrix AA almost surely.

Specifically, they proved a sharp upper bound on the covariance matrix depending on the interaction of AA and pp, Cov(Q)⪯k−m(m−d)(k−d−1Cp∣ACov(Q)\preceq\frac{k-m}{(m-d)(k - d - 1}C_{p|A}, where d=rank(A(diag(p)−pp⊤)A⊤)d = rank (A(diag(p) - pp^\top)A^\top).

The coefficient is sharp uniformly over all instances with the same k,m,dk, m, d.

From this, they are able to draw a connection between the protected problem (sparse random vector with the constraint AQ=ApAQ = Ap) and the unprotected one. Finally, they construct an efficient sampler of QQ that approximately achieves the sharp covariance guarantee.

Critical strengths
  • Theorem 1 is an interesting result that provides a uniform sharp upper bound on the covariance matrix of the protected sparse random vector QQ. This result implies a potentially interesting connection between the protected problem with the unprotected problem.
  • They also provide an expected polynomial-time sampler of Q that approximately achieves the universal covariance guarantee (up to the coefficient of 1+ϵ1+\epsilon), which might be of practical relevance.
Critical weaknesses
  • The proposed sampler is not instance-optimal for each A,pA, p pair.
  • I found the paper difficult to follow, particularly the motivation of the protected sparsification problem. Can you give a concrete example showing how the constraint AA is chosen?
Questions for authors

The proposed algorithm assumes that AA is known. What happens if AA is unknown, but we know an upper bound on dd?

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

The paper asks when a sparse vector QQ exists that approximates a probability vector pp well, while placing two additional requirements. First, the authors require QQ to protect a set of prespecified linear statistics given by a matrix AA. In particular, QQ has to satisfy AQ=ApAQ = Ap almost surely. Second, they ask that QQ is an unbiased estimator of pp. In this setting, the authors prove a (non-constructive) upper bound on the achievable performance by bounding the covariance of the estimator by a constant multiple of Cp∣AC_{p \mid A}, defined as the covariance of the categorical draw e∼pe \sim p conditioned on Ae=ApAe = Ap. Moreover, they show that this constant multiplier is optimal and that this guarantee can be achieved almost exactly by an efficient sampler.

Critical strengths
  • Problem. I find the problem of sparsification with protected directions conceptually interesting, as it is a natural constrained variant of the well-known problem of approximately representing a probability vector.
  • Positive results. The authors give a tight guarantee in Loewner order and achieve it to arbitrary accuracy with an efficient algorithm.
Critical weaknesses
  • Presentation. The paper is extremely difficult to read: the exposition is really dense, and intuition is limited. For instance, the authors never explain why comparison to Cp∣AC_{p \mid A} in the Loewner order makes sense as the central measure of performance. Apart from that, the paper introduces non-standard terminology that is not explained anywhere (e.g., “fiber,” “radial oracle”), and the same holds for notation (e.g., Δk∘\Delta_k^\circ on page 5).

Overall, the presentation is the main reason for my score. As currently written, the paper adds limited value to the community.

Questions for authors
  • The authors give an upper bound on Cov⁡(Q)\operatorname{Cov}(Q) in Lowner's order as a constant multiple of Cp∣AC_{p \mid A}. As far as I understand, the authors never explain the significance of Cp∣AC_{p \mid A}, i.e., why one would be concerned with upper bounds that scale with Cp∣AC_{p \mid A}.
  • Do you have intuition of how allowing some "slack" in protected directions would affect the results (e.g., if we only ask that protected directions are preserved up to error ϵ\epsilon)?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.