Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: This paper proposes to extend the three operator splitting (TOS) algorithm via stochastic gradients, subgradients and adaptive step-sizes respectively. Convergence rates and numerical experiments of these extensions are provided. 
main_review: Originality: 

The application of subgradients in a TOS scheme seems to be original to me. The use of stochastic gradients in a TOS scheme is well mentioned in Section 2 of the paper. 


Quality and significance: 

The quality of this paper is above average. I also believe that the proposed extensions are significant to study. 


Clarity: 

I think some statements in the paper require clarifications as they are misleading. For instance, in the abstract, point (ii) has led me to think that the authors are going to replace the functions which we evaluate their proximity operators on (i.e., $g$ and $h$) by their subgradients. But after looking into the paper, the authors are replacing $\nabla f$ by $\partial f$ instead, where the smooth function $f$ in the original TOS becomes nonsmooth. The subsection titles of numerical experiments are also misleading: these problems are also nonsmooth because of the nonsmooth regularizers. 

Typos: 
* Line 16: $\mathbb{R}\cup\lbrace +\infty\rbrace$ instead of $\mathbb{R}\cap\lbrace +\infty\rbrace$ 
* Line 120: *splitting* instead of slitting
* Line 143: redundant *an*
* Line 233: $X$ instead of X
* Line 284: 93% instead of %93 

**Post-rebuttal:** 
I have read the author response and decided to keep my evaluation unchanged, given that the authors agree to clarify the misleading notions in the original manuscript. 
limitations_and_societal_impact: While the author have discussed the limitations of their work, I do expect numerical experiments to illustrate the theoretical results in Section 5.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper provides an extension of the Three Operator Splitting methods for composite optimization, of the form $f + g + h$. Previous work assumed $f$ to be smooth. This work tackles two cases: 1) the case where $f$ is non-smooth, and the case where additionally, only a stochastic estimator of the (sub)gradient of $f$ is available. It can be seen as an extension of (Yurtsever et al 2018) in the non-smooth, non-strongly convex case.
The paper provides a theoretical worst-case analysis of convergence, and gives non-asymptotic rates for these two cases. It also proposes an analyses an adaptive variant, where step size depends on the previous observed subgradient magnitudes, a la AdaGrad. It provides experimental validation of the method on a non-smooth problem, and on a non-convex non-smooth problem.
main_review: The paper is clear and well written. Extensions of the TOS method in the non-smooth setting should be interesting to the community.

Additional experiments in the 1st setting (robust recovery) in the stochastic setting (large images + subsampling pixels to compute the [sub]gradients) would be interesting to evaluate scalability of the stochastic method vs non-stochastic.

Question on the Image recovery experiment: I see in the code that the loss is not the squared loss for the L2 case. Why is that? Since the squared L2 is strongly convex, and the two problems are equivalent, the squared loss would always be used in practice. Also, it allows to avoid numerical instability due to dividing by the norm of $\mathcal A(x) - y$. 

Question on ResNet experiments: what sparsity structure did you try to enforce in your preliminary experiments ? Using individual convolutional filters as groups for the group LASSO (and not penalizing/regularizing the fully connected layer) may be beneficial in this context. Also, keeping some type of L2 regularization (weight decay) should also be helpful. I would be greatly interested in these results.

The latest commit on Lasagne was in 2015... Perhaps consider writing the AdapTOS optimizer in PyTorch, Jax or Tensorflow to promote its usage, and reproducibility?

Comments on the form:
Typo: line 115 unnecessary "a" 
Typo: line 202: we believe this to be a limitation...
limitations_and_societal_impact: N/A
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper considers three extension of the three operator splitting (TOS) algorithm: sub-gradient instead of gradient, stochastic  gradient and adaptive step-sizes. Convergence rates are established for each extension. 

main_review: First of all, the paper missed a recent work “Three Operator Splitting with a Nonconvex Loss Function, A. Yurtsever et al 2021’’ which studied TOS in the non-convex setting and with stochastic gradient. For example, problem of type (15) was studied in this work.

