首页 > AI前沿 > Protected Unbiased Sparsification: A Sharp Loewner Curve

Protected Unbiased Sparsification: A Sharp Loewner Curve

arXiv机器学习 2026-11-11 17:36 15 阅读 查看原文

问题与设定

Random sparsification replaces a probability vector by a random vector with few nonzero entries. We ask for unbiasedness, exact preservation of prescribed linear statistics, and a covariance guarantee for every downstream linear response. Let $p$ have $k$ positive coordinates, let $A$ specify the protected statistics, and let $d\le k-2$ be their effective rank.

主要构造与理论结果

For every $d+1\le m\le k$, we construct an unbiased random probability vector $Q$ with at most $m$ nonzero coordinates, $AQ=Ap$ on every realization, and $\operatorname{Cov}(Q)\preceq h C_{p\mid A}$, where $h=(k-m)/((m-d)(k-d-1))$ and $C_{p\mid A}$ is the categorical covariance after optimal linear adjustment for the protected statistics.

This coefficient is sharp uniformly over instances, even among biased estimators when error is measured by its second moment.

扩展与采样器

A residual covariance bridge extends the concurrent unprotected curve to arbitrary pathwise linear protection. We also characterize instance-optimal constants for partitions with uniform weights within classes and derive bounds for peaked weights.

For rational inputs, an exact Las Vegas sampler attains the curve within a factor $1+ε$ in expected polynomial time. A separate fast block-pivotal sampler preserves block masses and is no worse in covariance order than independent sampling within blocks.

实验验证

Experiments illustrate the theory on synthetic weights and language-model attention. In Qwen2.5-7B-Instruct decoding, the fast sampler preserves block masses