acceptodds
Under review as a conference paper at ICLR 2027

Differentially Private Worst-Case Ratio Analysis via Entropic Smoothing

Abstract

Discriminative dimensionality reduction seeks a subspace in which the classes remain separated, and the pairs of classes that lie closest together are the hardest to keep apart. In this paper we investigate pairwise worst-case ratio analysis (PWCRA), a criterion that protects those pairs by maximizing, over all class pairs, the smallest ratio of the between-class scatter of a pair to its own within-class scatter. The resulting problem is a non-convex, non-smooth max–min fractional program. A second difficulty is that the learned projection is a function of class means and covariances, so releasing it can reveal information about individual samples. We address both with entropic smoothing. Reversing the sign of the criterion turns it into the minimization of a pointwise maximum, and replacing that maximum by a log-sum-exp function gives a smooth surrogate whose gap to the exact maximum is additive, independent of the ambient and the target dimension, and vanishing as the temperature tends to zero. Built on majorization–minimization principles, the resulting single-loop algorithm, ESRA, assembles at every iteration a gradient with closed-form softmax weights and then takes one polar-factor update, with no inner solver. We then make the same pipeline differentially private by releasing the per-class sufficient statistics once through a Gaussian mechanism, so that the whole optimization is post-processing and the privacy budget does not grow with the number of iterations. We prove privacy, monotone descent, stationary convergence and an end-to-end utility bound, together with a stability bound for the softmax weights that sets the temperature from the noise level of the mechanism, so the tighter the budget, the warmer the smoothing at which we stop. The private variant follows the privacy budget closely, and in terms of the nearest-neighbour, nearest-mean and quadratic discriminant error rates, supported by paired significance tests, ESRA outperforms the state-of-the-art and benchmark methods.

Primary area:
optimization
Keywords:
differential privacy, discriminative dimensionality reduction, minimax fractional programming, pairwise worst-case ratio analysis, worst-case class separation

Reviews

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

The paper proposes ESRA and DP-ESRA, which is the differentially private version of ESRA, to solve pairwise worst-case ratio analysis. The problem is solved by maximizing the minimum ratio of between-class to within-class scatter across class pairs. The proposed method, ESRA, uses entropic smoothing to obtain a closed-form polar-factor step without an inner solver. Its private extension, DP-ESRA, perturbs the matrices directly and uses the post-processing property of DP. The paper provides utility analyses with experiments on image datasets. The methodological contribution appears limited, and the motivation for combining entropic smoothing with differential privacy needs clearer justification.

Critical strengths
  1. I think the problem formulation is interesting. Is the formulation of the pairwise worst-case ratio analysis novel? Using pairwise within-class scatter is reasonable when the class distributions have different variances. More discussion about the

  2. The algorithm is simple and computationally attractive. ESRA replaces the inner problem with softmax-weighted gradient calculations, which yields a closed-form polar-factor update.

Critical weaknesses
  1. The privacy extension provides very limited additional novelty. Using the standard Gaussian mechanism and the post-processing property of differential privacy is very standard in the differential privacy literature.

  2. The theoretical analysis contains a gap between the utility and the algorithm. The utility guarantee assumes a global minimizer of the objective, but the proposed algorithm guarantees only stationarity.

Questions for authors
  1. Is the proposed pairwise ratio analysis novel, or is it adopted from existing work? Please clarify the contributions of the formulation.

  2. What technical contribution does DP-ESRA provide beyond applying the Gaussian mechanism and post-processing? Can the authors demonstrate the specific benefit of entropic smoothing compared with other solvers using the same privatized statistics?

  3. Some related work shows that when the initial point lies within the basin of attraction, then the algorithm can converge to a global minimum. Can the authors use similar techniques to establish global convergence?

Reviewer_HD5rOpenReview ↗
Rating
2(+1)
Confidence
2
Informativeness
2
Presentation
1
Soundness
2(+1)
Read review
Paper summary

