A Tight Convergence Analysis of Inexact Stochastic Proximal Point Algorithm for Stochastic Composite Optimization Problems
Authors: Shulan Zhu
Chenglong Bao
Defeng Sun
Yancheng Yuan
Venue: ICLR 2025 Poster (2025)
Keywords: inexact stochastic proximal point method
stochastic composite optimization
quadratic growth
rate of convergence
Primary area: optimization

Abstract: The \textbf{i}nexact \textbf{s}tochastic \textbf{p}roximal \textbf{p}oint \textbf{a}lgorithm (isPPA) is popular for solving stochastic composite optimization problems with many applications in machine learning. While the convergence theory of the (inexact) PPA has been well established, the known convergence guarantees of isPPA require restrictive assumptions. In this paper, we establish the stability and almost sure convergence of isPPA under mild assumptions, where smoothness and (restrictive) strong convexity of the objective function are not required. Imposing a local Lipschitz condition on component functions and a quadratic growth condition on the objective function, we establish last-iterate iteration complexity bounds of isPPA regarding the distance to the solution set and the Karush–Kuhn–Tucker (KKT) residual. Moreover, we show that the established iteration complexity bounds are tight up to a constant by explicitly analyzing the bounds for the regularized Fr\'echet mean problem. We further validate the established convergence guarantees of isPPA by numerical experiments.

