Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper studied the problem of differentially private stochastic optimization. The authors establish new results for the convex generalized linear model and new algorithms for nonconvex optimization. The main contribution of the current paper is the faster algorithms and stronger results for solving the nonsmooth DP-SCO in the case of generalized linear loss.
main_review: I think the new algorithms are interesting and the utility and convergence results seem to be strong. However, my major concerns are about the algorithms and results in nonconvex setting, and I summarize it as follows:
1. It is unclear the novelty of the proposed Private Frank-Wolfe algorithm. It seems to be a straightforward application of the variance reduced stochastic Frank-Wolfe algorithm to the private setting. The authors should clarify the novelty.
2. What are the main challenges for analyzing your proposed Private Frank-Wolfe algorithm? This could help readers understand the contributions of the paper.
3. The proposed Private Frank-Wolfe algorithm requires a very large batch at each iteration, suggesting that the proposed algorithm will have very bad scalability.
4. The utility guarantee of the proposed algorithm is worse than existing work. For example, in the l_2 setting, the utility guarantee is worse than the result in [ZCH+20].
5. There are no experiments to validate the effectiveness of the proposed methods in the current paper.
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: The paper considers differential private stochastic optimization in a number of convex and non-convex settings. Their contributions are as follows:

1. Faster (nearly linear time) algorithm for $\ell_2$ non-smooth convex generalized linear losses (GLLs).

2. Algorithm with smaller error (nearly dimension independent) in $\ell_1$ non-smooth convex GLLs.

3. New algorithms for smooth non-convex and non-smooth weakly convex stochastic optimization in non-Euclidean ($\ell_p$) settings.
main_review: 1. The paper makes many novel and important contributions to the field of differentially private stochastic optimization. Importantly, as mentioned in the paper, many results in non-Euclidean non-convex settings are novel even without privacy constraints. 

2. The writing and presentation is very good and to the point. Also, the authors try to give the necessary background (in the Appendix) and explain many subtleties as required.

3. The first result is a nearly-linear time algorithm for non-smooth GLLs. This contributes to a recent line of work which try to devise fast algorithms for DP-SCO. This result solves a special case of the non-smooth convex landscape. I think this result has an interesting consequence: *most* known high-dimensional oracle complexity lower bound instances in optimization are GLLs. So this result tells us that if it is indeed the case that non-smooth DP-SCO is harder than SCO, then we need to look at *new* hard instances.

4. The smooth non-convex setting considers a polyhedral constrained setup even in standard $\ell_2$ setting. I think that it is more natural/standard in literature to consider an $\ell_2$ ball (or a simple convex set with an easy oracle-access projection). I wonder why did the authors not consider the later? Also, why not consider the unconstrained setup, which would also enable comparison with some of the previous work?

5. On a related note, the non-smooth weakly convex part is not in the polyhedral constraint setting. So, do we need to access to a projection oracle for the claimed guarantees in Theorem 16? If yes, then I could not find it mentioned in this section. If no, then why is it so?

6. **Coherence**: Since the authors make many contributions, one downside is that parts of the paper feel disconnected from each other -- it feels like a collection of results the authors were able to obtain in various settings. For example: GLLs part of the paper has little to do with the non-convex setting (in terms of goal/techniques). This, lots of settings and results, also led to authors' being able to put only one algorithm description (in full, as a pseudo-code) in the main paper, and the rest is deferred to the appendix.
 
7. **Tightness of rates**: The authors only provide upper bounds for the settings they consider. Is there a way (perhaps from previous works?) to assess how sharp are the attained rates?

limitations_and_societal_impact: No direct societal impact.
review_title: null

