Stability and Generalization for Stochastic (Compositional) Optimizations

1 Introduction

Recently, the Stochastic Compositional Optimization (SCO) problem has found extensive applications in machine learning, including model-agnostic meta-learning (MAML) [Finn et al., 2017] and reinforcement learning [Dann et al., 2014]. The SCO problem [Qi et al., 2021; Chen et al., 2021; Wang et al., 2017; Gao and Huang, 2021] is formulated as follows:

* Corresponding Authors.

where f : Rd1 → Rd2 and g : Rd → Rd1 are defined on a convex domain X ⊂ Rd , ν and ω are independent random variables. Here, gω(·) and fν(·) represent random functions parameterized by ω and ν, respectively. Solving the SCO problem is challenging because, in SCO, acquiring unbiased gradient estimates of the compositional function F(x) is particularly difficult. In other words, the expectation Eν,ω[∇fν(gω(x))] does not equal ∇fν(gω(x)), making it infeasible to obtain an unbiased estimate of F(x).

Due to the prevalence of SCO, many studies have been developed to address its challenges [Jiang et al., 2022; Liu et al., 2024]. Notable contributions include the development of Stochastic Composite Gradient Descent (SCGD) [Wang et al., 2017], which is based on the momentum technique to estimate the inner function value and achieves an O(T -1/4 ) convergence rate in non-convex settings. Additionally, Variance Reduction (VR) techniques [Johnson and Zhang, 2013; Fang et al., 2018; Cutkosky and Orabona, 2019] have been developed. VR techniques typically employ a gradient estimator to track the gradient more accurately, updating it using estimated gradient values rather than relying solely on stochastic gradients. Building on the Variance Reduction (VR) technique, SCSC and COVER were proposed in [Chen et al., 2021] and [Qi et al., 2021], respectively. SCSC achieves a convergence rate of O(T -1/4 ), while COVER improves this rate to O(T -1/3 ) in non-convex settings.

Although numerous algorithms for solving the SCO problem have been developed based on different techniques for designing estimators, as shown above, much of the focus over the past few decades has been on improving convergence rates by using different types and quantities of estimators. However, the impact of estimator variations on the generalization of these algorithms is often overlooked. This aspect is crucial, as generalization serves as a key indicator of how well a learned model, trained on given training samples, performs on unseen test data [Bassily et al., 2020; London et al., 2016].

To explain the impact of estimators, we begin with the Stochastic Optimization (SO) problem [Zhang, 2004; Bottou et al., 2018], which can be viewed as a special case of the SCO problem (when g(x) = x). It can be formulated as follows:

Due to the complexity of the SCO problem, different algorithms choose different update strategies for different levels of the function, making it difficult to control variables for comparison. In contrast, the SO problem allows us to compare two algorithms-one with estimators and one without-making the comparison more intuitive and convenient. Therefore, we compare SGD with other variance-reduced (VR) algorithms within the SO problem. Among VR-based algorithms, STOchastic Recursive Momentum (STORM) [Cutkosky and Orabona, 2019] stands out, as it significantly improves the convergence rate from SGD's O(T -1/4 ) to O(T -1/3 ) in nonconvex settings, bringing the solution closer to near-optimality.

We conducted a toy experiment to compare SGD and STORM in convex and non-convex settings, as shown in Figure 1. In the non-convex setting, STORM demonstrated a faster convergence rate than SGD, as shown in Figure 1b, and it also exhibited superior generalization performance because the gap between training loss and testing loss is smaller. However, in the convex setting (Figure 1a), the trend reversed. It can be noticed that the estimator not only changes the convergence rate of the algorithm, but also the generalization of the algorithm. This observation raises an interesting question: How does the estimator affect the generalization?

Therefore, in this paper, we analyze the effect of estimators on generalization under the SO and SCO problems. We first conduct a generalization analysis of STORM, comparing the results to SGD and exploring the estimator's impact on generalization as an initial step. Considering the complexity of the SCO problem, we then propose a generalized algorithmic framework that encompasses many existing algorithms and applies to multiple estimators and various estimation strategies-i.e., the objects to which the estimator is applied. Subsequently, we analyze the generalization of this framework in both convex and non-convex settings. Through our analysis, we identify the estimators that are crucial and those that are less important. Furthermore, we perform a generalization analysis of three representative algorithms-SCGD, SCSC, and COVER-under the SCO problem to compare how different estimation strategies impact algorithm generalization. Based on this analysis, we also establish a relationship between the convergence rate and generalization, summarized in Table 2. In summary, the main contributions of this paper are as follows:

