A Unified Theory of Stochastic Proximal Point Methods without Smoothness
Stochastic optimization;empirical risk minimization;stochastic proximal point algorithm;variance reduction;sampling
Yes
No ethics review needed.
My main consideration is the importance of the Assumptions 5 and 6. Although these assumptions is more general than smooth condition, it is unclear whether they are useful in real-applications. It looks that Assumptions 5 and 6 are proposed only for convergence analysis.
1. Can you provide some applications which satisfy Assumption 5 or 6 and but do not hold smoothness?
2. The experiments on linear regression look not very relevant to this paper, since it can be solved by the algorithms based on smoothness assumption.
The presentation is good. The authors provide solid theoretical analysis to support the proposed framework.
This paper provided a framework for analyzing the stochastic proximal point methods for solving strongly convex optimization problem without smoothness. It leads to several new algorithm by introducing the techniques of sampling strategies, variance-reduction and correction.
The motivation of this paper is unclear. The assumption without smoothness used in this paper looks not popular.
Yes
No ethics review needed.
**Q1.** Is the combination of Assumption 6 and strong convexity a weaker condition than the $\nu$-smooth condition? If so, could you provide an example?

**Q2.** Could the proposed SPPM-LC framework be extended or adapted for non-convex optimization, such as weakly convex optimization?

**Q3.** How do the proposed algorithms compare with the proximal point method in [1], which is applicable to weakly convex functions using a diminishing step size?

**References:**
[1] Davis, D., & Drusvyatskiy, D. Stochastic model-based minimization of weakly convex functions. *SIOPT*, 2019.
**S1:** This paper is generally well-written and easy to follow. It is well-grounded in theoretical analysis, establishing convergence guarantees without relying on smoothness assumptions.

**S2:** It unifies multiple SPPM variants under a single theoretical framework, making it easier to understand the relationships and convergence behavior across methods.

**S3:** The development of new SPPM variants, such as SPPM with Nonuniform Sampling and SPPM with Arbitrary Sampling, enriches the field by expanding the applicability of SPPM.
The paper presents a unified theoretical framework for stochastic proximal point methods (SPPM) applied to problems that do not require smoothness assumptions but do rely on a strong convexity assumption.

The paper establishes a single convergence theorem applicable to multiple SPPM variants, providing the robust convergence behavior of these methods.

They propose a general algorithm called SPPM-LC (SPPM with Learned Correction) and integrates techniques such as variance reduction and arbitrary sampling through a flexible correction vector. Several new SPPM variants have been considered.

Experiments have been conducted to show some inherent properties of these approaches.
**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.
Yes
No ethics review needed.
Can the main result in Theorem 1 be strengthened to interpolate between the sublinear rate of the standard SPPMs and the linear rate of SPPMs with gradient correction or variance reduction?
The proposed universal SPPM algorithmic framework sounds interesting, and novel as far as the reviewer knows about. The convergence analysis is generally well presented, with sufficient details provided in  a clear and neat way in the appendix sections.
This paper presents a unified algorithmic framework of stochastic proximal point methods that encapsulates several existing SPPM-style algorithms, and some new extensions with variance reduction and arbitrary sampling as well. The proposed universal algorithm comes with a convergence analysis under relatively mild conditions, without imposing individual smoothness assumption on loss functions. A preliminary numerical study is carried out to demonstrate the performance of newly introduced algorithms on some toy linear regression tasks.
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.
@inproceedings{
anonymous2024a,
title={A Unified Theory of Stochastic Proximal Point Methods without Smoothness},
author={Anonymous},
booktitle={Submitted to The Thirteenth International Conference on Learning Representations},
year={2024},
url={https://openreview.net/forum?id=AqHbMV28o7},
note={under review}
}
This paper presents a comprehensive analysis of a broad range of variations of the stochastic proximal point method (SPPM). Proximal point methods have attracted considerable interest owing to their numerical stability and robustness against imperfect tuning, a trait not shared by the dominant stochastic gradient descent (SGD) algorithm. A framework of assumptions that we introduce encompasses methods employing techniques such as variance reduction and arbitrary sampling. A cornerstone of our general theoretical approach is a parametric assumption on the iterates, correction and control vectors. We establish a single theorem that ensures linear convergence under this assumption and $\mu$-strong convexity of the loss function, and without the need to invoke smoothness. This integral theorem reinstates best known complexity and convergence guarantees for several existing methods, which demonstrates the robustness of our approach. We expand our study by developing three new variants of SPPM, and through numerical experiments elucidate various properties inherent to them.
I certify that there is no URL (e.g., github page) that could be used to find authors’ identity.
I acknowledge that I and all co-authors of this work have read and commit to adhering to the ICLR Code of Ethics.
Stochastic optimization empirical risk minimization stochastic proximal point algorithm variance reduction sampling
I certify that there is no acknowledgement section in this submission for double blind review.
/pdf/5ed07959fdb12c9bb6739c413e836cfcb2ec7797.pdf
optimization
I understand the reciprocal reviewing requirement as described on https://iclr.cc/Conferences/2025/CallForPapers. If none of the authors are registered as a reviewer, it may result in a desk rejection at the discretion of the program chairs. To request an exception, please complete this form at https://forms.gle/Huojr6VjkFxiQsUp6.
I certify that this submission complies with the submission instructions as described on https://iclr.cc/Conferences/2025/AuthorGuide.
A Unified Theory of Stochastic Proximal Point Methods without Smoothness
ICLR 2025 Conference Submission
ICLR.cc/2025/Conference/Submission