acceptodds
Under review as a conference paper at ICLR 2027

Support Vector Machines with Randomized Response

Abstract

The linear support vector machine (SVM) is a fundamental binary classification model. In many classification applications, labels are sensitive, and randomized response can ensure label differential privacy (LabelDP). This paper studies statistical inference for the linear SVM under randomized response. We construct a corrected loss to estimate the linear SVM parameter. Since the hinge loss is non-differentiable, we apply convolution smoothing to obtain a differentiable objective and the corresponding estimator. For the estimator, we analyze its asymptotic properties and establish confidence intervals. We then select the randomized response probabilities by minimizing the trace of the covariance contribution induced by randomized response within the feasible regions of -LabelDP and -LabelDP, leading to optimal randomized response mechanisms. Simulation studies and a real-data application show that the proposed method improves parameter estimation, confidence interval coverage, and prediction accuracy.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
support vector machines, randomized response, label differential privacy, asymptotic inference, optimal mechanism

Reviews

Among:
Shape:
1234this paper, Bottom 2%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.33 over 3 reviews, above 2% of the others.
Reviewer_ZRu6OpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies estimation and inference for the linear SVM when binary labels are privatized through randomized response. It combines loss correction with convolution smoothing, develops asymptotic inference for a local estimator, and characterizes optimal binary response probabilities under pure and approximate LabelDP for a specified variance criterion. Simulations and a real-data application compare the proposed method with naive private and nonprivate SVM baselines.

Critical strengths
  1. The paper addresses parameter inference under label privacy, extending the evaluation of private SVMs beyond prediction accuracy. Its corrected and smoothed formulation connects estimation of the clean-label SVM target with an explicit covariance estimator, providing a useful framework for understanding how label randomization affects parameter uncertainty.
  2. The variance decomposition separates ordinary sampling variability from the additional variability introduced by randomized response, making the statistical cost of label privacy explicit. The characterization of optimal binary RR mechanisms under the chosen trace criterion provides interpretable and tractable guidance for mechanism design.
Critical weaknesses
  1. The asymptotic guarantees do not sufficiently connect to the actual estimated quantities used in practice. They focus on the local minima within the neighborhood of the unknown target, while the actual implementation of optimization starts from biased RRSVM estimation and does not guarantee to reach the solution. The paper also acknowledges the serious lack of interval coverage in the Gaussian experiments, but does not investigate whether the coverage improves with the increase in sample size, nor does it diagnose the optimization error and variance estimation error. This limits the evidence for the actual reliability of the proposed confidence intervals. 2.The actual mechanism selection procedure has not been proven to constitute a complete privacy inference process. The paper does not explain how the privacy-protected samples of each candidate mechanism are obtained, so it is impossible to determine whether the loss correction matches the actual randomization mechanism and how privacy is calculated across candidate mechanisms. Additionally, the trace of the minimum score covariance is usually not equivalent to the trace of the parameter covariance, which also includes the Hessian factor. These gaps limit the actual effectiveness and inference interpretation of the claimed optimal mechanism.
Questions for authors
  1. What guarantees the actual optimizer implementation to reach the local solutions analyzed in Theorem 1-3? Can the author report the changes in coverage with the increase in sample size and provide optimization diagnostics as well as sensitivity analyses of initialization and bandwidth to explain the observed coverage deficiency? 2.How are the privacy-protected labels used by the three candidate mechanisms generated? Please explain the complete selection and training protocol, its privacy accounting, and why the covariance estimates used for comparing candidate mechanisms remain valid under this protocol. 3.Why does the mechanism selection criterion omit the Hessian factor in the sandwich covariance of the estimator? Will minimizing the trace of the complete parameter covariance change the selection between approximate LabelDP mechanisms?
Reviewer_gvtUOpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

The paper studies inference for linear SVM parameters when binary labels are privatized through randomized response. It combines a noise-corrected hinge loss with convolution smoothing and develops local asymptotic theory, covariance estimation, and component-wise confidence intervals. It also decomposes the score variance into nonprivate and privacy-induced contributions and characterizes mechanisms minimizing a trace-based criterion under pure and approximate label DP. Simulations supports their theories. Also, some confidence interval coverage remains substantially below the nominal level.

Critical strengths
  1. The paper aims to recover the population SVM parameter defined using the original labels, rather than merely fit a classifier to privatized labels. The corrected-loss identity and privacy-variance decomposition make the statistical consequences of randomized response explicit.
  2. Its local strong-convexity analysis, asymptotic expansion, and sandwich covariance construction form a substantive technical framework. Although there are some proof and implementation issues, see weaknesses below.