• We propose a generalized algorithmic framework for the SCO problem. We then analyze the proposed framework
• in both convex and non-convex settings, along with the generalization performance of three representative algorithms-SCGD, SCSC, and COVER-to understand how different strategies influence generalization outcomes. In addition, we have found that convergence and generalization are closely related; specifically, a faster convergence rate tends to enhance generalization performance.
• For the non-convex setting of the SCO problem, we introduce a novel definition of stability. This new stability definition is based on the gradient of the objective function, recognizing that in a non-convex setting, the goal is often to find a stationary point rather than the global minimum. We also introduce a new excess risk decomposition for the SCO problem in the non-convex setting. To the best of our knowledge, this new definition and the new excess risk decomposition allow us, for the first time, to generalize our analysis of algorithms for the SCO problem in the non-convex setting. Through our analysis, we provide guidance on the use of estimators when designing algorithms.

2 RelatedWork

SO and SCO Algorithms. In addition to SGD [Zhang, 2004; Bottou et al., 2018] and VR-based methods [Johnson and Zhang, 2013; Fang et al., 2018; Cutkosky and Orabona, 2019] for stochastic optimization, several improved algorithms have emerged from various perspectives. For example, Nesterov acceleration [Nesterov, 1983; Attouch and Peypouquet, 2016] and adaptive learning rates [Duchi et al., 2011; Kingma and Ba, 2014; Zhou et al., 2018] can achieve an impressive O(T -1/2 ) convergence rate. Due to biased gradient estimations on both inner and outer functions, the predominant trend in addressing SCO problems is leveraging VR techniques. For example, variants of SARAH [Nguyen et al., 2017] and SPIDER [Fang et al., 2018] achieve an impressive O(T -1/3 ) convergence rate with large batch sizes [Zhang and Xiao, 2019]. COVER [Qi et al., 2021] proposes a batch-free algorithm based on STORM with the same rate without using mini-batches. Furthermore, recent advancements extend VR techniques to federated SCO [Gao and Huang, 2021], multilevel SCO [Jiang et al., 2022], and compositional minimax problems [Liu et al., 2024]. Despite extensive exploration of these problems, their generalization remains under-explored.

Generalization Analysis. Algorithmic stability is a cornerstone concept in learning theory, gauging an algorithm's resilience to perturbations in the training dataset, closely intertwined with its learnability [Rakhlin et al., 2005; ShalevShwartz et al., 2010]. One of the most widely employed stability concepts is uniform stability [Bousquet and Elisseeff, 2002], often signaling nearly optimal generalization bounds with high probability [Feldman and Vondrak, 2019; Bousquet and Elisseeff, 2002]. While ML methods can excel in training data but falter in generalization, the uniform convergence approach in generalization analysis helps illuminate the discrepancy between training and testing across the entire hypothesis space [Foster et al., 2018; Nagarajan and Kolter, 2019]. Initially, uniform convergence focused on function values [Bartlett and Mendelson, 2002], which is less suited for stochastic optimization with nonconvex loss functions. Subsequent studies have improved upon this, encompassing uniform convergence of function values [Lei et al., 2021], gradient risks in smooth problems [Ghadimi and Lan, 2013], and Moreau envelope gradients in weakly convex problems [Davis and Drusvyatskiy, 2019].

3 The Target of Analysis and Our Framework

In this section, we illustrate the target of the generalization analysis for both convex and non-convex settings, and then we introduce our proposed framework, followed by some necessary notation.

3.1 The Target of Analysis

We first introduce some notations to clarify our final target. Let x∗ = argminx∈X F(x) be the model with the minimal population risk in X. Let A be a randomized learning algorithm and A(S) be the output model when applying A to the dataset S. Let ∥ · ∥ denote the Euclidean norm, and let ∇f(x) represent a subgradient of f at x. If f is differentiable, then ∇f(x) corresponds to the gradient of f at x. It is important to note that we use the same symbols, FS(x), F(x), to represent the empirical risk and population risk for both SO and SCO problems. However, their meanings differ in these two contexts, and we will provide detailed notations in Section 4 and 5 to clarify them in the following section.

