Clustered Randomized Smoothing for Stochastic Prediction Functions

• URL: http://arxiv.org/abs/2608.12037v1
• Date: Wed, 12 Aug 2026 13:20:36 GMT
• Title: Clustered Randomized Smoothing for Stochastic Prediction Functions
• Abstract summary: We propose a framework that partitions noisy samples using an arbitrary clustering algorithm, and applies $$-smoothing locally within each cluster.<n>By interpreting the smoothing distribution as a mixture of $$-smoothers, we derive a lower bound on the probability that the smoothed prediction lies within a union of compact regions.<n>We empirically evaluate our framework on two benchmarks, demonstrating substantial improvements over state-of-the-art methods.
• Score: 8.570050655718417
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Modern stochastic predictors can model rich, multi-modal outcome distributions. However, this expressive power comes with challenges in ensuring robust predictions $-$ a critical requirement in safety-critical domains. Randomized smoothing is a leading technique for improving robustness, particularly against adversarial perturbations. Yet, in stochastic multi-modal regression settings, randomized smoothing often fails due to mode collapse, yielding averaged predictions that do not reflect the underlying distribution. To address this limitation, we propose clustered $α$-smoothing, a framework that (1) partitions noisy samples using an arbitrary clustering algorithm, (2) applies $α$-smoothing locally within each cluster, and (3) combines the resulting predictions into a mixture distribution. By interpreting the smoothing distribution as a mixture of $α$-smoothers, we derive a lower bound on the probability that the smoothed prediction lies within a union of compact regions corresponding to distinct modes. We empirically evaluate our framework on two benchmarks, demonstrating substantial improvements over state-of-the-art methods. In stochastic trajectory prediction on a driving simulator dataset, our approach achieves, on average, a $27\%$ lower Wasserstein distance to the ground-truth distribution compared to $α$-smoothing. In quadrotor control, where modes correspond to distinct feasible paths to a target, our method reduces the collision rate by $81\%$ relative to the state-of-the-art randomized smoothing.

Related papers

• Estimating Mixture Distributions via Stochastic Mirror Descent [15.58350224981605]
  We revisit the problem of estimating an unknown distribution from its samples by fitting a mixture model that minimizes cross-entropy loss.<n>We propose a family of estimators derived from the mirror descent (SMD) algorithm.<n>We demonstrate that under mild conditions, the proposed estimators achieve near-optimal convergence rates.
  arXiv  Detail & Related papers  (2026-05-24T08:19:42Z)
• Robust and Consistent Ski Rental with Distributional Advice [13.811651343801579]
  The ski rental problem is a canonical model for online decision-making under uncertainty.<n>We propose a framework that integrates distributional advice of unknown quality into both deterministic and randomized algorithms.<n>We show that our framework improves consistency significantly over existing point-prediction baselines while maintaining comparable robustness.
  arXiv  Detail & Related papers  (2026-03-31T04:04:21Z)
• Revisiting Randomization in Greedy Model Search [16.15551706774035]
  We propose and analyze an ensemble of greedy forward selection estimators that are randomized by feature subsampling.<n>We design a novel implementation based on dynamic programming that greatly improves its computational efficiency.<n>Contrary to prevailing belief that randomized ensembling is analogous to shrinkage, we show that it can simultaneously reduce training error and degrees of freedom.
  arXiv  Detail & Related papers  (2025-06-18T17:13:53Z)
• Theory on Score-Mismatched Diffusion Models and Zero-Shot Conditional Samplers [49.97755400231656]
  We present the first performance guarantee with explicit dimensional dependencies for general score-mismatched diffusion samplers.<n>We show that score mismatches result in an distributional bias between the target and sampling distributions, proportional to the accumulated mismatch between the target and training distributions.<n>This result can be directly applied to zero-shot conditional samplers for any conditional model, irrespective of measurement noise.
  arXiv  Detail & Related papers  (2024-10-17T16:42:12Z)
• Rejection via Learning Density Ratios [50.91522897152437]
  Classification with rejection emerges as a learning paradigm which allows models to abstain from making predictions.<n>We propose a different distributional perspective, where we seek to find an idealized data distribution which maximizes a pretrained model's performance.<n>Our framework is tested empirically over clean and noisy datasets.
  arXiv  Detail & Related papers  (2024-05-29T01:32:17Z)
• Scalable Dynamic Mixture Model with Full Covariance for Probabilistic Traffic Forecasting [14.951166842027819]
  We propose a dynamic mixture of zero-mean Gaussian distributions for the time-varying error process.<n>The proposed method can be seamlessly integrated into existing deep-learning frameworks with only a few additional parameters to be learned.<n>We evaluate the proposed method on a traffic speed forecasting task and find that our method not only improves model horizons but also provides interpretabletemporal correlation structures.
  arXiv  Detail & Related papers  (2022-12-10T22:50:00Z)
• Tractable and Near-Optimal Adversarial Algorithms for Robust Estimation in Contaminated Gaussian Models [1.609950046042424]
  Consider the problem of simultaneous estimation of location and variance matrix under Huber's contaminated Gaussian model. First, we study minimum $f$-divergence estimation at the population level, corresponding to a generative adversarial method with a nonparametric discriminator. We develop tractable adversarial algorithms with simple spline discriminators, which can be implemented via nested optimization. The proposed methods are shown to achieve minimax optimal rates or near-optimal rates depending on the $f$-divergence and the penalty used.
  arXiv  Detail & Related papers  (2021-12-24T02:46:51Z)
• SmoothMix: Training Confidence-calibrated Smoothed Classifiers for Certified Robustness [61.212486108346695]
  We propose a training scheme, coined SmoothMix, to control the robustness of smoothed classifiers via self-mixup. The proposed procedure effectively identifies over-confident, near off-class samples as a cause of limited robustness. Our experimental results demonstrate that the proposed method can significantly improve the certified $ell$-robustness of smoothed classifiers.
  arXiv  Detail & Related papers  (2021-11-17T18:20:59Z)
• Byzantine-Resilient Non-Convex Stochastic Gradient Descent [61.6382287971982]
  adversary-resilient distributed optimization, in which. machines can independently compute gradients, and cooperate. Our algorithm is based on a new concentration technique, and its sample complexity. It is very practical: it improves upon the performance of all prior methods when no. setting machines are present.
  arXiv  Detail & Related papers  (2020-12-28T17:19:32Z)
• Consistency Regularization for Certified Robustness of Smoothed Classifiers [89.72878906950208]
  A recent technique of randomized smoothing has shown that the worst-case $ell$-robustness can be transformed into the average-case robustness. We found that the trade-off between accuracy and certified robustness of smoothed classifiers can be greatly controlled by simply regularizing the prediction consistency over noise.
  arXiv  Detail & Related papers  (2020-06-07T06:57:43Z)
• Distributed Sketching Methods for Privacy Preserving Regression [54.51566432934556]
  We leverage randomized sketches for reducing the problem dimensions as well as preserving privacy and improving straggler resilience in asynchronous distributed systems. We derive novel approximation guarantees for classical sketching methods and analyze the accuracy of parameter averaging for distributed sketches. We illustrate the performance of distributed sketches in a serverless computing platform with large scale experiments.
  arXiv  Detail & Related papers  (2020-02-16T08:35:48Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.