Improved Sample Complexity for Private Nonsmooth Nonconvex Optimization

Authors: Guy Kornowski, Daogao Liu, Kunal Talwar
Primary area: alignment, fairness, safety, privacy, and societal considerations
Keywords: Differential privacy, nonconvex optimization, nonsmooth optimization, Goldstein stationarity

Abstract:
We study differentially private (DP) optimization algorithms for stochastic and empirical
objectives which are neither smooth nor convex, and propose methods that return a Goldstein-stationary point with sample complexity bounds that improve on existing works.
We start by providing a single-pass $(\epsilon,\delta)$-DP algorithm that
returns an $(\alpha,\beta)$-stationary point as long as the dataset is of size $\widetilde{\Omega}\left(1/\alpha\beta^{3}+d/\epsilon\alpha\beta^{2}+d^{3/4}/\epsilon^{1/2}\alpha\beta^{5/2}\right)$,
which is $\Omega(\sqrt{d})$ times smaller than the algorithm of \citet{zhang2023private} for this task,
where $d$ is the dimension.
We then provide a multi-pass polynomial time algorithm which further improves the sample complexity to $\widetilde{\Omega}\left(d/\beta^2+d^{3/4}/\epsilon\alpha^{1/2}\beta^{3/2}\right)$,
by designing a sample efficient ERM algorithm,
and proving that Goldstein-stationary points generalize from the empirical loss to the population loss.

Decision: reject
Reviewer scores: 6, 8, 5, 5

Reviews and discussion:
<thread>
creation date:
1730546992205

thread_type:
official_review

<thread_object>
creator: reviewer_wtus

<content>
summary:
This paper addresses differential privacy (DP) in nonsmooth, nonconvex optimization, aiming to improve sample complexity for finding Goldstein-stationary points in such challenging settings. Traditional DP optimization methods often assume convexity or smoothness, but this work proposes new algorithms that can handle nonsmooth nonconvex (NSNC) objectives.
### Key Contributions

1. **Single-Pass Algorithm**  
   The authors present a single-pass (ε, δ)-DP algorithm that finds an (α, β)-stationary point with improved sample complexity. This algorithm reduces dimensional dependence by a factor of \(\Omega(\sqrt{d})\) over previous approaches, making DP optimization feasible in high-dimensional settings while maintaining privacy guarantees.

2. **Multi-Pass Algorithm**  
   A multi-pass ERM-based algorithm further enhances sample efficiency, allowing the algorithm to iterate over the data multiple times and achieve sublinear dimension-dependent sample complexity. This approach improves convergence while satisfying DP constraints.

3. **Generalization from ERM to Population Loss**  
   The authors establish that Goldstein-stationarity achieved on empirical loss also applies to the population loss with high probability. This result expands the utility of their approach by ensuring that empirical results generalize to the population.


The proposed algorithms make notable progress in DP optimization for NSNC problems, improving sample efficiency while maintaining privacy. This advancement is valuable for practical applications where data privacy is essential, especially in high-dimensional machine learning settings. Additionally, the generalization result strengthens the applicability of Goldstein-stationary points beyond empirical settings.

strengths:
1. **Significant Improvement in Sample Complexity**  
   The paper offers a substantial reduction in sample complexity for differentially private (DP) nonsmooth nonconvex (NSNC) optimization. The single-pass algorithm achieves a lower dependence on dimension \(d\) compared to prior work, which is highly impactful for high-dimensional problems in machine learning.

2. **Innovative Use of Goldstein-Stationarity**  
   By focusing on Goldstein-stationary points, the authors leverage a nuanced stationarity condition suitable for nonsmooth nonconvex optimization, allowing for more practical solutions where traditional gradient-based methods fall short. This approach builds on and expands the utility of Goldstein-stationarity in DP settings.

3. **Generalization from Empirical to Population Loss**  
   The paper addresses a theoretical gap by proving that empirical guarantees of Goldstein-stationarity translate to the population loss. This generalization strengthens the theoretical foundation and practical relevance of the proposed algorithms, as it ensures that results on empirical data apply to broader distributions.

4. **Applicability to Real-World DP Machine Learning Tasks**  
   The proposed algorithms are zero-order (using only function evaluations) and thus avoid the need for gradient information, making them suitable for a wider range of machine learning models that may have nonsmooth, nonconvex loss landscapes. This approach is particularly beneficial in privacy-sensitive applications like federated learning.

5. **Novel Dimension-Independent Term**  
   The single-pass algorithm introduces a dimension-independent term in the "non-private" component of the sample complexity, challenging previous assumptions in DP optimization for NSNC objectives. This innovation indicates potential for further sample complexity improvements and opens new directions for DP research in nonconvex settings.

weaknesses:
1. There is some typo, for instance, line 077 the last word should be perform.