final_score: rating: 4: Ok but not good enough - rejection
review_content: summary: The paper studies three different (slightly related) problems in private optimization: 1. convex private optimization for non-smooth functions, 2. non-convex smooth private optimization, and 3. non-convex non-smooth private optimization. The authors study each of these settings separately, developing different algorithms for each that has certain advantages. The nature of improvement is different in each setting: in the first, the author claim to improve runtime (achieving linear runtime) while maintaining statistical utility, in the second, (for ell_2 geometry) the authors achieve worse rates while getting better runtime, and in the third setting the authors consider the setting of weakly-convex non-smooth functions (which I think was not studied before in the privacy literature) and provide private algorithms with certain convergence guarantees.
main_review: I think the results are mostly incremental, based on standard techniques with limited novelty (see below). Moreover, the different problems (settings) in the paper are only slightly related, making the story of the paper less coherent: basically a list of different results that the author prove in different settings. Overall, I don't think the paper has sufficient novelty and new results for acceptance.


1. Contribution for non-smooth GLL: while it is true that existing algorithms from [BFTT19, FKT20] take super-linear time for general non-smooth convex functions, the main bottleneck there is smoothening general functions which takes linear time. However, for the setting of GLL that the authors consider, it is immediate to see that existing algorithms give nearly linear time algorithms as smoothening GLLs (or finding the gradient of Moreau envelope) is quite simple as it is basically a 1-dimensional problem. So this result is basically a direct corollary of previous work.

2. Comments on smooth non-convex setting:
     
    2.1 The results for this section are based on private implementation of variance-reduced Frank-Wolfe algorithm similarly to the 
    existing private algorithm for the convex setting [AFKT21, BGN21]. The algorithm in this paper doesn't use privacy amplification by 
    sub-sampling (as done in [AFKT21]) hence suggesting their algorithm may not be optimal. 

    2.2 The author conjecture (line 78) that their algorithm has tight bounds for the ell_1 setting for linear time algorithms. Is there 
    any evidence for this prediction? Following my previous comment (2.1), I think it may be possible to improve the rates using better 
    privacy accounting as done in [AFKT21].

    2.3 Overall the authors overuse the term: "we provide the first algorithm for ...".  One such example is line 76 where the authors 
    say "we provide the first linear time private algorithms". There are two problems here. First, this sentence doesn't say anything 
    about the utility of the algorithm and so is not very informative. Secondly, the linear-time algorithm doesn't give optimal bounds 
    as [ZCH+20]. While the algorithm of [ZCH+20] takes n^2/\sqrt{d} time, we can run it for linear number of steps if we require a 
    linear time algorithm. The authors should compare their bound to the bound obtained by linear-time version of [ZCH+20].


3. Non-smooth weakly-convex: the authors should try to explain the strength of the bounds achieved in this section. Currently these are worse than the smooth setting which suggest they may not be optimal as the bounds are usually similar in ell_2 case for both smooth and non-smooth convex case. Moreover, the algorithm is a simple application of existing techniques. 


More comments:

1. I think it would be useful to add the dependence on epsilon in the bounds of the abstract as currently these are stated only for constant epsilon and makes it slightly harder to understand the privacy cost.

2. The term GLM (generalized linear models) is more common than GLL.


limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This work studies differentially private stochastic optimization and proposes several new algorithms for convex non-smooth generalized linear losses (GLL) / general non-convex smooth objectives / weakly convex non-smooth objectives equipped with Euclidean / non-Euclidean geometry. 
main_review: This work proposes several new algorithms that outperform the existing methods in differentially private stochastic optimization. The authors leverage techniques such as Moreau envelop smoothing for GLL and variance-reduced stochastic Frank-Wolfe to build several linear-time algorithms in the DP setting. The authors also make the first attempt to devise algorithms for weakly convex non-smooth objectives in the DP setting. The contributions are significant and the authors are rather careful in presenting the theoretical results, which is highly appreciated. The paper is well-written but with a lot of proposed algorithms and technical details deferred to the appendix, the results remain hard to parse. Perhaps it suggests that a conference with a small page limit is not the best venue?
limitations_and_societal_impact: The authors have adequately addressed the limitations and potential negative societal impact of their work.
review_title: null

Meta-review: This paper generated a lot of discussion among reviewers. The authors would be advised to improve the clarity of the discussion in order to better integrate their diverse-seeming results into one story. Please also include the improvements suggested in discussions between the reviewers and the authors.

Decision: Accept (Poster)