Critical weaknesses
  1. On p. 7, lines 324–334, candidate randomization probabilities are substituted into the objective and compared using empirical score covariance. If the same private labels are reused, a candidate generally does not match the channel that generated those labels, so the corrected risk identity no longer applies. If separate privatizations are used, the data acquisition protocol and privacy accounting remain unspecified. In addition, Theorem 1 concerns a local solution in a shrinking neighborhood of the unknown target, whereas the numerical algorithm is initialized at RRSVM. These gaps affect the central claim of a usable procedure with valid inference.

  2. In Figure 1 and the accompanying discussion on p. 8, nominal 95% intervals achieve average component-wise coverage of 0.686–0.806 under pure LabelDP and 0.713–0.791 under approximate LabelDP. This is a substantial shortfall, even though it improves on the uncorrected baseline.

  3. The paper’s soundness that do not appear easy to address. For examples:

Theorem 2 gives the parameter’s asymptotic covariance as

Σ0=H0−1V0H0−1.\Sigma_0 = H_0^{-1}V_0H_0^{-1}.

However, mechanism optimization uses tr⁡(Vcondp)\operatorname{tr}(V_{\mathrm{condp}}), and the explanation appeals to the sum of the asymptotic variances of the parameter components. The corresponding privacy contribution to that sum is instead

tr⁡(H0−1VprivH0−1).\operatorname{tr}\left(H_0^{-1}V_{\mathrm{priv}}H_0^{-1}\right).

It cannot generally be removed from a trace minimization problem. For the conditional-design version, the relevant weights would involve ∣∣H0−1Xi∣∣22||H_0^{-1}X_i||_2^2 rather than ∣∣Xi∣∣22||X_i||_2^2.

Similarly, assumption 7 requires

nhn2log⁡(1/hn)⟶∞,\frac{nh_n^2}{\sqrt{\log(1/h_n)}} \longrightarrow \infty,

whereas the proof obtains

sup⁡θ∈Nn∥Hn(θ)−H(θ)∥op=Op(log⁡(1/hn)nhn2+hn)=op(1).\sup_{\theta\in N_n} \|H_n(\theta)-H(\theta)\|_{\mathrm{op}} = O_p\left(\sqrt{\frac{\log(1/h_n)}{nh_n^2}}+h_n\right) = o_p(1).

The stated assumption does not justify the final equality. For example,

\qquad \lambda_n=n^{-1},$$ satisfy the stated sequence conditions, but the displayed square-root term is of order $(\log n)^{1/8}$. There are other similar issues and I cannot state them all here. The authors should carefully check the manuscript.
Questions for authors

Except the weaknesses,

  1. How often was each of the three candidate mechanisms selected in the simulations and the real-data experiment?

  2. How sensitive are the reported comparisons to the different bandwidth choices used for NP/RRSVM and ORRSVM?

  3. How were runs with optimization or covariance-estimation difficulties handled in the simulations?

  4. Were feature standardization and PCA fitted separately within the training portion of each real data split?

Reviewer_c6MaOpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
1
Soundness
3
Read review
Paper summary

The authors alter the loss function for linear support vector machines that allows for the bias for randomized response when the labels are data re noised. They find the optimal randomized response mechanism parameters that leads to the best output (measured in trace of the covariance). They apply their methods to synthetic and real-data to show their improvement over the naiver algorithm which finds the SVM on the output.

Critical strengths
  1. The paper is thorough and descriptive. Looking through the details in the text and appendix, I have no issues with soundness.
Critical weaknesses
  1. To me, the paper was not easy to read: the paper mostly follows a pretty technical program of Rybak et al with, in my opinion, little high level overview. Additionally, there are parameters that are not defined in the paper but presumably defined in Rybak et al that make it difficult to understand (See assumption 4 on page 3: What is X_{-1}? What is B(\theta^*, r_0)?)

  2. On a high level, what this paper does is debiases the output for randomized response to better find SVM when the hinge loss is smoothed. I do not see this as exceptionally novel, as several papers already debias randomized response in their regime to get better accuracy (the Ghazi et al paper they cited). Additionally, I think this has limited applicability since the work is restricted to SVMs.

Questions for authors
  1. Can you give more motivation for instances where you would need SVMs compared to another linear model, like logistic regression? Why not use the WALR algorithm (https://github.com/patcg-individual-drafts/ipa/blob/main/logistic_regression.md)?

  2. Why should the model be that we are optimizing for the best randomized response mechanism and we can set the parameters? Should not the assumption be that p_{-1} and p_{+1} are set for us?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.