This paper studies a variant of supervised dimensionality reduction, where we have CC classes that are well-separated in dimension dd, but we want to reduce the dimension to m≪dm \ll d while keeping the classes separated. Linear discriminant analysis (LDA) is a widely used method for this, but the paper argues that it averages the separations of all class pairs and is therefore dominated by far-apart pairs, making closer pairs indistinguishable after dimension reduction. In PWCRA, instead of maximizing average separation, it maximizes the separation of the worst-separated pair of classes. Wang et al. 2024 [45] propose the WDDR algorithm, but their design yields O((d+m)4.5)O((d+m)^{4.5}) operations, and the recovered projection is not guaranteed to be optimal. Moreover, prior PWCRA algorithms are not private; the resulting projection can reveal information about individual samples, and existing methods (i.e., private PCA) do not clearly carry over to a worst-case separation criterion.

The paper has two contributions:

(1) The ESRA algorithm, a single-loop algorithm for PWCRA smoothing. It combines log-sum-exp smoothing with an iterative optimization method that updates a projection matrix using a gradient and an SVD.

(2) The DP-ERSA algorithm, which is essentially a differentially private variant of ESRA using a simple input-perturbation approach.

Critical strengths
  1. The studied problem, while poorly presented, is interesting, and I see its importance.
  2. The ERSA algorithm looks interesting according to my understanding.
Critical weaknesses
  1. This paper is very hard to read! I struggled to get even a basic understanding and intuition for the studied problem. I'm also not entirely convinced that PWCRA is the right objective, and I think the paper lacks a thorough comparison with other objectives (e.g., when we would prefer LDA over PWCRA).
  2. The utility guarantee of ERSA (Theorem F.1) and the conclusion regarding the end-to-end utility guarantee of DP-ERSA (as stated in Theorem 4.5) are unclear (see my question below).
  3. The experiments use a preprocessing step of (non-private) PCA to retain 98% of the energy, so the empirical conclusions w.r.t. the private algorithm are not really on real-world datasets.
  4. It is hard for me to evaluate the novelty and challenge beyond ERSA, but I can tell that moving from ERSA to DP-ERSA is very straightforward.
Questions for authors

The main objective of PWCRA is to maximize f(T)=min⁡i<jri,j(T)f(T) = \min_{i<j} r_{i,j}(T). Rather than maximizing ff directly, you minimize the smooth objective FτF_{\tau} and show that if T^\hat{T} is a global minimizer of FτF_{\tau}, then f(T^)f(\hat{T}) is close to the optimum (Proposition 3.2). But I don't understand how Theorem F. 1's guarantees imply closeness to the global minimizer of FτF_{\tau}. This raises a concern regarding the end-to-end utility guarantee of DP-ESRA (Theorem 4.5), which assumes that the output is a global minimizer of the private smoothed objective. Since the proposed algorithm does not satisfy this assumption, it is unclear whether Theorem 4.5 provides any meaningful utility guarantee for DP-ESRA's actual output. Could the authors clarify how they bridge this gap?

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

The paper designs a private algorithm for the problem of pairwise worst-case ratio analysis (PWCRA). In this problem we are given a high dimensional dataset comprising of k clusters and are asked to embed the samples in a much lower dimension while preserving the separation between clusters. To ensure that the embedding is preserving the separation between clusters it is scored on its ability to separate the hardest pair of clusters, and this is measured by the ratio between <squared distance between embedded cluster centers> / <trace of total covariance of cluster 1 and 2>.

This seems like a reasonable metric to optimize for embeddings, but I do not have a deep enough background on embeddings to judge this question, so I would appreciate more context from the authors / other reviewers on the significance of the problem.

The paper essentially has 3 parts:

  1. The authors show that the problem can be manipulated into a form where gradient descent converges to a point with near optimal loss, mostly by replacing the selection of worst-case cluster pairs. An added bonus is that this GD depends only on sufficient statistics like the mean and covariance of each cluster.
  2. This can be privatized in 2 ways: either using private gradient descent (adds a privacy cost comparable to the number of iterations), or the authors preferred method of privatizing the sufficient statistics using standard clipping+noise techniques
  3. Experimental evaluation of the method on real-world datasets.