Due to the above missing reference, the main strength of the paper is TOS with sub-gradient. However the proposed algorithm is not what I expected when reading lines 34-36 of the introduction. It appears to me that the authors would replace the computation of one prox-operator with sub-gradient descent. However, the proposed algorithm still needs computing two prox-operators, and gradient descent part is relaxed. 

The convergence results of the paper match existing result of sub-gradient descent and stochastic gradient.

The proposed AdapTOS is difficult to understand, as the step-size is motivated by adaptive stochastic gradient method, and there is no randomness here.  For problem (27) considered in the numerical experiments, it would be great if the authors comparing the proposed with other methods where no sub-gradient descent, such as ADMM type methods or Primal-Dual splitting. 

limitations_and_societal_impact: See above for limitations and no negative societal impact.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: In this paper, the authors analyze a variant of the classical three operator splitting algorithm where the smooth gradient (or co-coercive operator) is replaced by a subgradient (which is only a  monotone operator). This enables the minimization of the sum of three functions, two of which have explicit proximity operators and one is accessed through a subgradient. 
main_review: First of all, I would say that the main reason this case has not been covered previously is that with a subgradient, the TOS operator (ie (2) with u as in Lemma 1) is no longer firmly non-expansive which means that most of the usual operator theory for (Fejér monotonous) iterates convergence breaks down. If my intuition is correct maybe a sentence about that would be interesting for the reader.

* I understand the need to have a generic u_t in algorithm 1 but could you give the reader the intuition that it should be a gradient of f (in original TOS) or something related (maybe as a comment).

* In the proof of Lemma 1, you need Assumption 1 (for S.3 to hold) but it is not explicitly put in the lemma or the other theorems. Should this be a blanket assumption? (eg. in Theorem 1, you will need Lemma 1 but only assumption is put explicitly)


* I am a bit troubled by the formulation of Lemma 1 since TOS is not R^n to R^n but takes two values. Replacing u directly by its (set-)value and consider the resulting set-valued operator would be in line with standard monotone operator theory. (and the fact that it may not be single valued would show the difference with the usual case).

* I find Theorem 1 slightly deceiving as x_T is present in h while z_T is present in the other, I would be nice to have a warning. It would also be nice to have a sketch of the proof. Basically, I think that Supp. C builds on operator theory to get boundedness which is the only possible out come without smothness of the gradient and then in D, you explicitly use the functions to get a functional convergence.

* I also missed at first read that the adaptive part only focused on indicator functions, maybe the first sentence of Sec 5 should be emphasized. Also, what are the technical limitations that prevent from considering proximity operators there?

* In the numerical experiments, I am a bit dubious about the the smooth case of Figure 1. You use AdapTOS for smooth problems (except the sparse low-rank) which is outside of the theoretical framework right? Also, the LS version seem to perform worse than the vanilla counterparts in some experiments is that normal? In the nonsmooth Sparse Low Rank case, I would have expected to see also the policy of Theorem 1 for comparison.

Minor comments:
* line 16:  R \cap \{\infty\} should be  R \cup \{\infty\}
* Caption of Fig. 1  "Lipchitz constant the regularizer" ?
* in S.29, you have \gamma but above, line 80, you have gamma_t

Post-rebuttal: Despite some limitations and clarifications to be made, the paper has merits.
limitations_and_societal_impact: n/a
review_title: null

Meta-review: All reviewers agree that this paper is worthy of publication. Although some reviewers had initial remarks regarding missing reference, the authors have provided a strong rebuttal that addressed these concerns.

I encourage the authors to take into account the feedback provided by the reviewers, in particular:

  * Reviewers 7qvs, ofGn and eqKr make excellent clarification suggestions on motivation and presentation.

   * Reviewer fPkS suggests some improvements to the experimental section.

   * Reviewer eqKr raises the issue of an important missing reference. This review also raises issues regarding clarity, motivation and comparison with other methods.
Decision: Accept (Poster)