Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This paper studies the SCO with loss function that satisfies growth conditions in the differential privacy model. Firstly, it considers the empirical risk function and provide an algorithm based on the inverse sensitivity mechanism. Then they show an efficient algorithm and the lower bounds of the problem in the both $\epsilon$ and $(\epsilon, \delta)$-DP models.
main_review: Advantage:
1)They provide a high probability version of the previous algorithm on DP-SCO with general convex loss functions, which might be used to other problems. 
2)They give the first study on DP-SCO with loss functions that satisfy the growth condition and show their upper bounds and lower bounds 
limitations_and_societal_impact: Limitations:

1) Lower bounds only hold for the case where $k\geq 2$ for general dimension case. 
2) As we can see from the result, theoretically, the rate of DP-SCO with growth condition loss is  faster than the general convex loss. However, there is lack of experiments, most of the previous work on SCO with growth condition has experimental studies. So I think there is still improvements.
3)In Algorithm 2, step 10 need to do a projection step onto the set $\mathcal{X}_i$ which is the intersection of the constraint set $\mathcal{X}$ and a ball.  How to get the exact solution of this step. If we can get approximate solution by using such as Dykstra’s algorithm, then how to guarantee the DP and the upper bound? So I don't think it is an efficient algorithm. 

Based on the previous concerns, I tend to reject the paper.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper presents a differentially private mechanism for releasing data and an optimisation algorithm that can use the released data and minimise a convex function. While there are many such algorithms in prior work, the current manuscript provides an algorithm that is adaptive and has convergence rate that improves with the "growth" of the function around the optimum point. Furthermore, the authors present matching lower bounds, which show that their algorithm is close to optimal. 

main_review: *Contribution*
The main contribution of the paper is two-fold: an upper bound which attains the claimed convergence rate and the lower bound. I was unable to read the details about the lower bound in the supplementary material and the description in the main text didn't provide a clear picture to me. So I will focus on the upper bound. The algorithm is simple to describe: In each iteration, the algorithm limits the learning rate, reduces the domain to the neighborhood of the previous point, and repeats multiple iterations of a local optimization procedure. The local optimization procedure uses ERM to minimise an $\ell_2$-regularized version of the function with the regularizer weight updated exponentially in each inner iteration. Just before releasing the point, a Laplace noise is added to the output, which ensures differential privacy. I found it remarkable that the overall algorithm is so simple and can be (perhaps) implemented even in practice. 

I was able to roughly verify the proof, but I couldn't find a crisp high-level description of the algorithm. For instance, what was the role of exponentially decreasing variance in step 9? What is the tradeoff between privacy and convergence rate as a function of the noise parameter chosen in this step?


*Originality*
I found the problem and the result very interesting. The algorithm proposed (algorithms 1,2) are very simple, and somewhat intuitively clear. However, owing to my lack of knowledge about the prior work and lack of time to dig deeper, I was unable to evaluate the contribution in comparison with prior work. Nonetheless, the authors have provided adequate references to prior work, and I think the work is sufficiently novel. 

*Quality and clarity*
The paper is well-written, especially Section 4, and presents results on an important problem. I was a bit lost in Section 3 -- even the statement of Theorem was not very clear since the algorithm $A_{\tt gr-inv}(S)$ was not very clear. But overall the work is of high quality. 


*Significance*
There is broad interest in studying optimization under privacy and similar constraints, and this paper presents a new algorithm for that setting. Even if one ignores the theoretical optimality, the paper provides an interesting algorithm for a practitioner to build on.


limitations_and_societal_impact: Sufficiently addressed.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This work proposes private stochastic convex optimization algorithms that adapt to the growth condition of the objective function. This work also establishes several lower bounds that justify the optimality of the proposed algorithms.
main_review: This paper is well-written and easy-to-follow. The text has a nice flow of ideas. The developed algorithms only require a lower bound on the actual growth constant (probably need to make this requirement clearer in the abstract) and adapt to the true growth condition to improve the privacy rate, which is a significant contribution. The prior work/background is discussed at length throughout the paper and the theorems are attached with proof sketches and insights, which are highly appreciated. I only have some  minor comments as follows.

- I wonder how the growth constant $\kappa$ can be efficiently estimated and how a very rough estimate of $\kappa$ would affect the rate.
- Typos: Line 143, different fonts for A_1 and A_k; In Algorithm 1, at line 10, remove "algorithm"; Line 484, developing.
limitations_and_societal_impact: The authors have adequately addressed the limitations and potential negative societal impact of their work.
review_title: null

Meta-review: Despite some suggestions for additional results that could round out the paper, and presentation suggestions for clarifying the paper's conceptual contributions, I would like to recommend it for acceptance. In particular:

- As an algorithmic paper, providing a new suite of algorithms and complementing them with matching lower bounds tells a complete story. Experiments would be nice, but given the other results I do not believe they are necessary. 

- Concerning Reviewer pyyH's comment about inexact projections, the author's proposed modifications should indeed be implemented carefully. Ensuring that the approximate projections do not (even in the worst-case over the projection algorithm) significantly increase sensitivity affects the privacy guarantee of the final algorithm. So this is an important effect to be accounted for in detail.
Decision: Accept (Poster)