Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper focuses on the stochastic variant of the projective splitting (PS) algorithm. With a specific focus on monotone inclusion problems, the authors propose a novel separable algorithm featured by the ability to handle multiple constraints and non-smooth regularizers. Compared with similar approaches on variational inequality which is a special case of monotone inclusions, this paper uses a more direct error metric than the restricted gap function. Moreover, although with a slower convergence rate, this paper is the first discussion under the general discontinuous monotone inclusion case. 
main_review: One of the drawbacks of this paper is that the main idea of the algorithm is somehow based on several works in literature. Specifically, the algorithm SPS is a stochastic variant of the recently proposed projective splitting (PS) [Johnstone & Eckstein, 2020b]. Also, the Double Stepsize Extragradient Method (DSEG) [Hsieh et al., 2020] is a special case of SPS when removing all regularizers and constraints. To address this issue, the authors discussed the comparisons of their results with other related works and explains the significance of this work lies in the general applicability of their convergence rate, which is one of the advantages of this work. When compared with the preexisting PS framework, SPS enables computational efficiency on large datasets. When compared with other stochastic methods on special cases of monotone inclusions, SPS enables a strong ability to deal with constraints and regularizations. 

However, the theoretical convergence rate derived in this paper is no better than previous results when constrained to specific problems in other works. While the problem setting is indeed more general, I feel confused about the possible technical difficulties that have caused the $\mathcal{O}(K^{-1/4})$ convergence rate. In [Hsieh et al., 2020] they proved a $1/K^{1/3}$ last iterate convergence rate for the stochastic case, although Theorem 2 seems directly applicable to this setting, the convergence rate is $\mathcal{O}(K^{-1/4})$. From my viewpoint, a good convergence result under the general framework should not only be adaptive to the special cases but also obtain a sharp rate when specified to traditional settings. 

With this consideration, the contribution of this piece of work is a little weak. Moreover, why does the experimental result seem to outperform previous works, when the theory does not? In the first figure the pink FRB-VR curve seems to be descending at the right boundary, is it possible that FRB-VR reaches better solutions under some circumstances?

summary_of_the_review: Overall, the paper is well written with each part of the results clearly explained and well supported. This is a highly interesting piece of work for the SPS problem, but the significance of its contribution is vague to me.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper presents a stochastic variant of the projective splitting family of algorithms for solving monotone inclusion problems. In particular, it explains how the monotone inclusion problems can formulate several popular machine learning tasks like min-max optimization problems, game formulation and variational inequality problems and provides convergence guarantees of the proposed algorithm for solving monotone problems.

main_review: The paper is well written and the main contributions are clear. To the best of my knowledge this is the first paper that provides a stochastic variant of the projected splitting algorithm for solving monotone problems with convergence guarantees.

Below i provide some pointers for further clarification and improved presentation.

I believe that the broader audience of the ML community is not very familiar with the monotone inclusion problems. I would suggest the authors to expand further in the updated version the section 2 of the background on monotone inclusions. Have a proper statement of how these problems can formulate classical problems appearing in ML. For example the authors mentioned maximal operator without a proper definition. they also refer the interested reader to Ryu and Boyd (2016) for proper definitions. I think include all the necessary information in the main paper will be make this work self-contained and could reach broader audience. 

Also i notice that there are few places that the authors could do better job in the presentation. 

1) Add a reference for the equation (4) on first order necessary conditions for solving Nash-equilibrium problems and provide a bit more details of what this means.

2) More details required to be given on how one obtains the update rule (8) by projection step for a half space. What is the close form expression of $\nabla \phi_k$ and how this is computed relative to $\cal{P}$.

3) In theorems 1 and 2 add all assumptions on problem 1. Are the $A_i(z)$ and $B(z)$ monotone and L-Lipschitz? do you assume something beyond this and the noise assumptions for the proof to go through?

4) In the intro the authors mentioned that their algorithm includes the update rule of the algorithms proposed in Hsieh et al. 2020 as special case. However when they SPS method presented no more details are provided. can you elaborate more on this? how the method can be obtained as special case and how the convergence guarantees of the proposed method (Theorem 2) can be used in the setting of Hsieh et al. 2020? 

5) On experiments: I would suggest instead of only comparing running time to also include 3 more plots where the horizontal axis will be computational complexity (how many gradient/operator evaluations are required by each method). this would be a fair comparison as the implementations might vary and not be optimal between the algorithms (this will affect the running time but not the computational complexity).

Some Missing References:
Four recent papers on the convergence analysis of stochastic algorithms for solving stochastic games and stochastic variational inequalities (special cases of monotone problems):

[1] Loizou, Nicolas, Hugo Berard, Alexia Jolicoeur-Martineau, Pascal Vincent, Simon Lacoste-Julien, and Ioannis Mitliagkas. "Stochastic hamiltonian gradient methods for smooth games." In ICML 2020.

[2] Loizou, Nicolas, Hugo Berard, Gauthier Gidel, Ioannis Mitliagkas, and Simon Lacoste-Julien. "Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivity." NeurIPS 2021 (to appear).

[3] Mishchenko, Konstantin, Dmitry Kovalev, Egor Shulgin, Peter Richtárik, and Yura Malitsky. "Revisiting stochastic extragradient." In AISTATS 2020.

[4] Li, Chris Junchi, Yaodong Yu, Nicolas Loizou, Gauthier Gidel, Yi Ma, Nicolas Le Roux, and Michael I. Jordan. "On the convergence of stochastic extragradient for bilinear games with restarted iteration averaging." arXiv preprint arXiv:2107.00464 (2021).

