A Unified Theory of Stochastic Proximal Point Methods without Smoothness

The major concern is about the strength of the main result in Theorem 1. While exhibiting contraction rates, the bound there seems non-vanishing with respect to time instance unless $C_1=C_2=0$. As shown in Sectons B.6-B.8 that such a requirement can be fulfilled by variance reduction variants of SPPM, but not by the standard SPPM (with $h_k \equiv 0$) as shown in Section B.2 (which is not surprising due to the fundamental limit of pure stochastic optimization methods). It will be much more interesting if the convergence bound could be made adaptive to standard SPPM with sublinear rate of convergence.

The paper also falls short on the experiment side, where only toy linear regression problems are considered with very limited data scale. Since the SPPM-type algorithms have long been acknowledged to be superior to SGD in non-smooth settings, it is more desirable to test the performances of the proposed algorithms in non-smooth learning tasks such as SVMs with hinge loss.

W1. This paper appears more like a review article, which may not align well with the scope of ICLR. The authors propose seven algorithms for solving differentiable convex problems. However, these algorithms may lack sufficient novelty or clear performance advantages. Readers might still be uncertain about which algorithm is the best choice.

W2. The framework assumes strong convexity, limiting the applicability of the results to problems that are not strongly convex or to non-convex settings.

W3. Algorithm 1 uses a constant, sufficiently small step size, which is rarely practical in real applications. This can introduce additional estimation errors, as highlighted in Theorem 1. In practice, a more effective approach would involve a diminishing step size [1]. The authors should at least discuss the comparison between constant and diminishing step sizes.

W4. The authors claim to use a weaker assumption (without smoothness); however, in their experiment, they still consider a convex least squares problem that satisfies the smoothness assumption. I think the authors should provide an example that satisfies both strong convexity and Assumption 6 but violates the $\nu$-smoothness assumption.

W5. The empirical experiments provided by the authors are limited to strongly convex least squares problems, which may restrict their relevance to practical applications and broader research interests.

References: [1] Davis, D., & Drusvyatskiy, D. Stochastic model-based minimization of weakly convex functions. SIOPT, 2019.

The motivation of this paper is unclear. The assumption without smoothness used in this paper looks not popular.

The main novelty of the paper is the analysis of a unifying algorithm that allows to deal with variance reduced stochastic proximal point methods for an objective function which is only differentiable and strongly convex.

Though the main proofs are partially different from the ones used in the related literature, the idea is not new and it is a generalization of the approach proposed in the papers:

1. E. Gorbunov, F. Hanzely, and P. Richtarik. A unified theory of sgd: Variance reduction, sampling, quantization and coordinate descent.

2. C. Traore, V. Apidopoulos, S. Salzo, and S. Villa. Variance reduction techniques for stochastic proximal point algorithms

So the novelty of the contribution is limited.

In general, there is a tendency in the paper to overstate the contributions, which I did not appreciate. I enclose some examples below:

1. The title claims "A unified theory of stochastic proximal poin methods without smoothness". This is misleading since the analysis is performed only for smooth (differentiable) functions, while nonsmooth ones are not covered. With respect to the existing literature, the authors drop the assumption of Lipschitz continuity of the gradient, but in turn assume that the function is strongly convex.

2. the similarity assumption (Assumption 5) is indeed more general than the one in Khaled and Jin, but since it involves unknown quantities it is very unclear how more general it is in practice. Concrete examples of problems satisfying Assumption 5 but not the one in Khaled and Jin must be provided in order to establish whether this generalization has some kind of impact, or not.

3. the authors often state that a unifying framework for the study of variance reduction techniques is missing, but this is false, since both the papers mentioned above provides such framework (of course, under different assumptions on the objective function). We find out that the proposed framework s is similar to the ones of the papers 1) and 2) above only on line 174, after a long discussion.

4. In the table 1:

The authors show convergence of 8 algorithms (see Table 1). However:

Algorithm 1 is the "universal" one including all the others;

SPPM* and SPPM GC are not interesting from the practical point of view since it requires the gradients at the solution