The Convex Setting. For the convex setting that is lower bounded, there is always an optimal global minimum, denoted as x∗ . The model's behavior is quantified by the population risk, with the goal of analyzing the excess risk ES,A[F(A(S))] - F(x∗ ). The standard approach [Bousquet and Elisseeff, 2002] decomposes excess risk into two error terms as follows:

where we use the relation ES,A[FS(x∗ )] = F(x∗ ) because x∗ is independent of both A and S. We refer to the difference F(A(S)) - FS(A(S)) mentioned in (3) as the generalization error, as it reflects how the model generalizes from training to testing behaviors. The term FS(A(S)) - FS(x∗ ) is identified as the optimization error since it measures the algorithm's effectiveness in minimizing the empirical risk, which is widely used in [Hardt et al., 2016; Kuzborskij and Lampert, 2018; Charles and Papailiopoulos, 2018].

The Non-Convex Setting. However, for non-convex learning problems, we focus on whether the learning algorithm can find an approximate stationary point, that is, ∥∇FS(A(S))∥ ≤ ϵ because it is difficult to find the global optimum [Zhang, 2004; Bottou et al., 2018; Cutkosky and Orabona, 2019]. Consequently, the excess risk used in convex settings are not applicable. Instead, we employ the population gradient norm as the performance measure, shifting our final target to ES,A[∥∇F(A(S))∥]. Based on this measurement method, we have the following decomposition:

Similarly to the decomposition in the convex setting, we refer to the first term, ES,A[∥∇F(A(S)) - ∇FS(A(S))∥] as the generalization error and to the second term, ES,A[∥∇FS(A(S))∥], as the optimization error.

3.2 The Proposed Framework

We first introduce some notations. Similar to [Wang et al., 2017; Qu et al., 2023; Yang et al., 2023], we concern the case that the random variables ν and ω are independent. In practice, we do not know the population distributions for ν and ω for SCO problem but only have access to a set of training data S = {ν1, . . . , νn, ω1, . . . , ωm}. Now we give the framework for solving (2). For the algorithms of the SCO problem, their main difference lies in the different designs of ut and vt. Some commonly used approaches for estimating the inner function value are as follows:

Algorithm 1 Framework of SCO

• 1: Inputs: Training data S = {ν1, . . . , νn, ω1, . . . , ωm}; Number of iterations T , parameter sequence {ηt}, {βt}
• 2: Initialize x0 ∈ X and y0 ∈ Rd
• 3: for t = 0 to T -1 do
• 4: Randomly sample jt ∈ [1,m], obtain gωjt (xt) and ∇gωjt (xt) ∈ Rd×d2
• 5: Estimate inner function value ut according to Eq.(5)
• 6: Estimate inner function gradient vt according to Eq. (6) or Eq. (7)
• 7: Randomly sample it ∈ [1, n], obtain ∇fνit (ut) ∈ Rd
• 8: Calculate the total gradient vt = vt · ∇fνit (ut)
• 9: Update:
• 10: xt+1 = ΠX (xt - ηtvt )
• 11: end for
• 12: Outputs: A(S) = xT or xτ ∼ Unif({xt}Tt=1 )

For the inner function gradient, there are typically two cases. The first is to use the stochastic gradient directly, i.e.,

In other cases, an estimator is used instead of the stochastic gradient for updating. There are many types of estimators, and we list a few common ones below:

It is worth noting that there are many other types of methods, such as SPIDER [Fang et al., 2018], SVRG [Johnson and Zhang, 2013], and SAGA [Defazio et al., 2014]. It is also important to emphasize that algorithms based on the proposed framework are not limited to the aforementioned three methods but also include others, such as NASA [Ghadimi et al., 2020], CIVR [Zhang and Xiao, 2019], and Compositional SVRG [Lian et al., 2017], among others. Naturally, these algorithms select different parameter sequences depending on the estimator used.

Subsequently, we aim to analyze the generalization of the proposed framework. To achieve this, we derive generalization bounds with the help of stability analysis. Therefore, we first introduce the definition of stability. We begin by presenting the definition of stability in the context of the SO problem, followed by our newly introduced definition of stability for the SCO problem.

3.3 Definition of Stability

Definition 1 (Uniform Stability for SO). Let A be a randomized algorithm. Let S = (ν1, ν2, . . . , νn) be drawn i.i.d from D. Let S and S′ be neighboring datasets, differing by at most one data point.

