Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper proposes a framework for DP-SCO and DP-SMO, such that any non-private algorithm with a certain convergence guarantee can be plugged in. For smooth DP-SCO, it achieves the first near optimal guarantee without for algorithms apart from SGD; for smooth DP-SMO, it gives the first near linear time private algorithm.
strengths_and_weaknesses: The paper provides the first near linear bound for DP-SMO.
The paper provides an algorithm-independent framework, thus extending the near linear time guarantee to algorithms other than DP-SGD.
questions: It all looks good to me.
limitations: N/A
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: The paper studies DP stochastic convex optimization (SCO) and stochastic minmax optimization (SMO). They provide near-linear time algorithms under (strong) convexity assumptions that attain optimal or near-optimal rates. 
strengths_and_weaknesses: Strengths: 

-The phased output perturbation idea is nice and simple, but apparently also effective. 

-Apparently improved (faster) algorithms for convex-concave and SC-SC min-max are the main contributions. 

Weaknesses (and borderline strengths/contributions): 

-Missing related work: 

Theorem 3.3 (excess risk bounds with black box "bring your own algorithm" output perturbation for strongly convex loss) seems to have already been provided in prior work: see Corollary 3.4 and Corollary 4.2 of https://arxiv.org/pdf/2102.04704.pdf. The idea of "bring your own algorithm" output perturbation is also a theme in this work and should be credited. 

-Theorem 3.4 is a somewhere between a good contribution and a marginal contribution: it is essentially optimal excess risk and near-linear time: existing works (e.g. FKT20) give optimal excess risk in linear time with some mild smoothness restrictions that this excess risk bound removes, but smoothness is still required here. Furthermore, a restriction on the smoothness parameter seems to be required here in order to be linear time. Also, optimal algorithms for non-smooth losses require a bit more computation (e.g. $n^{11/8}$ is the smallest gradient complexity I believe) vs. Theorem 3.4 is $n + \sqrt{n} \ell$. On a related note, the units in the gradient complexity expression are not matching, as $\ell$ is not unit-free. What is the precise unit-free gradient complexity (e.g. with SVRG)? 

-**Discussion of optimality of the min-max bounds seems to be lacking. Lower bound for convex-concave was provided in Boob & Guzman, but I'm not sure its obvious that the the SC-SC lower bound follows immediately from SC SCO lower bound? It would be great to complete Table 1 with lower bounds. 

-Some imprecision/slight overclaiming of "optimal"  and "linear time" in places where this should be qualified with "near" (e.g. due to dependence on condition number). Also, "smooth" should be included  for emphasis whenever the problem class is smooth--e.g. Section 3.2 heading should be "near-linear time algorithms for smooth convex functions" since I don't think you are claiming near-linear time algorithms for general (non-smooth) convex functions. 
questions: I think most of my questions were asked in the above. Two more below:

-Could you elaborate on the reason for the asymmetry in the x and y regularizers in Algorithm 4? 

-You claim in Remark 2 that smoothness is not necessary for the utility bound to hold. Can you explain why? Also, what gradient complexity would be achievable without smoothness? 
limitations: N/A
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: The paper provides a general framework for solving smooth DP-SMO and smooth DP-SCO problems by utilizing the (phased) output perturbation mechanism, so there is no need for modifying the algorithms themself to have a DP result.
strengths_and_weaknesses: Strengths: theoretically sounded and working for a wide range of objective functions.

Weaknesses: 1. Lack of numerical results. The reviewer is curious about how to apply it to some popular algorithms and their performance compared with existing DP algorithms.
2. The presentation of this paper is hard to follow for the reviewer.
questions: 1. Shouldn't the input of the proposed algorithms (i.e., Algorithm 1) include the parameter $\mu$?

2. How could one decide $L$ in Algorithm 1 in practice? 


limitations: Yes.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper is one more link in the ever growing chain of results on DP ERM-based optimization algorithms, which dates all the way back to CMT08 and BST14. In this paper, the authors up the ante on two main axes, as follows. First, rather than looking at classic minimization problem, they deal with a min-max problem (a setting that does arise in practice, such as adversarial GANs), see Eqs. (1)-(2). Second, rather than giving their own algo. for such an optimization, the authors assume some off-the-shelf algorithm for which they can apply output perturbation since - by assumption - the optimization function is smooth and stongly-convex/strong-concave, a setting where an approximated loss must imply approximated models. Lastly, the authors achieve near-optimal loss in near-linear time ("near"=up to poly-log factors).

strengths_and_weaknesses: Ultimately this is an interesting paper that makes solid progress on one of the more canonical and current problems (or venues) studied in the DP-ML literature. While the novelty factor isn't that great (the assumption of a loss-function which is strongly-convex strong-concave and smooth does imply the result) I still believe it is a problem worth mentioning in NeurIPS, in particular as it may "lead the way" for min-max DP-optimization algorithms that require less on the loss-function.

Strengths: well written, solid progress on a very relevant problem.
Weaknesses: rather strong assumption on the loss-function
questions: The runtime complexity's dependency on \epsilon for DP-SGDA is cited correctly?
limitations: I wish they had a line saying "while having the loss-function strongly-convex / strongly-concave and smooth, we make rather a strong assumption, but this is ok as this is the first paper to ..."
review_title: null

Meta-review: metareview: This work studies minimax optimization for convex-concave objective. It studies the population loss version of this question and shows linear time differentially private algorithms for this problem that achieve the optimal privacy utility trade-off. The algorithm is based on the phased ERM approach.
The reviewers were in agreement that this problem is of interest and the paper makes a significant improvement on previous work to be interesting.  I would recommend acceptance.
confidence: Certain
Decision: Accept