A variance reduced framework for (non)smooth nonconvex-nonconcave stochastic minimax problems with extended Kurdyka-Lojasiewicz property

In this paper, we study stochastic constrained minimax optimization problems with nonconvex–nonconcave structure, a central problem in modern machine learning, for which reliable and efficient algorithms remain largely unexplored due to its inherent challenges. Prior approaches for nonconvex minimax optimization often require (strong) concavity on the maximization part, or certain restrictive geometric assumptions on the joint objective to have guaranteed convergence. In contrast, our method only assumes weak convexity in the primal variable and the extended Kurdyka–Łojasiewicz (KŁ) property, with exponent θ∈[0,1], in the dual variable, significantly broadening the class of tractable problems. To this end, we propose a variance reduced algorithm that provably handles this general setting and achieves an ε-stationary solution with state-of-the-art sample complexity: in the smooth finite-sum setting, the sample complexity is 𝒪⁡(N​ε−max⁡{4​θ,2}), where N is the number of total samples, and in the online smooth setting, it is 𝒪⁡(ε−max⁡{6​θ,3}). For the structured nonsmooth problem, the sample complexity is 𝒪⁡(N​max⁡{ε−3,ε−5​θ,ε−11​θ−32​θ}) and 𝒪⁡(max⁡{ε−4,ε−15​θ−12,ε−31​θ−94​θ}) respectively for the two settings. To the best of our knowledge, this is the first unified framework that jointly accommodates weak convexity, the extended KŁ property, and variance-reduced stochastic updates, making it highly suitable for large-scale applications.

1 Introduction

In recent years, minimax optimization problems have emerged as a central framework in modern Machine Learning, encompassing a wide range of applications such as Generative Adversarial Networks (GANs) (Goodfellow et al., 2014), (RL) (Pinto et al., 2017), Adversarial Training (Madry et al., 2018), Distributionally Robust Optimization (DRO) (Rahimian and Mehrotra, 2019), and Optimal Transport (OT) (Kim et al., 2025). Despite their broad applicability, solving minimax problems remains challenging in general, especially when the objective is nonconvex–nonconcave and possibly nonsmooth. In this work, we study a class of constrained minimax optimization problems of the form

minx∈𝒳⁡maxy∈𝒴⁡F⁡(x,y):=𝔼𝝃∼ℙ​[f⁡(x,y,𝝃)], (P)

where F:ℝdx×ℝdy→ℝ is nonconvex and possibly nonsmooth with respect to the primal variable x, and smooth but nonconcave with respect to the dual variable y. Here, ℙ denotes the probability distribution with support Ξ from which the data points are sampled. In the online setting, the distribution ℙ is unknown, and the algorithm accesses the objective only through stochastic samples 𝝃∼ℙ. When ℙ is the empirical distribution induced by N i.i.d. samples, problem (P) reduces to the finite-sum setting, i.e.,

F⁡(x,y)=1N​∑i=1Nf⁡(x,y,𝝃i). (1)

The feasible sets 𝒳⊆ℝdx and 𝒴⊆ℝdy are assumed to be nonempty, closed convex, and f:ℝdx×ℝdy×Ξ→ℝ represents the cost function associated with a random variable 𝝃∈Ξ. In this work, we first focus on a smooth formulation of problem (P), which serves as the cornerstone of our algorithmic development and theoretical analysis. To demonstrate the versatility of our framework, we also consider a nonsmooth variant where the cost function has a structured form commonly arising in DRO. By applying a suitable smoothing transformation, this variant can be efficiently brought into the smooth regime, allowing our framework to be applied directly while providing rigorous convergence guarantees.

1.1 Related Works

Table 1: Comparison of structural assumptions and sample complexities in finite–sum and/or online regimes for obtaining an ε-stationary solution of minimax optimization problems considered in several relevant works in the regime of N=𝒪⁡(ε−4). The columns Primal and Dual specify the assumptions on the objective function about primal and dual variables respectively; the column Type indicates whether the method uses stochastic or deterministic gradient. Here, 𝒳 and 𝒴 are nonempty convex sets. We denote D: Deterministic, ST: Stochastic, CP: Compact, Cl: Closed, S: Smooth, NS: Nonsmooth, WC: Weakly-Convex, C: Concave, SC: Strongly-Concave, and e-KŁ: extended KŁ. †They do not consider the finite sum setting separately, we infer the same sample complexity as the one obtained in the online case. Here, 𝒪~ hides a logarithmic factor of 1ε. ‡They consider different settings including a two-sided PŁ condition and discusses cases when condition number dominates the number of samples. Here for a fair comparison, we assume the underlying condition number is small. ∗They do not exploit the finite-sum structure, and all its complexity results are inferred from its online setting. ⋆They consider a more general setting where nonsmooth convex regularizers exist.

Source Type 𝒳 𝒴 Primal Dual Finite-Sum Online

(Rafique et al., 2018) ST ℝdx ℝdy S S&C 𝒪~​(N​ε−2+ε−6) N/A

NS&WC C 𝒪~​(ε−6)† 𝒪~​(ε−6)

(Chen et al., 2022)‡ ST ℝdx ℝdy S S&PŁ 𝒪~​(N​ε−2) N/A

(Jiang et al., 2024) ST ℝdx ℝdy S S&SC 𝒪⁡(N​ε−2) N/A

(Zhang et al., 2024)⋆ ST Cl Cl NS & WC NS&SC 𝒪⁡(ε−3.5) 𝒪⁡(ε−3.5)

ST Cl CP S NS&C 𝒪⁡(ε−6) 𝒪⁡(ε−6)

(Zheng et al., 2025) D Cl CP S S&KŁ 𝒪⁡(N​ε−max⁡{4​θ,2}) N/A

(Jiang et al., 2025) ST CP CP S S&C 𝒪⁡(N​ε−4) N/A

(Lin et al., 2025)∗ ST ℝdx CP S S&SC 𝒪⁡(ε−4) 𝒪⁡(ε−4)

S S&C 𝒪⁡(ε−8) 𝒪⁡(ε−8)

NS&WC SC 𝒪~​(ε−6) 𝒪~​(ε−6)

NS&WC C 𝒪⁡(ε−8) 𝒪⁡(ε−8)

This paper (Sect. 2) ST Cl CP S S&e-KŁ 𝒪⁡(N​ε−max⁡{4​θ,2}) 𝒪⁡(ε−max⁡{6​θ,3})

This paper (Sect. 3) ST CP CP NS&WC S&e-KŁ 𝒪⁡(N​ε−max⁡{3,5​θ,11​θ−32​θ}) 𝒪⁡(ε−max⁡{4,15​θ−12,31​θ−94​θ})

Practical challenges in minimax optimization have sparked extensive research across a wide spectrum of problem settings, from convex–concave to fully nonconvex–nonconcave regimes. Early works concentrated on convex–concave problems, leading to the development of optimal primal–dual methods (Chen et al., 2014; Hamedani and Aybat, 2021). Subsequent work addressed nonconvex–concave settings using gradient descent–ascent (GDA) based algorithms and near-optimal methods (Lin et al., 2020b; Lin et al., 2020a), while weakly convex–weakly concave problems were explored in (Liu et al., 2021). More recent advances have introduced adaptive and universal algorithms under Polyak–Łojasiewicz (PŁ) and smoothness assumptions (Yang et al., 2022; Huang et al., 2023), as well as universal GDA-type algorithms that provide convergence guarantees across multiple problem structures (Zheng et al., 2023; Zheng et al., 2025), and rates for nonsmooth nonconvex–nonconcave problems leveraging primal–dual balance and KŁ properties (Li et al., 2025).

A key limitation of much of the existing literature is the focus on deterministic settings or unconstrained smooth cases. While some methods have been extended to stochastic problems, they often require large batch sizes for each update (Lin et al., 2020b; Lin et al., 2025) and thus high computational costs, limiting their practicality. This motivates the incorporation of variance reduction techniques, such as SVRG (Johnson and Zhang, 2013) and SPIDER (Fang et al., 2018), which have demonstrated effectiveness in classical minimization tasks, into the more challenging minimax setting. Recent efforts in this direction aim to bridge the gap between theoretical efficiency and practical scalability. For instance, Chen et al. (2022) analyzed the SPIDER-based algorithm under the PŁ condition and demonstrated improved convergence rates, while Jiang et al. (2024) proposed a shuffling gradient descent-ascent method with variance reduction for nonconvex-strongly concave stochastic problems. More recently, Jiang et al. (2025) introduced single loop algorithms, incorporating variance reduction, tailored to the finite-sum regime and general nonconvex-concave stochastic minimax problems.

Despite these advances, a common limitation is the reliance on strong assumptions, such as unconstrained smoothness, and (strong) concavity, or the PŁ condition on the maximization part, which restricts their applicability to general nonconvex–nonconcave minimax problems. Addressing this limitation remains a major open challenge in the design of scalable and reliable minimax optimization algorithms.

To position our work relative to the existing literature, Table 1 summarizes relevant studies and their key structural assumptions on the considered problems as well as the sample complexities for obtaining a certain ε-stationary solution.

We emphasize that our results are new. In certain special cases, they are either strictly better than existing ones or match with the best-known ones but under strictly weaker conditions; see more discussions in Remarks 2.5 and 3.5.

1.2 Contributions

We summarize our key contributions as follows.

First, in contrast to prior methods, our approach addresses the fully nonconvex-nonconcave minimax problem under significantly weaker and more realistic assumptions in both the finite-sum and stochastic online regimes. Specifically, we assume the extended KŁ property in y in the sense that the exponent parameter θ can be any value on [0,1]; see Assumption 2.2. This property allows for significantly broader applications as compared to the PŁ condition assumed in (Chen et al., 2022), which only applies to unconstrained smooth cases with θ=12. Though Zheng et al. (2025) have also studied minimax problems with a classical KŁ property in y, their algorithm relies on deterministic gradients and thus will be inefficient on solving a finite-sum structured or stochastic online minimax problem. In addition, their analysis does not cover the case of θ=1 that is implied by the restricted (a.k.a. star-) concavity (see Remark 2.3) and is strictly weaker than the concavity condition assumed in (Jiang et al., 2025).

Second, designed for both the stochastic online and finite-sum settings, our algorithm employs a framework integrated with SPIDER-type variance reduction, enabling guaranteed convergence while significantly reducing computational as well as the sample complexity. In the smooth finite-sum setting, the sample complexity of our algorithm is 𝒪⁡(N​ε−max⁡{4​θ,2}) to produce an ε-stationary solution in expectation. Compared to the deterministic method in (Zheng et al., 2025) applied to the finite-sum case, our result achieves a factor N improvement. In the online smooth setting, we obtain a sample complexity of 𝒪⁡(ε−max⁡{6​θ,3}), which is new.

Third, by using the Moreau-envelope smoothing technique, we further extend our method and analysis to a structured nonsmooth nonconvex-nonconcave minimax problem, for which the sample complexity results of our method are 𝒪⁡(N​max⁡{ε−3,ε−5​θ,ε−11​θ−32​θ}) and 𝒪⁡(max⁡{ε−4,ε−15​θ−12,ε−31​θ−94​θ}) respectively for the finite-sum and the online settings. Both results are new.

To the best of our knowledge, our method is the first unified framework that jointly accommodates weak convexity, the extended KŁ property, and variance-reduced stochastic updates for nonconvex–nonconcave minimax optimization.

1.3 Notations and Definitions

Throughout this paper, ∥⋅∥ denotes the 2-norm. For an arbitrary set 𝒮, let ι𝒮 denote its 0-∞ indicator function and 𝒩𝒮​(s) for the normal cone to 𝒮 at s∈𝒮. The distance from a point a to a set 𝒮 is denoted by dist⁡(a,𝒮), and proj𝒮 is the projection operator onto 𝒮. A function Ψ:𝒳→ℝ is called ρ-weakly convex for some ρ≥0, if Ψ(⋅)+ρ2∥⋅∥2 is convex on 𝒳, and its δ-subdifferential is defined as

∂δΨ⁡(x)={v:Ψ⁡(x′)≥Ψ⁡(x)+v⊤​(x′−x)−ρ2​‖x′−x‖2−δ}. (2)

When δ=0, the δ-subdifferential reduces to the standard subdifferential.

For constrained smooth problems, we pursue an ε-game stationary point defined below.

For a given ε≥0, a random solution (x,y)∈𝒳×𝒴 is called an ε-Game Stationary (GS) point in expectation of Problem (P) if

𝔼⁡[dist​(0,∇xF​(x,y)+𝒩𝒳​(x))2]≤ε2and

𝔼⁡[dist​(0,−∇yF​(x,y)+𝒩𝒴​(y))2]≤ε2.

When F is nonsmooth about x, we pursue a nearly ε-game stationary point defined as follows.

For a given ε≥0, a random solution (x,y)∈𝒳×𝒴 is called a nearly ε-GS point in expectation of Problem (P) if

𝔼⁡[dist​(0,∂xε(F⁡(x,y)+ι𝒳​(x)))2]≤ε2and

𝔼⁡[dist​(0,−∇yF​(x,y)+𝒩𝒴​(y))2]≤ε2.

For convenience of stating our main results, we list several key notations in Tables 2.

Table 2: A few key notations and definitions

Notation Definition

Fr​(x,y,z) F⁡(x,y)+r2​‖x−z‖2

xr​(y,z) arg⁡minx∈𝒳​Fr​(x,y,z)

dr​(y,z) minx∈𝒳⁡Fr​(x,y,z)

pr​(z) maxy∈𝒴⁡minx∈𝒳​Fr​(x,y,z)

Frλ​(x,y,z) Fλ​(x,y)+r2​‖x−z‖2

drλ​(y,z) minx∈𝒳⁡Frλ​(x,y,z)

prλ​(z) maxy∈𝒴⁡minx∈𝒳​Frλ​(x,y,z)

2 Constrained Smooth Minimax Problems

We first study the case of smooth minimax problems, which satisfy the following assumptions.

The following statements hold:

The set 𝒴 is compact with diameter D𝒴=maxy1,y2∈𝒴⁡‖y1−y2‖<+∞.

There exists ℓ>0 such that ∀(x1,y1),(x2,y2)∈𝒳×𝒴,

𝔼⁡‖f⁡(x1,y1,𝝃)−f⁡(x2,y2,𝝃)‖

≤ℓ⁡(‖x1−x2‖+‖y1−y2‖).

There are constants Lx and Ly such that for all x,x1,x2∈𝒳 and y,y1,y2∈𝒴

𝔼​‖∇xf​(x1,y,𝝃)−∇xf​(x2,y,𝝃)‖2≤Lx2​‖x1−x2‖2,

𝔼​‖∇xf​(x,y1,𝝃)−∇xf​(x,y2,𝝃)‖2≤Ly2​‖y1−y2‖2,

𝔼​‖∇yf​(x1,y1,𝝃)−∇yf​(x2,y2,𝝃)‖2

≤Ly2​(‖x1−x2‖2+‖y1−y2‖2).

For any y∈𝒴, F⁡(⋅,y) is ρ-weakly convex.

There exist constants σx,σy≥0 such that for all x∈𝒳 and y∈𝒴,

𝔼⁡[∇f​(x,y,𝝃)|(x,y)]=∇F​(x,y);

𝔼​‖∇xf​(x,y,𝝃)−∇xF​(x,y)‖2≤σx2;

𝔼​‖∇yf​(x,y,𝝃)−∇yF​(x,y)‖2≤σy2.

There exists a constant F¯∈ℝ such that

maxy∈𝒴⁡minx∈𝒳⁡F⁡(x,y)≥F¯. (3)

For all x∈𝒳, F⁡(x,⋅) satisfies the extended KŁ property: there exist constants μ>0 and θ∈[0,1] such that ∀x∈𝒳,y∈𝒴.

dist⁡(0,−∇yF​(x,y)+𝒩𝒴​(y)) (4)

≥μ​(maxy′∈𝒴⁡F⁡(x,y′)−F⁡(x,y))θ.

It follows directly from Assumption 2.1(ii) that F⁡(x,y) is also ℓ-Lipschitz continuous. In addition, from Assumption 2.1(iii) and (v), it follows that for each x∈𝒳 and y∈𝒴, ∇xF​(⋅,y) is Lx-Lipschitz continuous, ∇xF​(x,⋅) is Ly-Lipschitz continuous, and ∇yF​(⋅,⋅) is Ly-Lipschitz continuous.

The classical KŁ property assumes θ∈[0,1) and is satisfied by a wide and practically relevant class of functions commonly encountered in ML (Bolte et al., 2014). An illustrative example showing that nonconcavity does not rule out the satisfaction of the KŁ property is provided in subsection D of the appendix.

When θ=1, the condition in (4) is implied by the restricted (a.k.a. star-) concavity by using the compactness of 𝒴. The proof is given in Section A.1 of the appendix.

2.1 Algorithm

Our algorithm is motivated by the smoothed proximal linear descent ascent (PLDA) method in (Li et al., 2025), which is a deterministic gradient-type method for solving composite nonsmooth minimax problems, as well as the Probabilistic Variance-Reduced Smoothed Gradient Descent-Ascent (PVR-SGDA) in (Jiang et al., 2025). Different from the deterministic PLDA and PVR-SGDA, our method uses stochastic gradients together with the SPIDER variance reduction technique that is originally developed for minimization problems in (Fang et al., 2018). The pseudocode of our algorithm is given in Algorithm 1, where the stochastic gradient estimators are given as follows:

