Venue: NeurIPS 2022 Conference

Reviews:

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 considers the problem of stochastic convex optimization with linear constraints. They proposed the so-called loopless projected stochastic approximation (LPSA) that randomly performs or skip the project step at each iteration. The authors provide the non-asymptotic convergence rate of the resulting algorithms. They also study the asymptotic behaviors of the algorithms under different conditions and parameters of the algorithm. Moreover, their asymptotic analysis provides insights of the effect of projection frequency on the convergence rates.

strengths_and_weaknesses: The paper is well written and technically strong. Analyzing asymptotic convergence rate of stochastic approximation algorithms with projection is generally difficult because of the discontinuous dynamics (which people usually resort to stochastic inclusion for establishing convergence). I did not check the proofs in the appendix, but outlines of proofs seems plausible. 
The results they obtained reveal the relationship between convergence rate and the tuning parameter that controls projection frequency, which is useful in practice.


Weakness:
Currently, the experiment focuses on validating convergence rate of the proposed algorithm. Since the paper consider stochastic optimization with projection. It could help readers understand the effect of loopless projection better by providing plots of number of projections or computational complexity for each parameter setting, along with the MSE figure.

questions: The paper proposed a loopless stochastic approximation algorithm. The main results are obtained for stochastic convex optimization. For general stochastic approximation, the mean field is not necessary a gradient function. I wonder would the proofs of Theorem 3.3 and Theorem 3.4 be easily adapted to this case?

limitations: Yes
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper proposes a jump diffusion perspective for a loopless variant of stochastic approximation schemes, essentially replacing the loop-length ratios by flipping a coin at each time step and performing projections accordingly. The main result is that there is a phase transition depending on the parameter , which controls the projection rate. The authors prove that in the frequent projection regime (), the asymptotic behavior of the algorithm is close to a diffusion, while in the occasional projection regime the asymptotic behavior goes to a discontinuous jump diffusion.

strengths_and_weaknesses: 
Strength: The analysis technique is fairly straightforward: The proof goes by decomposing the target sequences into a first-order term and then high-order terms that vanish in the long run. This technique is standard in stochastic approximation but seems adequate for the authors' purposes.

Weakness: The analysis relies heavily on strong convexity and does not seem to easily generalize to the non-strongly convex case; the latter, however, is of higher interest.

questions: Since I'm not an expert in the field, I find the constant drift outcome to be counterintuitive. Usually in stochastic approximation, the algorithms converge to either the gradient flow or, in the stochastic case, Langevin diffusion. Is there any intuition why we should expect a constant drift for both the frequent and occasionally projection regimes?

limitations: In my opinion, the most significant limitation of the work is the assumption of strong convexity; in the non-federated setting, we know that strong convexity is not necessary; see [Kushner-Yin]. It would therefore be great if the authors can point out potential avenues to improving/relaxing these restrictive assumptions.

[Kushner-Yin] Stochastic Approximation and Recursive Algorithms and Applications
review_title: null

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: This paper analyzes the performance of projected SGD in solving constrained optimization problems. It shows that a bias-variance tradeoff appears in the choice of the frequency of the projection. This bias-variance tradeoff is shown is two ways:
- a non-asymptotic analysis
- an asymptotic description with continuous-time stochastic processes. 
Understanding this bias-variance tradeoff enables to use the optimal communication rate in federated learning. 
strengths_and_weaknesses: The continuous-time perspective provides an elegant perspective on the choice of the projection frequency: either we have convergence to a diffusion process (variance dominates) or to a process with Poisson jumps (bias dominates). 
In general, this paper is well-written, elegant and rigorous. 
I do not master all the stochastic approximation results used in this paper. However, the authors introduce well the necessary tools, and provide all necessary references. 
It seems that the techniques used in this paper could be used to understand other stochastic approximation algorithms. 
questions: Minor comments:
(*) l.782: Can you explain "entry-wise linear interpolation"?
(*) L.780, 4th equality: why is there no more projection on the last term?
(*) eq. (16): should it be $v_{n+1}$ on the r.h.s.?
(*) l.58: did you mean $p_n$ instead of $\beta_n$?
(*) Could you explain (or give a ref) for the sentence l.185-186?
(*) l.232: should it be $-Y_{t-}$ instead of $-Y_{t}$?
limitations: I have none.
review_title: null

Meta-review: metareview: All the reviewers agreed that the paper is novel, interesting, and the results are mathematically rigorous. Some of the concerns have been aptly addressed by the authors during the rebuttal period. I congratulate the authors for the nice work and recommend an acceptance. 
confidence: Certain
Decision: Accept