Information-Theoretic Limits and One-Bit Estimation of Sparse Relation Matrices Under Personalized Local Differential Privacy and Byzantine Contamination

Source abstract

Sparse relation tables arise when users contribute sets of user–item, learner–concept, or user location pairs. We study population relation-matrix estimation under personalized local differential privacy with heterogeneous budgets and Byzantine report replacement. The target is globally sparse, without low-rank assumptions. We propose a joint personalized relation sketch (JPRS), a set-level mechanism mapping each capped relation set to one personalized bit through a public pair-safe signed score. Its decoder combines channel amplitude weighting with sparse capped-simplex projection. Two budget functionals distinguish honest channel information from adversarial leverage. Under strong privacy, we establish a contamination-trimmed minimax lower bound over all local channels and an upper bound for JPRS against adaptive valid-output attacks from a precommitted corrupted identity set. The bounds match up to support-search logarithms on regular budget classes. In homogeneous settings, recovery requires the effective private sample size to dominate the structural scale and contamination to vanish relative to epsilon. Experiments on six synthetic scenarios and three processed public datasets show that JPRS achieves the lowest private loss and reduces endpoint loss by 23% relative to the best non-JPRS private comparator. These results characterize how personalized privacy, sparsity, and Byzantine contamination jointly determine recoverability.