• We say A is ϵ-uniformly-stable in function values if for all neighboring datasets S, S′ , such that supν EA[fν (A(S)) - fν (A(S′ ))] ≤ ϵ.
• We say A is ϵ-uniformly-stable in gradients if for all neighboring datasets S, S′ , such that supν EA[∥∇fν (A(S)) - ∇fν (A(S′ ))∥2 ] ≤ ϵ2 .

Definition 1 defines stability for convex and non-convex settings. In convex settings, the goal is to find the global minimum, so stability is defined by function values. In nonconvex settings, the focus is on finding an approximate stable point [Cutkosky and Orabona, 2019; Levy et al., 2021; Lei, 2023], where the gradient approaches zero, leading to stability being defined by the function gradient.

When considering SCO problems in (1), the definition of stability becomes more complex. Changes in the sample may occur in either the set {ν1, ν2, . . . , νn} or the set {ω1, ω2, . . . , ωm}. Although various stability concepts, such as locally elastic stability [Deng et al., 2021; Zhang et al., 2021; Qu et al., 2022], hypothesis stability [Charles and Papailiopoulos, 2018; Bousquet et al., 2020], and PAC-Bayesian stability [Li et al., 2019; Rivasplata et al., 2020], have been developed, they are not suited for non-convex SCO problems. To address this, we introduce a novel stability concept designed for this context and utilize it in our analysis. Let Si,ν denote the change at the i-th data point in {ν1, ν2, . . . , νn}, and Sj,ω denote the change at the j-th data point in {ω1, ω2, . . . , ωm}, we propose a new definition of stability.

Definition 2 (UniformStability for SCO). Let A be a randomized algorithm.

• We say A is ϵ-uniformly-stable in function values if for all neighboring datasets S, Si,ν , we have supν,ω EA[fν(gω(A(S))) - fν(gω(A(Si,ν )))] ≤ ϵν, and for all neighboring datasets S, Sj,ω , we have supω EA[gω(A(S)) - gω(A(Sj,ω ))] ≤ ϵω.
• We say A is ϵ-uniformly-stable in gradients if for all neighboring datasets S, Si,ν , we have supν,ω EA[∥∇fν(gω(A(S))) -

∇fν(gω(A(Si,ν )))∥2 ] ≤ ϵ2ν , and for all neighboring datasets S, Sj,ω , we have supω EA[gω(A(S)) - gω(A(Sj,ω ))] ≤ ϵω.

In Definition 2, we stabilize the function value of the inner function g(·) for both settings. An alternative stability definition considers: supω EA[∥∇gω(A(S))-∇gω(A(Sj,ω ))∥2 ] ≤ ϵ2ω for the non-convex setting. However, this approach relies on the chain rule and requires additional assumptions, specifically that the gradient of the outer function is bounded, i.e. ∥∇fν(·)∥ is bounded, to control ∥∇fνi ( 1m ∑mj=1 gωj (A(S)))-∇fνit (g(A(S)))∥. In contrast, Definition 2 leverages the Lipschitz continuity of the outer function, avoiding the need for gradient boundedness.

Our final target is presented in (3) and (4). With the concept of stability and the stability bounds of algorithms, we can derive the generalization error, which corresponds to the first term on the right side of (3) and (4). By also considering the optimization error, represented by the second term, we can achieve the desired results.

4 Theoretical Analysis of SOs

For the SO problem in (2), the training and testing behavior can be typically measured by the empirical risk FS(x) := 1n ∑ni=1 fνi (x) and the population risk F(x) := Eν[fν(x)]. To facilitate our proof, we first present the following essential definitions. These concepts are fundamental to the generalization analysis of SO problems [Hardt et al., 2016; Bousquet and Elisseeff, 2002; Lei, 2023].

Definition 3. Let f : Rd → R. There exist constants Lf , Cf > 0 holding the following conditions:

• We say f is Lipschitz continuous if supν ∥fν(x) - fν (ˆx)∥ ≤ Lf ∥x - ˆx∥, ∀x, ˆx ∈ Rd .
• We say f is smoothness if supν ∥∇fν(x) -∇fν(ˆx)∥ ≤ Cf ∥x - ˆx∥, ∀x, ˆx ∈ Rd .