2. Randomized Smoothing is an ordinary technique used in this setting, and I wonder the novelty except for this to deal with the non-smooth setting.

questions:
1. Is the result in the paper tight? In other words, is there a lower bound provided?

2. What is the key challenge in improving the result by at least $\(\sqrt{d}\)$? Specifically, how does this improvement compare to the results in the referenced work?

3. What role does the (α, β)-Goldstein stationary point play in this paper?

4. What is the novelty of this paper compared to previous works?

5. Can you explain more about the result regarding the non-private term and private and how they contribute to the final result?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730671374719

thread_type:
official_review

<thread_object>
creator: reviewer_hf98

<content>
summary:
This paper explores differentially private (DP) optimization algorithms for stochastic and empirical objectives that are non-smooth and non-convex, presenting methods that achieve Goldstein-stationary points with improved sample complexity bounds compared to prior work. The authors introduce a single-pass ($\epsilon$,$\delta$)-DP algorithm capable of producing ($\alpha$,$\beta$)-stationary points. Subsequently, they propose a multi-pass, polynomial-time algorithm that further refines sample efficiency by designing an effective ERM algorithm and demonstrating that Goldstein-stationary points can generalize from the empirical to the population loss.

strengths:
The paper studies an important problem in DP non-convex optimization, and achieves improved sample complexity bounds over existing works.

weaknesses:
The presentation is at times unclear, leading to a disjointed reading experience.

Additionally, the paper offers limited technical innovation. Most of the algorithmic framework and techniques appear to be adapted from previous works.

questions:
1. The tree mechanism in Algorithm 1 is hard to understand and seems logically inconsistent. Specifically, regarding the function NODE, what is its intended purpose? There appears to be no defined output for NODE. Moreover, in line 13, $k'$ is assigned a value greater than $k$, however, line 14 subsequently tests the condition $k'\le k$, which can never be true. As a result, $S$ remains an empty set and is never updated.

2. In the fourth line of Proposition 2.5, for calculating each $X_i$, should it instead use $\sum_{j=1}^i M_j$  rather than the expression given in the paper  $\sum_{j=1}^i M_i$?

3. In (Cutkoskyetal.,2023), $\Delta_{t+1}$ is updated by $\Delta_{t}+\eta g$ (as stated in their Remark 10), while in Algorithm 2 line 8, $\Delta_{t+1}$ is updated by $\Delta_{t}-\eta g$. Could you clarify the rationale behind this difference?

4. In Theorem 3.1, while the sample complexity has been reduced by a factor of $\Omega(\sqrt{d})$ compared to (Zhang et al., 2024), this comes at the expense of increasing the number of random directions $m$ from $d$ to $d^2$, potentially resulting in a longer runtime.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730677339446

thread_type:
official_review

<thread_object>
creator: reviewer_ugbn

<content>
summary:
This paper studies the problem of designing Differentially Private Algorithms for Nonsmooth Nonconvex Optimization. It specifically studies the zeroth order settings. Thanks to more careful analysis, the paper is able to improve on the dimension dependence of the previous results. It also extends the past result to the ERM settings.

strengths:
- The paper is a fairly simple extension of previous results. The authors are able to improve the past sample complexity by an order of $O(\sqrt{d})$ by using a high probability subgaussian bound on the sensitivity of the queries. 

- The paper also extends the results to other settings.

- The generalization statement (Proposition 5.1) is a cool result to show the validity of the ERM approach for solving the Goldstein-stationary point.

- The paper is well written overall.

weaknesses:
- The paper is basically using the same algorithm proposed by [1]. This is not a huge issue since they are able to make some nice modifications to improve the sample complexity. However, this does limit the potential impact of the paper.

- I also think $m$ is quite large, which would make it really inefficient to run in practice. Currently, m can be something like $O(d^2T^{4/5})$, which is very hard to do in practice.

- It would be interesting if there were some matching upper bounds.

[1] Zhang, Qinzi, Hoang Tran, and Ashok Cutkosky. "Private zeroth-order nonsmooth nonconvex optimization." arXiv preprint arXiv:2406.19579 (2024).

questions:
- Why did the authors decide to use Gaussian Mechanism instead of the tree mechanism for ERM?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730692285888

thread_type:
official_review

<thread_object>
creator: reviewer_kzv5

<content>
summary:
The paper presents algorithms to improve sample complexity in differentially private (DP) nonsmooth, nonconvex (NSNC) optimization. The authors propose two zero-order algorithms that improve the results over Zhang et al. 2024
1. Single-pass, sqrt(d) improvement over Zhang et al. 2024. The authors also establish a dimension-independent “non-private” term, which is not known before for NSNC DP optimization.
2. A multi-pass algorithm further improves the sample complexity, yielding the first algorithm to preform private ERM with sublinear dimension-dependent sample complexity for NSNC objectives.
Additionally, the authors show that Goldstein-stationarity generalizes from the ERM to the population.