Overall, I liked the paper, but I think that the writing can be improved. In particular, it took me a while to understand this high level intuition. I think that it would be helpful to add (either formal or informal) theorem boxes to the intro saying things like "Theorem 1: There is an efficient algorithm that converges to a near optimal solution for PWCRA and uses only these sufficient statistics" and "Theorem 2: This algorithm can be privatized", with forward pointers to the relevant sections would make the paper much more approachable (right now this information is partially conveyed in prose, but that prose is pretty dense and hard to follow).

Critical strengths

The paper makes substantive algorithmic improvements by introducing a gradient descent based approach to PWCRA and proving its convergence to a near optimal solution, they show that this solution can be made private, and they show that their algorithm works well on realistic datasets.

Critical weaknesses

The biggest weakness in my opinion is the writing quality, especially earlier in the paper. I found the abstract + intro very dense and hard to read, I think that these would be much better served by providing better motivation for the problem (e.g., a real world example / lit survey / diagram to intuitively convey the importance of WDDR), and a clearer separation of the components of the paper.

Questions for authors

Main question: Could you give better context / background for the importance of PWCRA / where it will be used / if there are applications where you expect privacy to be a key desiderata?

Minor question: For many other privacy applications, DP-GD often outperforms sufficient statistics based approaches even though it needs to spread the privacy cost across many iterations. Have you tried a DP-SGD based approach here / do you have any intuitions for why it wouldn't work as well?

3 comments

I want to thank the authors for a thorough rebuttal and answering my main questions.

The writing of the paper was improved but in my opinion it is still far from being clear. For instance, I appreciate the new main result at a glance which is a nice addition, but I think it is still far too technical to provide intuition to a first-time reader of the paper. In general, I think that adding some more intuitive explanations throughout the paper would further improve its readability.

AuthorsOpenReview ↗

Sincere thanks to Reviewer Pzed, and a kind request to come back to the discussion

Dear Reviewer Pzed,

Thank you very much for your reply and for your kind words on our rebuttal and on the "main results at a glance" box.

Following your suggestion, we have started reading the whole paper again to find the parts whose readability can be further improved, adding intuitive explanations wherever they help, so that a first-time reader can understand the paper completely. We strive to complete this and re-upload the paper within the next four hours.

We kindly ask you to continue the discussion with us after the revision is uploaded. We hope that it fully meets your expectations, and if so, we would be sincerely grateful if you would consider raising your score to reflect your complete satisfaction.

With sincere thanks and kind regards,

Authors of Submission 9469

AuthorsOpenReview ↗

Revised paper uploaded, with a kind request to continue the discussion

Dear Reviewer Pzed,

As promised, we have uploaded the revised paper. Following your suggestion, we read the whole paper again and added intuitive explanations to the parts that a first-time reader may find hard to follow.

The "main results at a glance" box is now written in plain words. It explains what ESRA does in each iteration, why adding noise once to the per-class totals is enough, and why a noisier release calls for a softer maximum, while keeping the pointers to the formal statements. Section 2 now explains in words what the pairwise ratio measures. In Section 3 we explain why the log-sum-exp acts as a soft maximum, moving from an average over all pairs to the worst pair, why the update is closed-form, and how each pair pulls the projection in proportion to its weight. In Section 4 we explain why a single noisy release protects every record however long the optimization runs, describe the three steps of the utility analysis in plain terms, and explain why the temperature grows as the privacy budget tightens. The technical content and all results are unchanged.

We would be very grateful if you would take a look at the revised version and continue the discussion with us. We believe that the revised paper is now easy to follow, even for a first-time reader. If the revision now meets your expectations, we would be sincerely grateful if you would consider raising your score to reflect this.

With sincere thanks and kind regards,

Authors of Submission 9469

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.