summary_of_the_review: As i mentioned in my main review i find that the paper is well written and the main contributions are clear. To the best of my knowledge this is the first paper that provides a stochastic variant of the projected splitting algorithm for solving monotone problems with convergence guarantees.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This manuscript proposes a stochastic algorithm for monotone inclusion with more than two operators, where one is Lipschitz and the rest are maximally monotone and possibly set-valued.  Under standard noise conditions for a stochastic estimation for the Lipschitz operator, the authors showed almost sure convergence for step sizes satisfying some mild conditions, and provided convergence rates of O(k^{-1/4}) for an optimality measure if the number k is pre-specified.
main_review: This manuscript is ambitious in tackling the problem of multiple operators with a stochastic oracle. This can be seen as a natural generalization of stochastic gradient algorithms for more than one regularizers to the setting monotone inclusion, and can find potential applications in min-max problems and so on.  The motivation is more or less just replacing the deterministic oracle in Johnstone & Eckstein (2020b) with a stochastic one and applying a different stepsize scheduling, but surely this is of importance in large-scale machine learning applications such that accessing all data points could be prohibitively expensive.  However, with the given stepsize scheduling, although being able to achieve optimality asymptotically by driving a certain proxy measure to  zero, the proposed algorithm does not honor the specific structure induced by the resolvents, and therefore can fail to achieve the original purpose of adding multiple operators.

My detailed comments are as follows.

1. In comparison with the product space reformulation, a clear issue is that multiple existing approaches generate iterates that honor the structure induced by the resolvents of the maximally monotone operators because the final step is the resolvent, while the proposed algorithm does not. In the context of optimization, this means that the specific structure (like sparsity, boundedness, low rank) enforced by the proximal operators will not be kept by the proposed algorithm. This is problematic from the application point of view (although probably not easily visible from the monotone inclusion angle), as usually the regularizers are added exactly because the users need specific structures in the final output.

2. The setting is interesting, but it looks like the authors did not really find a relevant application in practice and therefore needed to invent one of their own and therefore ignored a key part of such a regularizer. As mentioned above, addition of a regularization term is usually for the purpose to enforce or promote a desired structure in the solution, and for the case of the L1 norm, the purpose is usually sparsity, as mentioned by the authors. Therefore, an important aspect to show is the sparsity level and how it changes with time for these algorithms being compared. I can actually imagine from the algorithm forms that probably the proposed algorithm does not generate any sparsity, while Tseng's method, FRB, and FRB-VR will provide stable sparsity levels. This greatly reduces the usefulness of the proposed algorithm.

3. Given the slow convergence and the issue of not honoring the structure from the resolvents, I wonder if one could just apply (stochastic) subgradient methods or ideas similar to that, at least to a narrower range of problems that still include most the interesting cases. In such a case, likely the convergence speed will not be too different, thus from a theoretical angle, the proposed algorithm is probably not of very great contribution.

4. Another concern I have with the experiment is that it seems like the proposed algorithm is fast only in the beginning, and after reaching a mild precision, the optimality measure stalls. From the result on real-sim, it seems like that deterministic algorithms are superior and the proposed method is beneficial only at the beginning for going through more iterations within the same amount of time. If the algorithm is more useful in large-scale problems, for presentation purposes, the authors should indeed present more results on larger datasets and probably skip small scale ones like the one for real-sim.

5. Moreover, although the authors argued in the appendix that the product space formulation can lead to a much smaller step size that slows the convergence, it does not seem so in the comparison between deterministic PS and FRB or Tseng's method. It seems like that the deterministic PS is faster only in one case, thus diminishing the claimed contributions.

6. Judging from the tickers, it also seems to me that some of the advantages of the proposed algorithms is actually from the better time efficiency, in comparison with other methods. (Interestingly, usually one would expect deterministic methods to run faster because of the memory access pattern and less for-loops to be called, and the results presented are quite counterintuitive to me.) If the comparison is in terms of epochs (so that implementation difference can be excluded), I wonder if the outcome would be much different.

7. I also find the organization and detailed description quite unsatisfactory. It seems that the length limit of the main text of ICLR is too short for this manuscript to fully articulate, and I'd therefore suggest the authors to consider a journal or a different conference with a longer length limit (such as ICML or AISTATS that uses a two-column format). In particular, the authors spent quite a length in introducing fundamentals that might not be directly relevant to the rest parts of the main text and are actually well-known to most readers interested in this topic (those who decided to check the paper after viewing the title and abstract). On the other hand, key issues like how existing algorithms work, what the experiment is about, and how the residuals are estimated are all skipped in the main text. This essentially requires everyone to go back and forth between the appendices and the main text, which kind of violates the meaning of the appendices.
In essence, appendices are for things that do not affect the reader's grasp of the whole story, but clearly the authors are simply treating the appendices as places to implicitly increase the length of the main text and the readers are unable to skip any of the appendices without losing understanding of the main idea.

summary_of_the_review: The problem considered is of interest, but the proposed algorithm does not fully address the need of the applications. The manuscript presentation also has a great room for improvement. The current organization seems to be incomplete given the length of the main paper.

After reading the revision and the responses of the authors, and discussing with the authors, my recommendation moves to weak rejection. The idea is indeed interesting, but there are still unclear parts in the text and organization, and the motivation for the algorithm seems more like finding extensions for an existing work, instead of a real need for the considered problem.
review_title: null

Meta-review: The submission considers a stochastic variant of the projective splitting algorithm, with a focus on monotone inclusion problems, and it proposes a novel separable algorithm with the ability to handle multiple constraints and non-smooth regularizers.  All reviewers felt that there were merits to the submission and that the submission was borderline.  Public and non-public discussion concluded that the paper would be of greater value to the community if the suggestions of the reviewers and related issues were addressed.
Decision: Reject