Published as a conference paper at ICLR 2025
A TIGHT CONVERGENCE ANALYSIS OF INEXACT STOCHASTIC PROXIMAL POINT ALGORITHM FOR STOCHASTIC COMPOSITE OPTIMIZATION PROBLEMS
Shulan Zhu', Chenglong Baot.*, Defeng Sun", Yancheng Yuaná.
Tsinghua University
The Hong Kong Polytechnic University
ABSTRACT
The inexact stochastic proximal point algorithm (isPPA) is popular for solving stochastic composite optimization problems with many applications machine learning. While the convergence theory of the (inexact) PPA has been well es- tablished, the known convergence guarantees of isPPA require restrictive assump- tions. In this paper, we establish the stability and almost sure convergence of isPPA under mild assumptions, where smoothness and (restrictive) strong convex- ity of the objective function are not required. Imposing local Lipschitz condition component functions and quadratic growth condition on the objective func- tion, we establish last-iterate iteration complexity bounds of isPPA regarding the distance to the solution set and the Baarush-Kuhi Kuhn-Tucker (KKT) residual. More- over, we show that the established iteration complexity bounds are tight up to constant by explicitly analyzing the bounds for the regularized Fréchet mean problem. We further validate the established convergence guarantees of isPPA by numerical experiments.
INTRODUCTION
We consider the following stochastic composite optimization problem: min <(x) a F(x) + r(x), ZERR
where F(x) - ESmP (f(:
(ComOpt)
where S is sample space, P represents a distribution over S, r: Rd - (-o0, +oo] is proper and closed function, and for P-almost & E S, the component function 8(=:):: Rd + (-o0, +oo is proper and closed, while the composite component function f(::s) + +(.) is proper and closed convex. A special case of problem (ComOpt) is the regularized finite-sum problem, where the sample space S is denoted by the finite discrete domain {1, .n. for some positive integer n, the function is defined as a finite sum of component functions, and the regularizer r is typically used impose sparsity the parameter Such discrete models common in statistics and machine learning, including linear regression model with Lasso regularizer or elastic net regularizer.
1.1 MOTIVATION AND RELATED WORKS
Numerous stochastic first-order methods have been proposed and analyzed for solving the stochastic problem (omOpt). The classical stochastic gradient descent (SGD) method developed by Robbins & Monro (1951) remains popular due to its simplicity. Nevertheless, theoretical and empirical results have shown that SGD suffers from instability and has significant difficulties and limitations in stepsize selection (Moulines & Bach, 2011: Asi & Duchi 2019). While SGD is commonly used practice, its drawbacks motivated developing alternative methods to alleviate these issues. One such method is the stochastic proximal point algorithm (sPPA) developed by [erttseass] (2011) for discrete problems and extended to continuous settings by Ryu & Boyd (2014). A sigmificant advantage of sPPA over SGD is the stability established in (Asi & Duchi 2019). Specifically, when
"Corresponding authors. Email: clbao@tainghua.c edu. cn yancheng.yuanppolly. wwwyyuuunnnlu..mmmmm edu.

---

Published as a conference paper at ICLR 2025
each component function is convex and there exists uniform upper bound subgradients over the optimal solution set, sPPA exhibits the following property: if the stepsizes are square summable but not summable and the subdifferential exchange with the expectation, then the iterates generated by sPPA are bounded almost surely.
Several theoretical convergence results have been proven for sPPA under different assumptions. Common assumptions include (restricted) strong convexity (Ryu & Boyd 2014] Patrascu & Necoara 2018 Davis & Drusvyatskiy 2019; Asi al. 2020) and (Lipschitz) smoothness (Ryu & Boyd 2014; Toulis et al., 2016; Patrascu & Necoara 2018| Yuan & Li 2023) or (global) Lips- chitz continuity (Patrascu Necoara 2018 Davis & Drusvyatskiy 2019) of component functions. Many other assumptions have also been proposed to obtain bounds of convergence rate for sPPA. For instance, when applied to problem (ComOpt with weak linear regularity of F and r 0. Pa- trascu (2021) ) proved an asymptotic ((k-P) sublinear convergence rate of sPPA with diminishing stepsizes og = -ook-3 in the expected squared distance to the optimal solution set. Some studies assumed "easy optimization" (Patrascu 2021 Asi & Duchi, 2019 Asi et al.) 2020), which requires that optimal solutions minimize each component function. However, this strong assumption is often violated in machine learning models. Most analyses considered the exact sPPA with batchsize of one, which assumes the subproblem in each iteration is solved exactly. This is a strong assumption that is typically difficult to achieve in practice. The only analysis of inexact sPPA was conducted by Yuan & Li (2023), who established ergodic convergence under the assumption that r satisfies Lipschitz continuity over the entire domain. Nevertheless, this condition violated by the clastic net regularizer. We refer to Table in Appendix A for a detailed comparison of these convergence rate results and their underlying assumptions.
Based on the above discussion, in this paper, we consider the inexact stochastic proximal point algorithm (isPPA) and provide the corresponding convergence analysis. Specifically, we aim to:
Establish convergence rate guarantees under assumptions that are satisfied by most com- mon regularized regression models in practice, including linear regression and logistic regression, while also allowing for nondifferentiability and local Lipschitz continuity of component functions and the regularizer.
Impose reasonable stopping criteria that can be implemented computationally for inexactly solving subproblems.
Derive various versions of convergence rate bounds, with some possessing theoretical in- sight while others being practically meaningful for assessing algorithm termination.
We mainly focus on the bounds for last-iterate convergence rates due to: a) their easier extension to nonconvex settings than ergodic convergence rates, which rely strongly on convexity; b) last iterates preserving properties like sparsity versus averaged iterates.
1.2 CONTRIBUTIONS
The main contributions of this paper can be summarized as follows:
Under mild conditions, we prove the stability of isPPA, extending the stability result for exact sPPA in literature (Asi & Duchi 2019) to the inexact variants.
Assuming local Lipschitz condition on component functions and a quadratic growth con- dition on the objective function, on the event that the iterate sequence remains bounded, we derive nonasymptotic last-iterate convergence rates for isPPA in terms of the expected squared distance to the optimal solution set. Specifically, this method converges linearly to an ((a)) neighborhood of the optimal solution set with constant stepsizes ag, and can achieve an O(k-8) asymptotic rate with diminishing stepsizes a₁ aok- (B (0, 1))- Based on these results, we can further obtain the corresponding rates in terms of the ex- pected Karush-Kuhn-Tuckee (KKT) residual. Since the KKT residual is commonly used in algorithm termination criteria, these rates have clear practical applications.
By using the Fréchet mean problem with squared b norm regularizer as an illustrative example, provide lower bounds on the convergence rates of isPPA for solving problem (ComOpt) under the assumptions proposed in this paper, demonstrating that our derived convergence rate guarantees are tight up to constant factors.
2

---

Published as a conference paper at ICLR 2025
Additionally, we verify the theoretical results by preliminary numerical experiments.
1.3 NOTATIONS AND BASIC ASSUMPTIONS
Denote the set [x]] _ (1, ,n). For any x E R. denote its g-norm as || For any x E IR" and X Rdd, let dist(xr,)) & vex || - yl be the Euclidean distance from æ to X, and set proj(2, X') to be the projection of x onto X' if A is nonempty and closed convex. For any proper and closed convex function p: IR (-o0, + oo]. the subdifferential of p at æ is denoted by Öp(x:) and the proximal mapping (r) associated with is defined by
prox,(2) _ arg min MER
p(v)
+ 2 11 =13
for all a E R..
It is known from (Rockafellar 1976b Proposition 1) that (.) is nonexpansive, i.e. Lipschitz continuous with constant 1. Consider the stochastic composite optimization problem (ComOpt). Let X & arg minger* ((x) denote the optimal solution set and set 6² inf d(x). For each s E S, the composite component function (p:;;) 8): Rd + (-o0, +oo] defined by
p(x:; 8) _ [x;; r(x) for all R
where (1)3)) and r(-) denote the component function and regularizer of problem (ComOpt respec- tively. Then, the objective function d(x) E s)] for all R2 For each k 24, use Slam & mm S to denote random minibatch of size m and define
m
f(;; S
fx; S
for all x R
(I.la)
YI
5 (2r;
Sk
Skmm
0 5h = (1; (h:a)) r(x) for all x E Rd.
(1.1b)
m
To solve problem (ComOpt., we consider the isPPA method shown in Algorithm The symbol indicates that the next iterate 1 is obtained by approximately solving the following subproblem:
1
min [(;; (l rxx) #EB4
|
xx112
20g
until F satisfies accuracy 6 specified by some stopping criterion (to be defined in Section 2 To establish the convergence properties isPPA (Algorithm([), we make the following assumptions.
Assumption 1. The function F: RRd R locally Lipschitz and Rdd (-c0, + a proper closed function. For P-almost all s E S, f(:s); Rd - (-20, too] is a proper closed function satisfying dom(f(: ()) dom(r), and ((::s): Rd (-20, +00] convex.
Assumption 2. The optimal solution set X is nonempty. There exists scalar dG E R++ such that
Ex-P [ =)][ S o for all x² E x" and all meusurable selections 4f ;x(x;; 8) E 38p(=";)) For any fixed x² X and o' (z*) 06(x*), there exists measurable mapping sf (x*:.-) such that such
(xxx) with sp (x*:s) =ap(=": ;s) for P-almost e S, where Ee-P jgp' (x*; is defined the integral Js Assumption 3. For any bounded open subset U C. dom(r), there exists measurable function (U)) for some constant Lr(U) E R__ depend-
Eae lip' (x":
L S BR,, satisfying /E (3, ing on U, such that for P-almost all S,
(x;;8) - (1; S Lxu(())] - yl12
holds for all x. E U.
Assumption 4. The objective function & satisfies the quadratic growth condition on X* globally, that is, there exists 0 such that
(xx) 2 8" + ciiitt(zz, X²)
holds for all E d
3

---

Published as a conference paper at ICLR 2025
It is worth noting that Assumption not essential for establishing the stability or almost sure vergence of isPPA. Moreover, this assumption can relaxed to its localized version (Assumption 5 when deriving the convergence rate of isPPA with square summable diminishing stepsizes, i.c., Ok ook for some 3 E (2.
Assumption 5. The objective function satisfies the quadratic growth condition on X" locally, that is, there exists C1 > O and > O such that
δ(x) 2 Ø" + x for all x E (x
where U(X"" ,6) denotes the set {Ir E TR di, X²) 6}.
Remark 1.1. A sufficient condition for the optimal solution set X' to be nonempty is the coercivity of the objective function é, which commonly holds for regularized regression models. The last condition Assumption 2 is implied by the equality
EgpP [d<p<:; s)] do(z) for all E dom(o),
(1.2)
where Es-P [0p(<:; 8)] is the expected subdifferential defined by
E [0p(x;))) v RRd UΦ.2 /s (z;
with (z(z; measurable and (a;;;) E 0p(a; s) for P-almost E S)-
In the discrete case where S [n]. it follows from (Rockafellar 1998 Theorem 23.8) that
Neesri(donm ((o-(((())))))) * 0 is sufficient for (1.2), with ri[dom((p( $jJ) relaxed to (p((s)(-:s)) s))
for polyhedral s):ss). For the continuous case, sufficient conditions are given in (Rockafellar &
Wets 1982 Bertsekas 1973). Specifically, if cp(:; s) is real-valued and convex for each S, 1.2
holds due to (Bertsekas] 1973. Proposition 2.2).
Algorithm 1 Inexact Stochastic Proximal Point Algorithm (isPPA)
Parameters: initial point 21, stepsizes {ax J221, accuracy parameters {ek (cx)221, minibatch size m, maximum iteration count K for 1.2..... K do
2: Draw random minibatch S.mm with St. iid. P
3: Update
Tk+1
arg min rERd
Fc; (m + r(x)
|| 1x
(1.3)
201
where F(r;; S1:") is defined in I.la
4: end for Output: last iterate
2 ANALYSIS OF INEXACT STOCHASTIC PROXIMAL POINT ALGORITHM
In this section, we establish the convergence properties of isPPA, including the stability, almost sure convergence, and convergence rate guarantees in terms of the squared distance the optimal solution set and the KKT residual.
Given Eg O, we consider the following three criteria and say that Tx+1 is obtained according to 1.3 it satisfies one of these criteria:
Fa+1 prox
(ase)
S
Skk:
(SCA)
22 (Ib+1; Slmm +
(SCB)
200k
dist (0, 0$ au mn (I++1; S
1:mm
Ck
(SCC)
a
where function & an 22 (1 S1mm): Rd + (-00, +o0| is defined by
1
T Pay.z (x; Sl.m) A x (x; St-m) +
|| 24 1
for all Rd
20
4

---

Published as a conference paper at ICLR 2025
and T Sh - mingeRd Par.a (x; skm denotes the minimum value. Leveraging the fact
that 4 ax (1 5km) is J strongly convex under Assumption og
| it is straightforward to verify that
Criterion (SCC)
Criterion (SCB)
Criterion (SCA)
(2.2)
Therefore, is sufficient to establish the convergence results for isPPA with {2y} satisfying criterion SCA). Due to (2.2). the derived conclusions also hold for isPPA with {ax} satisfying either criterion
SCB
criterion (SCC).
Unless otherwise stated, we will use the following notations for simplicity. For any B E R, the function Ss: R_- + R is defined by
i + 0,
(t(t)
(2.3)
[In(t) if =,
for all R4+. For any bounded open subset U C dom(r), we assume without loss of generality that E.- (s) and set
Var (I))
(v=+ (m- m
1)pa +1
ngU 2
and Pf.m,U
(2.4)
EanP [b)])(()}3]
Fix any E Z4. Let Fk - (S) s) be the a-field generated by the first random minibatch {S!!-m] Ji=1, and denote the conditional expectation [g[-] El- Fs-1). Additionally, we denote the proximal point prox (Ix) by #x+1-
2.1 STABILITY AND ALMOST SURE CONVERGENCE
Before establishing convergence rate guarantees for isPPA. we first prove conditions sufficient to ensure boundedness of the iterates (rxx ) generated by (13).. By adopting the proof of (Asi & Duchi, have the following theorem.
2019 Theorem 3.2 and Corollary 3.5) with suitable modifications,
The proof is omitted here and deferred to Appendix B.I
Theorem 2.1. Let Assumption 7 and hold, and let {Fa) be generated by isPPA (Algorithm) ! with stepsizes {ax} and parameters { Suppose that the parameters {Ek} satisfy ek = yaz. for each k E E4 with R4. Then the following assertions hold:
(i) For all T X2 and k E Z4, have
o + +
Ex -|1=+11-111
s (1 at) - 2|2]
||
222 + (1 at) a
(2.5)
(ii) Assume further that the stepsizes {ay} satisfy Ex of < co. Then ||ææ||2 < oc with probability 1.
sup
(2.6)
kEă
Remark 2.1. For the finite-sum regularized regression model with real-valued nonnegative convex component functions and real-valued convex coercive regularizer, Remark[[.]] combined with the compactness of the subdifferential of a real-valued convex function, implies that Assumption and hold. By Theorem 2.1 this observation shows that isPPA exhibits stability under mild conditions.
With Theorem 2.1 established, we are now positioned to demonstrate almost sure convergence of isPPA with diminishing stepsizes, assuming local Lipschitz continuity of component functions. Our proof sketch incorporates and modifies the methodologies from Davis & Drusvyatskiy (2019) Lemma 4.2) and [Bertsekas] (2011) Proposition 9) initially derive convergence results for exact sPPA (i.c., = 0), and subsequently extends these findings to inexact settings using the Cauchy- Schwarz inequality. See Appendix B.2 for detailed proof. is worth noting that our proof tech- nique diverges from that employed by Asi & Duchi (2019 Proposition 3.8); see Remark B. in Appendix B.2 for more details.
Theorem 2.2. Let Assumption hold, and let (ax} be generated by isPPA (Algorithm 7 with stepsizes {ax) and parameters {- Suppose that the stepsizes {ax) } satisfy Σx 0g 00 and Eee at < oo, and the parameters {ex} satisfy e₁ y for each k E E+ with y E R.. Then with probability 1, both lim inf inf--so ((xx) and there exists x" E X such that limg- 1|
x" ||2 = 0 hold.
5

---

Published as a conference paper at ICLR 2025
2.2 CONVERGENCE RATE IN THE SQUARED DISTANCE TO OPTIMAL SOLUTION SET
Recall the function defined in (2.3) and the notation fmm, introduced in (2.4). In this part, we consider the bounds the last-iterate convergence rate of isPPA, measured by the expected squared distance to the optimal solution set, under a local Lipschitz conditon on ((:)) and quadratic growth conditon on Φ.
Unless stated otherwise, if there is bounded open subset of dom(r) that contains the sequences { and { denote this subset by U. Let E (0,2) 2) be an arbitrary scalar and define
C.,,UU.iina)) Pf + (1 + a (1 ss1a)
(2.7)
(2 s)sc
for all IR+. By utilizing Lemma B.3 (see Appendix B and following the proof arguments of (Moulines Bach, 2011] Theorem I), we can thus derive nonasymptotic convergence rates for isPPA summarized Theorem 2.3 and 2.4 below.
Theorem 2.3. Let Assumption hold, and let (rx) be generated by isPPA (Algorithm 7 with and parameter Eu: = =nağ for all k E Et, where ag E R++ and E R4.
constant stepsize Denote by 8, A dist(z1, x²² and let s E (0,2) be an arbitrary scalar. Then, on the event that suP || < oc, we have
8-1
C....tiiinnoo)) ag
E [ditt( x ++80 801 Cko
81
(2.8)
801
for all l. E R.4, where Ü.,,,U,esa defined 2.7
Theorem 2.4. Let Assumption 1 hold, and let { } be generated by isPPA (Algorithm 7 with diminishing stepsize og = -okk== and parameter éx Tag for all k 24, where do E R R (0, and y Rt, Denote by 81 & dist(x1, and let (0, be an arbitrary scalar. Then, on the event that supkez, || < cc, the following assertions hold:
(i) B E (0, 1), then
E (dist(ak, x0)3] exp
1 30 51 81
$c100
4
aj
(2.9)
1 expl
1
1480100
4 a exp
SC1
1--8
k
2 + SCI (c))
-1-23
23
2
holds for all Z4, where Č (..,, is defined in 2.7
(ii) 3 = 1, then
E
[dist(rk, x²
46,
+ (a0ll2ee
2x og 2eseran
if ffeaa 2
14s0gor0
2-80100
(2.10)
481 i + 14
In(k)
if0100 2
2003 cop
46,
(1)
+
if 1100000
2
1+ec, cto
scrag-2
holds for all ls E Z4, where C.a..U,e is defined in 2.7
Focusing on dominant terms, we can immediately derive the asymptotic convergence rate for isPPA as shown in Corollary 2.5 which provides clearer estimate of the convergence rate obtained in
Theorem 2.4 Corollary 2.5. Consider the setting of Theorem 2.4 and let E (0,2) be arbitrary scalar. On
the event that supwez, ||ææ||2 < 0o, the following assertions hold:
(i) If 3 (0, 1), then E. [dist(xx X2 (k--) holds for all k Z

---

Published as a conference paper at ICLR 2025
(ii) 3 = 1, then
20cja
0 k 240qg0g
ifc100 87
E (is,,
0 [k (n(k))())
i90000
57
1
ifc100 > 8
holds for all E Z..-
The proofs of Theorem 2.3 2.4
and Corollary 2.5 can be found Appendix C
Diminishing stepsizes and localized quadratic growth condition. In the context of isPPA with diminishing stepsizes ag = agk and parameters Ej = =ya where ag E R+++ 8 E ( and y R4, and considering the square summability of {{a)) Theorem 2.1 ensures the al-
most sure boundedness of (xxx under Assumption and 2 In this setting, since Og S 0o and yak = 7okk 1/2 3/2
1/2 3/2 S <a00 -Ok the iterates (xx) also satisfy Criterion (SCA) with ég 4.0%
3/2
Og
where 7 ya0
1/2 Consequently, all the results in Theorem 2.4 and Corollary 2.5 hold with probability 1, even without assuming supkez, || < c0. Additionally, based on the fact that
{dist (x.t }}} converges to zero almost surely as implied by Theorem 2.2 Assumption 4 in The-
orem 2.4 can be replaced with its localized version (Assumption (). Under this localized quadratic
growth condition, convergence results analogous to those in Theorem 2.4 and Corollary 2.5 can be achieved for sufficiently large k.
Relationship with prior work. When each component function is Lipschitz smooth and restricted strongly convex, and the regularizer r is zero, the asymptotic convergence rate descirbed Theo- rem 4 of (Ryu & Boyd 2014) for standard sPPA (i.e., exact sPPA with a minibatch size of one) with stepsizes 0g = aok- can be deduced from Corollary 2.5 Similarly, the last-iterate convergence rate guarantees provided in Theorem of (Toulis et al. [0016) for standard sPPA with stepsizes On ao.. (3 E G 11) can be derived from Theorem 2.4 However, these guarantees established by Toulis al. (016) require more restrictive assumptions, such as the twice continuous differen- tiability and a specific structural condition on component functions. The last-iterate convergence guarantees in Theorem 4.3 of (Patrascu) 2021) apply exclusively standard sPPA, and achieving the linear rate of (Patrascu 2021 Corollary 4.5) requires the problem to be easy to optimize. The Olk-)) ergodic ergodic convergence rates in Theorem 10 of (Yuan & Li (003)) for inexact sPPA with step- sizes Og = aok are established under stringent conditions including Lipschitz smoothness of component functions, Lipschitz continuity of the regularizer across the entire domain, and suf- ficiently large minibatch size. Most previous work have focused on the convergence properties of standard sPPA when solving problem (ComOpt) with Lipschitz smooth component functions. As noted in Remark 2.1 the assumptions applied in this paper are reasonable and feasible in practice, and the above comparisons indicate that our derived convergence rate estimates are competitive.
2.3 CONVERGENCE RATE IN THE KKT RESIDUAL
The bounds the rate of convergence in terms of the expected squared distance to the optimal solution set given in Section 2.2 possess significant theoretical importance. However, termination criteria in practice are frequently associated with the KKT residual. Consequently, it is essential to establish convergence rate guarantees with respect to the KKT residual. Fortunately, the following relationship between the KKT residual and squared distance to the optimal solution set holds.
Lemma 2.6. Let o: T -> (-00, too be a proper and closed convex function, and denote the set of minimizers of 6 by X². X is nonempty, then for any E Rd, we have
|| prox (x)x2()))2 < 2 dist (z, X*),
The established relationship enables us to extend all conclusions from Section 2.2 the correspond- ing convergence rate bounds in terms of the expected KKT residual. For the sake of brevity, we focus exclusively on the asymptotic convergence rates of isPPA with diminishing stepsizes in this part.
Corollary 2.7. Consider the setting of Theorem 2.4 and let s E (0, 2) be an arbitrary sealar. On the event that supkez, || 2 <. co, the following assertions hold:
7

---

(Rockafellar Published as a conference paper at ICLR 2025
(i) If E (0, 1), then E ax proxx(xx))
00 x0( holds for all E E4.
(ii) B = L, then
ifc100
81
as prox, (xx)
o k (In()))3)
if fc100
0 k-
if fc1000
holds for all k E Z+.
The proofs of Lemma 2.6 and Corollary 2.7 are deferred to Appendix D
LOWER BOUNDS OF CONVERGENCE RATE
In this section, we establish a lower bound for the convergence rate of isPPA. The main results are summarized in the following proposition; Appendix E for detailed proof.
Proposition 3.1. Let {ps):=r Idd be given points and X R+. Consider the finite-sum comvex optimization problem:
min ((x) F(x) + +r()) 1
Σ 2 pall2 + |
(3.1)
Denote the set [n]] A fI.... n). Let {ax] be generated by (.3) with stepsize on R and
parameter c = 0 all k E Z4. Then the following assertions hold:
(i) Assumption hold for (.1 and x²
2 (2+2)n E the unique optimal solution.
(ii) Set Σ max [pell2 Then supkez_ |aalll S | + E<x, oc, Le., { is bounded.
(iii) Assume further that there exists in # ju E [m] with Pio # Pjo Then 0² & 1 E lpj
EE pill 0 and for any k E E..
[ | - x
20
if aa 2 ao for some Ogg E R+++,
(2+X)aa +1 40
8-8
if aa
Oo for some on TR++ and B E (0. 1]. ks
+1+
Tightness of derived bounds. Combined with the upper bounds derived in Section 2.2 the lower bound established Proposition 3.1 shows that for isPPA with last iterate output, solving problems (ComOpt) satisfying Assumption 1 the following holds if the convergence rate is measured by the expected squared distance and no other structure is known: a) when the stepsizes {ax. have uniform positive lower bound, the algorithm guarantees only convergence to neighborhood of the optimal solution (see Figure [(b)), and thus the bound on the convergence rate of isPPA with constant stepsizes from Theorem 2.3 cannot be improved; b) for the diminishing stepsizes {ar)
with ag = ag (3 E (0, 1)). the asymptotic convergence rate of O(k-3) from Corollary 2.5 is tight up constant factors (see Figure I(c)).
Comparison with deterministie PPA.
It is known that if the sequence of stepsizes {ax} satisfies ag + Ocoo for some ax E R.+, then inexact deterministic PPA exhibits linear convergence under quadratic growth condition and achieve superlinear convergence as Og 1976a Luque 1984). In contrast, our analysis shows that even when solving Fréchet mean problem (.1) with Lipschitz smooth component functions and strongly convex objective function. isPPA with lower bounded stepsizes merely approaches a neighborhood of the optimal solution but fails achieve exact convergence to the optimal solution. This discrepancy may stem from the noise
introduced during subproblem minimization through the term [(; S1:m) (see 1.3 As shown in
8

---

Published as a conference paper at ICLR 2025
Appendix C this noise contributes to the term Pt.m, LU)) in the nonasymptotic estimate of
Theorem 2.3 while the first term in this estimate geometrically converges to zero. The distinctions between the deterministic PPA and stochastic variants empirically validated by the numerical results presented in Figure ((a) and T(b)
Stcatte equacst
Bersined))
(a) Constant PPA
(b) Constant isPPA
Diminishing isPPA
Figure 1: Performance comparison of PPA and isPPA for solving the Fréchet mean problem (3.1) Legends "Algo-alphaO-oo" and "Algo-beta-3" denote methods with constant stepsizes ag = ogg and diminishing stepsizes O' agk 8 (B (0, 1)), respectively, where "Algo" refers to either PPA or isPPA.
NUMERICAL EXPERIMENTS
In this section, present numerical results validate the theoretical convergence rate guarantees derived in Section 2 For brevity, the discussion here is limited to the performance of isPPA on the synthetic data, with details on real data sets available in Appendix We generate the synthetic data using the model 6 = Ax* + af. where A is sampled from standard normal distribution, x² is the predefined true solution, & noise vector from standard normal distribution, and a denotes the noise level. The number of nonzero elements in x" is set to [p,d] with Ps = 1%. The results are averaged over 5 trials with consistent parameters and initialization across each trial isPPA.
4.1 LASSO LINEAR REGRESSION MODEL.
Consider the linear regression model with a Lasso regularizer (Tibshirani 1996):
min #ER
VInnso (x: A ||Ar - b112 A ||=|||
(4.1)
where matrix A Raxd and vector R" are given data, with Aι R++ the regularization parameter. For each trial of isPPA with diminishing stepsizes 0g = =ogk where 3 E ( 1), given that the optimal solution may not be unique, we first obtain an approximation, denoted by ă" of the optimal solution, to which the sequence }æu} converges almost surely as indicated in Theorem 2.2 See Appendix [F. for details on obtaining 2+
For the Lasso linear regression model 4.1 we utilize the efficient semismooth Newton (SSN) method (Li et al., 2018,, Algorithm SSN) solve the inner-loop subproblem (I.3) inexactly, with the sequence {Ix} satisfying criterion (SCA); see Appendix F. for further details. In our numerical experiments with synthetic data, we test with n = 10000 and 1000, setting to zero in noiseless experiments and to 10-2 otherwise. The regularization parameter X1 is set to A. | bll with
X, 10-2 The accuracy parameter eu is defined ya with 7 10-2, and the minibatch size m is fixed at 32. The top row of Figure 2 displays the convergence curves of isPPA with diminishing stepsizes ag aok- 8 for various stepsize exponents E {0.55, 0.75, 0.9, 1), starting with an initial stepsize au = 50. It is observed that isPPA with a stepsize exponent of B = exhibits the best performance. The asymptotic convergence rate measured by the squared distance to the solution set is ((k-²), considering |, - --'12 as an upper bound of (ist( x² also shows
that the asymptotic convergence rate regarding the KKT residual (defined in F.5 is ( -k--//2)
These observations confirm the results derived in Corollary 2.5 and 2.7

---

Published as a conference paper at ICLR 2025
4.2 ELASTIC NET LINEAR REGRESSION MODEL
The linear regression model with an elastic net regularizer (Zou & Hastie 2005) is defined by
A
min Velastic (x) _ || - 6122 A | + aERd
(4.2)
where Å1 A2 E I are the given regularization parameters. It is straightforward to verify that the objective function d'elastic is Ag-strongly convex over Rd ensuring the uniqueness of the optimal solution to (4.2). The setup for the numerical experiments of isPPA for solving (4.2) is similar to that previously described for (4.1); see Appendix F22 for further details. Notably, given the uniqueness of the solution to (4.2) we directly employ the semismooth Newton augmented Lagrangian (SS- NAL) method et al. 2018 Algorithm SSNAL) approximate the optimal solution, to which the sequence {r*} converges almost surely. This approximate optimal solution is denoted by Ø². The numerical results, illustrated in the bottom row of Figure 2 demonstrate asymptotic convergence rates of ())-)) for the squared distance I|.r - 10 and Ok for the KKT residual (defined
in (F8)), thereby validating the findings from Corollary 2.5 and 2.7
SET
SOTT
(a) Noiseless setting
(b) Noisy setting
Figure 2: Performance of isPAA in solving the linear regression models (Lasso - top and elastic net bottom) for four values of stepsize exponents 8 = 0.55, 0.75, 0.9 and 1. The legend "isPPA-beta-P denotes isPPA with diminishing stepsizes ag aok -8 (a) The noiseless setting with a 0. (b) The noisy setting with = 10-2
CONCLUSION
In this paper, we consider inexact stochastic proximal point algorithm (isPPA) for solving stochastic composite optimization problems, allowing subproblems be solved inexactly via suitable inner- loop stopping criteria. Under mild conditions, we demonstrate the stability and almost sure con- vergence of this method. By further assuming local Lipschitz condition component functions and a quadratic growth condition on the objective function, we establish convergence rate guaran- tees. These rates are measured by the expected squared distance the optimal solution and the expected KKT residual. While the former provides theoretical insights, the latter offers practical estimates for algorithm termination. Our findings confirm that these convergence rate guarantees are asymptotically tight up to constant factors. Empirical validation from numerical experiments supports our theoretical analyses. In future work. we will focus on enhancing its efficiency with acceleration strategies and variance reduction techniques, and establishing the corresponding con- vergence analysis.
REPRODUCIBILITY STATEMENT
Upon acceptance of the paper, we will release the code used for the demonstration examples in the numerical experiments.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTI
Yancheng Yuan is supported by the National Key R&D Program of China under grant (03YFA1000300) and the Research Center for Intelligent Operations Research. Shulan Zhu and Chenglong Bao are supported by the National Natural Science Foundation of China (No. 122712911 Defeng Sun is supported by the Research Center for Intelligent Operations Research, RGC Senior Research Fellow Scheme No. SRFS2223-SS02 and GRF Project No. 15304721. Shulan Zhu would like to thank Prof. Sun for hosting her research visit at the Hong Kong Polytechnic University, during which the foundational work of this study was initiated.
REFERENCES
Hilal Asi and John Duchi. Stochastic (approximate) proximal point methods: Convergence, opti- mality, and adaptivity. SIAM Journal on Optimization, 29(3):225-22990, 2019.
Hilal Asi, Karan Chadha, Gary Cheng, and John C Duchi. Minibatch stochastic approximate proxi-
mal point methods. Advances Neural Information Processing Systems, 33:21958 1-22195--2168,, 2020.
Dimitri Bertsekas. Stochastic optimization problems with nondifferentiable cost functionals. Jour- nal of Optimization Theory and Applications, 12(2):218 231, 1973.
Dimitri P Bertsekas. Incremental proximal methods for large scale convex optimization. Mathemat- ical Programming, 129(2):163-19)) 2011.
Chih-Chung Chang and Chih-Jen Lin. Libsvm: a library for support vector machines. ACM Trans- actions on Intelligent Systems and Technology, 2(3):1-27, 2011.
Damek Davis and Dmitriy Drusvyatskiy. Stochastic model-base based minimization of weakly convex functions. SIAM Journal on Optimization, 29(1):207-234) 2019.
Xudong Li, Defeng Sun, and Kim-Chuan Toh. A highly efficient semismooth newton augmented lagrangian method for solving lasso problems. SIAM Journal on Optimization, 28(1):433 458, 2018.
Fernando Javier Luque. Asymptotic convergence analysis of the proximal point algorithm. SIAM Journal on Control and Optimization, 22(2):277-293, 1984.
Eric Moulines and Francis Bach. Non-asymptotic analysis of stochastic approximation algorithms for machine learning. Advances in Neural Information Processing Systems, 14:451-459 2011.
Andrei Patrascu. New nonasymptotic convergence rates of stochastic proximal point algorithm for stochastic convex optimization. Optimization,
2021.
Andrei Patrascu and lon Necoara. Nonasymptotic convergence of stochastic proximal point methods for constrained convex optimization. Journal of Machine Learning Research, 18( 198) 2018.
Herbert Robbins and Sutton Monro. A stochastic approximation method. Annals of Mathematiaal Statistics, 22(3))400-407, 1951.
Herbert Robbins and David Siegmund. A convergence theorem for non negative almost super- martingales and some applications. Optimizing Methods Statistics, pp. 233-257. Elsevier, 1971.
R Tyrrell Rockafellar. Augmented lagrangians and applications of the proximal point algorithm in convex programming. Mathematics of Operations Reseurch, 1(2):97-116, 1976a
Tyrrell Rockafellar. Monotone operators and the proximal point algorithm. SIAM Journal on Control and Optimization, 14(5):877-898, 1976b.
R Tyrrell Rockafellar. Convex Analysis. Princeton University Press, Princeton, New Jersey, 1998.
R Tyrrell Rockafellar and Roger J-B Wets. On the interchange of subdifferentiation and conditional expectation for convex functionals. Stochastics: An International Journal of Probability and Stochastic Processes, 7(3):173-182, 1982.
11

---

Published as a conference paper at ICLR 2025
Emestt K. Ryu and Stephen Boyd. Stochastic proximal iteration: non-asymptotic improvement upon stochastic gradient descent. Author website, 2014. URL https:/ web. stanford. edu/
Robert Tibshirani.
Regression shrinkage and selection via the lasso, Journal of the Royal Statistical Society: Series B (Methodological), 58(1):267-288, 1996.
Panos Toulis, Dustin Tran, and Edo Airoldi. Towards stability and optimality in stochastic gradient descent. Artificial Intelligence and Statistics, pp. 1990-1298. PMLR, 2016.
Xiao-Tong Tong Yuan and Ping Li. Sharper analysis for minibatch stochastic proximal point methods: Stability, smoothness, and deviation. Journal of Machine Learning Research, 24(270):1-52, 2023.
Hui Zou and Trevor Hastie. Regularization and variable selection via the elastic net. Journal of the Royal Statistical Society: Series B (Methodological), 67(2):301-320, 2005.
12

---

Published as a conference paper at ICLR 2025
A COMPARISON OF CONVERGENCE RESULTS FOR SPPA SCHEMES
Table summarizes and compares convergence rate guarantees and associated assumptions for sPPA-typ type schemes in solving problem (ComOpt). We use the following abbreviations:
bd (bounded), cld (closed)
lin.reg (linear regularity)
cvx (convex), s.cvx (strongly convex), r.s.cvx (restricted strongly convex), wk.cvx (weakly convex);
Lip (Lipschitz continuous), loc.Lip (locally Lipschitz continuous), Lip.sm (Lipschitz con- tinuous gradient), C² (twice continuously differentiable), sm (differentiable)
wk.lin.reg (weak linear regularity). qd.grow (quadratic growth), e.qd.grow (expected quadratic growth), e.sharp.grow (expected sharp growth)
easy.opt (easy to optimize)
Le (sufficiently large)
sq.dist (convergence rate in terms of [ - =111)))) sq.dist.set (convergence rate in terms of sq.norm.grad (convergence rate in terms of the squared gradient f--nrrm of Moreau envelope with respect to ())
func.gap (convergence rate in terms of {Φ(*)) o² }),
Table 1:
Comparison of convergence rates for sPPA-type methods solving stochastic composite optimization problem (ComOpt).
Method
Literature
Model
Assumptions
Stepsize
Rate
f(; rsccv & Lip.sm
sq.dist O())
{co I.e.)
Ryu & Boyd 2014
r=
f(:8) r.s.cvx
0XO
linear convergence to
O(oa) (dist)
f(x;8) f(a.a);; f(38) cvx & &
sq.dist O
K
(8 E (4) 1)] or
Toulis et al. 2016
r=
sPPA
(8 1 & ao le.)
0f(:;) on F ww..lin.rg
distsst O
(5 (0, 1)] or
1 & ao I..)
Patrascu 2021
r=0
0](:3) bd on o
linear convergence (sq dsq.dsstset)
l' (n) 0):
easy.opt
[(:s) CvX & Lip:
Op O
func.gap O (ergodic)
X neexx.:
cld.evx lin.re:
[ s.cvx sm;
linear convergence to O(ag) (sq.dist)
X = Neesx::
a
New-sPPA
Patrascu & Necoara (2018
1x
X. eld.evx & X lin.reg;
f( 8) s.evx & Lip.sm;
sq.dist O ( 8 (0, 1)} or
= Nsesx.:
X. cld.cvx & X lin.reg;
{ {== & ap Le.
f(: & e.sharp.grow; easy.opt
eg
linear convergence (sq.dist.se)
{3 E (-o0, 1)}
APROX
Asi & Duchi 2019
1x
f(:s) cvx & e.qd.grow; easy.opt
linear convergence
R
(sq.distsee)
{8 E R)
continued on next page
13

---

Published as a conference paper at ICLR 2025
continued from previous page
Method
Literature
Model
Assumptions
Stepsize
Ratc
F loc.Lip:
cld;
Oko
sq iq.norm.grad.Mi
O
"V
fa(38) +r(-) wk.cvx;
fx(38) Lip;
F Lip:
func-gap O
Model-hased
Davis & Drusvyatskiy 2019
f(:88) --(())o) evx;
cldd;
O
1 VE
(ergodic)
vT
f(:s) Lip:
F Loc.pip:
reld;
0g O
func. gap (
f(::8) - -(() s.cvx;
(ergodic)
f(38) Lip:
(13)) cvx & Lip.sm:
func. O
22
mk
cvx;
(ergodic)
X cld.cvx:
Le)
qd.grow
[rg l.e. func.gap
M-SPP
Yuan & Li 2023
r= 1x
f(::8) evx & Lip.sm;
Og O v
mik
(ergodic)
cld.evx
{ {oo const (m, k, Lip,))
f(:8) cvx & Lip.sm:
func.gan O RT +
mk
r cvx & Lip:
(ergodic)
X' cld.evx;
{ m [m
qd.grow
{ [ao l.e & c 0
mp
Inexact M-SPP
Yuan Li 2023
-=r+lx 1x
f(:s) 5) cvx & Lip.sm: cvx & Lip;
func.gap O Vink
mk
0g O vT
(ergodic)
X' cld.cvx
{ <i const (m,, k, Lip,))
{ cx = 00=00,.0 ((,b)
linear convergence to O(oa) (sq (sq.dist.set)
Theorem 2.3
F loc.Lip;
r cld;
(a = 7a
isPPA
f(;8) +r(-) (5ss Lip: á qd.grow
sq.dist.sct O (
{ [a aa
Theorem 2.4
_ (0, 1))
[= 1 & az l.e.}
Here 1, denotes the indicator function of a set X' C RRd which is defined by
if E X,
1
(x)
otherwise.
The symbol "(ergodic)" appearing in the table indicates the ergodic convergence rate. Otherwise, the shown refers the last-iterate convergence rate by default.
B PROOFS FOR THE RESULTS IN SECTION 2.1
In this section, we provide the detailed proof for Theorem 2.1 and 2.2 presented in Section 2.1 Recall that the notation ē*41 is defined the proximal point nI.U and m given (2.4) are defined by
(Ix), and the symbols
Var (s) ExpP (s)2
(v
1+ (m 1)nfu +1
nyUu A 1
and Pfmm.
A
m
The following three technical lemmas are needed in our proof argument.
Lemma B.1. The following assertions hold:
(i) Let Assumption 7 hold. Then the function o is proper and closed convex.
14

---

Published as a conference paper at ICLR 2025
(ii) Let Assumption 3 hold. Then the function F is Lipp)--ipshhit any bounded open subset U dom(r)) r), i.e.,
[F(x) F(V) S Lp(U)|l= - ull2 for all x, E U.
Lemma B.2. Let Assumption hoold and let [ be generated by isPPA (Algorithm) D with stepsizes {. Then for all x E R and h: E Zez, we have
[ x112 _ 110g - =12 20x [ (iN+1: - P (x; sp - 11xx-1 - 2x112.
(B.1)
Lemma B.3. Let Assumption 7 and hold, and let { be generated by isPPA (Algorithm D with stepsizes {.x}. Suppose that the sequences { and { are contained in some bounded open set U C (r) Then for all x E IR and k E Z+, we have
E& [|l x01]]
1
x=12 20x E& (0(#x+1) - x(x)] L a
(B.2)
which implies
Es [1 -2 I [1+ ;) (1LEx -x13 - Ex (0(x++++1) 6(x)])
(B.3)
1+ !) PLmoULLU of +1 (1+t)c
for any t I+++
The proof of the previous three lemmas are deferred to Appendix
B.3
B. PROOF OF THEOREM 2.1
Proof of assertion (i). Fix any ह E X and k E E., Note that é is convex by Lemma B.I i). It
follows that 0 E aδ(z) and thus, by the second condition in Assumption 2 01( St) such that
we can take op (x;
S
E& [ St) 0 for 1, ..... m. E
(B.4)
Set (T & 1 Based on the convexity of S( implied by Assumption we have
(T; S. Then ( S. E ÖØ(;; S 1am and Eg ( (T;
(T:
m
T b
S
(#x+1: S S (
(z) Sk:.) cl:m) I - Tk+1)
T
sl:m
Jkk Tet1) + ( (T:S%
(B.5)
<
(50
(x;
St cl:m)
+
O'k
sl:m |1 |e
(x::
St
| - 2x
2
20r
where the last inequality uses the Cauchy-Schwarr inequality. By setting in inequality B.1 of Lemma B. and combining it with (B5). we can conclude that
|
||
21/ + 20
(
I St
(l.m)
T -xa)
+
ak
Stim 1|
2
(B.6)
+ 20
| xx 112
|| 1
x 112
|| - 21/2 200k
(
(x;
N
xR)
a
|ل
(x; S J:m 12-
Fix any E 4. It follows directly from the Cauchy-
Cauchy-Schwarzz Schwarz inequality and criterion SCA) that
[ x112
|| -x+ 112 ||āx+1 x012 2(x T Jx+1 2)
S || - -x+1112 ++|iix+11 - -x11² + || Tx41 12 + ||āA+1 - x (B.7)
s + 1) | - 2112 (1 + 1) for all x E Rdd
15

---

Published as a conference paper at ICLR 2025
It follows from the definition of "p' (x; s) that
k
||s0'
(x; St m12
= Ex
(1: Sks)
t=1
= Ex
(0' St) - Es 1&0' (z: (1))
m 1=1
(B.8)
1
B₁s || (x. (x:
Es [&p' (I: St]]
m 2
|| (z; 11
Es
m
where the second equality uses condition (B.4), the third holds because of the independence of the random variables and the last use again condition B.4h. By setting x = Σ, and 6₁ za in inequality (B.7) have
og
[ - 2 - a1+) |
-112 + (1 + az) af?
1 (1 + ax)) ||0r -x112 + 2om (ve' (t:)) x mx) + oz 11 (t:)) [1]]
(1 a3) a²²²
where the second inequality follows from (B.6). Taking expectations on both sides of the previous inequality with respect to Fx-1 yields that
E& [|or =112]
< (1 + ag || 2
(1 az
|
(x; 11:m |12] + +2²)
a
(1 + at)) ||
(1 at) a
1
Ex
||1e'
(I:: Sk) [2]
+ +
m
03
$ (1 + ai))
||
21/
(1
a a
+72
m
where the first inequality comes from the condition that Ex [ SZ. S.m)) = 0 and the last is due to Assumption and the equality holds because of (B.8). This completes the proof of inequality (2.5)
in assertion
k= of < co. To prove assertion (ii), we first recall the so-called supermartingale convergence lemma, the proof of which can be found in (Robbins & Siegmund 1971, Theorem 1).
Proof of assertion (ii). Now we assume that Σ
Lemma B.4. Let Zu. Ps. &v and S& be nonnegative random variables adapted to the filtration FR and satisfying
Zx E Z Fxl (1 3x) t Sk
for all K E Z. Then on the event that Σ k= 3y < 00 and >x= EN < co, with probability 1, we have Ex=1 Sk < oo and there exists a random variable Zoe such that lim Zx = Zoo.
Fix any I E X*, The assumption that Ex Ckzz or < < implies as I 1 for l sufficiently large and thus
Σ a1) ar < xc.
By Lemma B.4 given the conditions that >x=1 ox < oo and Σx (1 +1 + o < oo, we can
deduce from the derived inequality (.5) that the sequence f|| - x (2) converges to some finite value with probability 1. This implies (2.6). thus completing the proof of assertion (ii).
16

---

Published as a conference paper at ICLR 2025
B.2 PROOF OF THEOREM 2.2
By assumptions given in Theorem 2.2.
we can deduce from Theorem 2.1 that with probability 1,
sup kEe4
|axl|2 < 3o
(B.9)
Then, to prove Theorem 2.2 it is sufficient to show that on the event B.9 holds, with probability both
(i) lim on ((xx) o² and
(ii) the sequence {ax} converges to some x² 2
On the event that [.9 holds, criterion SCA) along with the conditions that y and
Ex og < oo implies suPkez, ||xx|| DC. Thus, we denote by U bounded open subset of dom(r) satisfying
kez, U kEt C..
By setting & = of
and E = ya in inequality (B3) of Lemma B.3 we have
Ex [| - =112] S (1 + ax)) (1|= x112 200 R& (0((++1) - ((x)))
(B.10)
(p +
+ (1 (1+a at
for all k E Z+ and x Rd. To prove the assertion (i) and (ii) above, recall the following elementary inequality:
+ exp(t) for all E TR.
(B.11)
Proof of assertion (i). Suppose on contrary that there exists > 0 such that
P lim inf ((Tx) > 6- + 3c > 0. k-400
(B.12)
The definition of o* implies the existence of é Rd such that
o² + 2 (()).
(B.13)
On the event that lim in ((xx) > o² + 3c, it follows from BB13 that
lim inf ((xx) 2 x(+) + 2c.
(B.14)
k
Note that we can pick some K E 24 such that
((xx) 2 iim ((āx) - and k-000
(B.15a)
Lo + +72) or Se for all k E 24 and > K,
(B.15b)
where the first inequality uses the definition of the limit inferior of (o()))), and the second follows from the fact limg ag. 0 implied by the condition Ex=1 of < c0. Without loss of generality, we assume that 2 2.
Fix any k E 24 with k > K. Then B.14 together with (B. 15a) yields ((5x+1) 2 and thus
Eg (0(*++1) x(²)] 2 e.
It then follows from the previous inequality and (0. with f that
Eg [|| - + 2| = (1 a [||= - a112 20ge + Lo + +2²) af)
By taking the expectation of both sides of the preceding inequality and applying the law of total expectation, we can derive
E [||
< (1 + a.)
E
-
-112] 20ge + Do + +22) az)
x (1 + a E bi
- -012]] axc).
17

---

Published as a conference paper at ICLR 2025
where the second inequality comes from [B.15b.. Thus,
0 s IE
||I
=113
- (1 + a (L
I2x =1[2 .aae)
s (1+ + at) (11+ 2/ (B [||-a=1 - [1]]] 16- - axt)
1 (1 + at) ((1 + oz
E [1-21-1 - -b1ā]] - -a-- 1 - ax()
k
s s (1 + at)
II (1 + at) E ||| 211
Oki
j=
==
which combined with B.11 and the assumption that Ei=l az
< 00 implies
Σ K=K
a
11
E [| - -=18]]
1
exp Σ of
E [| =1
k=
8
S
exp
ai
E
|||0K
=12
for all k E Z. and k 2 K.
Taking oc yields that
Σ
20
ak
1 S exp
Σ
DC
of
E
||
- 21]
(B.16)
e
k=K
Additionally, for each k E Z4, holds that
E& [|| - -11
< (1 a2) (1IZ -012 20x E& (0(ix-1) - -d(()
+7²) (1+ az) ox
S (1 + at) (1
104--113 --2 22nx)) (D..m.uLLFUU) +??) (1+ (g) az.
where the first inequality is due to (0.10) with x = â. and the second follows from (B.13)
and the fact that o()x+1) 2 o² Taking the expectation of both sides of the preceding inequality and applying the law of total expectation gives
E [[ =1 < (1 + at) (E [||= =12]] + 2aze + (pg.m (U)² + +3)) az)
Applying this recursively times leads to
E ||+11 - -
k II (1+a3)
< (1 + of) ||-|
1112 + 2c
oz)
1=1
1=1
j=i
+ 1o + +72)
II (1+a3)
1=1
j=i
k
+ of)
||00 ||m1- -812 +
ai + (p + 72)
Σ o
k
(1e1-ati - 2112+ 2c
#
< exp
Σ
2
Σ
as + (U +2)
Σ
1=1
1=1
1=1
and thus
E ||I>
- -+112]
K-1
K-1 2c Σ 1=1
K-1
(B.17)
< exp
Σ at
||
-
as + (p.m,
+22)
Σ
a
i=1
1=1
18

---

Published as a conference paper at ICLR 2025
Combining B.16 with (B.17)
confirms that
K-
+
exp
Σ
aj
B 2K
2112
k=1
1= k
Σ ar
||0|
1112 +20 2c Σ as + (p)m +
Σ at
0kk +
exp
k=1
<.00
on the event that lim ino p(īx) > 0² 3e. Then B.12 implies that
P
20 PP
lim inf ((Tx) > 00 + 3e 3e k0000
> 0,
which leads to contradiction of the assumption that E B.9 holds, lim + Φ(āx) = o* holds with probability 1.
k= 0g co. Therefore, the event that
Proof of assertion (ii). Since X' nonempty by Z assertion (i) derived above implies lim + ((x)) = o* e R. Then by using the definition of the limit inferior of {Ø(āz)}, one can easily deduce that there exists convergent subsequence {ő(RK))Ke of (d((+x) such that
lim kE
(Tx) = lim inf á (Tx) = =
(B.18)
k-+00
Fix any I E X", It then follows from (010)) with x E that
Ex || - -
< (1 am) (I = 20k Es (0(āx+1) - ((क) + (P.m..LLLU)) + af)
< (1 a ||ال - b1ž2 + (0 Lr) +²) oo (1 + az) for all h: E Z
which combined with Lemma B.4 and the condition Σ a < oo confirms that the sequence {||æ - ] converges to some himite value with probability 1. That is, for each X",
the sequence [||0 - Ø||2} converges with probability 1.
Combining the previous result with the fact that
lim on =0 0 and || - TR+ 112 S = = for all l: E Z, 80000
(B.19)
yields
the sequence {llT - Il|2} converges with probability 1.
(B.20)
The proof of assertion (ii) as follows:
If X {x*) is a singleton, then by (B.20) we have {1] - } converges with prob- ability Note that { is bounded and thus its subsequence {#x kee is bounded. Then there exists subsequence {0x heER of {ix heek such that {ēe bye converges to some
T E Rdd Since @ is closed by Lemma B. 1 (i), it follows from B..18) that
((²)= < lim inf & (xx) kEK
lim k
@ (āx) = lim
& (ix) = =
k
koo
which implies ((ā) o² and x". Hence, on the event that { xx [12] converges,
we have
lim lim || x kE | x = | xx x=1|2 0, k00
where the second equality comes from the fact that {+x converges to J..
Now we consider the case where X contains two or more points. Since ø is convex by Lemma i.) then X is convex and thus infinite. Thus, X" being infinite subset of the seperable metric space (Rd ,| (1-122), (12),, is seperable and we can choose a countable dense subset V of X For each V. by (B.20) we have {[|ã vll2) converges with probability 1, which combined with the countability of V leads to the conclusion that with probability 1.
the sequence {1] e1|2) converges for all v V.
(B.21)
19

---

Published as a conference paper at ICLR 2025
By following argument nearly identical to that in the discssion for the where X' is a singleton, we can obtain that there exists a subsequence {ēx JEEK converges to some I E X² Fix any O. The fact that V is dense in X implies that there exists V V such j oell2 < 6. Then, on the event that (B.21) holds, we have
lim lim || - U. vel12 k-> k-000
|
U. uel12 = || vel12 <,
where the second equality uses the fact that heek converges to Ā. By combining the preceding inequality with the triangle inequality, one can easily derive
lim sup || - 2 S lim || vell2 + ||0. - ø||2 < 2c.
k-+00
10+000
Taking to 0 yields that lime-soo || x||2 O with I E X
Therefore, the event that B.9 holds, there exists some x" E X such that
{ converges to x with probability 1,
which combined with (B.19) yields assertion (ii). This completes the proof of Theorem 2.2
Remark B.1. is worth noting that the proof technique adopted here differs from that of Proposition 3.8 in (Asi & Duchi 2019). For the case where all the assumptions in Theorem 2.2 hold, even if the accuracy parameter e = O, i.e.. subproblems are solved exactly, we cannot directly apply the argument in the proof of (Asi & Duchi [2119] Proposition 3.8) to deduce the almost sure convergence of isPPA. The reason for this is that when using (B22) in Lemma B.3 with I = E E X", we can only obtain
Es [| - x [ S p 2ाद
20x Es [0((++1) - x*) Ps ur of (B.22)
for all k E Z.... However, observing that the term appearing the right-hand side of (B22) is
Ex [0(I++1) 6") rather than Φ(xx) " we cannot apply the supermartingale convergence lemma
(see Lemma B.4) to conclude that
ax [d(xx)) - --1 < oo with probability 1,
which is the key to deriving the desired convergence results via the proof technique of (Asi & Duchi 2019 Proposition 3.8). Indeed, the proof technique provided in this paper is inspired by the proof of (Bertsekas) 2011] Proposition 9), with appropriate modifications deal with the case where subproblems are solved inexactly.
B.3 PROOF OF AUXILIARY LEMMAS
B.3.1 PROOF OF LEMMA
(C3)-(C4)) with p = 0. Note that Assumption and 3 correspond to (Davis & Drusvyatskiy, 2019
Lemma B.I then follows by argument almost identical to that used for (Davis & Drusvyatskiy Lemma 4.1). The details are provided below:
2019
(i) Suppose that Assumption I holds. Then by definition, function ò is proper and closed with dom(Ø) = dommr). It only remains to show that is convex. Pick some s S such that ((:a) ) is proper, dom(r) C ((=(f(=s)) and s(;s) is convex. Then dom(r) dom(yp 8)) and thus dom(r) is convex, implying the convexity of dom(Ø). Fix any x. y E do dom(r) and 0 E [0, 1]. Set or (1 f)y. We can easily deduce that
<<z) F(z) + +r(z) EamP [((;;)) + r((z)
[ f(z P(s) ((3) / (((z)))+(()))l
< [ (f(((;)) + +x(x)) + (1 (f(rs) +)
Js
= 0 (F(()) +r())))(z)))++) +1 (F
+r()))
+ (1-)))()))))
where the inequality uses Assumption |
Then ø is convex, which completes the proof of
assertion (i).
20

---

Published as a conference paper at ICLR 2025
iii Now assume that Assumption holds. Let U be a bounded open subset of dom(r) and fix any 2, y. E U. It holds that
[F(x) - F(u)
[f(;;) - f(vss)
8
Σ [((;s) - f(y:s)
s
[=w(()]|== ul12d P(s) Egur [[) | -yl2
$ L || ulla < (U)]] - yll2,
where the second last inequality uses Jensen's inequality. This completes the proof of assertion (ii).
B.3.2 PROOF OF LEMMA B.2
It follows from Assumption that functions (p St:m)) and (a;; Stam) + 24, | xx convex and or -trongly convex with respect to the variable x, respectively. Then the definition of T implies
3 (x; m))
||
JA
200k
(# Sk +
|
+
|| f2til12
for all E Rdd
20c
20
which completes the proof of Lemma B.2
B.3.3 PROOF OF LEMMA B.3
Inspired from the technique used in (Davis & Drusvyatskiy 2019 Lemma 4.2), we provide the following proof of Lemma B.3 Recall that the terms TI.UU and Pf.m.U are defined as follows:
Var (s))
and Pfmmu (VI [1+ 1)mru +1
MFU
Ega [s)
In the case where 1. B.2 follows directly from (Davis & Drusvyatskiy 2019 (4.12)) with т = 1) O. To extend this to the minibatch case, we employ the following result whose proof is straightforward and provided at the end of this section.
Lemma B.5. Let XI, Xm be independent and identically distributed random variables with mean [[ y and variance Var(X;) = o² for each = 1,... , If [[(()))] > 0, then
1 + (m 1)m (xx))))
E
X
0
112
where 1) A
Var(X,
[
By assumption, U bouned open subset of dom(r) which contains the sequences { and (- Fix any x E Rd and & Z
Proof of Lemma B.3
(i) Taking the conditional expectation with respect to FR-1 on both sides of inequality [B.I) in Lemma B.2 gives
Ex [|| - -4+1 || 22 ||-- 1
(B.23)
< 2ox Ee [T; + r(xx) F(āx+1;; r(0x+1)]
21

---

Published as a conference paper at ICLR 2025
Let t - v BBkl [k+1 xxll2]- Then we have
Es || Øx+1118
1
+ 12 2x112
2ax
E& [ (2; St: + r(x) [ skiT)) r((k+1)]
+ 200k Eg
L y (Sh) ||0x+1 2262
m
2aa E& [F(x) + r(x) - F(xx) r r(x++1)
(B.24)
27 Σ (Sk) i=1
m
+ 20k
ER
E& ||| 1x11
m
2ay Es (Z + r(xx) - F((x) r r(xx+1)l
+ (m 1MSU
+ 20
LF (U) tk-
772
where the first incquality comes from Assumption and the fact that Tye 2641 U, the second is due to the Cauchy-Schwer inequality and the last follows from Assumption 3 and Lemma B.5
By Jensen's 's inequality, the following assertion holds:
Ex [|lă++1 - xxllal S tx.
(B.25)
Using inequality B.24
we can deduce that
E2 [||= 1 11 th
|| 2x112
S 2ax Ex (F) + r(x) (F(#x+1) [U))|((RR+ xxlle) r(āx+1)]
+ (m 1)MFJU (F(U)tt + +aak|
m
S 20x Ex [F(x) + r(x) F((x41) r(tx-1)] + (PP.mLLLLLP) onti:
where the first inequality uses Lemma (ommmaB.I[ji)) and the fact that Ik Øs+1 E U, the second follows from (B.25 and the definition of Pf.mUU- Rearranging the previous result, conclude that Ex ||| Ts+1
||x - 2x 12 20x Eg (o(Tx+1) c(x)]
+ 2/ v LF (U) axle - lh
|| 2/ 1/ 2ak Eg [6(0x11) x(x)]
{2 P.Pij.m. m (U( aasl 12]
max EER_
|| zz 12 which completes the proof of (B.2).
20k E& (o(āx+1) c(x)] Pm.. Lf af..
Inequality (B.3) follows directly from the combination of B. derived in (i) and (B77)
mentioned before.
This completes the proof of Lemma B.3
B.3.4 PROOF OF LEMMA B.5
The first equality is casily established as follows:
27
)
2
m
1 m
m
E
Σ
x,
Var
X;
E
Σ X
m
m
m
1
Var
Σ Xi
+
E
[X:]
m²
111
i=1
1=1
m
1
Var (X,)
+
E
[2,]
=
0² + 22
m
m
m
1=1
22

---

Published as a conference paper at ICLR 2025
where the second last equality uses the fact that the random variables X1, Xm are independent.
Note that o² + uº = Var(X1) + (B[X,])² = [[(X)] >
Then
Var(X1) =1 [[ [ (x)
1 ==1-
and
+ (m - 1)/ E((x))
0
(1- (
m
m
which proves the second equality and completes the proof of Lemma B.5
C PROOFS FOR THE RESULTS IN SECTION 2.2
In this section, we establish the convergence rate guarantees for isPPA in terms of the expected squared distance to the optimal solution set. Recall that function şø is defined in (2.3) follows:
if 3 + 0, if B = 0,
(=(())
ln(t)
for all E R++. To prove the convergence rate results presented in Section 2.2 following three technical lemmas, the proofs of which are deferred to Appendix C.4 for brevity.
we need the
Lemma C.I. Consider the scalar sequence {6x} satisfying the recursive relation:
8x+1 S d1ob + 02 for all E Z
for some constants 01 (0, 1) and 02 E RR. Then holds that:
8х S a 18 + (1 a1)= for all k B+.
Lemma C.2. Consider the scalar sequence { satisfying the recursive relation:
8k+1 S exp(=a;au)0 + aza for all & E
with ar =ak for some constants (0, 1), ag R++, a1 E E++ and a2 E R.. Then
holds that
8u S exp (-ajaosi-s(())
1 ko
4 Pazaeexp (-0100x1- 51
(-apoo))))
for all k E Z4.-
Lemma C.3. Consider the scalar sequence {8k} satisfying the recursive relation:
1
a
8k+1 S
8y a2
for all k E4
It ajas
ajap
with oy -a for some constants og R4+, a1 IR++ and a2 R4. Then it holds that
46,
4as(2tarao)aa
2a 24aia0
if a00000 < 2,
I4:000
2 2-0100
64 <
481
40za0 &
In(k)
a1 2,
20
S4or +
if aaao > 2.
I+aya0
41ag
Let E (0, 2) be an arbitrary scalar. Recall that the term U. (ap) defined as:
(am, e PI.m,uL(UU) + (1 20 (1 + 8C, sc100)
72 for ag E R4+.
(2 1 s)c1
As mentioned Section 2.2 if exists, denotes a bounded open subset of dom(r) which contains the sequences {*R) and [kk.
23

---

Published as a conference paper at ICLR 2025
C.1 PROOF OF THEOREM 2.3
On the event that suPRez, | 30, similar to the proof of Theorem 2.2 we utilize the Cauchy-
Schwarz inequality combined with criterion (SCA) and the condition e yag to show that supRez_ ||قx|| oc. Consequently, there exists bounded open subset of dom(r) containing
the sequences { } and {.x}. We denote this subset by U by default. Let 6% & Eldist( X x²) for each & E E+. The proof of Theorem 2.3 proceeds by establishing the validity of the following deterministic recursive relation:
Claim C.I. Let Assumption 4 hold, and let { be generated by isPPA (Algorithm) 7 with step- sizes {ax} and accuracy parameters Ej = -a for all k E E. with y E R4. Suppose that the sequences {ax} and } contained in some bounded open set U dom(r). Then for all E Z4,, we have
6k+1
1
8x + CG,,U,a (ak)- 1 + scias
at
for all e Z4.
1 scias
Assuming that the above assertion holds, we immediately have
1
aB
8k+1 S 1 s0100
6ā + Cf,,,lerr (au)- 1 + sc100
for all Z+.
Taking (1 + +088 00)100)= and 02 = =2= U, (0o) I+s0 in Lemma C. leads to inequality
(.8) in Theorem 2.3 The only remaining task is to prove Claim deferred Appendix C.2.I
C.1 For brevity, its proof is
C.2 PROOF OF THEBREM 2.4
Use the same notations as the proof of Theorem 2.3 and set 6g & Eldist(rx: 2 for each k E Z4. Now prove the results for isPPA with diminishing stepsizes as ank- where
| E (0, 1].
Then
0 <<a ag S ax+1 S ap for all & E E...
(C.1)
On the event that supkez, || < oc, similar to the proof of Theorem 2.2 the combination of
criterion (SCA), ; the Sahwhy-Schwarz inequality, and the condition conclusion that suprez, || 2o. We can thus use U to denote a bounded open subset of dom(r) containing the sequences {m and {#x}- This confirms that all the assumptions required
y S 700 leads to the
in Claim C.I are satisfied. Fix any A E Z.,. Note that C,,,,U,., (-) is nondecreasing on R, and thus by (C.T). we have
Comuuo (ax) S C.m.Uooo (ao).
(C.2)
Then, follows from Claim C.I that
ax
8x+1 5
52 + Cy,m,U (ax) + 801
1 + sc
a 1 SC1
òz + C.mmm.U.rr (0o)
(C.3a)
+ OFk
sc1ak
8y +CS,m,Ueen (ao) 1 8C
a²
+ 8C1
801
ot
< exp
1+scja, 5% Cym,lleeryy (ao) + Sc ac
1 + SC 05k
$ exp
8C1 Okk
8x + C.,m (oo) - o
(C.3b)
1 + sC1 Okg
where the second inequality uses the relation because of inequality (C.1
C.2 the third follows from B.1l and the last holds
24

---

Published as a conference paper at ICLR 2025
Proof of assertion (i). If E (0, 1), by taking d1 =sc, s0100) and 0g C.m.UU... (ao)
in Lemma C.2 we can easily obtain the estimate (2.9) from inequality (C.3b thus confirming assertion (i) of Theorem 2.4
Proof of assertion (ii). As for the case where = 1, the estimate (2.10) follows from (C.3a) and Lemma C.3 with ai 8c] and 02 E S.m.U.ou.. This verifies assertion (ii) and thus completes the
proof of Theorem 2.4
C.2.1 PROOF OF CLAIM
only remains to prove Claim C.1 We present the detailed proof as follows: Fix any E E..
Setting proj( X²) in inequality B.7 yields
dist (IK+1,, )²² $ |
proj (1x+1, x21
s
+
||*++1 - proj (#*+1,,**)) x12 t1+
+ dist (#R+1, x²12² + (1 (1+ +)
and thus
Eg dist (#x+1, x²1 1 1 (
Ek dist (Tx+1, x²2 + +1++
(C.4)
Note that the sequences {æg] and { are contained in U. By setting v = proj( x²) in in- equality (B.2) of Lemma B.3 one can conclude that
Eg dist (#x+1, x
|| proj( x11
$ || proj( x )|2 2az Es j6 (xx+1) - 601 + P LF of
< || proj( x' )12 2c E& [dist(Ex+1, x²) P L
= dist (zx, x²3² - 20 Ex [dist(fx- )² + (U oz
where the last inequality comes from the quadratic growth condition in Assumption Rearranging the preceding inequality yields
Ex dist (#x+1, )²
S
dist (Ik, (Ix, x²1)² + Uf.m,uLL(UU) (U)2
of
(C.5)
1 + 2010rk
1 20
Applying (C.5) to inequality
C.4) with
1tsgay and c 70 and using the fact that (2-s)ejag
1 )
1
+ 2cjak
1
1 2c
+ 80
1 20,
1 SCI ag
1 + 2c10k
(1 + 2+20aa)) (1 +1++ sc1 a
(1+ a
at
(2 s)c1ak
(2 12-8) s)c
+ SC100
we have
Ex dist (I 200
dist (Ix, 221)2 + (f,m,LL(UU)) + (1+ 2c) (1 SC)(2) 72
1 sctas
(2-s)a,
s01a
Taking the expectation of both sides of the previous inequality, applying the law of total expectation and using the definition of Cf,.,..iaan defined (.7). we can immediately derive Claim C.
C.3 PROOF OF COROLLARY 2.5
For the case where B 1, the dominant term of the bound (2.10) obtained in Theorem 2.4 can be readily determined. Thus, we only need to check the case where / (0, 1). Note that the bound 2.9 given in Theorem 2.4 can be written as
C2 E [di ) s Ciexp(-Assi-o(1) + b
+ Czexp (-Agk S1-20 2 (C.6)
25

---

Published as a conference paper at ICLR 2025
where C₁ R4 and A, E R++ for i 1,2,3 and j = Since B (0, 1), then
Ciexp(-A1si =0( (B²"-*) < < (K
0
for sufficiently large k. where bn (0,
ii If 3 E (0, }),, then 51-20 } - O (kt-28) by C.7 (see Lemma C.4 below). Note that
B.11 implies exp(-() S I=f for all R..
Thus we have
Czexp (-A2k
k
s o
(1-8) k2=25) O (1=-)
29
2
(ii) If 3 2' then
Czexp (- (-A2h! 51
(2)
k 0
b In(k)) s (k
2
for sufficiently large k, where b2 E (0,
(ii) If 3 E ( 1). then ())) S 23-1 by C.7 and thus
k
Czexp (-A2h² 51-23
for sufficiently large k, where by E (0,1).
Combining the previous results with (C.6) verifies the estimates for the case where B E (0, 1), thereby completing the proof of Corollary 2.5
Remark C.1. The convergence rate results in Theorem 2.3 and Theorem 2.4 provide insights into
how the minibatch size m affeets the performance of isPPA. In general, increasing the minibatch size improves the convergence rate of isPPA. Specifically, from equation 2.4 we have
Ns E [0, 1] and Pf.mU = (v
NF.U m
+ +1)
indicating that PU is a nonincreasing function of m. Then, from the definition of Č C...UUee in (2.7p. C.m,,Uee.,)ay decreases with m for a fixed a. This leads to the following observations:
Neighborhood shrinks when using constant stepsizes. For isPPA with constant stepsizes, when increasing the minibatch size m, the linear convergence of {xx} to neighborhood the optimal solution set improves, as the neighborhood shrinks due to the noise term in (.8 from Theorem 2.3 being proportional to Cy
Coefficient decreases when using diminishing stepsizes. For isPPA with diminishing stepsizes, when increasing the minibatch size m, the sublinear convergence of (xx) im- proves in the sense that the coefficient of the dominant term decreases. For instance, as shown in the proof of Corollary 2.5 the dominant term in (.9) from Theorem 2.4 is the second part O(k-3), whose coefficient is proportional C (am.U....)(aa)
While larger minibatch size improves the convergence rate of isPPA, it also increases the com- putational cost solving the subproblem. Therefore, a trade-off must be considered when selecting
C.4 PROOF OF AUXILIARY LEMMAS
only remains to prove the auxiliary lemmas presented before. Note that the proofs of Lemma C.2 and Lemma C33 leverage techniques similar those employed in the proof of Theorem I in [Moulines & Bach 2011). We first present the following lemma summarizing several useful in- equalities to subsequently employed.
Lemma C.4. The following assertions hold:
26

---

Published as a conference paper at ICLR 2025
(i) Let 3 E R. Then the function Sg satisfies cs(1) 0.
if < 0, if 0.
st(t) -
(C.7)
for all t E R++, and is nondecreasing over R++. (ii The following inequality holds:
k + 22
for all k 2,.
(C.8)
k
Let 3 E R and j, ls E N with
j Then
23 (s (k+ 1/ + 1)] 2
1
Σ
1
5k+1
s341 +1)
i=1+1
if320, 0,
(C.9a)
1B+1 + - -53+1 + +1) v Σ
1
15s+1 (k: + +1) - -53+1 + +1]]
25
i=j+1
<3.
(C.9b)
Moreover. jf E Z4 with k 2 j + 1, then
SB+1(k) S (j) v
18 s (3 2) - (kk) -841
is > 0, (C.10a)
t=++
8 S sk-1(k) s3+1(i)
1 S 0. (C.
(=+11
(iii) Let 3 E (0, 1). Then the following assertions hold:
(1 +) < 11 St for all (-1,
(C.1la)
J0 S (t(t) 58 ( for all t R++.
(C.11b)
(iv) Let R4+ and define h(t) nondecreasing over R++.
I-exp(-atj for all R... Then the function h is
An elementary proof of the previous lemma is deferred to Appendix C.4.4 for reference.
C.4.1 PROOF LEMMA C.1
Fix any & E4. Applying the recursion & times yields that
1 1- of
81+1 < 00 + 02 Σ
a2
(1
< 6 + a2 (1 a1)
where the equality is due d1 1, and the second inequality follows from the facts that (0, 1) and 02 E RR This completes the proof Lemma C.
C.4.2 PROOF LEMMA
C
Fix any k Z4. Applying the recursion i times yields that
4 -01
8x+1 5 exp
-01 ai
Σ
81 +
2
exp
Σ aj
(rBound)
1=1
1=1
#=
27

---

Published as a conference paper at ICLR 2025
Define
11 _ exp
aa1 Σ
as
and
1 -
a
exp
-1
Σ
aj
(defTerm)
im1
j=x+1
Note that 0g agk
for all l
24 with 3 E (0, 1). Then it follows from (C9b)
with that
= exp -0100 exp
Σ
S exp (xpp--100sssppp 2 + + s
(IIBound)
1=1
exp (-0100
51-3(k + 1)),
where the last equality uses the fact that 51 (1) 0 implied by Lemma C.4 (). It only remains to obtain upper bound on 1g. Set m
k-1
We can easily verify that
2
I m + 15 k+1
(C.12)
2
2
For simplicity, we denote by Di=j" Ok, the term I2 can be written by
0 for j. k E 24 with > k. Then by using the definition of
1
eexp
-g000
Σ
aeexp
01
aj
A
2
(1)
12
j=++1
i=++1
j=i+1
By assumption, we have (0, 1). Then the term I can be bounded by
m
1
af exp (- 0100 (51- + 1) 5- 1)))
exp
(-r1a0 (51- 1) 51-0(m + 1)))
Σ
a
1=1
<
+ 51-0(k 00jD0 exp
-I
k k+1
Σ
2
2
1=1
m
exp
0100
(k + 1)2-3) Σ
a
2
1=1
I 4 agexp
(-
0100
(k: + 1) 1)
(51- (m +1) -1-
2
< 4 agexp
0100
(k + 1) -)
k: k+1
S1-20
2
2
where the first and second last inequalities follow from C.9b). the second is due to Lemma C.4
the third and last are due to Lemma () and inequality C.12) and the fourth comes from C.I1b For the term 1/2
we obtain the following bound:
(2)
12
axexp
aj
1=++1
jmitl
a
exp
01
aj
exp
01
aj
exp
(g
i=m+1
j=1+1
j=i
<0m+1'
04
exp
Σ
Oj
exp
1 exp
a1a;)
i=m+1
j=++1
J=1
k
Qn
< am+1 1 exp (-ajan)
exp
-a1
0j
exp
-11
0j
1=++1
=++1
|=1
28

---

Published as a conference paper at ICLR 2025
0g
0m
1 exp
-11
aj
exp (-0100)
jmm+1
0m+1
ag
0
(m + +1=
exp (-a1a0)
exp
(-a100)
ag
k
-9
a
1++1 1 -9
k
1 exp (-aj00)
(
exp (-a100) 2
+
0g
2
k - 1
-B
exp --aaa)
4
where the first inequality is due to (C.I), the second follows from Lemma C.4 second last comes from (C112) and the last holds by CC.8
iv)
and
C.1
the
8 Thus,
12 S 4 aexp
0100
(k
1) 1-
-1-28
k +
2
2
(12Bound-11)
4
(k + 1)
exp
01 Qn)
Combining (rBound) with (defTerm).
[IBuund) and [2Bound-I1] proves Lemma C.2
C.4.3
PROOF OF LEMMA
The proof of Lemma C.3 differs from the proof of Lemma recursion i times yields that
C.2 because now B 1. Applying the
a
k
8k+1 z
81 + a2
(rBound')
+ a1
0i
+ araj
j=i+1
Define
k 11
k
and 12
(defTerm')
1 + 010;
1 + 010g
1 1 ajay s=i+1
i=1
i=1
Note that ag = agk for all & E E4 and that
a100 < apaii for all E, and 2 2.
(C.13)
With the previous observation, we can establish the following bound on I
0 0g0
=
+ 010;
1 a10gi-1
i 0100
i 01
2aja0
20,00
i-1
(C.14)
2i ajani
0100
20 Opp
< exp
:-1
for all i E E, and 2,
+ 0100
where the first inequality follows from C.13 and the second is due to B.11 derive that
Using C. C. above,
k
1
2a axo
1
exp
+ 0100
+ 0104
1 0100
2 +
1=
1=2
1
2a Co
<
exp
[so(k + 1) - -00(2)]
+ 01000
2 + 4100
(IIBound')
Za1 og.
1
2a Co
k + 1
))
2
240100
exp
In
0100
2 + 0100
2
+ 0100
1: k+
2o
1
240100
1 20
k +1
29

---

Published as a conference paper at ICLR 2025
where the second inequality is due to (C.9b with
1, and the last uses the fact that
20100
2.
(C.15)
0100
It remains obtain upper bound on 12. By using
C.144 again, easily verify that
k
20
exp
+ a1az
2 + 0100 jmit1
jmi+1
20 20
I exp
2 + 0100
[50 + 1) 1 + 1)1
(C.16)
20100 2-0100 00
201 In
k+1
i+1
exp
+ 0100
k +
for i = 1, ... .kk
where the second inequality comes from (C.9b) with j i. Then
k
2a
1 = + aia;
II
a
i
1 ajaj
k ++1
i=1
1=i+1
i=
= ag (k + 1) 210190
cep
2-2 (i 1)
2T
201
23j 20
201ap
-2 it 1
ag (k + 1)
214190
(i + 1)
210190
(C.17)
I 4ag (A: + 1)
2ny
Σ
(i ( 240100
-2 4aa (A: + 1)
2ng 240100
2 og
-2
< 400 (k: + 1)
2=a og
20j00
20100
(K +
-1 (1)
2+0100
20100 T+nyog
4a + 1)
2ag 2401
1)
where the first inequality follows from C.16 the second last is due to (C.8) and the last comes from (C.15) and (C.10b) with j = 1. Using the previous inequality and the fact that
20
@1 0g < 2,
2 + 0100
2aj00
010g 2,
(C.18)
2 + a1 Ckg
2a
01 0g 2,
+ a100
we can deduce from the relation C.7 in Lemma C.4 i) and the definition of function
ag 214140
given (2.3) that the following assertion holds:
og 240100
4(2+ta an)
if 0100 2,
2 aj ao lu(k+1)
(12Bound-e1')
4 k+1
if a ap 2,
4(2+a1 (a)
if ffaj0p > 2.
Combining (rBound' with (defTerm
[[Buundd and [2Bound-e1* proves Lemma C33
C.4.4 PROOF OF LEMMA C.4
By using the definition of the function So given in 2.. Lemma C.4 can be derived from elementary calculations, shown below:
30

---

Published as a conference paper at ICLR 2025
Proof of assertion (i). Fix any 3 R and R4+. Using the definition of <æ given in 2.3). can easily verify that (1 = and that
if <,
co(t) =
if > 0.
B
Note that the derivative </((1) 10-1 > 0 for all / E +++ Thus, the function sa(+) is nondecreasing
over +++
Proof of assertion (ii). Note that C.8
holds since + :/2 s 2 for all & E 2+. Let j. k E N such
that k 2 j j+1.
Suppose that B 2 0. Then
1
Σ
(i+ 1)9
i
8
2
1
(i 1)
(i+1)
2
1=j+1
i=j+1
i=j+1
1
k
1-1
1 pktl
( t
(1+1)
t tt = 28
2
2
i=++1"
i=++1
j+1
1
[s3+
(k +)
S8+ 1 1)],
2
where the first inequality follows from C.8 and the fact that B 2 0. Similarly,
++1
Σ
Σ
dts
Σ
t
ij+1
ij+1
i=j+1
k+1
t
c841
53+1 + 1),
j+1
which combined with the previous inequality implies (C.a).
Now consider the case where < O. We can obtain
i+1
i+1 dt = (0+1
dd
Σ
-3+1 (0 + 1),
i=j+1
i=1+1
i=メ+1*
and
8
i
8 =
(i + 1)
<
(i
1)
i+1
2
imf+1
imj+1
imj+1
k
(1+ 1) <
t
2
23
SS+ (k + + - + 1)]
23
where the first inequality follows from (C.8) and the fact that B < 0. This completes the proof of (C.9b).
Now assume that j, E. with & 2 + 1.
If 3 < 0, then we have
Pats Σ I
tddt = 1
* &d = (k)) S3+1(1),
Σ
Σ
i=1+1 1-1
1= 1=1+
that is, (C.10b) holds.
31

---

Published as a conference paper at ICLR 2025
If 3 > 0, then
R-1
Σ
8 + k - S (3+1(k) - s3+1(i) + k. -
(C.19)
1=/+1
where the inequality follows from C.9a). The fact that and 2 12 2 implies
(3 1) 15a+1 (k) - se+1(i)] - (R. - -j²)
(k - -k²) -
1. (k: 1) + 5
k9 (k- 1) + j k) = -kk² jo) (k-1)
that is,
k. - S (1+ [S341 1 55+1(1))
Combining the preceding inequality with (C.19) yields (C.10a) and completes the proof of assertion (ii).
Proof of assertion (iii). Note that E 1). We first show (C. holds. If -1 then
holds trivially. Thus we consider the case where E 1,). Define g(l) A (1 1) for any
t T (=), Then g is twice continuously differentiable with
g(()) = 3(1 + 1)8-1 and g"(t) = ((3 - 1)(1 + =- <
for any 1 E (-1, 20), which implies y is concave over (0), Thus, have
(1 1) ,(t) - ((0) (0) - = 1 for all t E (-1,
which completes the proof of (C. Ta). Then we prove C.1lb) by using this result. Fix any E R++- It follows from the definition of Sa given in (2.3 that
(=(1)= - 5,3
1
8
8
B
111
10-11-
(1
2
1
8
(1
3
/
9
2
2
where the incquality comes from (C.Ila). This completes the proof assertion (iii).
Proof of assertion (iv).
This result follows immediately from the fact that h is differentiable over
R++ and
h((1) 1- expepppac 1 (aexp(-al)) 1 (1 al) exp( 2 0
(1
(1 exp(-at))
for all & E R4,, where the inequality uses B..l with t = at. This completes the proof of Lemma
D PROOFS FOR THE RESULTS IN SECTION 2.3
In this section, prove the main results the convergence rate in terms of the KKT residual outlined in Section 2.
D.1 PROOF OF LEMMA 2.6
Fix any E IRd. Recall that X arg minger ((x). By assumption, we have @ is proper and closed convex. Then by using the characterization of the proximal mapping prox,(-) Rockafellart 1976b (2.2)), one can derive the following relation:
X*
I E O0(x")
x (x)
$ I prox -xprox,(x)) 0.
32

---

Published as a conference paper at ICLR 2025
Thus, combining the preceding equivalence relation with the triangle inequality and the nonexpan- siveness of the proximal mapping p RRockafellar 1976b Proposition I(c)) gives
æ - prox, s (z)]11
= || prox, - (I prox, (T)xx(T))ll
S || ø|12 + ||prox((z) prox (T)
$ 2 2| Ø|l2 for all X",
which implies
| prox p (zr)l S 2 dist (z, X*)
and thus completes the proof of Lemma 2.6
D.2 PROOF COROLLARY 2.7
Fix any & E E4. It follows directly from the Jensen's inequality and Lemma 2.6 that
E [|TT prox (1x))l12 S
E [| proxs (1x)
S 2 E dist (IR, X²)].
Using this bound on the expected KKT residual, all results in Corollary 2.7 follows immediately from Corollary 2.5 proved earlier.
E PROOFS FOR THE RESULTS IN SECTION 3
In this section, we present the proof of Proposition 3.1 shown in Section S
E.1 PROOF OF PROPOSITION 3.1
Proof of assertion (i). Denote the sample space S [n]]. For each s E S, define
[(x; 8) A | pall for all x E Rd.
Then, the function F(x) can be expressed as the expectation Ex-p]f(x; s)], where P denotes the discrete uniform distribution over S.
For each & S, function f(: 8) is real-valued, locally Lipschitz and 2-strongly convex, which implies F is locally Lipschitz and Assumption holds.
Note that function r(-) is real-valued and A-strongly convex. Then p(::s) is real-valued and (2 + X)-strongly convex for each s E S, leading to the (2 + X)-strong convexity of over Rdd Thus, Assumption and hold.
The existence and uniqueness of x follow from the strong convexity of d. Additionally, it can be readily inferred from the optimality condition for differentiable convex functions that
0- vo(=')=
2 Σ n1
(x" - ps) + xxxx
+
x
Σ P4
2
2
1=1
Then, the optimial solution set X fxr) is nonempty, and
E Eaw [Vp(("
pill σ <0,
which proves the first and second conditions in Assumption 2 By Remark 1.2 holds and thus the last condition in Assumption 2 holds.
I.I
we have
This completes the proof of assertion (i).
33

---

Published as a conference paper at ICLR 2025
Proof of assertion (ii.. Fix any & Z.. By the definition of 2x+1 and the optimality condition of differentiable convex functions, we can obtain
2
Ik+1 = arg min vER
Pst
+ ||
|
mk
m
20r
(E.1)
20k
1 m
Psj
2k- (2
(2 + Ajoc +
m
A)ex +
Recall that Σ = maxie[1] l1p:ll2. It follows from
E.1 and the triangle inequality that
200
|ka+1ll2
Pst
(2 + 1)ax +1 ||
(2 + A)ax 1
m
2
i=1
20c
Σ +
11xll22-
(2 X)ax +1
(2 + A)ax +1
Applying the recursion lo times yields that
(2 + A) am + )
| S
|211|2 +
Σ
20s II
E
2
2) au
+1
1=1
1=1
m=1
k
< |111122 +
Σ 20z
II
E
(2 + X) am +
1=1
m=
(E.2)
(2 + A) am +1 ).5
|| lll
2Σ
< || 12
<
||00 || E,
2 2
X
where the equality comes from the following relation:
20
2a
II
1
(2+ A) am +1
(2 A) ai
(2+ 2) am
1=1
1=
m=1+1
k
k
k
201
1
(2
+ X) 04 +1
(2 + A) am +
(2 + )) am +
1=1
12+A)a++
Am=l+1
m=m
2
II
II
d:
2+X X
(2 + A) am +1
(2 am +
2
1
2+X
2
(2+
am
m=1
Assertion (ii) follows directly from E.2 and the trivial observation that ||l| llz S ||011122 + E.
Proof of assertion (iii).
Recall that ²² 1 Ey lp, 1 "E Pr 12. Then o² 2 0 and
0² =
Pj
p for all j E [n]
pi = Ps for all i,j E [n]]
from which we have の² 0 according to the assumption that Pi * Pjo for some in # jo [n]. Fix
any le E Z.. It follows from E. that
20y
Ik+1
Pst
+
34 x²,
(2 + X) +
(2 + A)a +1
34

---

Published as a conference paper at ICLR 2025
which implies
Es |1x+11 - -x"11]
Es [[ x 2k+1 x²'
4a
Ex
Ps
200
Bk
1
Σ
Pst
1(2 + A)ar + 112
[(2 + A)aa + +1
m
i=1
i=1
201
E2
Pst x0*
(2 + ))0x
(E.3)
1=1
20
|
(Tk x²)
+
(2 + AJOE + 1)2
EE
Tke
Psj
+
[22 + A)CI + 1]2
(2 A)aa +1
200
1
(0", (.
1Ex
Pis
(2 + 1)co 1 ||=0 11=="12--
(2 + A)ax +
m
1=1
Note that
1
n
2 + X
Eg
Pst
Pj
for all i
[m]]
and
Eg
Pst
2
Pj
x² (E.4)
m
Then we can prove the following two assertions:
(a)
It follows from
E.4) that
1
2 2 X
2 X
Pst
Jk
Pj. Tk
x,, Ik
(x),
m
2+ X
x*
Pjs xx
2 x
1 1
j=1
which combined with E.3
yields that
Ex
||aa+1
4a7
2
(2 2) az
-1) (EET.
Es
Σ
Pst
+
[(2 +))ak
+ 1]²
(2 + A)are +1
(2 + A)ax +
iml
|| 12
2(2 A)ock
||0011
[2 + A)ar 1]²
(2+ A)ax +
| 1/- (rrk, x²) ||a0
4a
1
+
Es
Σ Pst
[[2 + A)ax + +1/2
[(2 + X)ax + 112
m
+ (1 2(2 2)ax
1
1|00112
(2 x)ax +1
[(2 A)ax 112
27
1 x11 112
4
1
+
X
2
+
Ex
PSs
[2 Ajar + 112
[[2 Alay + 1j²
m
2
(b) Using E.4 again, one can derive that
27
27
1
2
1
Ps
Eg
Ps
Ex
Ps
2
t=1
1=1
1=1
35

---

Published as a conference paper at ICLR 2025
27
m
m
m
1)
Eg
Pst
Es
Pst
EE
Pst
En
ps;
m
m
m1
m
1 m
1
n
σ²
Ek
Pst
Es
Pst
Ex
Pst
Pj
772
T1
m
j=1
where the third last equality holds because the random variables St. dent and identically distributed, and the last comes from the definition of
Sk are indepen-
Assertion (a) together with assertion (b) above leads us to the result that
E& || x²1[]]
x x" 11
a² [(2 + A)oa + 1|²
4a
+
(2 + Ajoa + 1|²
Taking the expectation of both sides the previous inequality and applying the law of total expec- tation gives
x11 [2 + \)ay + 1]²
E 1 x
[kk+1 - x=1
+
4
(E.5)
[(2 + A)aı
1]
m
Denote by 81
| x² x²112- Applying the recursion k times yields that
E
|
- =211/2
II
4
1
40
[I
(E.6)
81
+
at
(2 + \)an + 11²
[22 + a)am + 112
1=1
mm
holds for all & Z..
First consider the case which og 2 ag for some ag E R... for all & E R__.. Then is differentiable over R++ and
Define l((t) A [2+X]c+I
ht(t) = (2 + A) - (2 (2+
>0 for all t R
[(2 + A) + 1]2
(2 1)++1
that is, is nondecreasing over Rt+. We can thus obtain from that
E -11411--011 N [(2 AjaR
4a
0²
a&
2 40
+ 1
m
(2 + A) +
m
a
402
40 2 2
(2 + A)oo
+
m
[2
A)ao 1]
holds for all le E Z..
Now prove the assertion for the case where as ark- for some og R_+ and
3 E (0, 1]. Observe that
[22 + a)am +1²
of
[2 + Aaa + 112
[(2 a)am + 11²
m==++1
k
1
Σ
of
II
(2 + A) 0g
(2 + A)am +1
m-=1+1
36

---

Published as a conference paper at ICLR 2025
where the inequality uses the fact that ap ag for all & E Z+. Moreover, the last term is bounded below by
Σ 1=1
of
II \m=/+1
(2 + A)am +1
(2 + 1)am
(2 + A) +1
(2+x)a++I
Am=1+1
m=!
(2 2) af + ta
k
k
II
2 + A
(2 + a)am +1
(2 + Namm +
Am=1+1
m=
ai
1=1 + X
(2 + Ajam +
(2 + a)am +1
mm=/+1
m=/
II
2
(2 + 1)am +1
(2 1)am +1
\m=/+1
m=!
k
ak
0kk
1
1
2 2+
2 2 X
(2 + 1)am +1
(2+ N)a
m=1
0
: K
2+ X
(2 A)ao +1
(2
A) 20
where the second inequality is due to the fact that ai 2 ag for all E Z4 with I and the second last equality comes from the fact that a1 0g implied by the definition of the stepsizes. Combining (E.6) with the previous two relations leads us to the conclusion that
4a &
E |1 11
II
m
+ A)am +13
m=!
4
a
2
k 8
[22 + X) 00 + +1s
(2 A) on
4
m [2 + Aaao 1)at -
holds for all ls e Z..
This completes the proof of assertion (iii) and thus proves Proposition 3.1
F DETAILS OF NUMERICAL EXPERIMENTS
In this section, we provide the essential details required to implement the numerical experiments described in Section 4
LASSO LINEAR REGRESSION MODEL
Recall the Lasso linear regression model defined as:
min #E
L'Lasso (x) A ||Ar 6112 A ||
Solve inner-loop subproblems. Denote the sample space S by the finite discrete domain [n]] Then, when using isPPA to solve Lasso linear regression model, the inner-loop subproblem (1.3) iteration & can be formulated as
A1 |
min zERd
|| A [Asumm.. I - botin
||
x 11
(F.1)
2m
7
20
37

---

Published as a conference paper at ICLR 2025
where Asg.m. ; denotes the submatrix of A consisting of rows indexed by S and bsg. denotes
the subvector generated by the elements of b indexed by s. Set Y1 - X1 and dg _ ez Then F.T can be written as
m
min H (Astmm..)
+ +p(x)= +
|| Txll
200
(FF2
1 where (v)) - 2
2
b spm for all y E R and p(æ) 2 A1 I for all x E R
In effort obtain the next iterate T4+1 satisfying the stopping criterion (SCA). propose the following claim and defer its proof to the end of this section for reference.
Claim F.1. Consider the subproblem (22 at iteration of iPP (Algorithm) with stepsizes {ax) and accuracy parameters { Define
(EE) & (E) + +p"
prox
+
0*k 2
2k
A
prox
- Apmm AAmmm.)) for all E R="
ōck
trg
Örk
where H. and pd are the Fenchel conjugate functions of H and respectively. Fix any l E Z If Tk+1 is obtained via the following update rule:
pt Uk+1 prox
Ik
A Ag..
Sx+1
with
3%
āg
Ex+1 R3 arg min EER"
VT(EE
where
I/V (Ex+1)ll2 S
(F.3)
Vāt
Tk+1 Tk ās
(A]) S5tt + uo+1) = proxaup
IK âsA (k+1),
| prONau7(:s! ) S S6b
then 2441 satisfies the stopping criterion SCA), i.e,,
Note that
H (E) sup {gy (y))
1
Ikl1 + (bst.. k) for all R"
(F4)
y
F.1 is 1-strongly convex and continuously differentiable on Then the function V defined in Claim Imm with
I A Agim, prox g
IR A -.) )s)
VV((E) = V (H) Ō. A spmm:
OA
= + betim
Astm m PrO
ER ou mpmm
for all & E IR...
Therefore, utilizing Claim F.1
can obtain E by applying the semismooth Newton (SSN)
method (Li et al. 2018 Algorithm SSN) to solve the minimization subproblem in F3
Obtain an approximate optimal solution. For each data set, we first apply the semismooth New- ton augmented Lagrangian (SSNAL) method (Li et al. (2018) to solve problem 44.1) and obtain an approximate solution i" satisfying the relative KKT residual Thel, < 10 where
(5* AT (At* 1 b))
prox I1-11,
Lasso
+
|
l2 + A (Aa* - b) ll
Then thLasso (x*) can be taken as an approximation of the optimal function value. For each trial, we run isPPA to solve (.. and obtain an approximate solution 1* such that the relative gap d 10-3 where
|VT (8*) a/so (T*)
S
1 | (ī+))
Then i* is the desired approximation of the optimal solution, which { converges almost surely.
38

---

Published as a conference paper at ICLR 2025
Numerical results real data sets. The real data sets are taken from the UCI data repository (Chagg & Lin 2011) and the original features of the obtained data are expeneded by following the settings in (Li et al. 2018). We test real data sets abalone7 with (n, (4177, 6435) and space-ga9 with (n, d) (3107, 5005), and set the regurlarization parameter A1 Ae || bll
with >, 10-2 2 The KKT residual with respect to the Lasso model is defined by
proo 1-l1 (x - A (Ar - -6) for all x E R4.
Maass (x)
(F.5)
Given that E E X if and only if z prox ||-1| (7 A (AE b)), it follows that Masooo (x) 1 (2 [1ll))disttarr X"), ensuring the applicability of all results from Corollary 2.7 to YJLassso As illustrated in the top row of Figure the convergence curves are analogous to those the synthetic data, where the asymptotic convergence rates for the squared distance to the optimal solution set and the KKT residual are Ok--8) and (k--//2), respectively.
F.2 ELASTIC NET LINEAR REGRESSION MODEL
The elastic net linear regression model is presented follows:
A2
min #R
Velastic (x) A 2 Ax - bl2 + X ||l| +
||00|
2
Solve inner-loop subproblems.
Use the same notations as in Appendix
F.1 and set
X2
fx
Ik
and â%
1 XzâR
1 + λzōz
Then we can formulate the inner-loop subproblem
1.3 at iteration as follows:
d2
min
H (Astim, (2) +p(l))
|1 xxx xx
#ERd
2
1 + πzā
2)
min #ERd
H (Asimm..) 20) +p(x)+
x
2ā
1 1 dzā
(F.6)
min .ERd
H [ [Agim
pp()) + 2 || 1|0- 2xll2
where
H(y)
y b st for all y E R and p(x) & Xx |z]1| for all x E Rd.
2
By using the equivalent formulation F.6 described above and following the proof argument of Claim F.1 for the Lasso model, can easily check the validity of the claim below:
Claim F.2. Consider the subproblem (F6 at iteration of PAPPA (Algorithm ! with stepsizes {ax} and accuracy parameters { Define
(EE A (E) + +p" prox pz
Ab.m..))
for all R. where H" and p" are the Fenchel conjugate functions of H and respectively. Fix any l E Z4 If Tk+1 is obtained via the following update rule:
âkk
2x
AT
Am.m
prox
A
A
{)
2
Crk
Ix
uk+1 =prox
at 0%
-Apmm, _kt11
with
Ex+1 R3 arg min cE
V((E)
where
IIV (Ex+1)ll2 <
(F.)
Vāx
#k+1 = Sh âz
IJsmm,SAt + met1) = proxaup ( dr gton (a+1)
then Jb+1 satisfies the stopping criterion SCA), i.e., | prOx (zx) S Ek.
Similar to the Lasso model, the iterates {ax} generated by isPPA are computed by employing the SSN method to solve the minimization subproblem specified in (E7
39

---

Published as a conference paper at ICLR 2025
Obtain approximate optimal solution. For each data set, employ the SSNAL method to solve problem (4.2) and obtain an approximate solution I" satisfying the relative KKT residual
clel.clastic < 10" where
Prox A 1-11, (i* AT (AT* b) A2 )2
elllelastic
x 2 + ||A (Ar - -b) + \22 ll2
Then 8² is the desired approximation of the optimal solution
4.2
Test setup for synthetic and real data and numerical results for real data sets. For numerical 10000 and d = 1000, setting to zero for noiseless
experiments synthetic data, conditions and to 10 otherwise. The regularization parameters, A and Xg, are set to Xe, ||ATb] 6ll
and deş | pc respectively, with Ac₁ 5 10-2 and Aez 5 10-2 For test real data sets, specifically the data sets abalone7 and space ga9, we set the regularization parameters (A1, 22) (Ac, A ATb xo Aez || bl).)) with (Acy Aez) (10-1, 10-1) for abalone7 and (Meg Aea) (10 10-2) for space ga9, respectively. The accuracy parameter сg is defined as yog with 10-2, and the minibatch size m is fixed at 32. The KKT residual for the elastic net Lasso model defined as:
Melaatic (x) 1 prox (x A (Ax- - -)22))))
(F88
disttr, X(", affirming that all the results from Corollary 2.7 apply Melastic. The performance of isPPA with diminishing stepsizes aą agk -8 for various stepsize exponents 3 E (0.55. 0.75, 0.9, 1). starting with an initial stepsize on = 50, is displayed in
which is upper bounded by +2 ||
the bottom row of Figure 3 The observed convergence results align with those tested synthetic data, thus validating Corollary 2.5 and 2.7
(a)
(b)
Figure 3: Performance of isPPA in solving the linear regression models (Lasso top and elastic net bottom) for four values of stepsize exponents B = 0.55, 0.75, 0.9 and 1. The legend "isPPA-beta-9" denotes isPPA with diminishing stepsizes ag = ki - (a) The test on data set abalone7. (b) The test data set space.ga9.
F.3 PROOF OF CLAIM
The proof Claim F.I are based on the following result. Here we still use H and p² to denote the Fenchel conjugate functions of H and respectively.
Claim F.3. Consider the following composite optimization problem
min #ER4
((x) e H (Ax) p(z),
(F99
40

---

Published as a conference paper at ICLR 2025
where A E Rmxdd H: R" + (-00,+00) and p: IR + (-00, tool proper and closed convex
functions. Fix any E R., a E R++ and E R4. Define
x -AAE5)
V(E) - - Pp
prox
A
prox
-
ATE) )
for all & R."
Suppose that H is -t--onny convex for some hl
E + 1f
û prox g-
A
with
(F.10)
a R arg min (5) Se
where
V
(5) S
nH e,
then ā 2 1=-=a(A1) + ū) satisfies
I arg min sERd
((Ax) + p(x) + 20
|| x12
where
|| - prox (T)ll Se.
By using Claim F33
with A = Asumm and functions and p defined in F.2 we can deduce from
the 1-strong convexity of H (see that
ØR+1 prox p (Tx) ||2 | prox a (Tx)
S cN.
where ((x) A (A) + p(z) for all x E RRd. It only remains to prove Claim F33
Proof of Claim F33
Let &
o (T). We assume that (É, ū) RTm x Rd satisfy 1. and
5 2 I
T + ū
By following an argument nearly identical to that in the proof of
(Rockafellar
1976a
Proposition 6), we can obtain
| - 2| < 2a
(5(()
1
inf (E) EER
(F.11)
Given that H is MH strongly convex, V is also лH -tronnyy convex. Thus,
inf V (E) gelm
inf
V
, E)
+ T1
2
$ - 12
1
V
FER
2
This property together with implies
| - 2112 $
V 2a
(
inf EERm
(E)
2a
V
(
Sc
2MH
where the last incquality follows from the definition of E in F.
This completes the proof of Claim
F3
For completeness, we provide a detailed proof of [.1 below. Let La denote the augmented
Lagrangian function:
La u,)) e (E((E) +p)))
(A E + u. 2) +
a AAT & + ull2
2
for all (E, u. x)
T
x Rd gd
Note that
V L. ū. -(A (AT +
a
Then, the concavity of La La(E, ū. leads us to
La (5, ( + a -1 1 (ā x, x x) 2 La
E ū, x
inf xu
La u.)
(F.12)
41

---

Published as a conference paper at ICLR 2025
Fix any R. It is easily verified that the maximization problem
max
(Ay) -p"
2a 11v xz112
yERd
is the dual of the following minimization problem:
min (5) + (AT & u. + 2 1| ş u1/
(R.))ERm xRd
min
(5) + p" (1) (w, x)
2 1
(F.13)
(R XR xRd
s.t. A u + w
Note that the objective function of problem (F.13) is proper, closed and strongly convex. Then, is bounded below over nonempty feasible set, ensuring that the optimal value of problem (F.13) is finite. By combining this property with the fact that problem (F.13) is convex and satisfies Slater's condition, we conclude that strong duality holds, i.e..
inf La (S, u, x) sup (5.a)ERT XR
2a 1l
x1
yERd
Based on this result, and given that both Il and p are proper and closed convex, deduce that
inf La (5, u, x) sup
-H
ppl)
2a |1
x11
(5.u)ERmxx) xBx
yERd
(F.14)
sup vERd
-m(y)
1
11 21B3
for all x ER
Combining F.12 with F.14 yields
La E ú
F
1 - x1
(ī- H, I)
for all E Rd.
(F.15)
20
Similarly, obtain
1
inf
La (E, (,,)
sup yERd
(b()
11y 212
(G.))ER"xP""
2a
inf yER
+(y) +
|1 x1/
(F.16)
2a
(8)
||@
x 2
2a
where the first equality comes from F..14) with x = H, and the last follows from the definition of f. the other hand, it follows from the definition of v and that
(R.")ERT x3d La u,)
inf
inf inf
(H) + +p0p+pp()) (u)
u. + |
g+ +
=1(2]
EERM weRd
1
inf inf EERm weRd
H²((E) +p- 2
A
|1
2a
inf EElt
(²((E) + p¹
proxx
AT ATE))
0x
AT {
prox
A
a
a
2
|
2a
1
inf (E(
SERm
2a
and
La
(,, ū (E,ū,))-HH( -H
+p
a
A
A
1
|
1
|
2
a
2a
2a
42

---

Published as a conference paper at ICLR 2025
Then, deduce from the previous two equations that
V
inf
V (E)
Lo. (E,
inf (G.a)ER" xR=
La (E, U,),,
which combined with F.15
and F.16 implies
V
inf
V (5)
EERm
2
(t)
||
1
(00 T,
T
(2)
| 01
20
2a
[|
x12
||
x
(ī I, x x)
for all x E R.
2a
Hence, the inequality
F.11) can be derived from the aforementioned results as follows:
1
V
inf EE
v/ (5) 2
sup mE
[
|| 1 2 -E-- - -
2xx
1
||
m|
2
||
21² 2 (5 I 5))
20
1
=1|2
2a
43


Reviews:
[{"review_id": "zuMm0MCCRK", "reviewer": "Reviewer_XLfK", "summary": "The paper considers the inexact stochastic proximal point algorithm (isPPA) for solving convex stochastic composite optimization problems.\n\nThe authors relax the convergence assumptions by removing the requirements for smoothness and strong convexity, instead imposing a local Lipschitz condition and a quadratic growth condition on the objective function.\n\nThey establish non-ergodic (last-iterate) convergence rates for the algorithm.\n\nFinally, the authors present empirical results to show the asymptotic convergence rates for the distance to the solution set and the KKT residual.", "questions": "I would like to ask two questions regarding the nonconvex scenario, as it is more general and widely applicable.\n\n**Q1.** Referring to Lines 84-85, why is the proposed methodology more readily extendable to nonconvex settings?\n\n**Q2.** How does the proposed algorithm compare to the proximal point method in the cited paper *Davis, D., & Drusvyatskiy, D. (2019). Stochastic model-based minimization of weakly convex functions*, which is designed for minimizing weakly convex functions?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "**S1**. This paper proposes isPPA to solve nonsmooth convex stochastic optimization problems under weaker assumptions of **a local Lipschitz continuity condition** and **a quadratic growth condition**, broadening its applicability in nonsmooth settings.\n\n**S2**. This paper provides a tight analysis of the last-iterate convergence rates for the distance to the optimal solution set and the KKT residual, as shown in Theorems 2.4 and 2.7.\n\n**S3**. Using the simple regularized Frechet mean problem, the authors establish the lower bounds for the convergence rate of the distance to the optimal solution set. By comparing the lower and upper bounds, they show that the asymptotic convergence rate is tight up to constant factors.", "weaknesses": "**W1.** Algorithm 1 is a double-loop algorithm, as it relies on another optimization algorithm to solve each subproblem. Such algorithms are rarely used; instead, single-loop algorithms, where each iteration precisely solves the subproblem, are more common. Although the algorithm specifies the required accuracy for each subproblem, these accuracy estimates tend to be conservative and are seldom used in practice, as they can significantly reduce the overall efficiency of the algorithm.\n\n**W2.** For general non-smooth convex optimization problems, the paper does not provide the required iteration complexity for solving the subproblems.\n\n**W3.** The authors claim that the algorithm requires weaker conditions than all existing methods. To support this claim, it would be beneficial to include a practical machine learning example where other methods fail, but the proposed method succeeds. The two examples provided in the experiments do not fully support the claim of requiring weaker assumptions.\n\n**W4.** The authors mention in Lines 68-69 that the Lipschitz continuity condition is violated by the elastic net regularizer. I think this statement is inaccurate; a function that is continuously differentiable on a closed compact set is indeed Lipschitz continuous. Given that the iterative sequence is assumed to be bounded (see Lines 95 and 296), the elastic net regularizer should also be globally Lipschitz.\n\n\n**W5.** Typo. Line 440: It should be \"iteration(k)\".", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "87VdqyWOYG", "reviewer": "Reviewer_Lrjb", "summary": "In this paper, the authors consider inexact stochastic proximal point algorithm (isPPA) for solving stochastic composite optimization problems. Under mild conditions, the authors demonstrate the stability and almost sure convergence of this method. By further assuming a local Lipschitz condition on component functions and a quadratic growth condition on the objective function, the authors establish convergence rate guarantees. Empirical validation from numerical experiments supports these theoretical analyses.", "questions": "The authors should make more remarks about how the assumptions in this submission is weaker than the assumptions from previous papers and compared more about the theoretical analysis in this work with the previous works.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "In this submission, the authors prove the stability of isPPA under mild conditions, extending the stability result for exact sPPA. The authors provided non-asymptotic last-iterate convergence rates for isPPA in terms of the expected squared distance to the optimal solution set. They also provide lower bounds on the convergence rates of isPPA for solving problem under the assumptions proposed in this paper, demonstrating that the derived convergence rate guarantees are tight up to constant factors. All the theoretical analysis are proved by detailed mathematical analysis and empirical results from the numerical experiments are consistent with the theoretical analysis.", "weaknesses": "The only weakness of this submission is that the authors should explain more about how the assumptions provided in this paper is \"mild\" or less restrictive compared with the previous results. And how exactly the results of this paper differ from the results of the previous works. How exactly the assumptions one to five are more general compared with the assumptions in the previous results and how this impact the theoretical proof and analysis.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "1hssndDHMI", "reviewer": "Reviewer_KLe5", "summary": "The paper presents the convergence of an inexact stochastic proximal point algorithm for solving stochastic composite optimization problems. The main contributions lies in weakening the assumptions on the function class and illustrating the tightness of the established bounds.", "questions": "1. Remark 2.1: The conditions in Remark 1.1 are insufficient to ensure Assumption 2. For example, consider the indicator function of $x \\geq 0$; its subgradient at $x = 0$ is a cone, and thus an unbounded set.\n2. Theorem 2.3: Is there an achievable high-probability bound on the distance to the optimal set?\n3. Could the assumption ${\\rm sup}\\\\|x_k\\\\|_2 < \\infty$ be removed to obtain a cleaner theoretical result?\n4. It would be helpful comment on the impact of minibatch size $m$.\n5. Numerical experiments: The applications considered are somewhat outdated, and the datasets used are synthetic. Since the theory targets a more general setting where $f$ and the regularizer are not necessarily convex, it would be valuable to see results on more general machine learning problems with this structure.\n6. Numerical experiments: The current experiments resemble an ablation study. It would be helpful to include comparisons with other state-of-the-art algorithms for these problems to demonstrate practical applicability.", "limitations": "", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "The problem setting, assumptions, and theoretical results are clearly stated, and necessary comparisons with the existing literature are provided.", "weaknesses": "1. The applicability of the proposed proximal point algorithm is limited. It requires two loops, and the complexity of the inner loop can also be prohibitive. The complexity of solving the inner problems is not considered in the paper.\n2. Deriving the stability result from existing exact PPA algorithms in the literature does not seem particularly challenging. Additionally, given coercivity and the assumption that $\\|x_k\\|$ is bounded, it would be more natural to use local Lipschitz continuity rather than global Lipschitz continuity. It’s essential to clearly state the technical difficulties involved.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "7xIx4yrdF5", "reviewer": "Reviewer_eTPG", "summary": "This paper proposes an inexact stochastic proximal point algorithm. It gives conditions that the inexact subproblem solutions should satisfy, and analyzes the convergence of the algorithm based on the conditions being satisfied. Specifically, the paper shows the convergence rate of the distance of current iterate to the optimal solution set is O(k^{-\\beta}), and the convergence rate of the residual of current iterate to the exact proximal solution is O(k^{-\\beta/2}), where \\beta \\in (0,1] defines the diminishing stepsize. The experimental results align with the theoretical convergence rates for different values of \\beta.", "questions": "1) Line 219: equation (2.2). Why does Criterion SCB imply Criterion SCA?\n2) \\sup_k ||x_k||_2 < \\infinity is a condition in Theorem 2.3 where constant stepsize is used. I’m curious what is the challenge of proving sup_k ||x_k||_2 < \\infinity when using constant stepsize. \n3) In Section 2.3, why is the distance ||x - prox_\\phi (x)||_2 referred to as the KKT residual?\n4) In the experiment setting Line 479, for the  accuracy parameter \\epsilon_k = \\gamma \\alpha_k^2, what is the practical rule for tuning \\gamma?\n5) Theorem 2.4 uses \\epsilon_k = \\gamma \\alpha_k^{3/2}, which is different from the experiment setting. Does it make a difference? Does Theorem 2.4 specifically rely on the exponent 3/23/2?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "The contribution seems very nice and, as far as I can see, the analysis appears to be sound.", "weaknesses": "1) The paper does not present a general algorithm for solving the proximal subproblem inexactly to satisfy SCA for arbitrary problems. Although Appendix F.1 provides an algorithm, it is specifically designed for problem (4.1). \n2) There is no computation cost and convergence comparison between sPPA and isPPA.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)