Gx,τk ={1B​∑i=1B∇xf​(xτk,yτk,𝝃τ,ik), if ​τ=0,1M​∑i=1M∇xf​(xτk,yτk,𝝃τ,ik)−1M∑i=1M∇xf(xkτ−1,yτ−1k;𝝃kτ,i)+Gx,τ−1k,else. (5)

Gy,τk ={1B​∑i=1B∇yf​(xτk,yτk,𝝃τ,ik), if ​τ=0,1M​∑i=1M∇yf​(xτk,yτk,𝝃τ,ik)−1M∑i=1M∇yf(xkτ−1,yτ−1k;𝝃kτ,i)+Gy,τ−1k,else. (6)

Here, when τ=0, we draw a mini-batch of B i.i.d. samples {𝝃0,1k,…,𝝃0,Bk} from the distribution ℙ for the online setting, and take all N samples (thus B=N) for the finite-sum setting in (1); when 0<τ<T, we draw a mini-batch of M i.i.d. samples {𝝃τ,1k,…,𝝃τ,Mk} from ℙ, compute sampled gradients at the current iterate (xτk,yτk) and the previous iterate (xτ−1k,yτ−1k), and then apply the momentum term to update the stochastic gradient estimator to reduce variance. Though the algorithm appears to be double-loop, it does not require any subroutine but instead the double iteration indices k and τ are used for the gradient estimator.

Algorithm 1 Smoothed Stochastic Gradient Descent-Ascent Method with SPIDER Variance Reduction

2.2 Roadmap of Convergence Analysis

Here, we sketch the key steps for establishing the convergence of Algorithm 1 under Assumptions 2.1 and 2.2. Specifically, we start off by deriving the error bounds for the stochastic gradient estimators employed in the algorithm (see Lemma A.1). These errors carry over the entire analysis, and with appropriate choices of batches size and variance reduction, we are able to control them in a user-specified level. To further understand the behavior of our algorithm, we then bound the error between the actual iterate xτ+1k and the virtual regularized solution xr​(yτk,zτk) defined in Table 2 (see Lemma A.5) . Also, we analyze how changes in the dual variable y affect the regularized solution, which helps us understand the interaction between the primal and dual updates (see Lemma A.7). These results play a central role in characterizing algorithmic progress.

With all these error bounds established, we then show the one-iteration progress of our algorithm, measured based on a Lyapunov function similar to that used in (Li et al., 2025). Specifically, we define Φr:ℝdx×ℝdy×ℝdx→ℝ as follows:

Φr​(x,y,z):= Fr​(x,y,z)−dr​(y,z)⏟Primal Descent

+pr​(z)−dr​(y,z)⏟Dual Ascent+pr​(z)⏟Proximal Descent. (7)

This Lyapunov function is designed to reflect the structure of the algorithm by combining the behavior of the primal, dual, and proximal variable updates. Instead of analyzing each component separately, this unified function captures their interaction in a single expression. In particular, it reflects descent in x, ascent in y, and the descent in z. Analyzing decrease in this function allows us to track convergence in a principled and coherent way, closely aligned with the actual algorithmic updates (see Lemma A.12).

Finally, we establish auxiliary bounds (see Lemma A.15) associated with the adopted optimality conditions (see Lemmas A.17 and A.18) and combine all components to derive the iteration and sample complexity guarantees for the smooth case in Theorem 2.4 (presented below). We note that our results encompass both the finite–sum and online settings.

2.3 Complexity Results for Smooth Problems

Under Assumptions 2.1 and 2.2, let ε>0 be given. Suppose ρ=𝒪⁡(min⁡{Lx,Ly}) and min⁡{Lx,Ly}=Ω⁡(1) and denote Δ​Φ=(Φr​(x00,y00,z00)−F¯), where F¯ is the constant in Assumption 2.2[vi]. For the finite-sum setting, take all N samples to obtain Gx,τk and Gy,τk when τ=0 in Algorithm 1, thus B=N; for the online setting, let

B={Θ⁡((Ly2​(σx2+σy2)(Ly2+Lx)​ε2)​max⁡{Lx+Ly2,Ly+Lxμ2}), if ​θ∈[0,12],Θ((σx2+σy2Ly2+Lx)max{Ly2​(Ly2+Lx)ε2,(Ly2+Ly​Lx)2​θ​Lyμ2​ε4​θ,(Lx+Ly2)2​θ−12​θ​Ly12​θ​(Ly2+Ly​Lx)μ1θ​ε4​θ−1θ,Ly2​(Ly+Lx)3​θ−1θμ1θ​ε4​θ−1θ}), if ​θ∈(12,1].

In addition, take T=M=⌈B2⌉, choose

r=max{ 2​ρ+325​(Ly+1)+12​Lx​2​(Ly+1),

2ρ+54Ly(Ly+1)+4Lx3​Ly​(Ly+1)},

αx=min⁡{112​(r+Lx+2​Ly),(r−ρ)224​(r+Lx)2​(Ly+1),r−(ρ+2​Ly)2​Ly​(Lx+r)} and

αy=min⁡{αx,140​Ly,14​(2​Ly+1)}.

Moreover, let

β={min⁡{130,130​r,Ly20​r​ϖ}, if ​θ∈[0,12],Θ(min{1r,αx2​θ−12​θLy−12​θμ1θε2​θ−1θ,r−(2​θ−1)​μ2​Ly−1​ε4​θ−2,r−2​θ−1θLyθ−1θμ1θε2​θ−1θ}), if ​θ∈(12,1].

Then Algorithm 1 can output an ε-GS point (x~,y~) in expectation of (P) and have 𝔼​‖∇zdr​(y~,x~)‖2=𝒪⁡(ε2) in

K​T={𝒪⁡(Δ​Φ​max⁡{Lx+Ly2,(Ly+Lx)μ2}ε2), if ​θ∈[0,12],𝒪(ΔΦmax{Ly2​(Ly2+Lx)ε2,(Ly2+Ly​Lx)2​θ​Lyμ2​ε4​θ,(Lx+Ly2)2​θ−12​θ​Ly12​θ​(Ly2+Ly​Lx)μ1θ​ε4​θ−1θ,Ly2​(Ly+Lx)3​θ−1θμ1θ​ε4​θ−1θ}), if ​θ∈(12,1],

iterations and by 𝒪⁡(⌈B⌉​K​T) sampled gradients.

Notice 4​θ≥4​θ−1θ for all θ>0. Hence, to only show the dependence on ε, we have the overall iteration complexity 𝒪⁡(ε−max⁡{4​θ,2}) in both the finite-sum and online settings. Consequently, the sample complexity in the finite–sum setting is 𝒪⁡(N​ε−max⁡{4​θ,2}) while for the online setting, since B has the same order dependence on ε as K​T, the overall sample complexity is 𝒪⁡(ε−max⁡{6​θ,3}). When θ∈[0,12], our results are optimal, matching the established lower bound of stochastic first-order methods for the special nonconvex minimization problem (Arjevani et al., 2023).

Let us elaborate the superiority of our results over existing ones in a few special cases. We first note that when θ=12, our sample complexity is 𝒪⁡(N​ε−2). It matches the result in (Chen et al., 2022), which assumes the PŁ condition for unconstrained problems. In addition, under the same KŁ condition, our sample complexity is lower by a factor of N than that in (Zheng et al., 2025) on solving the finite-sum structured problem. Moreover, when θ=1, our result is 𝒪⁡(N​ε−4) for the finite-sum case. It matches that of (Jiang et al., 2025), which assume concavity about y, a stronger assumption than ours. In the online setting, when θ=1, our sample complexity is 𝒪⁡(ε−6). It matches the result in (Rafique et al., 2018) but requires a weaker condition, and it improves over the result in (Lin et al., 2025) by a factor of ε−2.

3 Composite Nonsmooth Minimax Problems

In this section, we consider a structured problem setting where the cost function f in (P) has the form of

f⁡(x,y,𝝃)=φ⁡(h⁡(c⁡(x,𝝃)),y,𝝃), (8)

with functions φ:ℝdh×ℝdy×Ξ→ℝ, h:ℝdc→ℝdh, and c:ℝdx×Ξ→ℝdc. Here, φ and c are assumed to be smooth, while h can be nonsmooth. Consequently, we note that the population function F⁡(x,y) is possibly nonsmooth in x and smooth in y.

3.1 Motivating Applications

Several applications in machine learning naturally fall within this framework. Notable examples include ϕ-Divergence distributionally robust optimization (DRO) (Levy et al., 2020) as well as Group DRO (Sagawa et al., 2020) which focuses on maintaining strong performance across different subgroups in the data to improve model fairness and robustness. In subsection C of the appendix, we elaborate on each of these applications and show that, under suitable choices of φ, h, and c, the corresponding objective functions can be expressed in the form of (8).

3.2 Convergence Results

In this section, we make the following assumptions.

The sets 𝒳,𝒴 along with the functions c, h, and φ in (8) satisfy:

The set 𝒳 is compact with diameter D𝒳=maxx1,x2∈𝒳⁡‖x1−x2‖<+∞.

The set 𝒴 is compact with diameter D𝒴=maxy1,y2∈𝒴⁡‖y1−y2‖<+∞.

For each 𝝃∈Ξ, c⁡(⋅,𝝃) is ℓc-Lipschitz continuous.;

Each component of h is convex, potentially nonsmooth, and ℓh-Lipschitz continuous;

For each 𝝃∈Ξ, φ⁡(⋅,⋅,𝝃), is nondecreasing in its first argument, and ℓφ-Lipschitz continuous;

There exists Lc such that ∀x1,x2∈ℝdx

𝔼​‖∇xc​(x1,𝝃)−∇xc​(x2,𝝃)‖2≤Lc2​‖x1−x2‖2. (9)

There exists Lφ>0 such that for any u1,u2∈ℝdh, y1,y2∈ℝdy, and 𝝃∈Ξ,

‖∇1φ​(u1,y1,𝝃)−∇1φ​(u2,y2,𝝃)‖2

≤Lφ2​(‖u1−u2‖2+‖y1−y2‖2), (10)

‖∇yφ​(u1,y1,𝝃)−∇yφ​(u2,y2,𝝃)‖2

≤Lφ2​(‖u1−u2‖2+‖y1−y2‖2), (11)

where ∇1φ denotes the gradient wrt the first argument.

There exist δ~>0, μ>0, and θ∈[0,1] such that for all x∈𝒳 and all u:Ξ→ℝdh satisfying ‖u⁡(𝝃)−h⁡(c⁡(x,𝝃))‖≤δ~,∀𝝃∈Ξ, it holds for g⁡(u,y):=𝔼𝝃∼ℙ​[φ⁡(u⁡(𝝃),y,𝝃)] that

dist⁡(0,−∇yg​(u,y)+𝒩𝒴​(y))

≥μ​[maxy′∈𝒴⁡g⁡(u,y′)−g⁡(u,y)]θ,∀y∈𝒴. (12)

3.2.1 Smoothing by Moreau Envelope and Key Properties

The potential nonsmoothness of h implies that F⁡(x,y) is typically nonsmooth in x, although it remains smooth in y. Hence, Algorithm 1 cannot be directly applied. To address the challenge caused by the nonsmoothness, we propose to apply the Moreau envelope smoothing technique to each component of h, yielding a smooth approximation. The resulting smoothed objective function is given by

Fλ​(x,y) :=𝔼𝝃∼ℙ​[fλ​(x,y,𝝃)]

:=𝔼𝝃∼ℙ​[φ⁡(hλ​(c⁡(x,𝝃)),y,𝝃)]. (13)

Here, hλ:ℝdc→ℝdh is the component-wise Moreau envelope of h, defined as

hλ​(w):=(h1λ​(w),…,hdhλ​(w)),∀w∈ℝdc,

where

hjλ(w):=minq∈ℝdc{hj(q)+12​λ∥w−q∥2},j=1,…,dh.

Since 𝒳 and 𝒴 are both compact, there must exist a constant F¯∈ℝ such that (3) holds. Moreover, denote Fλ¯=F¯−λ​Lφ​Lh2​dh2<∞.

This smoothing step enables us to apply Algorithm 1 developed for smooth problems while carefully controlling the approximation error introduced by the Moreau envelope.

However, before applying Algorithm 1 and deriving iteration and sample complexity guarantees in the nonsmooth regime, we need to establish several key properties of the smoothed objective Fλ that are required for the algorithm’s convergence analysis.

Details on showing these properties are given in the appendix. Here we simply state what properties Fλ has. We begin by establishing the Lipschitz continuity of Fλ​(x,y) (see Lemma B.1). We then show that the gradient ∇Fλ is Lipschitz continuous (see Lemma B.2). Moreover, we characterize the weak convexity moduli of both the original objective F and its smoothed counterpart Fλ (see Lemma B.3). Finally, we verify that for all x∈𝒳, the function Fλ​(x,⋅) satisfies the extended KŁ property (see Lemma B.4).

Having established the necessary properties, we are consequently in a position to apply Algorithm 1 to the smoothed objective Fλ​(x,y). While smoothing allows us to use the algorithm designed in the smooth regime, it introduces an additional approximation error. This error affects the stationarity measures of the original nonsmooth problem, as Fλ​(x,y) only approximates F⁡(x,y), introducing a residual in the stationarity conditions. As a result, the algorithm guarantees convergence only to a nearly ε-GS point of the original problem, rather than an exact ε-GS point. In Lemma B.6, we formalize the relationship between the stationarity measures of the original nonsmooth problem and the corresponding measures of the smoothed problem.

3.2.2 Complexity Results – Nonsmooth regime

We now apply Algorithm 1 developed in Section 2 to the smoothed problem minx∈𝒳⁡maxy∈𝒴​Fλ​(x,y). As shown in Lemmas B.1, B.2, and B.3, the smoothed function Fλ​(x,y) satisfies Assumption 2.1 with smoothness constants and weak convexity constant

ℓ=ℓλ,Lx=Lλ,x,Ly=Lλ,y,ρ=ρλ.

Consequently, all relevant constants in Section 2 that depend on these parameters need to be updated accordingly. Additionally, when λ≪1 and dh=Ω⁡(1), we have ρλ=𝒪⁡(min⁡{Lλ,x,Lλ,y}) and min⁡{Lλ,x,Lλ,y}=Ω⁡(1). Furthermore, assume there exist constants σλ,x,σλ,y≥0 such that ∀x∈ℝdx,y∈ℝdy,𝝃∈Ξ,

𝔼⁡[∇fλ​(x,y,𝝃)|(x,y)]=∇Fλ​(x,y); (14a)

𝔼​‖∇xfλ​(x,y,𝝃)−∇xFλ​(x,y)‖2≤σλ,x2, (14b)

𝔼​‖∇yfλ​(x,y,𝝃)−∇yFλ​(x,y)‖2≤σλ,y2. (14c)

Finally, similar to Section 2, we define the Lyapunov function as Φ^r:ℝdx×ℝdy×ℝdx→ℝ as follows:

Φ^r​(x,y,z)= Frλ​(x,y,z)−drλ​(y,z)+prλ​(z)

−drλ​(y,z)+prλ​(z).

With all the established properties and updated constants, we can now directly obtain the following convergence result for the nonsmooth problem from Theorem 2.4.

Under Assumptions 3.1 and 3.2 and conditions in (14a)-(14c), let ε>0 be given. Choose λ=Θ⁡(ε) and T=M=⌈B2⌉. Let Φ^r0=Φ^r​(x00,y00,z00) and denote Δ​Φ^=Φ^r0−F¯λ. Apply Algorithm 1 to the smoothed problem minx∈𝒳⁡maxy∈𝒴​Fλ​(x,y) with

r=max{ 2​ρλ+325​(Lλ,y+1)

+12​Lλ,x​2​(Lλ,y+1),

2​ρ+54​Lλ,y​(Lλ,y+1)

+4Lλ,x3​Lλ,y​(Lλ,y+1)},

αx=min{ 112​(r+Lλ,x+2​Lλ,y),

(r−ρλ)224​(r+Lλ,x)2​(Lλ,y+1),r−(ρλ+2​Lλ,y)2​Lλ,y​(Lλ,x+r)}

and

αy=min⁡{αx,140​Lλ,y,14​(2​Lλ,y+1)}.

Additionally, for the finite-sum setting, take all N samples to obtain the gradient estimators when τ=0, thus B=N, while for the online setting, let

B={𝒪((σλ,x2+σλ,y2(Lλ,y2+Lλ,x)​ε2)max{Lλ,x+Lλ,y2,(Lλ,y+Lλ,x)μ2,Lλ,y(Lλ,y+Lλ,x)2}), if ​θ∈[0,12],𝒪((σλ,x2+σλ,y2Lλ,y2+Lλ,x)max{Lλ,y2​(Lλ,y2+Lλ,x)ε2,(Lλ,y2+Lλ,y​Lλ,x)2​θ​Lλ,yμ2​ε4​θ,(Lλ,x+Lλ,y2)2​θ−12​θ​Lλ,y12​θ​(Lλ,y2+Lλ,y​Lλ,x)μ1θ​ε4​θ−1θ,Lλ,y2​(Lλ,y+Lλ,x)3​θ−1θμ1θ​ε4​θ−1θ}), if θ∈(12,1].

Moreover, let

β={min⁡{130,130​r,Lλ,y20​r​ϖλ}, if ​θ∈[0,12],Θ(min{1r,αx2​θ−12​θLλ,y−12​θμ1θε2​θ−1θ,r−(2​θ−1)​μ2​Lλ,y−1​ε4​θ−2,r−2​θ−1θLλ,yθ−1θμ1θε2​θ−1θ}), if ​θ∈(12,1].

Then the algorithm can output a nearly ε-GS point in expectation of (P) in

K​T={𝒪((Δ​Φ^​Lλ,y2ε2)max{Lλ,x+Lλ,y2,(Lλ,y+Lλ,x)μ2}), if ​θ∈[0,12],𝒪(ΔΦ^max{Lλ,y2​(Lλ,y2+Lλ,x)ε2,(Lλ,y2+Lλ,y​Lλ,x)2​θ​Lλ,yμ2​ε4​θ,(Lλ,x+Lλ,y2)2​θ−12​θ​Lλ,y12​θ​(Lλ,y2+Lλ,y​Lλ,x)μ1θ​ε4​θ−1θ,Lλ,y2​(Lλ,y+Lλ,x)3​θ−1θμ1θ​ε4​θ−1θ}), if ​θ∈(12,1],

iterations and by 𝒪⁡(⌈B⌉​K​T) sampled gradients.

Given ε∈(0,1), note that when λ=Θ⁡(ε), we have from from Lemma B.2 that Lλ,x=Θ⁡(λ−1)=Θ⁡(ε−1), and Lλ,y is independent of ε. Thus, without specifying the dependence on other quantities, we have the overall iteration complexity K​T=𝒪⁡(max⁡{ε−3,ε−5​θ,ε−11​θ−32​θ}). Consequently, the sample complexity in the finite-sum setting is 𝒪⁡(N​max⁡{ε−3,ε−5​θ,ε−11​θ−32​θ}). For the online setting, since Lλ,x=Θ⁡(ε−1) and Lλ,y is independent of ε, we have B=𝒪⁡(max⁡{ε−2,ε−5​θ+1,ε−9​θ−32​θ}), thus the overall sample complexity is 𝒪⁡(max⁡{ε−4,ε−15​θ−12,ε−31​θ−94​θ}).

These results are novel. We discuss a few special cases below. In the finite-sum setting, when N=Ω⁡(ε−2), our result is better than that of the deterministic method in (Li et al., 2025), which assumes a stronger proximal-linear-type oracle. When θ=1, our result reduces to 𝒪⁡(N​ε−5). Recall that in this case, the e-KŁ condition is implied by the concavity on y. Thus our result is better than the 𝒪⁡(ε−8) complexity in (Lin et al., 2025) if N=𝒪⁡(ε−6) under a weaker condition. Moreover, in the online setting, when θ∈[0,35], our result becomes 𝒪⁡(ε−4), which matches the 𝒪⁡(ε−4) complexity in (Lin et al., 2025) for the smooth nonconvex-strongly-concave case and strictly better than 𝒪~​(ε−6) complexity in (Lin et al., 2025) for the nonsmooth nonconvex-strongly-concave case. When θ=1, our result reduces to 𝒪⁡(ε−7); it is worse than the 𝒪~​(ε−6) complexity in (Rafique et al., 2018), but notice that our assumption of e-KŁ is weaker than the concavity assumed by the latter.

4 Concluding Remarks

We have presented a variance-reduced framework for solving fully nonconvex-nonconcave stochastic minimax optimization problems under weak convexity and the extended KŁ property — assumptions which are substantially weaker than those commonly adopted in literature. By integrating SPIDER-type variance reduction, our method achieves guaranteed convergence with improved iteration and sample complexity in both the online and finite-sum settings. By Moreau-envelope smoothing, we are able to further extend our framework by applying it to a structured nonsmooth problem and establish rigorous complexity results.

We observe that, in the nonsmooth case, the sample complexity becomes 𝒪⁡(ε−7) in the extreme case of θ=1, which is implied by a restricted concavity condition in the dual variable. Although this result is new, we conjecture that this complexity can be further reduced, which is worth exploring in future work.

References

Arjevani et al. (2023) Y. Arjevani, Y. Carmon, J. C. Duchi, D. J. Foster, N. Srebro, and B. Woodworth Lower bounds for non-convex stochastic optimization. Mathematical Programming 199 (1), pp. 165–214. Cited by: Remark 2.5.

Bolte et al. (2014) J. Bolte, S. Sabach, and M. Teboulle Proximal alternating linearized minimization for nonconvex and nonsmooth problems. Mathematical Programming 146 (1–2), pp. 459–494. External Links: Document Cited by: Remark 2.3.

Chen et al. (2022) L. Chen, B. Yao, and L. Luo Faster stochastic algorithms for minimax optimization under polyak–Łojasiewicz conditions. In Advances in Neural Information Processing Systems (NeurIPS), Vol. 35, pp. 1–14. Note: arXiv preprint External Links: 2307.15868 Cited by: §1.1, §1.2, Table 1, Remark 2.5.

Chen et al. (2014) Y. Chen, G. Lan, and Y. Ouyang Optimal primal-dual methods for a class of saddle point problems. SIAM Journal on Optimization 24 (4), pp. 1779–1814. Cited by: §1.1.

Drusvyatskiy and Paquette (2019) D. Drusvyatskiy and C. Paquette Efficiency of minimizing compositions of convex functions and smooth maps. Mathematical Programming 178 (1-2), pp. 503–558. External Links: Document Cited by: Appendix B, Appendix B, Appendix B.

Fang et al. (2018) C. Fang, C. J. Li, Z. Lin, and T. Zhang SPIDER: near-optimal non-convex optimization via stochastic path integrated differential estimator. Advances in Neural Information Processing Systems 31, pp. 689–699. Cited by: §1.1, §2.1.

Goodfellow et al. (2014) I. Goodfellow, J. Pouget-Abadie, M. Mirza, B. Xu, D. Warde-Farley, S. Ozair, A. Courville, and Y. Bengio Generative adversarial nets. In Advances in Neural Information Processing Systems, pp. 2672–2680. Cited by: §1.

Hamedani and Aybat (2021) E. Y. Hamedani and N. S. Aybat A primal-dual algorithm with line search for general convex-concave saddle point problems. SIAM Journal on Optimization 31 (2), pp. 1299–1329. Cited by: §1.1.

Huang et al. (2023) F. Huang, C. Xuan, X. Wang, S. Zhang, and S. Chen Enhanced adaptive gradient algorithms for nonconvex-pl minimax optimization. arXiv preprint. Note: arXiv:2303.03984 Cited by: §1.1.

Jiang et al. (2024) X. Jiang, L. Zhu, A. M.-C. So, S. Cui, and J. Sun Shuffling gradient descent-ascent with variance reduction for nonconvex-strongly concave smooth minimax problems. arXiv preprint arXiv:2410.04761. Cited by: §1.1, Table 1.

Jiang et al. (2025) X. Jiang, L. Zhu, T. Zheng, and A. M. So Single‑loop variance‑reduced stochastic algorithm for nonconvex‑concave minimax optimization. Note: arXiv preprint arXiv:2501.05677Submitted on 10 January 2025 External Links: Link Cited by: §A.2, §1.1, §1.2, Table 1, §2.1, Remark 2.5.

Johnson and Zhang (2013) R. Johnson and T. Zhang Accelerating stochastic gradient descent using predictive variance reduction. In Advances in neural information processing systems, pp. 315–323. Cited by: §1.1.

Kim et al. (2025) K. Kim, R. Yao, C. Zhu, and X. Chen Optimal transport barycenter via nonconvex‑concave minimax optimization. Note: arXiv:2501.14635 [cs, math] External Links: Link, 2501.14635 Cited by: §1.

Levy et al. (2020) D. Levy, Y. Carmon, J. C. Duchi, and A. Sidford Large-scale methods for distributionally robust optimization. In Advances in Neural Information Processing Systems, External Links: Link Cited by: item i. , item i. , §3.1.

Li et al. (2025) J. Li, L. Zhu, and A. M. So Nonsmooth nonconvex–nonconcave minimax optimization: primal–dual balancing and iteration complexity analysis. Mathematical Programming, Series A 214, pp. 591–641. External Links: Document, Link Cited by: §A.2, §A.2, §A.2, §A.2, §A.2, §A.2, §A.2, §1.1, §2.1, §2.2, Remark 3.5.

Lin et al. (2020a) T. Lin, C. Jin, and M. I. Jordan Near-optimal algorithms for minimax optimization. In Conference on Learning Theory, pp. 2738–2779. Cited by: §1.1.

Lin et al. (2020b) T. Lin, C. Jin, and M. I. Jordan On gradient descent ascent for nonconvex-concave minimax problems. In International Conference on Machine Learning, pp. 6083–6093. Cited by: §1.1, §1.1.

Lin et al. (2025) T. Lin, C. Jin, and M. I. Jordan Two‐timescale gradient descent ascent algorithms for nonconvex minimax optimization. Journal of Machine Learning Research 26 (11), pp. 1–45. Note: Published 2025 Cited by: §1.1, Table 1, Remark 2.5, Remark 3.5.

Liu et al. (2021) M. Liu, H. Rafique, Q. Lin, and T. Yang First-order convergence theory for weakly-convex–weakly-concave min-max problems. Journal of Machine Learning Research 22 (1), pp. 7651–7684. Cited by: §1.1.

Madry et al. (2018) A. Madry, A. Makelov, L. Schmidt, D. Tsipras, and A. Vladu Towards deep learning models resistant to adversarial attacks. arXiv preprint arXiv:1706.06083. Cited by: §1.

Oren et al. (2019) Y. Oren, S. Sagawa, T. B. Hashimoto, and P. Liang Distributionally robust language modeling. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP‑IJCNLP), pp. 4227–4237. External Links: Document, Link Cited by: item ii..

Pang (1987) J.-S. Pang A posteriori error bounds for the linearly-constrained variational inequality problem. Mathematics of Operations Research 12 (3), pp. 474–484. Cited by: §A.2.

Pfohl et al. (2022) S. R. Pfohl, H. Zhang, Y. Xu, and N. H. Shah A comparison of approaches to improve worst-case predictive model performance over patient subpopulations. Scientific Reports 12, pp. 3254. External Links: Document, Link Cited by: item ii..

Pinto et al. (2017) L. Pinto, J. Davidson, R. Sukthankar, and A. Gupta Robust adversarial reinforcement learning. In International Conference on Machine Learning, pp. 2817–2826. Cited by: §1.

Rafique et al. (2018) H. Rafique, M. Liu, Q. Lin, and T. Yang Weakly-convex concave min-max optimization: provable algorithms and applications in machine learning. External Links: 1810.02060, Link Cited by: Table 1, Remark 2.5, Remark 3.5.

Rahimian and Mehrotra (2019) H. Rahimian and S. Mehrotra Distributionally robust optimization: a review. arXiv preprint arXiv:1908.05659. Cited by: §1.

Sagawa et al. (2020) S. Sagawa, P. W. Koh, T. B. Hashimoto, and P. Liang Distributionally robust neural networks for group shifts: on the importance of regularization for worst‑case generalization. arXiv preprint arXiv:1911.08731. Note: Published as a conference paper at ICLR 2020 Cited by: item ii., §3.1.

Wen et al. (2022) H. Wen, X. Yi, T. Yao, J. Tang, L. Hong, and E. H. Chi Distributionally‐robust recommendations for improving worst‐case user experience. In Proceedings of the ACM Web Conference 2022 (WWW ’22), Virtual Event, Lyon, France, April 25–29, 2022, pp. 3606–3610. External Links: Document Cited by: item ii..

Yang et al. (2022) J. Yang, A. Orvieto, A. Lucchi, and N. He Faster single-loop algorithms for minimax optimization without strong concavity. In International Conference on Artificial Intelligence and Statistics, pp. 5485–5517. Cited by: §1.1.

Zhang and Xiao (2019) J. Zhang and L. Xiao A stochastic composite gradient method with incremental variance reduction. arXiv preprint arXiv:1906.10186. External Links: Link, 1906.10186 Cited by: §A.2.

Zhang et al. (2024) X. Zhang, N. S. Aybat, and M. Gürbüzbalaban SAPD+: an accelerated stochastic method for nonconvex-concave minimax problems. arXiv preprint arXiv:2205.15084v4. External Links: Link Cited by: Table 1.

Zheng et al. (2023) T. Zheng, Z. Linglingzhi, A. M.-C. So, J. Blanchet, and J. Li Universal gradient descent ascent method for nonconvex-nonconcave minimax optimization. In Advances in Neural Information Processing Systems, Vol. 36, pp. 54075–54110. Cited by: §1.1.

Zheng et al. (2025) T. Zheng, A. M.-C. So, and J. Li Doubly smoothed optimistic gradients: a universal approach for smooth minimax problems. arXiv preprint. Note: arXiv:2506.07397 Cited by: §1.1, §1.2, §1.2, Table 1, Remark 2.5.

We provide complete proofs of all theorems claimed in the main body of the paper. Beyond the key notations in Table 2, we list a few more in Table 3 for convenience of our analysis.

Table 3: More Notations and Definitions

Notation Definition

y+​(z) proj𝒴​(y+αy​∇yF​(xr​(y,z),y))

Y⁡(z) arg⁡maxy∈𝒴​dr​(y,z)​; ​y​(z)∈Y⁡(z)

xτ,+k​(y,z) proj𝒳​(xτk−αx​∇xFr​(xτk,y,z))

yτ,+k​(z) proj𝒴​(yτk+αy​∇yF​(xr​(yτk,z),yτk))

xrλ​(y,z) arg⁡minx∈𝒳​Frλ​(x,y,z)

Appendix A Proofs for the smooth case

We first provide the claim in Remark 2.3 that our assumed e-KŁ condition is implied by the star-concavity in the case of θ=1.

A.1 Proof of the claim in Remark 2.3

To show this claim, for any y∈𝒴, let us define

y∗∈argmaxy′∈𝒴​F​(x,y′),

g∗∈argming∈−∇yF​(x,y)+𝒩𝒴​(y)​‖g‖.

When F⁡(x,⋅) is restricted concave on 𝒴, i.e.,

F⁡(x,y∗)≤F⁡(x,y)+⟨∇yF​(x,y),y∗−y⟩,∀y∈𝒴,

we have from Cauchy-Schwarz inequality that

maxy′∈𝒴⁡F⁡(x,y′)=F⁡(x,y∗)

≤F⁡(x,y)+⟨−g∗,y∗−y⟩

≤F⁡(x,y)+‖g∗‖​‖y∗−y‖

≤F⁡(x,y)+D𝒴​dist​(0,−∇yF​(x,y)+𝒩𝒴​(y)).

Thus F⁡(x,⋅) satisfies (4) with parameters μ=1D𝒴 and θ=1.

A.2 Proofs for the smooth case

To establish our main complexity results in the smooth case, we start from showing a few error bound inequalities.

Let Gx,τk and Gy,τk be defined in (5) and (6) and denote

Cσ,x=Cσ,y=0, for finite-sum setting,

Cσ,x=σx2B,Cσ,y=σy2B, for online setting.

Then under Assumption 2.1, for any k≥0 and any 0≤τ≤T−1, the following error bounds hold:

𝔼​‖Gy,τk−∇yF​(xτk,yτk)‖2≤Ly2M​∑b=0τ−1𝔼​‖xb+1k−xbk‖2+Ly2M​∑b=0τ−1𝔼​‖yb+1k−ybk‖2+Cσ,y, (15)

𝔼​‖Gx,τk−∇xF​(xτk,yτk)‖2≤2​Lx2M​∑b=0τ−1𝔼​‖xb+1k−xbk‖2+2​Ly2M​∑b=0τ−1𝔼​‖yb+1k−ybk‖2+Cσ,x. (16)

For ease of notation, denote the variance of a random variable ζ by Var⁡(ζ)=𝔼​‖ζ−𝔼⁡(ζ)‖2. Then following the proof of (Zhang and Xiao, 2019, Lemma 1), we have

𝔼​‖Gy,τk−∇yF​(xτk,yτk)‖2

≤ 𝔼​‖Gy,τ−1k−∇yF​(xτ−1k,yτ−1k)‖2+Var⁡(1M​∑i=1M(∇yf​(xτk,yτk,𝝃τ,ik)−∇yf​(xτ−1k,yτ−1k,𝝃τ,ik)))

≤(i) 𝔼​‖Gy,τ−1k−∇yF​(xτ−1k,yτ−1k)‖2+1M​𝔼​‖∇yf​(xτk,yτk,𝝃τ,ik)−∇yf​(xτ−1k,yτ−1k,𝝃τ,ik)‖2

≤(i​i) 𝔼​‖Gy,τ−1k−∇yF​(xτ−1k,yτ−1k)‖2+Ly2M​(𝔼​‖xτk−xτ−1k‖2+𝔼​‖yτk−yτ−1k‖2)

≤(i​i​i) 𝔼​‖Gy,0k−∇yF​(x0k,y0k)‖2⏟①+Ly2M​∑b=1τ(𝔼​‖xbk−xb−1k‖2+𝔼​‖ybk−yb−1k‖2) (17)

where (i) follows since the samples are i.i.d and 𝔼​‖ζ−𝔼⁡(ζ)‖2≤𝔼​‖ζ‖2, (i​i) follows from the Ly-Lipschitz continuity of ∇yf​(⋅,⋅,𝝃), and (i​i​i) follows from applying the inequality recursively.

We now bound ① in (17). In the finite-sum setting, since we take all N samples, we have

Gy,0k=1N​∑i=1N∇yf​(x0k,y0k,𝝃0,ik)=∇yF​(x0k,y0k),

and thus ①=0. In the online setting, since the samples are i.i.d., Assumption 2.1(v.) implies ①≤σy2B. Plugging these bounds back into (17) yields the desired result in (15).

Similarly, we have

𝔼​‖Gx,τk−∇xF​(xτk,yτk)‖2

≤ 𝔼​‖Gx,τ−1k−∇xF​(xτ−1k,yτ−1k)‖2+1M​𝔼​‖∇xf​(xτk,yτk,𝝃τ,ik)−∇xf​(xτ−1k,yτ−1k,𝝃τ,ik)‖2. (18)

Now, by applying Young’s inequality and using the fact that ∇xF​(x,y) is Lx-Lipschitz in x and Ly-Lipschitz in y, we can bound the second term in (18) by

𝔼​‖∇xf​(xτk,yτk,𝝃τ,ik)−∇xf​(xτ−1k,yτ−1k,𝝃τ,ik)‖2

≤ 2​𝔼​‖∇xf​(xτk,yτk,𝝃τ,ik)−∇xf​(xτ−1k,yτk,𝝃τ,ik)‖2+2​𝔼​‖∇xf​(xτ−1k,yτk,𝝃τ,ik)−∇xf​(xτ−1k,yτ−1k,𝝃τ,ik)‖2

≤ 2​Lx2​‖xτk−xτ−1k‖2+2​Ly2​‖yτk−yτ−1k‖2

Plugging this bound back into (18) and utilizing a line of reasoning similar to that in the proof for (15), we retrieve (16). ∎

For any y,y′∈𝒴 and z,z′∈ℝdx, we have

‖xr​(y,z)−xr​(y,z′)‖2≤σ12​‖z−z′‖2, (19)

‖xr​(y,z)−xr​(y′,z)‖2≤σ22​‖y−y′‖2, (20)

where σ1=rr−ρ and σ2=2+Lyr−ρ.

First, we note that the proof of (19) in (Li et al., 2025) fundamentally relies on the weak convexity of the function in x and the Lipschitz smoothness of the objective in y. Since our assumptions on F⁡(x,y) satisfy these same conditions, we can directly adopt their proof without modification.

We now turn to the proof of (20). The overall structure of our proof closely follows that of (Li et al., 2025), with minor adjustments to accommodate our specific setting. In particular, since F⁡(⋅,y) is ρ-weakly convex in x for any fixed y, it follows that

Fr​(xr​(y′,z),y,z)−Fr​(xr​(y,z),y,z)≥r−ρ2​‖xr​(y′,z)−xr​(y,z)‖2, (21)

Fr​(xr​(y,z),y′,z)−Fr​(xr​(y′,z),y′,z)≥r−ρ2​‖xr​(y,z)−xr​(y′,z)‖2, (22)

Additionally, from the Ly-Lipschitz continuity of ∇yF​(⋅,⋅), we have

Fr​(xr​(y,z),y′,z)−Fr​(xr​(y,z),y,z)≤⟨∇yF​(xr​(y,z),y,z),y′−y⟩+Ly2​‖y−y′‖2, (23)

Fr​(xr​(y′,z),y,z)−Fr​(xr​(y′,z),y′,z)≤⟨∇yF​(xr​(y′,z),y′,z),y−y′⟩+Ly2​‖y−y′‖2, (24)

Adding (21) and (22), plugging in the sum of (23) and (24), and using the Lipschitz continuity of ∇yF along with the Cauchy–Schwarz inequality, we get

(r−ρ)​‖xr​(y,z)−xr​(y′,z)‖2

≤ ⟨∇yFr​(xr​(y,z),y,z)−∇yFr​(xr​(y′,z),y′,z),y′−y⟩+Ly​‖y−y′‖2

≤ ‖∇yFr​(xr​(y,z),y,z)−∇yFr​(xr​(y′,z),y′,z)‖​‖y′−y‖+Ly​‖y−y′‖2

≤ (Ly​‖xr​(y,z)−xr​(y′,z)‖+Ly​‖y′−y‖)​‖y′−y‖+Ly​‖y−y′‖2

= Ly​‖xr​(y,z)−xr​(y′,z)‖​‖y′−y‖+2​Ly​‖y−y′‖2 (25)

Letting ϱ=‖xr​(y,z)−xr​(y′,z)‖‖y′−y‖ and rearranging (25), we get

ϱ2≤ Lyr−ρ​ϱ+2​Lyr−ρ

≤(i) 12​ϱ2+Ly22​(r−ρ)2+2​Lyr−ρ

= 12​ϱ2+Ly2+4​Ly​(r−ρ)2​(r−ρ)2

≤ 12​ϱ2+(Ly+2​(r−ρ))22​(r−ρ)2,

where (i) follows from Young’s inequality. The desired result follows immediately from the above and this completes the proof. ∎

The next lemma is taken directly from (Li et al., 2025). Though our algorithm is stochastic, the definition of xr and dr is based on the deterministic function. Thus this lemma also holds for our case.

For any y,y′,y′′∈𝒴 and z,z′,z′′∈ℝdx, we have

‖∇ydr​(y′,z)−∇ydr​(y′′,z)‖≤Ldr​‖y′−y′′‖, (26)

where Ldr=(σ2+1)​Ly.

Under Assumption 2.1, for any k≥0 and 0≤τ≤T−1, we have

‖xτk−xr​(yτk,zτk)‖≤η⁡‖xτk−xτ,+k​(yτk,zτk)‖, (27)

where η=αx​Lx+αx​r+1αx​r−αx​ρ.

The proof follows (Pang, 1987), with modifications to fit our setting. Let us first define

uτk=xτk−xτ,+k​(yτk,zτk)⟹xτk−uτk=xτ,+k​(yτk,zτk)∈𝒳.

By the definition of xr​(yτk,zτk), the first-order optimality condition yields

⟨∇xFr​(xr​(yτk,zτk),yτk,zτk),(xτk−uτk)−xr​(yτk,zτk)⟩≥0

⟹⟨αx​∇xFr​(xr​(yτk,zτk),yτk,zτk),(xτk−uτk)−xr​(yτk,zτk)⟩≥0. (28)

Similarly, by the definition of the projected gradient step xτ,+k​(yτk,zτk) we obtain

⟨(xτk−uτk)−(xτk−αx​∇xFr​(xτk,yτk,zτk)),xr​(yτk,zτk)−(xτk−uτk)⟩≥0. (29)

Adding (28) and (29) leads to

⟨αx​∇xFr​(xr​(yτk,zτk),yτk,zτk)−αx​∇xFr​(xτk,yτk,zτk)+uτk,(xτk−xr​(yτk,zτk))−uτk⟩≥0,

which, after rearranging terms, implies

⟨αx​∇xFr​(xτk,yτk,zτk)−αx​∇xFr​(xr​(yτk,zτk),yτk,zτk),xτk−xr​(yτk,zτk)⟩

≤ ⟨αx​∇xFr​(xτk,yτk,zτk)−αx​∇xFr​(xr​(yτk,zτk),yτk,zτk),uτk⟩+⟨uτk,xτk−xr​(yτk,zτk)⟩−‖uτk‖2

≤ ‖αx​∇xFr​(xτk,yτk,zτk)−αx​∇xFr​(xr​(yτk,zτk),yτk,zτk)‖​‖uτk‖+‖xτk−xr​(yτk,zτk)‖​‖uτk‖

≤(i) (αx​(r+Lx)+1)​‖xτk−xr​(yτk,zτk)‖​‖xτk−xτ,+k​(yτk,zτk)‖, (30)

where (i) follows from the (r+Lx)-Lipschitz smoothness of ∇xFr​(⋅,y,z) and the definition of uτk.

Now, since Fr​(⋅,y,z) is (r−ρ)-strongly convex, we have

⟨αx​∇xFr​(xτk,yτk,zτk)−αx​∇xFr​(xr​(yτk,zτk),yτk,zτk),xτk−xr​(yτk,zτk)⟩≥αx​(r−ρ)​‖xτk−xr​(yτk,zτk)‖2 (31)

Finally, combining (31) and (30) yields the desired inequality, completing the proof. ∎

We are now ready to establish the primal error bound.

Under Assumption 2.1, for any k≥0 and 0≤τ≤T−1, we have

𝔼​‖xτ+1k−xr​(yτk,zτk)‖2≤ (5​η22+5)​𝔼​‖xτ+1k−xτk‖2+5​η2​αx2​Lx2M​∑b=0τ−1𝔼​‖xb+1k−xbk‖2

+5​η2​αx2​Ly2M∑b=0τ−1𝔼‖yb+1k−ybk‖2+5​αx2​η2​Cσ,x2.

Utilizing Young’s inequality, we have

𝔼​‖xτ+1k−xr​(yτk,zτk)‖2≤ 5​𝔼​‖xτ+1k−xτk‖2+54​𝔼​‖xτk−xr​(yτk,zτk)‖2

≤(i) 5​𝔼​‖xτ+1k−xτk‖2+5​η24​𝔼​‖xτk−xτ,+k​(yτk,zτk)‖2

≤(i) (5​η22+5)​𝔼​‖xτ+1k−xτk‖2+5​η22​𝔼​‖xτ+1k−xτ,+k​(yτk,zτk)‖2, (32)

where (i) follows from Lemma A.4. We now bound the second term in (32) by

𝔼​‖xτ+1k−xτ,+k​(yτk,zτk)‖2= 𝔼​‖proj𝒳​(xτk−αx​[Gx,τk+r⁡(xτk−zτk)])−proj𝒳​(xτk−αx​∇xFr​(xτk,yτk,zτk))‖2

≤(i) αx2​𝔼​‖∇xF​(xτk,yτk)−Gx,τk‖2

≤(i​i) 2​αx2​Lx2M​∑b=0τ−1𝔼​‖xb+1k−xbk‖2+2​αx2​Ly2M​∑b=0τ−1𝔼​‖yb+1k−ybk‖2+αx2​Cσ,x, (33)

where (i) follows from non-expansiveness of the projection operator, and (i​i) holds by (16). Consequently, plugging (33) into (32), we get the desired inequality. ∎

The next lemma is adapted directly from (Li et al., 2025). The only modification is that we assume ρ-weak convexity, and apart from this, all other arguments in its proof remain unchanged.

Under Assumption 2.1, for any y∈𝒴 and z∈ℝdx, we have

r−ρ2​‖xr​(y⁡(z),z)−xr​(y+​(z),z)‖2≤maxy′∈𝒴⁡F⁡(xr​(y+​(z),z),y′)−F⁡(xr​(y+​(z),z),y+​(z)). (34)

We are now in a position to formally establish the dual error bound. Its proof adapts from that in (Li et al., 2025) but tightens the bound for the case of θ∈(0,12].

Under Assumptions 2.1 and 2.2, for any y∈𝒴 and z∈ℝdx, we have

‖xr​(y⁡(z),z)−xr​(y+​(z),z)‖2≤ϖ​‖y−y+​(z)‖2, f​o​r​θ∈[0,12], (35)

‖xr​(y⁡(z),z)−xr​(y+​(z),z)‖2≤κ​‖y−y+​(z)‖1θ, f​o​r​θ∈(12, 1], (36)

where ϖ=2​(ℓ​D𝒴)1−2​θr−ρ​(2αy2+2​Ly2​σ22+2​Ly2μ2), and κ=2r−ρ​(2αy2+2​Ly2​σ22+2​Ly2μ)1θ, with σ2=2+Lyr−ρ the same as that in Lemma A.2.

We first discuss the case when θ=0. We note that if maxy′∈𝒴⁡F⁡(xr​(y+​(z),z),y′)−F⁡(xr​(y+​(z),z),y+​(z))=0, then from (34), it follows trivially that

r−ρ2​‖xr​(y⁡(z),z)−xr​(y+​(z),z)‖2≤0≤ℓ⋅D𝒴​(2αy2+2​Ly2​σ22+2​Ly2)μ2​‖y−y+​(z)‖2,

which renders the desired inequality in (35) for θ=0. Hence, we suppose maxy′∈𝒴⁡F⁡(xr​(y+​(z),z),y′)−F⁡(xr​(y+​(z),z),y+​(z))≠0. Then from (4), it holds

dist⁡(0,−∇yF​(xr​(y+​(z),z),y+​(z))+𝒩𝒴​(y+​(z)))≥μ. (37)

By the definition of y+​(z) in Table 2, we have

0 ∈(y+​(z)−y)−αy​∇yF​(xr​(y,z),y)+𝒩𝒴​(y+​(z))

⟹ 1αy​(y−y+​(z))+∇yF​(xr​(y,z),y)−∇yF​(xr​(y+​(z),z),y+​(z))∈−∇yF​(xr​(y+​(z),z),y+​(z))+𝒩𝒴​(y+​(z))

Hence, by Young’s inequality, the Ly-Lipschitz continuity of ∇yF and (20), it follows

(dist⁡(0,−∇yF​(xr​(y+​(z),z),y+​(z))+𝒩𝒴​(y+​(z))))2

≤ ‖1αy​(y−y+​(z))+∇yF​(xr​(y,z),y)−∇yF​(xr​(y+​(z),z),y+​(z))‖2

≤ 2αy2​‖y−y+​(z)‖2+2​‖∇yF​(xr​(y,z),y)−∇yF​(xr​(y+​(z),z),y+​(z))‖2

≤ (2αy2+2​Ly2​σ22+2​Ly2)​‖y−y+​(z)‖2, (38)

which together with (37) gives

1μ2​(2αy2+2​Ly2​σ22+2​Ly2)​‖y−y+​(z)‖2≥1. (39)

In addition, by the ℓ-Lipschitz continuity of F from Assumption 2.1, it holds that

maxy′∈𝒴⁡F⁡(xr​(y+​(z),z),y′)−F⁡(xr​(y+​(z),z),y+​(z))≤ℓ⋅D𝒴. (40)

Now by (34), (39), and (40), we get (35) for θ=0.

Second, we discuss the case when θ∈(0,12]. We have

μ​(maxy′∈𝒴⁡F⁡(xr​(y+​(z),z),y′)−F⁡(xr​(y+​(z),z),y+​(z)))12

= μ​(maxy′∈𝒴⁡F⁡(xr​(y+​(z),z),y′)−F⁡(xr​(y+​(z),z),y+​(z)))θ

(maxy′∈𝒴⁡F⁡(xr​(y+​(z),z),y′)−F⁡(xr​(y+​(z),z),y+​(z)))12−θ

≤ (ℓ​D𝒴)12−θ​(2αy2+2​Ly2​σ22+2​Ly2)​‖y−y+​(z)‖,

where the inequality follows from (4), (38), and (40). The above inequality together with (34) implies (35).

Third, we discuss the case when θ∈(12,1]. We have from (4) and (38) that

μ​(maxy′∈𝒴⁡F⁡(xr​(y+​(z),z),y′)−F⁡(xr​(y+​(z),z),y+​(z)))θ

≤ (2αy2+2​Ly2​σ22+2​Ly2)​‖y−y+​(z)‖

which together with (34) gives (36). This completes the proof. ∎

In preparation for establishing a sufficient decrease condition for the Lyapunov function defined in (7), we first present several auxiliary lemmas that will be vital in the subsequent analysis.

Under Assumption 2.1, let {xτk,yτk,zτk} be generated from Algorithm 1. Then it holds for any k≥0 and any 0≤τ≤T−1 that

𝔼⁡[Fr​(xτk,yτk,zτk)−Fr​(xτ+1k,yτ+1k,zτ+1k)]

≥ (12​αx−r+Lx2)​𝔼​‖xτ+1k−xτk‖2−αx​Lx2M​∑b=0τ−1𝔼​‖xb+1k−xbk‖2−αx​Ly2M​∑b=0τ−1𝔼​‖yb+1k−ybk‖2

+𝔼⁡⟨∇yFr​(xτ+1k,yτk,zτk),yτk−yτ+1k⟩−Ly2​𝔼​‖yτ+1k−yτk‖2+(2−β)​r​β2​𝔼​‖xτ+1k−zτk‖2−αx​Cσ,x2.

Our proof technique is similar to that in (Jiang et al., 2025), upon which we build to accommodate our setting and extend the result. We split the change of function to three parts as follows

𝔼⁡[Fr​(xτk,yτk,zτk)−Fr​(xτ+1k,yτ+1k,zτ+1k)]

= 𝔼⁡[Fr​(xτk,yτk,zτk)−Fr​(xτ+1k,yτk,zτk)]⏟①+𝔼⁡[Fr​(xτ+1k,yτk,zτk)−Fr​(xτ+1k,yτ+1k,zτk)]⏟②

+𝔼⁡[Fr​(xτ+1k,yτ+1k,zτk)−Fr​(xτ+1k,yτ+1k,zτ+1k)]⏟③ (41)

We first bound ① in (41). From the update for xτ+1k in Algorithm 1, we have that for any x∈𝒳, it holds

⟨xτ+1k−(xτk−αx​[Gx,τk+r⁡(xτk−zτk)]),x−xτ+1k⟩≥0.

Letting x=xτk in the above inequality and rearranging terms yields

⟨Gx,τk+r⁡(xτk−zτk),xτ+1k−xτk⟩≤−1αx​‖xτ+1k−xτk‖2. (42)

In addition, by the (r+Lx)-smoothness of Fr(.,y,z) , we have

Fr​(xτ+1k,yτk,zτk)≤Fr​(xτk,yτk,zτk)+⟨∇xFr​(xτk,yτk,zτk),xτ+1k−xτk⟩+r+Lx2​‖xτ+1k−xτk‖2. (43)

For the inner product term in (43), we split it and then bound each term by

⟨∇xFr​(xτk,yτk,zτk),xτ+1k−xτk⟩

= ⟨∇xF​(xτk,yτk)−Gx,τk,xτ+1k−xτk⟩+⟨Gx,τk+r⁡(xτk−zτk),xτ+1k−xτk⟩

≤ αx2​‖∇xF​(xτk,yτk)−Gx,τk‖2+12​αx​‖xτ+1k−xτk‖2−1αx​‖xτ+1k−xτk‖2, (44)

where the inequality follows from the Young’s inequality and (42). Now taking expectation on both sides of (44) and using (16), we obtain

𝔼⁡[⟨∇xFr​(xτk,yτk,zτk),xτ+1k−xτk⟩]≤ αx​Lx2M​∑b=0τ−1𝔼​‖xb+1k−xbk‖2+αx​Ly2M​∑b=0τ−1𝔼​‖yb+1k−ybk‖2

−12​αx​𝔼​‖xτ+1k−xτk‖2+αx​Cσ,x2.

Taking expectation on both sides of (43), plugging the above inequality, and rearranging terms, we obtain

𝔼⁡[Fr​(xτk,yτk,zτk)−Fr​(xτ+1k,yτk,zτk)]≥ (12​αx−r+Lx2)​𝔼​‖xτ+1k−xτk‖2−αx​Lx2M​∑b=0τ−1𝔼​‖xb+1k−xbk‖2

−αx​Ly2M∑b=0τ−1𝔼‖yb+1k−ybk‖2−αx​Cσ,x2. (45)

Second, for ② in (41), since ∇yFr​(x,⋅,z) is Ly-Lipschitz continuous, we have

𝔼⁡[Fr​(xτ+1k,yτk,zτk)−Fr​(xτ+1k,yτ+1k,zτk)]≥ 𝔼⁡[⟨∇yFr​(xτ+1k,yτk,zτk),yτk−yτ+1k⟩]−Ly2​𝔼​‖yτ+1k−yτk‖2. (46)

Third, for ③ in (41), based on the update for z, we get

𝔼⁡[Fr​(xτ+1k,yτ+1k,zτk)−Fr​(xτ+1k,yτ+1k,zτ+1k)]=(2−β)​r​β2​𝔼​‖xτ+1k−zτk‖2. (47)

Plugging (45), (46), (47) into (41) gives the desired inequality. ∎

The next two lemmas can be shown by the same proofs of those in (Li et al., 2025, Lemma 6 and Lemma 7), which fundamentally rely on weak convexity in x and smoothness in y. Our assumptions on F⁡(x,y) align with these conditions, thus the proofs in (Li et al., 2025) apply directly to our setting.

Under Assumption 2.1, let {xτk,yτk,zτk} be generated from Algorithm 1. Then it holds for any k≥0 and any 0≤τ≤T−1 that

dr​(yτ+1k,zτ+1k)−dr​(yτk,zτk)≥ ⟨∇yFr​(xr​(yτk,zτk),yτk,zτk),yτ+1k−yτk⟩−Ldr2​‖yτ+1k−yτk‖2

+r2​⟨zτ+1k−zτk,zτ+1k+zτk−2​xr​(yτ+1k,zτ+1k)⟩,

where Ldr is given in Lemma A.3.

Under Assumption 2.1, let {xτk,yτk,zτk} be generated from Algorithm 1, and y⁡(zτ+1k)∈Y⁡(zτ+1k). Then it holds for any k≥0 and any 0≤τ≤T−1 that

pr​(zτk)−pr​(zτ+1k)≥ r2​⟨zτ+1k−zτk,2​xr​(y⁡(zτ+1k),zτk)−zτk−zτ+1k⟩.

We still need the following lemma that upper bounds the actual y-iterate with the virtual iterate yτ,+k.

Under Assumption 2.1, let {xτk,yτk,zτk} be generated from Algorithm 1 with r≥2​ρ. Then, it holds

𝔼​‖yτ,+k​(zτ+1k)−yτ+1k‖2

≤ 24​αy2​β2​Ly2​𝔼​‖xτ+1k−zτk‖2+6​αy2​Ly2​𝔼​‖xτ+1k−xr​(yτk,zτk)‖2+3​αy2​Ly2​𝔼​‖xτ+1k−xτk‖2

+3​αy2​Ly2M∑b=0τ−1𝔼‖yb+1k−ybk‖2+3​αy2​Ly2M∑b=0τ−1𝔼‖xb+1k−xbk‖2+3αy2Cσ,y. (48)

By the definition of yτ,+k​(z) and the update formula of y, it follows

𝔼​‖yτ,+k​(zτ+1k)−yτ+1k‖2

= 𝔼​‖proj𝒴​(yτk+αy​∇yF​(xr​(yτk,zτ+1k),yτk))−proj𝒴​(yτk+αy​Gy,τk)‖2

≤(i) 𝔼​‖yτk+αy​∇yF​(xr​(yτk,zτ+1k),yτk)−yτk−αy​Gy,τk‖2

≤(i​i) 3​αy2​𝔼​‖∇yF​(xr​(yτk,zτ+1k),yτk)−∇yF​(xτ+1k,yτk)‖2+3​αy2​𝔼​‖∇yF​(xτ+1k,yτk)−∇yF​(xτk,yτk)‖2

+3​αy2​𝔼​‖∇yF​(xτk,yτk)−Gy,τk‖2

≤(i​i​i) 3​αy2​Ly2​𝔼​‖xr​(yτk,zτ+1k)−xτ+1k‖2+3​αy2​Ly2​𝔼​‖xτ+1k−xτk‖2+3​αy2​Ly2M​∑b=0τ−1𝔼​‖yb+1k−ybk‖2

+3​αy2​Ly2M∑b=0τ−1𝔼‖xb+1k−xbk‖2+3αy2Cσ,y

≤(i​v) 6​αy2​Ly2​𝔼​‖xr​(yτk,zτ+1k)−xr​(yτk,zτk)‖2+6​αy2​Ly2​𝔼​‖xτ+1k−xr​(yτk,zτk)‖2+3​αy2​Ly2​𝔼​‖xτ+1k−xτk‖2

+3​αy2​Ly2M∑b=0τ−1𝔼‖yb+1k−ybk‖2+3​αy2​Ly2M∑b=0τ−1𝔼‖xb+1k−xbk‖2+3αy2Cσ,y, (49)

where (i) follows from the non-expansiveness of the projection operator, (i​i) and (i​v) are by Young’s inequality, and (i​i​i) holds from the Ly​-Lipschitz continuity of ​∇yF​(⋅,y) and (15). Moreover, by (19), it holds

𝔼​‖xr​(yτk,zτ+1k)−xr​(yτk,zτk)‖2≤σ12​𝔼​‖zτ+1k−zτk‖2≤4​β2​𝔼​‖xτ+1k−zτk‖2, (50)

where the second inequality follows from the update of z in Algorithm 1 and σ1≤2 (since OPENr≥2​ρ). Plugging (50) into (49) yields the desired result. ∎

We are now ready to establish the sufficient decrease condition for the Lyapunov function defined in (7).

Under Assumption 2.1, let {xτk,yτk,zτk} be generated from Algorithm 1 with r≥max⁡{2​ρ,Ly+ρ}. Then it holds for any k≥0 and any 0≤τ≤T−1 that

𝔼⁡[Φr​(xτk,yτk,zτk)−Φr​(xτ+1k,yτ+1k,zτ+1k)] (51)

≥ (12​αx−r+Lx2−16​αy​Ly2−540​r​β​αy2​Ly2)​𝔼​‖xτ+1k−xτk‖2+(1116​αy−5​Ly)​𝔼​‖yτ+1k−yτk‖2

+((2−β)​r​β2−4​r​β2−r​β10−4320​r​β3​αy2​Ly2)​𝔼​‖xτ+1k−zτk‖2

−(1080​r​β​αy2​Ly2+4​αy​Ly2)​𝔼​‖xτ+1k−xr​(yτk,zτk)‖2−(16​αy​Ly2+540​r​β​αy2​Ly2+αx​Lx2M)​∑b=0τ−1𝔼​‖xb+1k−xbk‖2

−(16​αy​Ly2+540​r​β​αy2​Ly2+αx​Ly2M)∑b=0τ−1𝔼‖yb+1k−ybk‖2

−20​r​β​𝔼​‖xr​(y⁡(zτ+1k),zτ+1k)−xr​(yτ,+k​(zτ+1k),zτ+1k)‖2−αx​Cσ,x2−(16​αy+540​r​β​αy2)​Cσ,y.

Our proof technique is similar to that in (Li et al., 2025), upon which we build to accommodate our setting and extend the result. By the definition of Φr in (7), we utilize σ2≤3 (since OPENr≥Ly+ρ), Lemmas A.8, A.9, and A.10 to have

𝔼⁡[Φr​(xτk,yτk,zτk)−Φr​(xτ+1k,yτ+1k,zτ+1k)]

= 𝔼⁡[Fr​(xτk,yτk,zτk)−Fr​(xτ+1k,yτ+1k,zτ+1k)]+2​𝔼​[dr​(yτ+1k,zτ+1k)−dr​(yτk,zτk)]+2​𝔼​[pr​(zτk)−pr​(zτ+1k)]

≥ (12​αx−r+Lx2)​𝔼​‖xτ+1k−xτk‖2−αx​Lx2M​∑b=0τ−1𝔼​‖xb+1k−xbk‖2−αx​Ly2M​∑b=0τ−1𝔼​‖yb+1k−ybk‖2

+𝔼⁡⟨∇yFr​(xτ+1k,yτk,zτk),yτk−yτ+1k⟩−Ly2​𝔼​‖yτ+1k−yτk‖2+(2−β)​r​β2​𝔼​‖xτ+1k−zτk‖2

+𝔼⁡[⟨2​∇yFr​(xr​(yτk,zτk),yτk,zτk),yτ+1k−yτk⟩−Ldr​‖yτk−yτ+1k‖2]

+r​𝔼​[⟨zτ+1k−zτk,zτ+1k+zτk−2​xr​(yτ+1k,zτ+1k)⟩]+r​𝔼​[⟨zτ+1k−zτk,2​xr​(y⁡(zτ+1k),zτk)−zτk−zτ+1k⟩]−αx​Cσ,x2

≥ (12​αx−r+Lx2)​𝔼​‖xτ+1k−xτk‖2−5​Ly​𝔼​‖yτ+1k−yτk‖2+(2−β)​r​β2​𝔼​‖xτ+1k−zτk‖2

+𝔼⁡[⟨2​∇yFr​(xr​(yτk,zτk),yτk,zτk),−∇yFr​(xτ+1k,yτk,zτk),yτ+1k−yτk⟩]⏟①

+2​r​𝔼​[⟨zτ+1k−zτk,xr​(y⁡(zτ+1k),zτk)−xr​(yτ+1k,zτ+1k)⟩]⏟②−αx​Lx2M​∑b=0τ−1𝔼​‖xb+1k−xbk‖2

−αx​Ly2M∑b=0τ−1𝔼‖yb+1k−ybk‖2−αx​Cσ,x2. (52)

Below we bound ① and ② in (52). First, we have

𝔼⁡⟨2​∇yFr​(xr​(yτk,zτk),yτk,zτk)−∇yFr​(xτ+1k,yτk,zτk),yτ+1k−yτk⟩

= 2​𝔼​⟨∇yFr​(xr​(yτk,zτk),yτk,zτk)−∇yFr​(xτ+1k,yτk,zτk),yτ+1k−yτk⟩+𝔼⁡⟨∇yFr​(xτ+1k,yτk,zτk),yτ+1k−yτk⟩. (53)

For the first inner product term in (53), we bound it by

2​𝔼​⟨∇yFr​(xr​(yτk,zτk),yτk,zτk)−∇yFr​(xτ+1k,yτk,zτk),yτ+1k−yτk⟩

≥(i) −4​αy​𝔼​‖∇yFr​(xr​(yτk,zτk),yτk,zτk)−∇yFr​(xτ+1k,yτk,zτk)‖2−14​αy​𝔼​‖yτ+1k−yτk‖2

≥(i​i) −4​αy​Ly2​𝔼​‖xτ+1k−xr​(yτk,zτk)‖2−14​αy​𝔼​‖yτ+1k−yτk‖2, (54)

where (i) follows from Young’s inequality, and (i​i) is by the Ly Lipschitz continuity of ∇yFr​(⋅,y,z). For the second inner product term in (53), we split and bound it by

𝔼⁡⟨∇yFr​(xτ+1k,yτk,zτk),yτ+1k−yτk⟩

= 1αy​𝔼​⟨yτk+αy​Gy,τk−yτ+1k,yτ+1k−yτk⟩−𝔼⁡⟨Gy,τk−∇yFr​(xτ+1k,yτk,zτk),yτ+1k−yτk⟩+1αy​𝔼​‖yτ+1k−yτk‖2

≥ −𝔼⁡⟨Gy,τk−∇yFr​(xτ+1k,yτk,zτk),yτ+1k−yτk⟩+1αy​𝔼​‖yτ+1k−yτk‖2, (55)

where the inequality holds because ⟨yτk+αy​Gy,τk−yτ+1k,yτ+1k−yτk⟩≥0 by the update of y. The first inner product term in (55) is bounded by

𝔼⁡⟨Gy,τk−∇yFr​(xτ+1k,yτk,zτk),yτ+1k−yτk⟩

= 𝔼⁡⟨Gy,τk−∇yF​(xτ+1k,yτk),yτ+1k−yτk⟩

≤ 8​αy​𝔼​‖Gy,τk−∇yF​(xτ+1k,yτk)‖2+116​αy​𝔼​‖yτ+1k−yτk‖2

≤ 16​αy​𝔼​‖Gy,τk−∇yF​(xτk,yτk)‖2+16​αy​𝔼​‖∇yF​(xτk,yτk)−∇yF​(xτ+1k,yτk)‖2+116​αy​𝔼​‖yτ+1k−yτk‖2

≤ 16​αy​Ly2M​∑b=0τ−1𝔼​‖yb+1k−ybk‖2+16​αy​Ly2M​∑b=0τ−1𝔼​‖xb+1k−xbk‖2+16​αy​Ly2​𝔼​‖xτ+1k−xτk‖2+116​αy​𝔼​‖yτ+1k−yτk‖2

+16​αy​Cσ,y, (56)

where the last inequality follows from (15) and the Ly-Lipschitz continuity of ∇yF​(⋅,y). Plugging (56) into (55) we get

𝔼⁡⟨∇yFr​(xτ+1k,yτk,zτk),yτ+1k−yτk⟩

≥ 1516​αy​𝔼​‖yτ+1k−yτk‖2−16​αy​Ly2M​∑b=0τ−1𝔼​‖yb+1k−ybk‖2−16​αy​Ly2​𝔼​‖xτ+1k−xτk‖2−16​αy​Ly2M​∑b=0τ−1𝔼​‖xb+1k−xbk‖2

−16​αy​Cσ,y. (57)

Plugging (54) and (57) into (53) yields

𝔼⁡⟨2​∇yFr​(xr​(yτk,zτk),yτk,zτk)−∇yFr​(xτ+1k,yτk,zτk),yτ+1k−yτk⟩

≥ 1116​αy​𝔼​‖yτ+1k−yτk‖2−16​αy​Ly2M​∑b=0τ−1𝔼​‖yb+1k−ybk‖2−16​αy​Ly2​𝔼​‖xτ+1k−xτk‖2−16​αy​Ly2M​∑b=0τ−1𝔼​‖xb+1k−xbk‖2

−4​αy​Ly2​𝔼​‖xτ+1k−xr​(yτk,zτk)‖2−16​αy​Cσ,y. (58)

Second, we bound ② in (52) by

2​r​𝔼​[⟨zτ+1k−zτk,xr​(y⁡(zτ+1k),zτk)−xr​(yτ+1k,zτ+1k)⟩]

= 2​r​𝔼​[⟨zτ+1k−zτk,xr​(y⁡(zτ+1k),zτk)−xr​(y⁡(zτ+1k),zτ+1k)⟩]

+2​r​𝔼​[⟨zτ+1k−zτk,xr​(y⁡(zτ+1k),zτ+1k)−xr​(yτ+1k,zτ+1k)⟩]

≥(i) −2​r​𝔼​(‖zτ+1k−zτk‖​‖xr​(y⁡(zτ+1k),zτk)−xr​(y⁡(zτ+1k),zτ+1k)‖)

−2​r​𝔼​(‖zτ+1k−zτk‖​‖xr​(y⁡(zτ+1k),zτ+1k)−xr​(yτ+1k,zτ+1k)‖)

≥(i​i) −2​r​σ1​𝔼​‖zτ+1k−zτk‖2−r10​β​𝔼​‖zτ+1k−zτk‖2−10​r​β​𝔼​‖xr​(y⁡(zτ+1k),zτ+1k)−xr​(yτ+1k,zτ+1k)‖2

≥(i​i​i) −(4​r​β2+r​β10)​𝔼​‖xτ+1k−zτk‖2−10​r​β​𝔼​‖xr​(y⁡(zτ+1k),zτ+1k)−xr​(yτ+1k,zτ+1k)‖2, (59)

where (i) holds by Cauchy-Schwarz inequality, (i​i) follows from (19) and Young’s inequality, and (i​i​i) is obtained from the update of z and σ1≤2 (since r≥2​ρ). For the second term in (59), we bound it by

𝔼​‖xr​(y⁡(zτ+1k),zτ+1k)−xr​(yτ+1k,zτ+1k)‖2

≤(i) 𝔼⁡(2​‖xr​(y⁡(zτ+1k),zτ+1k)−xr​(yτ,+k​(zτ+1k),zτ+1k)‖2+2​‖xr​(yτ,+k​(zτ+1k),zτ+1k)−xr​(yτ+1k,zτ+1k)‖2)

≤(i​i) 2​𝔼​‖xr​(y⁡(zτ+1k),zτ+1k)−xr​(yτ,+k​(zτ+1k),zτ+1k)‖2+2​σ22​𝔼​‖yτ,+k​(zτ+1k)−yτ+1k‖2

≤(i​i​i) 2​𝔼​‖xr​(y⁡(zτ+1k),zτ+1k)−xr​(yτ,+k​(zτ+1k),zτ+1k)‖2+18​(24​αy2​β2​Ly2​𝔼​‖xτ+1k−zτk‖2CLOSE

+6​αy2​Ly2​𝔼​‖xτ+1k−xr​(yτk,zτk)‖2+3​αy2​Ly2​𝔼​‖xτ+1k−xτk‖2+3​αy2​Ly2M​∑b=0τ−1𝔼​‖yb+1k−ybk‖2

+3​αy2​Ly2M∑b=0τ−1𝔼‖xb+1k−xbk‖2+3αy2Cσ,y)

= 2​𝔼​‖xr​(y⁡(zτ+1k),zτ+1k)−xr​(yτ,+k​(zτ+1k),zτ+1k)‖2+432​β2​αy2​Ly2​𝔼​‖xτ+1k−zτk‖2

+108​σ22​αy2​Ly2​𝔼​‖xτ+1k−xr​(yτk,zτk)‖2+54​αy2​Ly2​𝔼​‖xτ+1k−xτk‖2+54​αy2​Ly2M​∑b=0τ−1𝔼​‖yb+1k−ybk‖2

+54​αy2​Ly2M∑b=0τ−1𝔼‖xb+1k−xbk‖2+54αy2Cσ,y, (60)

where the (i) holds by Young’s inequality, (i​i) follows from (20), while (i​i​i) is obtained from σ2≤3 (since r≥Ly+ρ) and (48). Plugging (60) into (59) gives

2​r​𝔼​[⟨zτ+1k−zτk,xr​(y⁡(zτ+1k),zτk)−xr​(yτ+1k,zτ+1k)⟩]

≥ −(4​r​β2+r​β10+4320​r​β3​αy2​Ly2)​𝔼​‖xτ+1k−zτk‖2−(1080​r​β​αy2​Ly2)​𝔼​‖xτ+1k−xr​(yτk,zτk)‖2

−540​r​β​αy2​Ly2​𝔼​‖xτ+1k−xτk‖2−540​r​β​αy2​Ly2M​∑b=0τ−1𝔼​‖yb+1k−ybk‖2−540​r​β​αy2​Ly2M​∑b=0τ−1𝔼​‖xb+1k−xbk‖2

−20​r​β​𝔼​‖xr​(y⁡(zτ+1k),zτ+1k)−xr​(yτ,+k​(zτ+1k),zτ+1k)‖2−540​r​β​αy2​Cσ,y. (61)

Now we obtain the desired result by plugging (58) and (61) into (52). ∎

Under Assumptions 2.1 and 2.2, let {xτk,yτk,zτk} be generated by Algorithm 1 with β≤Ly20​r​ϖ if θ∈[0,12], where ϖ is given in Lemma A.7. Then for any k≥0 and any 0≤τ≤T−1, it holds

20​r​β​‖xr​(y⁡(zτ+1k),zτ+1k)−xr​(yτ,+k​(zτ+1k),zτ+1k)‖2

≤ Ly​‖yτk−yτ,+k​(zτ+1k)‖2+χθ​Cβ, (62)

where Cβ=((2​θ−12​θ)​(20​r​κ(2​θ​Ly)12​θ)2​θ2​θ−1)​β2​θ2​θ−1 with κ defined in Lemma A.7.

When θ∈[0,12], since β≤Ly20​r​ϖ, we have from (35) that

20​r​β​‖xr​(y⁡(zτ+1k),zτ+1k)−xr​(yτ,+k​(zτ+1k),zτ+1k)‖2

≤ 20​r​β​ϖ​‖yτk−yτ,+k​(zτ+1k)‖2

≤ Ly​‖yτk−yτ,+k​(zτ+1k)‖2. (63)

When θ∈(12,1], we have from (36) that

20​r​β​‖xr​(y⁡(zτ+1k),zτ+1k)−xr​(yτ,+k​(zτ+1k),zτ+1k)‖2

≤ 20​r​β​κ​‖yτk−yτ,+k​(zτ+1k)‖1θ

= (20​r​κ​β(2​θ​Ly)12​θ)​((2​θ​Ly)12​θ​‖yτk−yτ,+k​(zτ+1k)‖1θ)

≤(i) (2​θ−12​θ)​(20​r​κ​β(2​θ​Ly)12​θ)2​θ2​θ−1+Ly​(‖yτk−yτ,+k​(zτ+1k)‖1θ)2​θ, (64)

where (i) follows from Young’s inequality for products, i.e., ab≤app+bqq where a,b≥0,p,q>1 such that 1p+1q=1.

Combining (63) and (64) and utilizing the definition of χθ yields the desired result. ∎

Suppose Assumption 2.1 holds and let αy≤110​Ly,β≤130. Then for any k≥0 and any 0≤τ≤T−1, we have

𝔼​‖yτk−yτ,+k​(zτ+1k)‖2≤ 2​𝔼​‖yτ+1k−yτk‖2+2​β125​𝔼​‖xτ+1k−zτk‖2+325​𝔼​‖xτ+1k−xr​(yτk,zτk)‖2

+350​𝔼​‖xτ+1k−xτk‖2+350​M​∑b=0τ−1𝔼​‖yb+1k−ybk‖2+350​M​∑b=0τ−1𝔼​‖xb+1k−xbk‖2+6​αy2​Cσ,y

Utilizing Young’s inequality, we get

𝔼​‖yτk−yτ,+k​(zτ+1k)‖2

≤ 2​𝔼​‖yτ+1k−yτk‖2+2​𝔼​‖yτ+1k−yτ,+k​(zτ+1k)‖2

≤(i) 2​𝔼​‖yτ+1k−yτk‖2+48​αy2​β2​Ly2​𝔼​‖xτ+1k−zτk‖2+12​αy2​Ly2​𝔼​‖xτ+1k−xr​(yτk,zτk)‖2+6​αy2​Ly2​𝔼​‖xτ+1k−xτk‖2

+6​αy2​Ly2M∑b=0τ−1𝔼‖yb+1k−ybk‖2+6​αy2​Ly2M∑b=0τ−1𝔼‖xb+1k−xbk‖2+6αy2Cσ,y

≤(i​i) 2​𝔼​‖yτ+1k−yτk‖2+2​β125​𝔼​‖xτ+1k−zτk‖2+325​𝔼​‖xτ+1k−xr​(yτk,zτk)‖2+350​𝔼​‖xτ+1k−xτk‖2

+350​M∑b=0τ−1𝔼‖yb+1k−ybk‖2+350​M∑b=0τ−1𝔼‖xb+1k−xbk‖2+6αy2Cσ,y,

where (i) follows from (48), and (i​i) holds by αy≤110​Ly and β≤130. Rearranging the above gives the desired bound. ∎

The following lemma provides auxiliary bounds that will be used in the later lemmas to establish the optimality of the algorithm’s output.

Under Assumptions 2.1 and 2.2, let {xτk,yτk,zτk} be generated by Algorithm 1 with T=M and other parameters satisfying

r≥max⁡{2​ρ,Ly+ρ}, (65)

24​(Ly+1)(r−ρ)2≤αx≤α¯x:=min⁡{112​(r+Lx+2​Ly),(r−ρ)224​(r+Lx)2​(Ly+1),r−(ρ+2​Ly)2​Ly​(Lx+r)}, (66)

αy≤min⁡{140​Ly,14​(2​Ly+1)}, (67)

β≤{min⁡{130,130​r,Ly20​r​ϖ} if ​θ∈[0,12],min⁡{130,130​r} if ​θ∈(12,1]. (68)

Additionally, denote χθ:={0,θ∈[0,12],1,θ∈(12,1], Φr0=Φr​(x00,y00,z00) along with

Cσ=Cσ,x​(2​(1+Ly)​(αx2​(r+Lx)2(r−ρ)2+1(r−ρ)2)+αx2)+Cσ,y​(16​αy+6​αy2​(Ly+3)).

Then for any k≥0 and any 0≤τ≤T−1, we have

∑k=0K−1∑τ=0T−1𝔼​‖xτ+1k−xτk‖2≤8​αx​((Φ00−F¯)+χθ​Cβ​K​T+Cσ​K​T),

∑k=0K−1∑τ=0T−1𝔼​‖yτ+1k−yτk‖2≤4​αy​((Φ00−F¯)+χθ​Cβ​K​T+Cσ​K​T),

∑k=0K−1∑τ=0T−1𝔼​‖xτ+1k−zτk‖2≤2r​β​((Φ00−F¯)+χθ​Cβ​K​T+Cσ​K​T),

where Cβ is defined in Lemma A.13.

By substituting the bounds established in Lemmas A.13 and A.14 into (51) and rearranging terms, we obtain

𝔼⁡[Φr​(xτk,yτk,zτk)−Φr​(xτ+1k,yτ+1k,zτ+1k)]

≥ (12​αx−r+Lx2−16​αy​Ly2−540​r​β​αy2​Ly2−3​Ly50)​𝔼​‖xτ+1k−xτk‖2+(1116​αy−7​Ly)​𝔼​‖yτ+1k−yτk‖2

+((2−β)​r​β2−4​r​β2−r​β10−4320​r​β3​αy2​Ly2−2​β​Ly125)​𝔼​‖xτ+1k−zτk‖2

−(1080​r​β​αy2​Ly2+4​αy​Ly2+3​Ly25)​𝔼​‖xτ+1k−xr​(yτk,zτk)‖2

−(16​αy​Ly2+540​r​β​αy2​Ly2+αx​Lx2M+3​Ly50​M)∑b=0τ−1𝔼‖xb+1k−xbk‖2

−(16​αy​Ly2+540​r​β​αy2​Ly2+αx​Ly2M+3​Ly50​M)∑b=0τ−1𝔼‖yb+1k−ybk‖2−αx​Cσ,x2

−(16​αy+540​r​β​αy2+6​αy2​Ly)​Cσ,y−χθ​Cβ.

Plugging the bound established in Lemma A.5 into the above inequality, noting Ly≤r and rearranging terms renders

𝔼⁡[Φr​(xτk,yτk,zτk)−Φr​(xτ+1k,yτ+1k,zτ+1k)] (69)

≥ (12​αx−(r+Lx2+5940​r​β​αy2​Ly2+2700​r​β​αy2​Ly2​η2+36​αy​Ly2+10​αy​Ly2​η2+3350​Ly+1550​Ly​η2)⏟①)​𝔼​‖xτ+1k−xτk‖2

+(1116​αy−7​Ly)⏟②​𝔼​‖yτ+1k−yτk‖2+((2−β)​r​β2−4​r​β2−r​β10−4320​r​β3​αy2​Ly2−2​r​β125)⏟③​𝔼​‖xτ+1k−zτk‖2

−(16​αy​Ly2+540​r​β​αy2​Ly2+αx​Lx2+5400​r​β​αx2​αy2​Lx2​Ly2​η2+20​αx2​αy​Lx2​Ly2​η2M+3​Ly50​M+3​αx2​Lx2​Ly​η25​M)⏟④∑b=0τ−1𝔼‖xb+1k−xbk‖2

−(16​αy​Ly2+540​r​β​αy2​Ly2+αx​Ly2+5400​r​β​αx2​αy2​Ly4​η2+20​αx2​αy​Ly4​η2M+3​Ly50​M+3​αx2​Ly3​η25​M)⏟⑤∑b=0τ−1𝔼‖yb+1k−ybk‖2

−(2700​r​β​αy2​Ly2​αx2​η2+10​αy​Ly2​αx2​η2+3​Ly​αx2​η210+αx2)⏟⑥​Cσ,x−(16​αy+540​r​β​αy2+6​αy2​Ly)⏟⑦​Cσ,y−χθ​Cβ.

Below we bound the seven underbraced terms in (69). First, noting that αy≤140​Ly and β≤min⁡{130,130​r}, we have

①≤ r+Lx2+5940​r30⋅1600+2700​η230⋅1600+36​Ly40+10​Ly​η240+33​Ly50+15​η2​Ly50

≤ r+Lx2+r2+η2+Ly+η2​Ly2+Ly+η2​Ly2

≤ r+Lx+2​Ly+η2​(Ly+1). (70)

By Young’s inequality, it holds

η2=(αx​(Lx+r)+1)2αx2​(r−ρ)2≤2​(r+Lx)2(r−ρ)2+2αx2​(r−ρ)2. (71)

Plugging this into (70) and from the conditions of αx gives

①≤r+Lx+2​Ly+η2​(Ly+1)≤ r+Lx+2​Ly+2​(r+Lx)2​(Ly+1)(r−ρ)2+2​(Ly+1)αx2​(r−ρ)2≤14​αx. (72)

For ② in (69), we use αy≤140​Ly to have

②≥1116​αy−740​αy≥12​αy. (73)

For ③ in (69), by β≤130 and αy≤140​Ly, it follows

③≥(2−130)​r​β2−4​r​β30−r​β10−4320​r​β900⋅1600−2​r​β125≥r​β2. (74)

For ④ in (69), by αx≤12​Lx, αy≤140​Ly, and β≤min⁡{130,130​r}, it holds

④≤ 1M​(16​Ly40+540​r30⋅1600+Lx2+5400​η230⋅4⋅1600+20​η2​Ly4⋅40+3​Ly50+3​η2​Ly20)

≤ 12​M​(r+Lx+2​Ly+η2​(Ly+1))

≤ 18​αx​M, (75)

where the last inequality follows from (72). For ⑤ in (69), it follows from αx≤12​Ly, αy≤140​Ly, and β≤130​r that

⑤≤ 1M​(16​Ly40+54030⋅1600+Ly2+5400​αx2​Ly2​η230⋅1600+20​η2​Ly3​αx240+3​Ly50+3​η2​Ly3​αx220). (76)

Moreover, from (71) and αx≤r−(ρ+2​Ly)2​Ly​(Lx+r), we have

αx2​Ly2​η2≤ 2​αx2​(r+Lx)2​Ly2(r−ρ)2+2​Ly2(r−ρ)2

≤ 2​(r+Lx)2​Ly2(r−ρ)2​(r−(ρ+2​Ly)2​Ly​(Lx+r))2+2​Ly2(r−ρ)2

= 12+2​Ly(r−ρ)​(2​Ly(r−ρ)−1)

≤ 12−Lyr−ρ

≤ 12, (77)

where the third inequality follows from r≥ρ+4​Ly. Plugging this bound into (76) yields

⑤≤ 1M​(16​Ly40+54030⋅1600+Ly2+5400​Ly60⋅1600+20​Ly80+3​Ly50+3​Ly40)≤1M​(2​Ly+1)≤14​αy. (78)

where in the last inequality, we have used αy≤14​(2​Ly+1). For ⑥ in (69), by αy≤140​Ly, β≤130​r, and (71), we get

⑥≤901600​αx2​η2+Ly​αx2​η24+3​Ly​αx2​η210+αx2≤2​(1+Ly)​(αx2​(r+Lx)2(r−ρ)2+1(r−ρ)2)+αx2. (79)

Similarly, from β≤130​r, we have

⑦≤16​αy+18​αy2+6​αy2​Ly=16​αy+6​αy2​(Ly+3). (80)

Now substituting (72), (73), (74), (75), (78), (79) and (80) into (69), we get

𝔼⁡[Φr​(xτk,yτk,zτk)−Φr​(xτ+1k,yτ+1k,zτ+1k)]

≥ 14​αx​𝔼​‖xτ+1k−xτk‖2+12​αy​𝔼​‖yτ+1k−yτk‖2+r​β2​𝔼​‖xτ+1k−zτk‖2−18​αx​M​∑b=0τ−1𝔼​‖xb+1k−xbk‖2

−14​αy​M∑b=0τ−1𝔼‖yb+1k−ybk‖2−χθCβ−Cσ. (81)

Before proceeding further we first note that

∑k=0K−1(∑τ=0T−1∑b=0τ−1𝔼​‖xb+1k−xbk‖2)≤T​∑k=0K−1∑τ=0T−1𝔼​‖xτ+1k−xτk‖2, (82)

∑k=0K−1(∑τ=0T−1∑b=0τ−1𝔼​‖yb+1k−ybk‖2)≤T​∑k=0K−1∑τ=0T−1𝔼​‖yτ+1k−yτk‖2. (83)

Additionally, we have

∑k=0K−1∑τ=0T−1𝔼⁡[Φr​(xτk,yτk,zτk)−Φr​(xτ+1k,yτ+1k,zτ+1k)]=𝔼⁡[Φr​(x00,y00,z00)−Φr​(x0K,y0K,z0K)]. (84)

We note that from the definitions of Fr​(x,y,z), dr​(y,z) and pr​(z) in Table 2, we have for all x∈𝒳, y∈𝒴 and z∈ℝdx,

Φr​(x,y,z)= (Fr​(x,y,z)−dr​(y,z))+(pr​(z)−dr​(y,z))+pr​(z)

≥ pr​(z)

= maxy∈𝒴⁡minx∈𝒳​Fr​(x,y,z)

≥ maxy∈𝒴⁡minx∈𝒳⁡F⁡(x,y)

≥ F¯, (85)

where the second inequality follows from Fr​(x,y,z)≥F⁡(x,y), and the last inequality holds from Assumption 2.1 [vi.]. Plugging (85) into (84) yields

∑k=0K−1∑τ=0T−1𝔼⁡[Φr​(xτk,yτk,zτk)−Φr​(xτ+1k,yτ+1k,zτ+1k)]≤Φ00−F¯. (86)

Taking sum on both sides of (81), plugging (82), (83) and (86), utilizing T=M, and rearranging terms renders

18​αx​∑k=0K−1∑τ=0T−1𝔼​‖xτ+1k−xτk‖2+14​αy​∑k=0K−1∑τ=0T−1𝔼​‖yτ+1k−yτk‖2+r​β2​∑k=0K−1∑τ=0T−1𝔼​‖xτ+1k−zτk‖2

≤ (Φ00−F¯)+χθ​Cβ​K​T+Cσ​K​T.

The desired results follow immediately from the above, thus completing the proof. ∎

In (66), both lower and upper bounds are imposed on αx. We discuss how to choose r such that the interval for αx is not empty, namely, we require

24​(Ly+1)(r−ρ)2⏟ⓘ≤min⁡{112​(r+Lx+2​Ly)⏟ii⃝,(r−ρ)224​(r+Lx)2​(Ly+1)⏟iii⃝,r−(ρ+2​Ly)2​Ly​(Lx+r)⏟iv⃝}.

First, we have

ii⃝≥ⓘ⇔ (r−ρ)2≥288​(Ly+1)​(r+Lx+2​Ly)

⇔ (r−(ρ+144​(Ly+1)))2≥ 288​(Ly+1)​[ρ+72​(Ly+1)+Lx+2​Ly],

which is implied by

r≥ρ+144​(Ly+1)+OPEN288​(Ly+1)​(ρ+72​(Ly+1)+Lx+2​Ly)).

Second, it holds

iii⃝≥ⓘ⇔(r−ρ)4≥576​(Ly+1)2​(r+Lx)2⇔(r−ρ)2≥24​(Ly+1)​(r+Lx),

which is indicated by

r≥ρ+12​(Ly+1)+24​(Ly+1)​(ρ+Lx+6​(Ly+1)).

Third, assuming r≥ρ+2​Ly+1, we have iv⃝≥12​Ly​(Lx+r). Hence, it suffices to require

12​Ly​(Lx+r)≥ⓘ⇔(r−(ρ+24​Ly​(Ly+1)))2≥48​Ly​(Ly+1)​(ρ+Lx+12​Ly​(Ly+1)),

which is implied by

r≥ρ+24​Ly​(Ly+1)+48​Ly​(Ly+1)​(ρ+Lx+12​Ly​(Ly+1)).

Therefore, a valid value of αx exists if

r≥max{ ρ+144​(Ly+1)+288​(Ly+1)​ρ+Lx+74​Ly+72,

ρ+24Ly(Ly+1)+48​Ly​(Ly+1)ρ+Lx+12​Ly​(Ly+1)}.

By a+b≤a+b and 2​a​b≤a+b for any nonnegative numbers a and b, we can further relax the bound on r and take it as

r=max{ 2ρ+325(Ly+1)+12Lx2​(Ly+1), 2ρ+54Ly(Ly+1)+4Lx3​Ly​(Ly+1)}. (87)

Building on these auxiliary bounds, the next two lemmas establish results that are crucial for proving the optimality of the output of Algorithm 1.

Under Assumption 2.1, let {xτk,yτk,zτk} be generated by Algorithm 1 with T=M. Then for any k≥0, 0≤τ≤T−1, it holds

𝔼⁡[dist​(0,∇xF​(x~,y~)+𝒩𝒳​(x~))2]+𝔼⁡[dist​(0,−∇yF​(x~,y~)+𝒩𝒴​(y~))2]

≤ 1K​T​(4αx2+16​Lx2+8​r2+6​Ly2)​∑k=0K−1∑τ=0T−1𝔼​‖xτ+1k−xτk‖2+1K​T​(3αy2+22​Ly2)​∑k=0K−1∑τ=0T−1𝔼​‖yτ+1k−yτk‖2

+8​r2K​T∑k=0K−1∑τ=0T−1𝔼‖xτ+1k−zτk‖2+(4Cσ,x+3Cσ,y).

We first bound 𝔼⁡[dist​(0,∇xF​(xτ+1k,yτ+1k)+𝒩𝒳​(xτ+1k))2]. By the update for xτ+1k in Algorithm 1, it holds

0 ∈(xτ+1k−xτk)+αx​(Gx,τk+r⁡(xτk−zτk))+𝒩𝒳​(xτ+1k)

⟹1αx​(xτk−xτ+1k)+r⁡(zτk−xτk)−Gx,τk+∇xF​(xτ+1k,yτ+1k)∈∇xF​(xτ+1k,yτ+1k)+𝒩𝒳​(xτ+1k)

Hence, we use Young’s inequality and Lemma A.1 to have

𝔼⁡[dist​(0,∇xF​(xτ+1k,yτ+1k)+𝒩𝒳​(xτ+1k))2]

≤ 𝔼​‖1αx​(xτk−xτ+1k)+r⁡(zτk−xτk)−Gx,τk+∇xF​(xτ+1k,yτ+1k)‖2

≤ 4αx2​𝔼​‖xτ+1k−xτk‖2+4​r2​𝔼​‖xτk−zτk‖2+4​𝔼​‖Gx,τk−∇xF​(xτk,yτk)‖2

+4​𝔼​‖∇xF​(xτk,yτk)−∇xF​(xτ+1k,yτ+1k)‖2

≤ (4αx2+8​Lx2+8​r2)​𝔼​‖xτ+1k−xτk‖2+8​r2​𝔼​‖xτ+1k−zτk‖2+8​Lx2M​∑b=0τ−1𝔼​‖xb+1k−xbk‖2

+8​Ly2M∑b=0τ−1𝔼‖yb+1k−ybk‖2+8Ly2𝔼‖yτ+1k−yτk‖2+4Cσ,x. (88)

Second, we bound 𝔼⁡[dist​(0,−∇yF​(xτ+1k,yτ+1k)+𝒩𝒴​(yτ+1k))2]. By the update of yτ+1k in Algorithm 1, we have

0 ∈(yτ+1k−yτk)−αy​Gy,τk+𝒩𝒴​(yτ+1k)

⟹ 1αy​(yτk−yτ+1k)+Gy,τk−∇yF​(xτ+1k,yτ+1k)∈−∇yF​(xτ+1k,yτ+1k)+𝒩𝒴​(yτ+1k)

Hence, by Young’s inequality, the smoothness of F, and Lemma A.1, it follows

𝔼⁡[dist​(0,−∇yF​(xτ+1k,yτ+1k)+𝒩𝒴​(yτ+1k))2]

≤ 𝔼​‖1αy​(yτk−yτ+1k)+Gy,τk−∇yF​(xτ+1k,yτ+1k)‖2

≤ 3αy2​𝔼​‖yτ+1k−yτk‖2+3​𝔼​‖Gy,τk−∇yF​(xτk,yτk)‖2+3​𝔼​‖∇yF​(xτk,yτk)−∇yF​(xτ+1k,yτ+1k)‖2

≤ (3αy2+3​Ly2)​𝔼​‖yτ+1k−yτk‖2+3​Ly2M​∑b=0τ−1𝔼​‖yb+1k−ybk‖2+3​Ly2M​∑b=0τ−1𝔼​‖xb+1k−xbk‖2+3​Ly2​𝔼​‖xτ+1k−xτk‖2

+3​Cσ,x. (89)

Adding (88) and (89) we get

𝔼⁡[dist​(0,∇xF​(xτ+1k,yτ+1k)+𝒩𝒳​(xτ+1k))2]+𝔼⁡[dist​(0,∇yF​(xτ+1k,yτ+1k)+𝒩𝒳​(yτ+1k))2]

≤ (4αx2+8​Lx2+8​r2+3​Ly2)​𝔼​‖xτ+1k−xτk‖2+(3αy2+11​Ly2)​𝔼​‖yτ+1k−yτk‖2+8​r2​𝔼​‖xτ+1k−zτk‖2

+8​Lx2+3​Ly2M∑b=0τ−1𝔼‖xb+1k−xbk‖2+11​Ly2M∑b=0τ−1𝔼‖yb+1k−ybk‖2+4Cσ,x+3Cσ,y. (90)

Taking sum on both sides of (90), plugging (82), (83) and utilizing T=M, we get

∑k=0K−1∑τ=0T−1𝔼⁡[dist​(0,∇xF​(xτ+1k,yτ+1k)+𝒩𝒳​(xτ+1k))2]+𝔼⁡[dist​(0,−∇yF​(xτ+1k,yτ+1k)+𝒩𝒳​(yτ+1k))2]

≤ (4αx2+16​Lx2+8​r2+6​Ly2)​∑k=0K−1∑τ=0T−1𝔼​‖xτ+1k−xτk‖2+(3αy2+22​Ly2)​∑k=0K−1∑τ=0T−1𝔼​‖yτ+1k−yτk‖2

+8r2∑k=0K−1∑τ=0T−1𝔼‖xτ+1k−zτk‖2+(4Cσ,x+3Cσ,y)KT.

Dividing both sides of the above by K​T, and using the definition of the uniform random output (x~,y~), yields the desired result. ∎

Under Assumption 2.1, let {xτk,yτk,zτk} be generated by Algorithm 1 with T=M, and r and αx satisfying the conditions in (65) and (66). Then for any k≥0 and 0≤τ≤T−1, it holds

𝔼​‖∇zdr​(y~,x~)‖2

≤ 1K​T​(15​r2+97αx2)​∑k=0K−1∑τ=0T−1𝔼​‖xτ+1k−xτk‖2+35​r2K​T​∑k=0K−1∑τ=0T−1𝔼​‖yτk−yτ+1k‖2

+12​r2K​T∑k=0K−1∑τ=0T−1𝔼∥xkτ+1−zkτ∥2+61Cσ,x.

By Danskin’s Theorem, it holds ∇zdr​(yτ+1k,xτ+1k)=r⁡(xτ+1k−xr​(yτ+1k,xτ+1k)). Hence,

𝔼​‖∇zdr​(yτ+1k,xτ+1k)‖2

= r2​𝔼​‖xτ+1k−xr​(yτ+1k,xτ+1k)‖2

≤(i) 3​r2​(𝔼​‖xτ+1k−xr​(yτk,zτk)‖2+𝔼​‖xr​(yτk,zτk)−xr​(yτ+1k,zτk)‖2+𝔼​‖xr​(yτ+1k,zτk)−xr​(yτ+1k,xτ+1k)‖2)

≤(i​i) 3​r2​𝔼​‖xτ+1k−xr​(yτk,zτk)‖2+3​r2​σ22​𝔼​‖yτk−yτ+1k‖2+3​r2​σ12​𝔼​‖xτ+1k−zτk‖2

≤(i​i​i) (15​r2​η22+15​r2)​𝔼​‖xτ+1k−xτk‖2+27​r2​𝔼​‖yτk−yτ+1k‖2+12​r2​𝔼​‖xτ+1k−zτk‖2

+15​r2​η2​αx2​Lx2M∑b=0τ−1𝔼‖xb+1k−xbk‖2+15​r2​η2​αx2​Ly2M∑b=0τ−1𝔼‖yb+1k−ybk‖2+15​αx2​r2​η2​Cσ,x2, (91)

where (i) follows from Young’s inequality, (i​i) is by Lemma A.2, and (i​i​i) follows from Lemma A.5, σ1≤2 and σ2≤3 (since r≥max⁡{2​ρ,Ly+ρ}). Taking sum on both sides of (91), plugging (82) along with (83), and utilizing T=M renders

∑k=0K−1∑τ=0T−1𝔼​‖∇zdr​(yτ+1k,xτ+1k)‖2

≤ (15​r2​η22+15​r2+15​r2​η2​αx2​Lx2)⏟①​∑k=0K−1∑τ=0T−1𝔼​‖xτ+1k−xτk‖2+(27​r2+15​r2​η2​αx2​Ly2)⏟②​∑k=0K−1∑τ=0T−1𝔼​‖yτk−yτ+1k‖2

+12r2∑k=0K−1∑τ=0T−1𝔼∥xkτ+1−zkτ∥2+15​αx2​r2​η22⏟③Cσ,xKT. (92)

Utilizing αx≤12​Lx and (71) , we bound ① in (92) by

①≤24​r2​(r+Lx)2(r−ρ)2+24​r2αx2​(r−ρ)2+15​r2≤96​(r+Lx)2+15​r2+96αx2≤15​r2+97αx2,

where the second inequality holds by r≥2​ρ and thus rr−ρ≤2, and the last inequality follows from 1αx≥12​(r+Lx). Also, from (77), we have ②≤35​r2. Furthermore, utilizing (71) and r≥2​ρ, we get

③≤15​αx2​r2​(r+Lx)2(r−ρ)2+15​r2(r−ρ)2≤60​(αx2​(r+Lx)2+1)≤61,

where the last inequality follows from αx≤112​(r+Lx). Plugging these bounds into (92), dividing both sides of the above by K​T, and using the definition of the uniform random output (x~,y~), yields the desired result. ∎

We are now ready to present the main convergence result for the smooth case, encompassing both the finite–sum and online settings.

By substituting the bounds from Lemma A.15 into Lemma A.17, and rearranging terms, we get

𝔼⁡[dist​(0,∇xF​(x~,y~)+𝒩𝒳​(x~))2]+𝔼⁡[dist​(0,−∇yF​(x~,y~)+𝒩𝒴​(y~))2]

≤ 8​αx​Δ​ΦK​T​(4αx2+16​Lx2+8​r2+6​Ly2)⏟①+4​αy​Δ​ΦK​T​(3αy2+22​Ly2)⏟②+16​r​Δ​Φβ​K​T⏟③

+8​αx​χθ​Cβ​(4αx2+16​Lx2+8​r2+6​Ly2)⏟④+4​αy​χθ​Cβ​(3αy2+22​Ly2)⏟⑤+16​r​χθ​Cββ⏟⑥

+8​αx​Cσ​(4αx2+16​Lx2+8​r2+6​Ly2)⏟⑦+4​αy​Cσ​(3αy2+22​Ly2)⏟⑧+16​r​Cσβ⏟⑨+4​Cσ,x+3​Cσ,y⏟⑩. (93)

We first discuss the finite–sum setting. In this case, since Cσ,x and Cσ,y=0, the last four terms vanish. Hence, to have (x~,y~) as an ε-GS point, it suffices to make each of the six remaining underbraced terms upper bounded by ε26. When θ∈[0,12], χθ=0, and thus we only need to consider the first three terms. By the choice of αx and αy, it follows that ② is dominated by ①, and to have both of ① and ② in the order of ε2, it suffices to have K​T=Θ⁡(Δ​Φαx​ε2). In addition, by the assumption of ρ=𝒪⁡(min⁡{Lx,Ly}) and min⁡{Lx,Ly}=Ω⁡(1), we have from (87) that r=Θ⁡(Ly2+Ly​Lx), and thus by (66), it follows αx=Θ⁡(1Lx+Ly2). Therefore, having

K​T=Θ⁡(Δ​Φ​(Lx+Ly2)ε2) (94)

will push both of ① and ② to 𝒪⁡(ε2). Moreover, to have ③=𝒪⁡(ε2), we need K​T=Θ⁡(r​Δ​Φβ​ε2). Notice that ϖ=Θ⁡(Ly2μ2​(r−ρ)). Thus Ly2​r​ϖ=Θ⁡(μ2Ly), and the chosen β=Θ⁡(min⁡{1r,μ2Ly}). Hence, having

K​T=Θ⁡(Δ​Φ​max⁡{r2,r​Lyμ2}ε2)=Θ⁡(Ly2​Δ​Φ​max⁡{Ly2+Lx,Ly+Lxμ2}ε2) (95)

will ensure ③=𝒪⁡(ε2). Together with (94), this completes the proof for the case of θ∈[0,12] in the finite–sum setting.

When θ∈(12,1], we have κ=Θ⁡(Ly1θr​μ1θ), and thus

Cβ=((2​θ−12​θ)​(20​r​κ(2​θ​Ly)12​θ)2​θ2​θ−1)​β2​θ2​θ−1=Θ⁡(Ly12​θ−1μ22​θ−1​β2​θ2​θ−1). (96)

Again, by the choice of αx and αy, ⑤ is dominated by ④. Since β=𝒪⁡(αx2​θ−12​θ​Ly−12​θ​μ1θ​ε2​θ−1θ), we have

④=Θ⁡(αx−1​Cβ)=Θ⁡(αx−1​Ly12​θ−1​μ−22​θ−1​β2​θ2​θ−1)=𝒪⁡(ε2),

and ⑤=𝒪⁡(ε2) as well. In addition, by β=Θ⁡(r−(2​θ−1)​μ2​Ly−1​ε4​θ−2), we get

⑥=Θ⁡(r​Cββ)=Θ⁡(r​Ly12​θ−1​μ−22​θ−1​β12​θ−1)=𝒪⁡(ε2).

To have ③=𝒪⁡(ε2), from the choice of β, we need

K​T=Θ⁡(r​Δ​Φβ​ε2)=Θ⁡(r​Δ​Φmin⁡{r−1,αx2​θ−12​θ​Ly−12​θ​μ1θ​ε4​θ−1θ,r−(2​θ−1)​μ2​Ly−1​ε4​θ,r−2​θ−1θ​Lyθ−1θ​μ1θ​ε4​θ−1θ}).

Now plugging αx=Θ⁡(1Lx+Ly2) and r=Θ⁡(Ly2+Ly​Lx) and combining the requirements on K​T in (94) and (95) completes the proof for the case of θ∈(12,1] in the finite–sum setting.

We now discuss the online setting. In this regime, since Cσ,x=σx2B and Cσ,y=σy2B, we have

Cσ= σx2B​(2​(1+Ly)​(αx2​(r+Lx)2(r−ρ)2+1(r−ρ)2)+αx2)+((16​αy+6​αy2​(Ly+3)))​σy2B

= 𝒪⁡((σx2+σy2)​αxB), (97)

where the second equation follows from αx=𝒪⁡(1r+Lx), Ly=Ω⁡(1), r=Θ⁡(Ly2+Ly​Lx), and αy=Θ⁡(αx). Hence, by the fact that ⑦ dominates ⑧, it suffices to have

B=Θ⁡((σx2+σy2)​αxαx​ε2)=Θ⁡(σx2+σy2ε2) (98)

to have both ⑦ and ⑧ to be 𝒪⁡(ε2). Additionally, because Cσ,x=σx2B and Cσ,y=σy2B, having B in (98) makes ⑩ is 𝒪⁡(ε2) as well.

Lastly, for bounding ⑨, we consider the cases when θ∈[0,12] and (12,1] separately. When θ∈[0,12], from β=Θ⁡(min⁡{1r,μ2Ly}) and (97), having

B=Θ⁡((σx2+σy2)​αx​max⁡{r2,r​Lyμ2}ε2)=Θ⁡((σx2+σy2)​αx​Ly2​max⁡{Ly2+Lx,Ly+Lxμ2}ε2)

ensures ⑨ is 𝒪⁡(ε2). When θ∈(12,1], from the choice of β, we need

B=Θ⁡(r​αx​(σx2+σy2)β​ε2)=Θ⁡(r​αx​(σx2+σy2)min⁡{r−1,αx2​θ−12​θ​Ly−12​θ​μ1θ​ε4​θ−1θ,r−(2​θ−1)​μ2​Ly−1​ε4​θ,r−2​θ−1θ​Lyθ−1θ​μ1θ​ε4​θ−1θ})

to render ⑨ is 𝒪⁡(ε2). Hence, plugging αx=Θ⁡(1Lx+Ly2) and r=Θ⁡(Ly2+Ly​Lx) and combining all the above requirements on B completes the proof for the online setting.

We now prove 𝔼​‖∇zdr​(y~,x~)‖2=𝒪⁡(ε2). Substituting the bounds from Lemma A.15 into Lemma A.18 and rearranging terms, we get

𝔼​‖∇zdr​(y~,x~)‖2

≤ 8​αx​Δ​ΦK​T​(15​r2+97αx2)⏟ⓘ+140​αy​r2​Δ​ΦK​T⏟ii⃝+24​r​Δ​Φβ​K​T⏟iii⃝

+8​αx​χθ​Cβ​(15​r2+97αx2)⏟iv⃝+140​αy​r2​χθ​Cβ⏟ⓥ+24​r​χβ​Cββ⏟vi⃝

+8​αx​Cσ​(15​r2+97αx2)⏟vii⃝+140​αy​r2​Cσ⏟viii⃝+24​r​Cσβ⏟vi⃝+61​Cσ,x⏟ix⃝. (99)

As before, we first discuss the finite–sum setting. Since in this regime, Cσ,x=Cσ,y=0, the last four terms vanish. Comparing the six remaining underbraced terms in (99) to those in (93), we only need to show that ii⃝ is 𝒪⁡(ε2) when θ∈[0,12] and that ii⃝ and ⓥ are both 𝒪⁡(ε2) when θ∈(12,1] with the selected K​T and β. Since r=Θ⁡(Ly2+Ly​Lx) and αy=Θ⁡(1Ly), to ensure ii⃝ is 𝒪⁡(ε2), it suffices to have

K​T=Θ⁡(Ly​Δ​Φ​(Ly+Lx)2ε2)=Θ⁡(Ly​Δ​Φ​(Ly2+Lx)ε2).

This finishes the proof for the case of θ∈[0,12]. In addition, when θ∈(12,1], using αy=Θ⁡(1Ly) and β=𝒪⁡(r−2​θ−1θ​Lyθ−1θ​μ1θ​ε2​θ−1θ), we have

ⓥ=Θ⁡(αy​r2​Cβ)=Θ⁡(r2​Ly2−2​θ2​θ−1​μ−22​θ−1​β2​θ2​θ−1)=𝒪⁡(ε2).

For the online setting, we only need to further check viii⃝, which is dominated by vii⃝ and thus is 𝒪⁡(ε2) as well.

Finally, the sample complexity is given by

2​K​B+4​K​T​M=2​K​T​(BT+2​M)=2​K​T​(BM+2​M)≤4​K​T​⌈2​B⌉=𝒪⁡(⌈B⌉​K​T),

which completes the proof. ∎

Appendix B Proofs for the nonsmooth case

In this section, we give the proofs of the claimed results for the nonsmooth case.

Suppose Assumption 3.1 holds. Then for every fixed sample 𝛏∈Ξ, the function fλ​(⋅,⋅,𝛏) defined in (13) is ℓλ-Lipschitz continuous with ℓλ=max⁡{ℓφ​ℓh​ℓc​dh,ℓφ}, i.e.,

‖fλ​(x1,y1,𝝃)−fλ​(x2,y2,𝝃)‖≤ℓλ​(‖x1−x2‖+‖y1−y2‖),∀(x1,y1),(x2,y2)∈𝒳×𝒴.

Also, Fλ is ℓ^-Lipschitz continuous.

We note that ∀w1,w2∈ℝdc, we have

‖hλ​(w1)−hλ​(w2)‖2=∑j=1dh|hjλ​(w1)−hjλ​(w2)|2​≤(i)​∑j=1dhℓh2​‖w1−w2‖2=dh​ℓh2​‖w1−w2‖2, (100)

where (i) follows from (Drusvyatskiy and Paquette, 2019, Lemma 2.1). Hence,

‖fλ​(x1,y1,𝝃)−fλ​(x2,y2,𝝃)‖= ‖φ⁡(hλ​(c⁡(x1,𝝃)),y1,𝝃)−φ⁡(hλ​(c⁡(x2,𝝃)),y2,𝝃)‖

≤(i) ℓφ​‖hλ​(c⁡(x1,𝝃))−hλ​(c⁡(x2,𝝃))‖+ℓφ​‖y1−y2‖

≤(i​i) ℓφ​ℓh​ℓc​dh​‖x1−x2‖+ℓφ​‖y1−y2‖

≤ ℓλ​(‖x1−x2‖+‖y1−y2‖),

where (i) holds by the ℓφ-lipschitz continuity of φ⁡(⋅,⋅), and (i​i) follows from (100) and the ℓc-lipschitz continuity of c. This completes the proof. ∎

The next lemma shows the Lipschitz continuity of ∇Fλ.

Suppose Assumption 3.1 holds. The gradient ∇xfλ​(x,y,𝛏) is Lλ,x-Lipschitz continuous in x and Lλ,y-Lipschitz continuous in y in expectation, i.e.,

𝔼​‖∇xfλ​(x1,y,𝝃)−∇xfλ​(x2,y,𝝃)‖2≤Lλ,x2​‖x1−x2‖2,∀(x1,y),(x2,y)∈𝒳×𝒴

𝔼​‖∇xfλ​(x,y1,𝝃)−∇xfλ​(x,y2,𝝃)‖2≤Lλ,y2​‖y1−y2‖2,∀(x,y1),(x,y2)∈𝒳×𝒴

where Lλ,x=3​ℓc4​ℓφ2​dhλ2+3​dh​ℓh2​ℓφ2​Lc2+3​ℓc4​dh2​ℓh4​Lφ2 and Lλ,y=max⁡{dh​Lφ​ℓh​ℓc,Lφ}. Additionally, ∇yfλ​(⋅,⋅,𝛏) is Lλ,y-Lipschitz continuous in expectation, i.e.,

𝔼​‖∇yfλ​(x1,y1,𝝃)−∇yfλ​(x2,y2,𝝃)‖2≤Lλ,y2​(‖x1−x2‖2+‖y1−y2‖2).

We first note that ∀w1,w2∈ℝdc,

‖∇hλ​(w1)−∇hλ​(w2)‖2=∑j=1dh‖∇hjλ​(w1)−∇hjλ​(w2)‖2​≤(i)​∑j=1dh1λ2​‖w1−w2‖2=dhλ2​‖w1−w2‖2, (101)

where (i) follows from (Drusvyatskiy and Paquette, 2019, Lemma 2.1). In addition, for each 𝝃∈{𝝃i}i=1N, we have

∇xfλ(x,y;𝝃)=∇xc(x;𝝃)∇hλ(c(x;𝝃))∇1φ(hλ(c(x;𝝃)),y;𝝃),

where ∇xc∈ℝdx×dc denotes the Jacobian matrix of c about x, ∇hλ∈ℝdc×dh is for the Jacobian matrix of hλ, and ∇1φ∈ℝdh denotes the partial gradient of φ about the first argument. For any (x,y), (x1,y1) and (x2,y2), we let

c=c⁡(x,𝝃),c1=c⁡(x1,𝝃),c2=c⁡(x2,𝝃),

hλ=hλ​(c⁡(x,𝝃)),h1λ=hλ​(c⁡(x1,𝝃)),h2λ=hλ​(c⁡(x2,𝝃)),

J=∇xc​(x,𝝃),J1=∇xc​(x1,𝝃),J2=∇xc​(x2,𝝃),

H=∇hλ​(c),H1=∇hλ​(c1),H2=∇hλ​(c2),

b1=∇1φ​(h1λ,y,𝝃),b2=∇1φ​(h2λ,y,𝝃),

q1=∇1φ​(hλ,y1,𝝃),q2=∇1φ​(hλ,y2,𝝃).

Then

𝔼​‖∇xfλ​(x1,y,𝝃)−∇xfλ​(x2,y,𝝃)‖2

= 𝔼​‖J1​H1​b1−J2​H2​b2‖2

≤ 3​‖J1​H1​b1−J2​H1​b1‖2+3​‖J2​H1​b1−J2​H2​b1‖2+3​‖J2​H2​b1−J2​H2​b2‖2

≤ 3​𝔼​‖H1​b1‖2​𝔼​‖J1−J2‖2+3​𝔼​‖J2‖2​‖b1‖2​𝔼​‖H1−H2‖2+3​𝔼​‖J2​H2‖2​𝔼​‖b1−b2‖2

≤(i) 3​dh​ℓh2​ℓφ2​𝔼​‖J1−J2‖2+3​ℓc2​ℓφ2​𝔼​‖H1−H2‖2+3​ℓc2​dh​ℓh2​𝔼​‖b1−b2‖2

≤(i​i) 3​dh​ℓh2​ℓφ2​Lc2​‖x1−x2‖2+3​ℓc4​ℓφ2​dhλ2​‖x1−x2‖2+3​ℓc4​dh2​ℓh4​Lφ2​‖x1−x2‖2

= (3​ℓc4​ℓφ2​dhλ2+3​dh​ℓh2​ℓφ2​Lc2+3​ℓc4​dh2​ℓh4​Lφ2)​‖x1−x2‖2, (102)

where (i) follows from the ℓφ- and ℓc-Lipschitz continuity of φ and c and the dh​ℓh-Lipschitz continuity of hλ by (100), and (i​i) holds by the (9), ℓc-Lipschitz continuity of c and dhλ-Lipschitz continuity of ∇hλ by (101), (10) and the dh​ℓh-Lipschitz continuity of hλ by (100).

Similarly, we have

𝔼​‖∇xfλ​(x,y1,𝝃)−∇xfλ​(x,y2,𝝃)‖2= 𝔼​‖J​H​q1−J​H​q2‖2

= 𝔼​‖J‖2​‖H‖2​‖q1−q2‖2

≤(i) dh​ℓh2​ℓc2​Lφ2​‖y1−y2‖2, (103)

where (i) follows from (10), ℓc-Lipschitz continuity of c and dh​ℓh-Lipschitz continuity of hλ. Moreover, we have

𝔼​‖∇yfλ​(x1,y1,𝝃)−∇yfλ​(x2,y2,𝝃)‖2= 𝔼​‖∇yφ​(hλ​(c⁡(x1,𝝃)),y1,𝝃)−∇yφ​(hλ​(c⁡(x2,𝝃)),y2,𝝃)‖2

≤(i) Lφ2​(‖h1λ−h2λ‖2+‖y1−y2‖2)

≤(i​i) dh​Lφ2​ℓh2​ℓc2​‖x1−x2‖2+Lφ2​‖y1−y2‖2, (104)

where (i) follows from (10), and (i​i) is by ℓc-Lipschitz continuity of c and (100). The desired result then follows from the specified choices of Lλ,x and Lλ,y and thus, the proof is complete. ∎

We now show that F and Fλ are weakly convex and have the same weak convexity module.

Suppose Assumption 3.1 holds and let ρλ=dh​Lφ​ℓh2​ℓc2+Lc​ℓφ​ℓh​dh. Then for each y∈𝒴, the functions F⁡(⋅,y) and Fλ​(⋅,y) are both ρλ-weakly convex.

For any x,x^∈𝒳 and y∈𝒴, we define the following notations for simplicity:

ϑ𝝃∈∂h⁡(c⁡(x,𝝃));w𝝃=h⁡(c⁡(x^,𝝃))−h⁡(c⁡(x,𝝃))−ϑ𝝃⊤​(c⁡(x^,𝝃)−c⁡(x,𝝃));v𝝃=c⁡(x^,𝝃)−c⁡(x,𝝃)−∇xc​(x,𝝃)⊤​(x^−x).

Then we have

F⁡(x^,y)

= 𝔼𝝃∼ℙ​[φ⁡(h⁡(c⁡(x^,𝝃)),y,𝝃)]

≥(i) 𝔼𝝃∼ℙ​(φ⁡(h⁡(c⁡(x,𝝃)),y,𝝃)+⟨∇1φ​(h⁡(c⁡(x,𝝃)),y,𝝃),h⁡(c⁡(x^,𝝃))−h⁡(c⁡(x,𝝃))⟩CLOSE

OPEN−Lφ2​‖h⁡(c⁡(x^,𝝃))−h⁡(c⁡(x,𝝃))‖2)

≥(i​i) 𝔼𝝃∼ℙ[φ(h(c(x;𝝃)),y;𝝃]+𝔼𝝃∼ℙ​⟨∇1φ​(h⁡(c⁡(x,𝝃)),y,𝝃),ϑ𝝃⊤​(c⁡(x^,𝝃)−c⁡(x,𝝃))⟩⏟①

+𝔼𝝃∼ℙ​⟨∇1φ​(h⁡(c⁡(x,𝝃)),y,𝝃),w𝝃⟩⏟②−dh​Lφ​ℓh2​ℓc22​‖x^−x‖2, (105)

where (i) holds since ∇1φ​(⋅,⋅,𝝃) is Lφ-Lipschitz continuous, and (i​i) follows from dh​ℓh-Lipschitz continuity of h and ℓc-Lipschitz continuity of c.

We bound ① in (105) by

𝔼𝝃∼ℙ​⟨∇1φ​(h⁡(c⁡(x,𝝃)),y,𝝃),ϑ𝝃⊤​(c⁡(x^,𝝃)−c⁡(x,𝝃))⟩

= 𝔼𝝃∼ℙ​⟨ϑ𝝃​∇1φ​(h⁡(c⁡(x,𝝃)),y,𝝃),∇xc​(x,𝝃)⊤​(x^−x)⟩+𝔼𝝃∼ℙ​⟨∇1φ​(h⁡(c⁡(x,𝝃)),y,𝝃),ϑ𝝃⊤​v𝝃⟩

≥(i) 𝔼𝝃∼ℙ​⟨∇xc​(x,𝝃)​ϑ𝝃​∇1φ​(h⁡(c⁡(x,𝝃)),y,𝝃),x^−x⟩−𝔼𝝃∼ℙ​‖∇1φ​(h⁡(c⁡(x,𝝃)),y,𝝃)‖​‖ϑ𝝃‖​‖v𝝃‖

≥(i​i) 𝔼𝝃∼ℙ​⟨∇xc​(x,𝝃)​ϑ𝝃​∇1φ​(h⁡(c⁡(x,𝝃)),y,𝝃),x^−x⟩−ℓφ​ℓh​Lc​dh2​‖x^−x‖2, (106)

where (i) holds by Cauchy-Schwarz inequality, and (i​i) follows from ℓφ-Lipschitz continuity of φ, dh​ℓh-Lipschitz continuity of h and 𝔼𝝃∼ℙ​‖v𝝃‖≤Lc2​‖x^−x‖2 (from (9)). Now, since h is convex and φ is non-decreasing in its first argument, it follows that

②=𝔼𝝃∼ℙ​⟨∇1φ​(h⁡(c⁡(x,𝝃)),y,𝝃),w𝝃⟩≥0. (107)

Plugging (106) and (107) into (105), we get

F⁡(x^,y) ≥F⁡(x,y)+⟨𝔼𝝃∼ℙ​[∇xc​(x,𝝃)​ϑ𝝃​∇1φ​(h⁡(c⁡(x,𝝃)),y,𝝃)],x^−x⟩−ρλ2​‖x^−x‖2, (108)

which renders that F⁡(⋅,y) is ρλ-weakly convex.

Noting that hλ​(⋅) is convex with the same Lipschitz continuity constant as h, i.e., ℓh​dh, we can follow the same arguments to show that Fλ​(x,y) is also ρλ-weakly convex and thus complete the proof. ∎

The lemma below establishes that the smoothed objective function Fλ​(x,y) satisfies the KŁ property with respect to y by choosing an appropriate smoothing parameter λ.

Suppose Assumptions 3.1 and 3.2 hold and let λ≤2​δ~ℓh2​dh. Then for all x∈𝒳, Fλ​(x,⋅) satisfies the extended KŁ property with parameters μ and θ.

By (Drusvyatskiy and Paquette, 2019, Lemma 2.1), it follows that for any w∈ℝdc,

‖hλ​(w)−h⁡(w)‖=∑j=1dh|hjλ​(w)−hj​(w)|2≤∑j=1dhλ2​ℓh44=λ​ℓh2​dh2. (109)

Since λ≤2​δ~ℓh2​dh, ∀𝝃∈Ξ, it holds ‖hλ​(c⁡(x,𝝃))−h⁡(c⁡(x,𝝃))‖≤δ~. Let u^:Ξ↦ℝdh be defined as u⁡(𝝃)=hλ​(c⁡(x,𝝃)). Consequently, we get

Fλ​(x,y)=𝔼𝝃∼ℙ​[φ⁡(hλ​(c⁡(x,𝝃)),y,𝝃)]=g⁡(u^,y),

and thus from Assumption 3.2, the desired result follows. ∎

The next lemma will be used to certify a δ-subgradient defined in (2).

Under Assumption 3.1, it holds

|F⁡(x,y)−Fλ​(x,y)|≤λ​Lφ​Lh2​dh2,∀x∈𝒳,y∈𝒴, (110)

|F⁡(x1,y)−F⁡(x2,y)|≤ℓφ​ℓh​ℓc​dh​‖x1−x2‖,∀x1,x2∈𝒳,y∈𝒴, (111)

‖∇yFλ​(x,y)−∇yF​(x,y)‖≤λ​Lφ​ℓh2​dh2,∀x∈𝒳,y∈𝒴. (112)

For any x∈𝒳,y∈𝒴, it holds

|F⁡(x,y)−Fλ​(x,y)|= |𝔼𝝃∼ℙ​[f⁡(x,y,𝝃)]−𝔼𝝃∼ℙ​[fλ​(x,y,𝝃)]|

≤ 𝔼𝝃∼ℙ​|f⁡(x,y,𝝃)−fλ​(x,y,𝝃)|

= 𝔼𝝃∼ℙ​|φ⁡(h⁡(c⁡(x,𝝃)),y,𝝃)−φ⁡(hλ​(c⁡(x,𝝃)),y,𝝃)|

≤(i) 𝔼𝝃∼ℙ​‖h⁡(c⁡(x,𝝃))−hλ​(c⁡(x,𝝃))‖

≤(i​i) λ​Lφ​Lh2​dh2,

where (i) follows from Lφ-Lipschitz continuity of φ, and (i​i) holds by (109). This proves (110).

Additionally, for any x1,x2∈𝒳,y∈𝒴, we have

|F⁡(x1,y)−F⁡(x2,y)|= |𝔼𝝃∼ℙ​[f⁡(x1,y,𝝃)]−𝔼𝝃∼ℙ​[f⁡(x2,y,𝝃)]|

≤ 𝔼𝝃∼ℙ​|f⁡(x1,y,𝝃)−f⁡(x2,y,𝝃)|

= 𝔼𝝃∼ℙ​|φ⁡(h⁡(c⁡(x1,𝝃)),y,𝝃)−φ⁡(h⁡(c⁡(x2,𝝃)),y,𝝃)|

≤ ℓφ​ℓh​ℓc​dh​‖x1−x2‖,

where the last inequality follows from ℓφ-, dh​ℓh-, and ℓc-Lipschitz continuity of φ, h, and c. Thus (111) follows.

Moreover, we have for any x∈𝒳,y∈𝒴 that

‖∇yFλ​(x,y)−∇yF​(x,y)‖= ‖𝔼𝝃∼ℙ​[∇yfλ​(x,y,𝝃i)]−𝔼𝝃∼ℙ​[∇yf​(x,y,𝝃i)]‖

≤ 𝔼𝝃∼ℙ​‖∇yfλ​(x,y,𝝃i)−∇yf​(x,y,𝝃i)‖

= 𝔼𝝃∼ℙ​‖∇yφ​(hλ​(c⁡(x,𝝃)),y,𝝃)−∇yφ​(h⁡(c⁡(x,𝝃)),y,𝝃)‖

≤(i) 𝔼𝝃∼ℙ​Lφ​‖hλ​(c⁡(x,𝝃))−h⁡(c⁡(x,𝝃))‖

≤(i​i) λ​Lφ​ℓh2​dh2,

where (i) follows from (11), and (i​i) is by (109). This proves (112) and completes the proof. ∎

Suppose Assumption 3.1 holds. Then for all x∈𝒳 and y∈𝒴 we have

dist​(0,∂xδ(F⁡(x,y)+ι𝒳​(x)))2≤ ‖∇zdrλ​(y,x)‖2, (113)

dist​(0,−∇yF​(x,y)+𝒩𝒴​(y))2≤ 2​d​i​s​t​(0,−∇yFλ​(x,y)+𝒩𝒴​(y))2+λ2​dh​Lφ2​ℓh42, (114)

where

δ=ρλ​D𝒳r​‖∇zdrλ​(y,x)‖+ℓφ​ℓh​ℓc​dhr​‖∇zdrλ​(y,x)‖+(ρλ2​r2+1r)​‖∇zdrλ​(y,x)‖2+λ​ℓφ​ℓh2​dh.

The optimality condition for xrλ​(y,x) gives 0∈∇xFλ​(xrλ​(y,x),y)−r⁡(x−xrλ​(y,x))+𝒩𝒳​(xrλ​(y,x)). In addition, by Danskin’s Theorem, we have

∇zdrλ​(y,x)=r⁡(x−xrλ​(y,x)). (115)

Hence,

∇zdrλ​(y,x)∈∇xFλ​(xrλ​(y,x),y)+𝒩𝒳​(xrλ​(y,x)). (116)

Now, from the ρλ-weak convexity of Fλ​(⋅,y) and (116), we have for any x^∈𝒳 that

Fλ​(x^,y)≥Fλ​(xrλ​(y,x),y)+⟨∇zdrλ​(y,x),x^−xrλ​(y,x)⟩−ρλ2​‖x^−xrλ​(y,x)‖2

which can be written as

F⁡(x^,y)+(Fλ​(x^,y)−F⁡(x^,y)) ≥F⁡(x,y)+(F⁡(xrλ​(y,x),y)−F⁡(x,y))+(Fλ​(xrλ​(y,x),y)−F⁡(xrλ​(y,x),y))

+⟨∇zdrλ​(y,x),x^−x⟩+⟨∇zdrλ​(y,x),x−xrλ​(y,x)⟩−ρλ2​‖x^−x‖2

−ρλ​⟨x^−x,x−xrλ​(y,x)⟩−ρλ2​‖x−xrλ​(y,x)‖2.

By (110), (111), and Cauchy-Schwarz inequality, we obtain from the above inequality that

F⁡(x^,y)+λ​ℓφ​ℓh2​dh2≥F⁡(x,y)−ℓφ​ℓh​ℓc​dh​‖x−xrλ​(y,x)‖−λ​ℓφ​ℓh2​dh2+⟨∇zdrλ​(y,x),x^−x⟩

+⟨∇zdrλ​(y,x),x−xrλ​(y,x)⟩−ρλ2​‖x^−x‖2−ρλ​‖x^−x‖​‖x−xrλ​(y,x)‖−ρλ2​‖x−xrλ​(y,x)‖2,

which together with (115) and ‖x^−x‖≤D𝒳 implies

F⁡(x^,y)≥F⁡(x,y)+⟨∇zdrλ​(y,x),x^−x⟩−ρλ2​‖x^−x‖2

−[ρλ​D𝒳r​‖∇zdrλ​(y,x)‖+ℓφ​ℓh​ℓc​dhr​‖∇zdrλ​(y,x)‖+(ρλ2​r2+1r)​‖∇zdrλ​(y,x)‖2+λ​ℓφ​ℓh2​dh].

Hence, from the definition of δ, it follows

F⁡(x^,y)≥F⁡(x,y)+⟨∇zdrλ​(y,x),x^−x⟩−ρλ2​‖x^−x‖2−δ.

Thus, we deduce from the definition of δ-subdifferential that

∇zdrλ​(y,x)∈∂xδ(F⁡(x,y)+ι𝒳​(x))⟹dist​(0,∂xδ(F⁡(x,y)+ι𝒳​(x)))2≤‖∇zdrλ​(y,x)‖2.

Finally, by Young’s inequality and (112), we have

dist​(0,−∇yF​(x,y)+𝒩𝒴​(y))2≤ 2​d​i​s​t​(0,−∇yFλ​(x,y)+𝒩𝒴​(y))2+2​‖∇yFλ​(x,y)−∇yF​(x,y)‖2

≤ 2​d​i​s​t​(0,−∇yFλ​(x,y)+𝒩𝒴​(y))2+λ2​dh​Lφ2​ℓh42.

This completes the proof. ∎

We are now ready to present the main convergence result for the nonsmooth case.

We first note that from the definitions of Frλ​(x,y,z), dr​(y,z) and pr​(z) in Table 2 we have for all x∈𝒳, y∈𝒴 and z∈ℝdx,

Φ^r​(x,y,z)= (Frλ​(x,y,z)−drλ​(y,z))+(prλ​(z)−drλ​(y,z))+prλ​(z)

≥ prλ​(z)

= maxy∈𝒴⁡minx∈𝒳​Frλ​(x,y,z)

≥ maxy∈𝒴⁡minx∈𝒳​Fλ​(x,y)

≥ maxy∈𝒴⁡minx∈𝒳⁡F⁡(x,y)−λ​Lφ​Lh2​dh2

≥ F¯−λ​Lφ​Lh2​dh2=:F¯λ, (117)

where the second inequality follows from Frλ​(x,y,z)≥Fλ​(x,y), the third one is by (110), and the last inequality holds from Remark 3.3.

Now, in light of Lemma B.6, we have

𝔼⁡[dist​(0,∂xδ(F⁡(x,y)+ι𝒳​(x)))2]+𝔼⁡[dist​(0,−∇yF​(x~,y~)+𝒩𝒴​(y~))2]

≤ 𝔼​‖∇zdrλ​(y~,x~)‖2⏟①+2​𝔼​[dist​(0,−∇yFλ​(x~,y~)+𝒩𝒴​(y~))2]⏟②+λ2​dh​Lφ2​ℓh42⏟③, (118)

where

δ=ρλ​D𝒳r​‖∇zdrλ​(y~,x~)‖+ℓφ​ℓh​ℓc​dhr​‖∇zdrλ​(y~,x~)‖+(ρλ2​r2+1r)​‖∇zdrλ​(y~,x~)‖2+λ​ℓφ​ℓh2​dh. (119)

Directly from Theorem 2.4, it follows that the algorithm produces (x~,y~) such that ①,②=𝒪⁡(ε2). Additionally, since λ=Θ⁡(ε), ③ in (118) is also 𝒪⁡(ε2).

The argument for the sample complexity is the same as the one presented in Theorem 2.4 and thus, the proof is complete. ∎

Appendix C Motivating Applications - Formulations

In this section, we present a detailed description of two classes of problems whose cost function can be formulated in accordance with (8).

ϕ-Divergence DRO

As discussed earlier, the objective of distributionally robust modeling is to ensure that the learned models remain reliable not only under adversarial perturbations but also in the presence of distributional shifts. In contrast to traditional empirical risk minimization, which optimizes performance under the empirical data distribution, distributionally robust optimization seeks to minimize the worst-case loss over an uncertainty set of probability distributions.

Levy et al. (2020) study this DRO problem and consider a slight generalization of ϕ-divergence–based DRO. Specifically, let ϕ:ℝ+→ℝ∪{+∞} be a convex function satisfying ϕ⁡(1)=0, and define the ϕ-divergence between distributions ℚ and ℙ as follows:

Dϕ​(ℚ,ℙ):=∫ϕ⁡(d​ℚd​ℙ)​𝑑ℙ, (120)

where ℚ is absolutely continuous with respect to ℙ. Then, for a convex function ψ with ψ⁡(1)=0, a constraint radius ρ≥0, penalty parameter λ≥0, and ℓ⁡(θ,⋅) denoting the loss function parameterized by θ, the objective considered in (Levy et al., 2020) takes the form:

minθ∈Θmaxℚ:Dϕ​(ℚ,ℙ)≤ρ{𝔼𝝃∼ℚ[ℓ(θ;𝝃)]−λDψ(ℚ,ℙ)}. (121)

We consider the case when ℙ is the empirical distribution induced by N i.i.d samples with support Ξ={𝝃i,…,𝝃N}. Since ℚ is absolutely continuous wrt ℙ, it follows that ℚ assigns probability mass only to points in Ξ. By the Radon–Nikodym theorem, for each 𝝃i∈Ξ, we then have:

ℚ⁡(𝝃i)=d​ℚd​ℙ​(𝝃i)​ℙ​(𝝃i)⟹d​ℚd​ℙ​(𝝃i)=ℚ⁡(𝝃i)ℙ⁡(𝝃i). (122)

Without loss of generality, denote ℚ⁡(𝝃i)=qi with q∈ΔN, the N-probability simplex. Then, utilizing (120) and (122) yields

Dϕ​(ℚ,ℙ)=∑i=1Nϕ⁡(d​ℚd​ℙ​(𝝃i))​ℙ​(𝝃i)=∑i=1Nϕ⁡(ℚ⁡(𝝃i)ℙ⁡(𝝃i))​ℙ​(𝝃i)=∑i=1Nϕ⁡(qi1N)​1N=1N​∑i=1Nϕ⁡(N​qi).

Similarly, we get

Dψ​(ℚ,ℙ)=1N​∑i=1Nψ⁡(N​qi).

Now, assuming each data sample 𝝃i is a pair (xi,yi) of features and targets, denoting the predictor function parameterized by θ as fθ and letting e𝝃i denote the it​h standard basis vector in ℝN, the DRO problem in (121) can be expressed as

minθ∈Θmaxq∈ΔN:∑i=1Nϕ⁡(N​qi)≤N​ρ1N∑i=1NNqiℓ(fθ(xi),yi)−λψ(Nqi). (123)

Under the choices of

c(θ;𝝃i)=(fθ(xi),yi),h(v1,v2)=ℓ(v1,v2),and φ(w1,w2;𝝃i)=N(e𝝃i⊤w2)w1−λψ(N(e𝝃i⊤w2)),

it then follows that the cost function in (123) exhibits the structure in (8).

Group–DRO

In many real-world applications, data points naturally belong to disjoint groups or subpopulations, and models trained via standard empirical risk minimization often underperform on minority or underrepresented groups. Group distributionally robust optimization (Group–DRO) addresses this by explicitly optimizing the worst-case performance across groups, rather than the average loss. This approach is particularly useful in domains where performance differences across groups can have undesired consequences; in healthcare where it can help address subgroup performance disparities (Pfohl et al., 2022), in recommendation systems to improve worst-case user experience (Wen et al., 2022), and in Natural Language Processing (NLP) to train models that are robust to topic shifts (Oren et al., 2019).

Formally, let the dataset be partitioned into M groups with distributions {ℙg}g=1M, and let fθ denote a predictor function parameterized by θ. Following (Sagawa et al., 2020), we have the Group–DRO problem objective as follows:

minθ∈Θ⁡max⁡∑g=1Mq∈ΔM⁡qg​𝔼(x,y)∼ℙg​[ℓ⁡(fθ​(x),y)],

where ΔM is the M-dimensional probability simplex, and q assigns weights to the groups. We note that:

∑g=1Mqg​𝔼(x,y)∼ℙg​[ℓ⁡(fθ​(x),y)]=∑g=1Mqg​1|𝒢g|​∑i=1|𝒢g|ℓ⁡(fθ​(xi),yi)​=(i)​1N​∑i=1NN​qgi|𝒢gi|​ℓ​(fθ​(xi),yi),

where (i) follows from the fact that the groups are disjoint and collectively cover all data points, and gi denotes the index of the group to which the data point (xi,yi) belongs. Let egi denote the gith standard basis vector in ℝM. Then under the choices of

𝒢={|𝒢j|}j=1M,𝝃i=(xi,yi),c(θ;𝝃i)=(fθ(xi),yi),h(v1,v2)=ℓ(v1,v2),φ(w1,w2;𝝃i)=N⁡(egi⊤​w2)​w1egi⊤​𝒢,

it then follows that the cost function exhibits the structure in (8).

Appendix D KŁ example

In this section we present an explicit example of a smooth but nonconcave function that satisfies the KŁ property. Consider the function g:[−2,2]→ℝ defined as

g⁡(y)={2​ey+1−1,−2≤y≤−1,−y2+2,−1<y≤1,2​e−y+1−1,1<y≤2. (124)

As can be observed, the function g is continuously differentiable on the compact set [−2,2]. Moreover, despite being nonconcave, it attains its unique global maximum at y⋆=0.

Figure 1 illustrates the shape of the function.

Figure 1: Illustration of the nonconcave function defined in (124).

The function g⁡(y) defined in (124) satisfies the KŁ property with θ=12 and μ=110, i.e., for all y∈[−2,2],

dist(0,−g′(y)+𝒩[−2,2](y))≥μ(maxy′∈[−2,2]g(y′)−g(y))θ. (125)

First, we note that maxy′∈[−2,2]⁡g⁡(y′)=2. Additionally, we have

𝒩[−2,2]​(y)={(−∞, 0],y=−2,0,y∈(−2,2),[0,∞),y=2,andg′​(y)={2​ey+1,−2≤y≤−1,−2​y,−1<y≤1,−2​e−(y−1),1<y≤2.

Since g′​(−2)>0, we have

dist(0,−g′(−2)+𝒩[−2,2](−2))=dist(0,(−∞,−g′(−2)])=|g′(−2)|=2e−1≥110(3−2e−1)12.

Thus (125) is satisfied for y=−2. Similarly, since g′​(2)<0, we have

dist(0,−g′(2)+𝒩[−2,2](2))=dist(0,[−g′(2),∞))=|g′(2)|=2e−1≥110(3−2e−1)12.

Hence, (125) is also satisfied at y=2.

We now discuss the scenario when y∈(−2,2). Here, we have dist⁡(0,−g′​(y)+𝒩[−2,2]​(y))=|g′​(y)|. Thus, it suffices to verify

|g′​(y)|≥110​(2−g⁡(y))12,∀y∈(−2,2). (126)

For the interval y∈(−2,−1], we have g′​(y)=2​ey+1 and 2−g⁡(y)=3−2​ey+1. Then

infy∈(−2,−1]|g′(y)|=2e−1≈0.37,supy∈(−2,−1]110(3−2ey+1)12=110(3−2e−1)12≈0.15.

Thus, (126) is satisfied on this interval.

For the interval y∈(−1,1], we have g′​(y)=−2​y and 2−g⁡(y)=y2=|y|2. Then (126) follows from 2​|y|≥110​|y|.

For the interval y∈(1,2), we have g′​(y)=−2​e−(y−1) and 2−g⁡(y)=3−2​e−(y−1). Then

infy∈(1,2)|g′​(y)|=2​e−1≈0.37,supy∈(1,2)110​(3−2​e−(y−1))12=110​(3−2​e−1)12≈0.15.

Hence, (126) is satisfied on this interval as well. Thus, the proof is complete. ∎