Definition 4. Let f : Rd → R and the constant σg > 0. With probability 1 w.r.t S, it holds that supx∈X 1n ∑ni=1 [∥∇fνi (x) - ∇fS(x)∥2 ] ≤ σ2 g .

As a preliminary step, and in conjunction with above two definitions, we employ the stability concept outlined in Definition 1 to derive the results of the SO problem.

Theorem 1 (Convex of STORM). Let FS be convex, EA[∥xtxS∗ ∥] ≤ Dx with t > 0, supν EA[fν(A(S))] ≤ L, ∀S and EA[∥v0 -∇fS(x0)∥2 ] ≤ ∆v. If we choose β ≥ 8L2f η2 , for any c > 0, ES,A [F (A(S))] - F (x∗ ) satisfies:

When we choose that η ≍ T -2/3 , β ≍ T -2/3 , and T ≍ L-3/4n3/4 , then we can obtain that ES,A[F(A(S))] - F (x∗ ) = O(n-1/4L1/4 ).

Remark 1. Theorem 1 shows that SGD requires more iterations, T ≍ n, to achieve a better generalization result of O(n-1/2 ). This makes direct comparison with STORM challenging under different iteration regimes. To ensure fairness, we fix the iterations to T ≍ n3/4 for both methods. Under this condition, SGD achieves an excess error bound of O(n-3/8 ), while STORM attains O(n-1/4 ). Clearly, SGD exhibits better generalization performance in this scenario. This explains STORM's inferior performance compared to SGD in the convex toy example (Figure 1a).

We now examine STORM in non-convex settings.

Theorem 2 (Non-convex of STORM). If FS is non-convex, ηt = O(T -1/3 ), βt = O(T -2/3 ), supν EA[∥∇fν(A(S))∥2 ] ≤ G2 , ∀S and EA[∥v0 - ∇fS(x0)∥2 ] ≤ ∆v, the output A(S) = xT satisfies:

In the non-convex setting, the proof reveals that generalization heavily depends on the estimator's error. A detailed analysis of the estimator's impact will be discussed later in the SCO problem, which includes the SO problem.

It important to notice that both Theorems 1-2 depend on the assumptions that function values and gradients are bounded when the algorithm's final output is reused as input. These widely used assumptions [Hardt et al., 2016; Lei, 2023; Wang et al., 2024] are automatically met by applying a projection operator to A(S), thus avoiding iterative projections.

In the following discussion, we will examine the SCO problem and conduct a comparative analysis of the framework and three algorithms across both settings, focusing on the impact of the estimator on generalization.

5 Theoretical Analysis of SCO

When the problem involves SCO [Qi et al., 2021; Chen et al., 2021; Wang et al., 2017; Gao and Huang, 2021], the objective function f(x) is extended into the compositional function f(g(x)). The empirical risk for SCO problems is defined as follows: minx∈X FS(x) := 1n ∑ni=1 fνi ( 1m ∑mj=1 gωj (x)), and the population risk as F(x) := Eν[fν(Eω[gω(x)])]. Due to the difference, we need to re-define the corresponding Lipschitz continuity and smoothness for the SCO problem.

Definition 5. Let f : Rd1 →Rd2 and g : Rd →Rd1 . There exist constants Lf , Lg, Cf > 0 holding the following conditions:

• We say f is Lipschitz continuous, if supν ∥fν(y) - fν (ˆ y)∥ ≤ Lf ∥y - ˆ y∥ for all y, ˆ y ∈ Rd1 .
• We say f is smoothness, if supν ∥∇fν(y) -∇fν(ˆ y)∥ ≤ Cf ∥y - ˆ y∥ for all y, ˆ y ∈ Rd1 .
• We say g is Lipschitz continuous, if supω ∥gω(x) - gω(ˆx)∥ ≤ Lg∥x - ˆx∥, ∀x, ˆx ∈ Rd .
• We say g is smoothness, if supω ∥∇gω(x) -∇gω(ˆx)∥ ≤ Cg∥x - ˆx∥ for all x, ˆx ∈ Rd .

Definition 6. Let f : Rd1 →Rd2 and g : Rd →Rd1 . There exist constants σg, σg′ > 0 holding that With probability 1 w.r.t S, it holds that supx∈X 1m ∑mj=1 [∥gωj (x) - gS(x)∥2 ] ≤ σ2 g and supx∈X 1m ∑mj=1 [∥∇gωj (x) - ∇gS(x)∥2 ] ≤ σ2 g′ .

