USimUL: Closing the Privacy Gap in Similarity-Based Weakly Supervised Learning

Meng Wei, Zhongnian Li, Peng Ying, Xinzheng XuSubmission to ICLR 2026 · Rejected

TL;DR

Conventional similarity-based learning relies on pairs of instances that share labels, creating a severe privacy vulnerability: uncovering one sample’s label immediately unmasks the other. USimUL fixes this by introducing an unlabeled distractor into each pair to form an "uncertain similarity triplet," proving that an unbiased risk estimator can achieve optimal convergence rates while cutting attacker label inference down to random guessing.

What Problem Does This Paper Address?

Similarity-based weakly supervised learning trains classifiers using pairwise relations ("are these two samples in the same class?") alongside unlabeled data, bypassing the need for expensive point-wise labels.

However, deterministic pairwise similarities present an acute privacy risk. If an adversary reveals or knows the sensitive attribute (e.g., medical diagnosis, financial status, or political affiliation) of one entity in a similarity pair $(x, x')$, the attribute of the other entity is instantly exposed. Existing methods using confidence comparisons or differences still maintain direct associations between instances. The authors ask: can we preserve the utility of similarity supervision while breaking the deterministic link that exposes private labels?

Methods

To break the pairwise linkage, the authors introduce Uncertain Similarity and Unlabeled Learning (USimUL):

  1. Uncertain Similarity Triplets: Instead of pairs $(x, x')$, the data annotator forms triplets $(x, \{x', x''\})$ where at least two instances share a label, but it is unknown which two.
  2. Pointwise Marginalization: Although the triplet formulation introduces joint dependencies, the authors show that if samples are drawn independently, each instance marginally follows a predictable mixture density $\tilde{P}_{US}(x) \propto 2(\pi_+^2 P_+(x) + \pi_-^2 P_-(x))$. This enables the model to break down triplets into individual pointwise samples.
  3. Unbiased Risk Estimator: By analytically matching expectations under the marginal triplet distribution $\tilde{P}_{US}$ and the unlabeled data distribution $P_U$ against the true risk, the authors derive closed-form weights ($\theta_{US}^+, \theta_{US}^-, \theta_U^+, \theta_U^-$). This yields an unbiased classifier risk estimator requiring no explicit ground-truth class labels.
  4. Absolute-Value Risk Correction: Because the risk formulation contains negative weights, empirical mini-batch loss can become negative and cause severe overfitting. Unlike standard ReLU clipping (which discards negative gradient signals), the authors apply an absolute value operator $g[z] = |z|$ to steer empirical risks towards zero.
  5. Class Prior Estimation & Error Bounds: The authors provide a mixture proportion estimation procedure to infer positive class priors $\pi_+$ when unknown, and prove that the empirical estimation error converges to zero at the optimal parametric rate $\mathcal{O}(1/\sqrt{N_{US}} + 1/\sqrt{N_U})$.
Traditional Pair:   (x, x') ---------> If x is exposed, x' is exposed! (100% leak)
USimUL Triplet:     (x, {x', x''}) --> If x is exposed, is x' or x'' similar? (Ambiguity protects privacy)

Datasets

The authors evaluated USimUL across three experimental settings:

  • Benchmark Vision Datasets: MNIST, Fashion-MNIST, Kuzushiji, CIFAR-10, and SVHN (binarized).
  • Real-World Weakly Supervised Benchmarks: Pendigits, Lost, MSRCv2, BirdSong, and Yahoo! News.
  • Privacy-Sensitive Medical/Biometric Datasets:
  • DDSM: Digital Database for Screening Mammography.
  • PDMD: Privacy Data of Monkeypox Disease (collected real-world dataset).
  • PDSD: Privacy Data of Skin Disease (collected real-world dataset).

Key Insights and Ideas

  • Uncertainty as Built-in Differential Defense: Simply appending an unlabeled distractor into the tuple prevents an adversary from determining which sample is linked. Under simulated linkage attacks, inferring hidden labels dropped from 100% on pairwise baselines to $\approx$50% on USimUL—equivalent to a random coin flip.
  • Weaker Supervision, Better Performance: Despite providing strictly less explicit pairwise information than confidence-difference methods (e.g., ConfDiff) or confidence-comparison approaches (e.g., Pcomp, PC-AUC), USimUL empirically surpasses them. Decoupling samples into a pointwise marginalized risk avoids error propagation from noisy confidence assignments.
  • Smooth Overfitting Mitigation: Enforcing non-negativity via $|z|$ rather than $\max(0, z)$ allows the learning algorithm to account for sub-zero deviations during gradient descent without hitting flat zero-gradient regions.

Key Results

  • Benchmark Superiority: Across various class priors ($\pi_+ \in \{0.2, 0.4, 0.6\}$), USimUL consistently outperforms baselines. On CIFAR-10 ($\pi_+ = 0.4$), USimUL achieves 84.62% accuracy compared to ConfDiff-ABS (82.13%) and Pcomp-ReLU (72.36%).
  • Real-World WSL Datasets: USimUL outperforms the best competing baseline by +2.67% on Pendigits (97.00%), +4.57% on Lost (81.46%), +3.78% on MSRCv2 (77.28%), and +3.58% on BirdSong (81.57%) ($\pi_+ = 0.4$).
  • Privacy-Sensitive Datasets: Under $\pi_+=0.4$, USimUL reaches 81.85% on DDSM, 90.00% on PDMD, and 91.86% on PDSD, improving by up to 4.86% over competing weak supervision methods while maintaining significantly lower variance.
  • Class Prior Robustness: Prior estimation errors decrease to $<0.03$ with moderate sample sizes, and intentionally mis-specifying training class priors (e.g., using $\pi_+ = 0.35$ or $0.45$ instead of $0.40$) results in minimal performance drops ($<1\%$).

Limitations and Future Work

  • Binary Classification Scope: The mathematical derivation assumes binary labels ($Y \in \{+1, -1\}$) and degrades if classes are exactly balanced ($\pi_+ = \pi_- = 0.5$, causing division by zero in loss weights). Extending this framework natively to multi-class classification—beyond standard reductions like Error-Correcting Output Codes (ECOC)—remains an open direction.
  • Independence Assumption: Theoretical derivations rely on samples within each triplet being drawn mutually independently from the underlying distribution, an assumption that might be violated under certain active sampling strategies.

Summary updated

Abstract

Existing similarity-based weakly supervised learning approaches often rely on precise similarity annotations between data pairs, which may inadvertently expose sensitive label information and raise privacy risks. To mitigate this issue, we propose Uncertain Similarity and Unlabeled Learning (USimUL), a novel framework where each similarity pair is embedded with an uncertainty component to reduce label leakage. In this paper, we propose an unbiased risk estimator that learns from uncertain similarity and unlabeled data. Additionally, we theoretically prove that the estimator achieves statistically optimal parametric convergence rates. Extensive experiments on both benchmark and real-world datasets show that our method achieves superior classification performance compared to conventional similarity-based approaches.
BibTeX
@misc{wei2025usimul,
  author = {Meng Wei and Zhongnian Li and Peng Ying and Xinzheng Xu},
  title = {{USimUL: Closing the Privacy Gap in Similarity-Based Weakly Supervised Learning}},
  year = {2025},
  eprint = {2509.11984},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2509.11984},
}
Figure