strengths:
- The paper is well-structured and easy to follow.
- The results improve over prior state of the art, establishing the first DP NSNC ERM algorithm with sublinear dim-dependent sample complexity. The non-private term is dimension-independent, which improves over the previous dimensional dependent result in Zhang et al. 2024.

weaknesses:
My main concern is about contextualizing the contribution:
Like Zhang et al. 2024, this paper also heavily relies on “Online-to-Non-Convex conversion” (O2NC) of Cutkosky et al. (2023). The authors also mention that a lower bound is unknown, making it hard to assess the contribution beyond incremental improvement.

A discussion of the Tree Mechanism is missing. It would be very hard for readers not familiar with the Tree Mechanism to understand.
Typo: page 2 and in particular is the first algorithm to [preform] private ERM

questions:
1. I am confused by the explanation of the improvement on the non-private term Remark 3.2. The authors explain that
> while the optimal zero-order oracle complexity is d/αβ^3 (Kornowski & Shamir, 2024), and in particular must scale
with the dimension (Duchi et al., 2015), the sample complexity might not.
Since the algorithm is one-pass, then the sample complexity would be worse than the oracle complexity?
2. Is Online-to-Non-Convex conversion optimal? (Related to the weakness above) If not, any algorithms based on it will be suboptimal.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732124947973

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Rebuttal: Common comment

comment:
We thank the reviewers for their time and effort. We are encouraged by their appreciation of our contributions, as well as by their constructive efforts in helping us strengthen our work.
We address all questions by responding directly to each review. Here we briefly reiterate our key responses.

**Novelty**:

Some reviewers asked about the novelty of our results and techniques, compared to previous results.
The sample complexity we derive in this work is not only better than previous results, it was previously erroneously claimed to be impossible - so we believe that even the fact that we have been able to get to these results carries novelty.

Furthermore, our analysis introduces several factors which were not used by previous works on this subject, which were also acknowledged by some reviewers.
First, by identifying a simple concentration argument for the gradient estimator, we reduce its sensitivity, already leading to a significant improvement over prior work. Moreover, to further improve the sample complexity, we analyze the empirical objective which was not considered by any prior work on DP nonsmooth nonconvex optimization, and prove that Goldstein-stationary points generalize from the empirical loss to the population. Not only does this generalization result lead to better sample complexity in the DP setting, we believe it is of independent interest in nonsmooth nonconvex optimization in general.

We would like to add that, in addition to the points above, it is indeed true that our work utilizes several well-studied techniques in DP optimization and in NSNC optimization. We believe that the fact that we are able to improve the sample complexity to the extent that we have (beyond what some thought possible), and the clarity in which we properly acknowledge the use of prior work in order to do so, is an advantage of our writing instead of a drawback. Throughout the paper we explain how we modify and build on top of previous algorithms in order to get these improved results, as generally acknowledged by the reviewers.

**Presentation of the tree mechanism**:
 
We thank the reviewers that have noted that the presentation of the tree mechanism can be improved, including spotting typos in the index counters.
While this mechanism is standard in the DP literature and our use of it is relatively straightforward, we will properly revise its introduction and add intuition about its utility and corresponding guarantee for readers who are less familiar with it.

**Efficiency**:

Some reviewers pointed out that, as we discuss in the paper, the improvement in sample complexity is at the expense of increased oracle complexity. We would like to emphasize two related points:
- First-order algorithm with significantly better runtime: In Appendix C, we introduce a first-order algorithm with a substantially reduced oracle complexity (see Remark C.5). We believe the first-order analysis complements our zero-order results, and in particular addresses the discussed issue. We will make sure to further emphasize this in the main text, in which we chose to provide only our zero-order algorithms due to lack of space, and as they directly correspond to the previous work on this subject.

- Trading off sample complexity and runtime: A key advantage of our analysis is that it easily allows trading-off sample vs. oracle complexity, which is controlled by the assignment of $m$ in the algorithm. Indeed, on one hand the oracle complexity clearly grows with $m$, while on the other hand the sensitivity bound we derive has an additional term which decays with $m$ (Lemma 3.3). We choose to assign $m$ large enough in order for this additional term to be negligible, hence reducing the sample complexity as small as possible, but this is not generally required by the analysis which enables trading them off smoothly.
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper presents new single-pass and multi-pass algorithms for differentially private (DP) optimization of nonsmooth nonconvex. Authors provide new state-of-art art sample complexity for both these types of algorithms. Algorithm similar to Zhang et al., 2024, but authors provide a new analysis utilizing the smoothness of the randomly smoothed envelope to improve sensitivity of zeroth order gradient and therefore improve utility trade off of private optimization. However, many reviewers had concerns about presentation and novelty of the techniques used. Paper also do not provide experimental validation of their results.