With the above definitions, we can then establish the quantitative relationship between Uniform Stability (i.e., Definition 2) and generalization error.

Theorem 3 (Generalization via Stability in Gradients). Let A be ϵ-uniformly-stable in gradients. Assume for any ω and ν, the function gω(·) and fν(·) is differentiable. Then,

Remark 2. Deriving the relationship between stability and generalization for SCO algorithms in non-convex settings presents significant technical challenges. Specifically, the first term in the convex setting decomposition is ES,A[Eν[fν(g(A(S)))] - 1n ∑ni=1 fνi (g(A(S)))], as shown in [Yang et al., 2023]. It can be handled similarly to the non-compositional setting: ES,A [Eν [fν(g(A(S)))] - 1n ∑ni=1 fνi (g(A(S)))] = ES,A,S′ ,ν [ 1n ∑ni=1 (fνi (g (A (Si,ν )) - fνi (g(A(S)))] ≤ Lf ∥∥g (A (Si,ν )) - g(A(S))∥∥. However, the corresponding term in the non-convex setting is: 2ES,A[∥Eν[∇fν(g(A(S)))] - 1n ∑ni=1 ∇fνi (g(A(S))∥2 ]. Since the Euclidean norm and expectation operations cannot be interchanged, the method for the convex setting [Yang et al., 2023] cannot be applied. We address this by re-decomposing the first term, inspired by [Hardt et al., 2016].

We now consider a class of algorithms, specifically SCO sampling-determined algorithms. Details on samplingdetermined algorithms can be found in Theorem 7 in the Appendix.

The generalization performance of the SCO framework is formalized in the following theorem, with the outcomes for the three algorithms summarized in Table 2.

Theorem 4 (Convex of SCO Framework). Let FS be convex, EA[∥xt - xS∗ ∥] ≤ Dx for any t > 0, supω EA[gω(A(S))] ≤ Lω and supν,ω EA[fν(gω(A(S)))] ≤ Lν, ∀S, for any constant γ > 0, define ϵgS t := EA[∥gS(xt) -ut∥2 ], if the framework is updated using Eq.(6), EA[FS(A(S)) -FS(xS∗ )] satisfies:

If the framework is updated using Eq.(7), EA[FS(A(S)) - FS(xS∗ )] satisfies:

Remark 3. According to Theorem 4, using an estimator for the gradient of the inner function in the convex setting does not yield significant improvements. Instead, the extra term γ+η T ∑Tt=1 E[∥vt -∇gS(xt)∥2 ] suggests that such an estimator may lead to worse generalization. To further investigate the effect of the estimator on generalization, we compare the three algorithms. SCGD and SCSC employ different estimators. For SCGD, the corresponding term is ηβ + β2+D2x β β , while for

SCSC, it is β 32 β + β √η +D2x√η. Although SCSC and COVER use the same estimator, COVER additionally incorporates an estimator for the inner function values, resulting in extra terms such as D2x (β + η2 β ), as summarized in Table 1. This aligns with Theorem 4 and explains why COVER did not outperform SCSC in the convex setting.

Remark 4. Although [Yang et al., 2023] established the excess risk for convex and strongly convex settings, it introduced additional constraints, such as η ≤ min{1/n, 1/m}, which may not always be feasible in practice. A very small learning rate is required for large datasets, potentially leading to slow convergence. In contrast, our analysis leverages samplingdetermined algorithms to derive a more informative excess risk at a practical learning rate. Furthermore, we introduce COVER, an algorithm not considered in [Yang et al., 2023]. This is significant because SCGD and SCSC differ only in their estimator techniques. Both algorithms estimate the inner function values, making it difficult to study the effect of the estimator on generalization in isolation.

Accordingly, we will demonstrate the generalization performance of the framework in more complex and broader non-convex settings, as follows:

Theorem 5. Let FS be non-convex, and EA[∥xt - xS∗ ∥] ≤ Dx for any t > 0, supω EA[gω(A(S))] ≤ Lω, and supν,ω EA[fν(gω(A(S)))] ≤ Lν for all S. For any Pt > 0, define ϵgS t := EA[∥gS(xt) - ut∥2 ] and ϵ∇gS t := EA[∥∇gS(xt)-vt∥2 ]. Denote θ = 2L2f σ2 g +2L2g C 2 f - 14 L2f L2g , if the framework is updated using Eq.(6), ES,A[∥∇F(A(S))∥] satisfies:

if the framework is updated using Eq.(7), ES,A[∥∇F(A(S))∥] satisfies:

Remark 5. According to Theorem 5, the main difference between the two is that one has the extra term √θ ∑Tt=1 ηt, while the other has ∑Tt=1 ηtϵ∇gS t . In this case, it is difficult to directly determine which case is more desirable. However, by analyzing the three algorithms, we find that the error of the COVER algorithm's estimator is O(T -1/3 ), while it is O(T -1/4 ) for both SCGD and SCSC. We also examined other algorithms that employ the same strategy as SCGD and SCSC, i.e., without estimating the gradient of the inner function, and found that their estimator errors all reach O(T -1/4 ). This suggests that estimating the gradient of the inner function in the non-convex setting further improves algorithm performance.

Remark 6. By comparing Table 2, we observe a positive correlation between algorithms' convergence rates and their generalization performance. Specifically, We can find that whether it is a SO problem or a SCO problem, and whether it is a convex setting or a non-convex setting, algorithms with faster convergence rates tend to exhibit superior generalization, both in convex and non-convex settings.

6 Performance Evaluation

We conduct simulations to validate our theoretical results by examining the relationship between convergence and generalization. To simulate high-dimensional issues, we set the dimension of X to 100. We generate data using the objective function and add Gaussian noise with mean 0 and variance 1 to each dimension to mimic stochastic optimization. We use MSE loss for the convex setting and combine the tanh activation function with MSE loss for the non-convex setting, resulting in a total loss of MSE loss +α · tanh(ypredict), where α = 0.1 in both SO and SCO problems. For SO problems, we use linear regression in both convex and non-convex settings.

For SCO problems, we generate two datasets, S1 and S2, with |S1| = |S2|. The inner function g(·) fits S1, and f(g(·)) fits S2. We aim to minimize the overall loss of the fits on both datasets. For iteration counts of different methods, we use the results from Table 2 and round to the nearest integer.

For SO problems (Figures 2a and 2b), SGD outperforms STORM in convex settings with faster convergence and better generalization, while STORM excels in non-convex settings. In the convex SCO setting (Figure 2c), SCGD converges slower than SCSC and COVER, which perform similarly, with SCGD also showing higher generalization error. In the non-convex setting, COVER converges faster than SCGD and SCSC, with Figure 2d demonstrating superior generalization for COVER. Overall, generalization error is lower in convex settings for both SO and SCO, consistent with theory.

To further test the effect of estimator errors on generalization, we conducted another set of simulation experiments. Since each algorithm uses a different number of estimators-i.e., COVER uses estimators for both the inner function value and its gradient, while SCGD and SCSC only use estimators for the inner function value-we added extra noise only to the estimators common to SCGD, SCSC, and COVER (i.e., those for the inner function values) for fairness. From Figure 3, it can be observed that larger estimation errors lead to worse generalization performance.

7 Conclusion

In this paper, we systematically analyze the impact of estimators on generalization. We first analyze the generalization of STORM and compare it with SGD under the SO problem. Later on, we propose a general framework for SCO that incorporates many existing popular algorithms, and then generalize it for both convex and non-convex settings. To analyze the non-convex setting under SCO, we also introduce a new definition of excess risk decomposition and stability in gradients. Finally, we select three representative algorithms and perform an analysis on them to further explore the effect of different estimator strategies on generalization. Through our analysis, we establish guidelines for using estimators when designing algorithms for SCO. Specifically, in the convex setting, the desired generalization result can be guaranteed without employing any estimator for the gradient of the inner function, which reduces computational and storage overhead. Additionally, we identify a relationship between convergence and generalization: algorithms with faster convergence rates tend to exhibit better generalization performance.

Acknowledgments

This work was supported by National Natural Science Foundation of China (NSFC) (62302525), the Project of Xiangjiang Laboratory (24XJJCYJ01003), the NSFC (U24A20256, 62202293, 62303306), the Science and Technology Innovation Program of Hunan Province (2022RC1031), the Natural Science Foundation of Hunan Province (2024JJ6527, 2025JJ50374), and the High Performance Computing Center of Central South University.