Research map / Learning theory and algorithms / Prediction and decision losses
Towards Large Certified Radius in Randomized Smoothing Using Quasiconcave Optimization
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes QCRS, an input-specific randomized smoothing method that exploits empirically observed quasiconcavity of the sigma-radius curve to find per-input noise levels via sign-based binary search, achieving larger certified radii with about 7% overhead.
Problem
Randomized smoothing applies one fixed Gaussian noise level to all inputs, yielding conservative certified radii and a truncation (waterfall) effect; prior input-specific methods are either computationally expensive or give marginal gains.
Approach
Observes that the sigma-radius curve R(sigma) is quasiconcave for most inputs (a weaker condition than concavity), so a binary search using only the sign of a forward-difference gradient estimate can find the per-input optimal sigma cheaply, with a fallback to the original sigma.
Key results
- On CIFAR-10, QCRS improves ACR over Cohen by 48%, 18%, and 22% for models trained with sigma 0.12, 0.25, 0.50 (e.g., 0.658 vs 0.538 at sigma 0.50).
- On ImageNet, QCRS raises ACR from 0.477 to 0.541 (sigma 0.25) and from 0.733 to 0.805 (sigma 0.50).
- QCRS adds about 7% inference overhead over Cohen; combined with MACER it reaches ACR 0.715 on CIFAR-10 (sigma 0.25).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use input-specific quasiconcave sigma search instead of fixed-sigma smoothing | Randomized smoothing · CIFAR-10, σ=0.12/0.25/0.50 | ACR: 0.270 -> 0.400; 0.429 -> 0.509; 0.538 -> 0.658 | Helped |
| Use input-specific quasiconcave sigma search instead of fixed-sigma smoothing | Randomized smoothing · ImageNet, σ=0.25/0.50 | ACR: 0.477 -> 0.541; 0.733 -> 0.805 | Helped |
| Apply QCRS at inference | MACER-trained randomized smoothing · CIFAR-10, σ=0.25/0.50 | ACR: 0.518 -> 0.715; 0.669 -> 0.786 | Helped |
| Expand the sigma search interval, holding step τ=0.4 and left endpoint at 0.12 (ablation) | QCRS · CIFAR-10, σ=0.5, id%50==0 | ACR: 0.619; 0.627; 0.638 | Helped |
| Vary the search interval with left endpoint 0.20 and step τ=0.4 (ablation) | QCRS · CIFAR-10, σ=0.5, id%50==0 | ACR: 0.624; 0.625; 0.628; 0.629; 0.639 | Helped |
| Vary gradient step τ for search interval [0.3, 1.2] (ablation) | QCRS · CIFAR-10, σ=0.5, id%50==0 | ACR: 0.640; 0.634; 0.630; 0.627; 0.615 | Hurt |
| Vary gradient step τ for search interval [0.12, 1.7] (ablation) | QCRS · CIFAR-10, σ=0.5, id%50==0 | ACR: 0.572; 0.640; 0.644; 0.639 | Mixed |
Surprising findings
- Almost all sigma-radius curves on CIFAR-10 and ImageNet are not concave (at least 189 of 200 CIFAR-10 images violated concavity), undermining the DDRS assumption.
- Fairness: the class 'cars' has a notably larger optimal sigma, likely because it is the unbounded class in the data space.
Limitations
- Quasiconcavity is verified empirically and only holds probabilistically ((v-,v+)-SQC condition), with Monte Carlo estimation noise.
- Input-specific sigma complicates deployment, since a consistent sigma may be required; a memory bank from DDRS is suggested but not fully evaluated.
- Evaluated only on l2 randomized smoothing with Gaussian noise and on CIFAR-10 and ImageNet with a subset of images for ImageNet and grid search.
Experimental setup
Datasets: CIFAR-10 ImageNet
Benchmarks: CIFAR-10 ImageNet
Metrics: average certified radius (ACR) certified accuracy time cost
Baselines: Cohen randomized smoothing DDRS DSRS Insta-RS Grid Search MACER
Builds on: Cohen randomized smoothing DDRS Insta-RS MACER
Closest papers by meaning
- The Lipschitz-Variance-Margin Tradeoff for Enhanced Randomized Smoothing (ICLR 2024 · similarity 0.90)
- Average Certified Radius is a Poor Metric for Randomized Smoothing (ICML 2025 · similarity 0.87)
- Certified Robustness for Deep Equilibrium Models via Serialized Random Smoothing (NeurIPS 2024 · similarity 0.87)
- Incremental Randomized Smoothing Certification (ICLR 2024 · similarity 0.87)
- Mitigating the Curse of Dimensionality for Certified Robustness via Dual Randomized Smoothing (ICLR 2024 · similarity 0.86)
- Trust Region Methods for Nonconvex Stochastic Optimization beyond Lipschitz Smoothness (AAAI 2024 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.