SIFAR: A Simple Faster Accelerated Variance-Reduced Gradient Method

1 Introduction

In this paper, we consider the fundamental finite-sum problems of the form

where f : Rd → R is a smooth and convex function. We consider two settings in this paper, i) general convex setting

(µ = 0); ii) strongly convex setting (µ > 0), where µ is the strongly convex parameter for f(x), i.e., f(x) - f(y) - ⟨∇f(y), x - y⟩ ≥ µ2 ∥x - y∥2 . Note that the case µ = 0 reduces to the standard convexity. Also note that the strong convexity is only corresponding to the average function f, is not needed for these component functions fis.

Finite-sum problem (1) captures the standard empirical risk minimization (ERM) problems in machine learning [ShalevShwartz and Ben-David, 2014]. There are n data samples and fi denotes the loss associated with i-th data sample, and the goal is to minimize the loss over all data samples. This optimization problem has found a wide range of applications in machine learning, statistical inference, and image processing. In recent years, there has been extensive research in designing gradient-type methods for solving this problem (1). To measure the efficiency of algorithms for solving (1), it is standard to bound the number of stochastic gradient computations for finding a suitable solution. In particular, our goal is to find a point ̂ x ∈ Rd such that E[f(̂ x) - f(x∗ )] ≤ ϵ, where the expectation is with respect to the randomness inherent in the algorithm. We use the term ϵ-approximate solution to refer to such a point ̂ x, and use the term stochastic gradient complexity to describe the convergence result (convergence rate) of algorithms.

Two of the most classical gradient-type algorithms are gradient descent (GD) and stochastic gradient descent (SGD) (e.g., [Nemirovski and Yudin, 1983; Nesterov, 2004; Nemirovski et al., 2009; Duchi et al., 2010; Lan, 2012; Ghadimi and Lan, 2012; Hazan, 2019]). However, GD requires to compute the full gradient over all n data samples for each iteration (xt+1 = xt - η 1n ∑ni=1 ∇fi(xt)) which is inefficient especially for large-scale machine learning problems where n is very large. Although SGD only needs to compute a single stochastic gradient (e.g., ∇fi(x)) for each iteration (xt+1 = xt - η∇fi(xt)), it requires an additional bounded variance assumption for the stochastic gradients (i.e., ∃σ > 0, Ei[∥∇fi(x) - ∇f(x)∥2 ] ≤ σ2 ) since it does not compute the full gradients (∇f(x), i.e., 1n ∑ni=1 ∇fi(x)). More importantly, for strongly convex problems, SGD only obtains a sublinear convergence rate O( σ2 µϵ ) rather than a linear rate O(· log 1ϵ ) achieved by GD.

To remedy the variance term E[∥∇fi(x) - ∇f(x)∥2 ] in SGD, the variance reduction technique has been proposed and it has been widely-used in many algorithms in recent years. In particular, [Le Roux et al., 2012; Schmidt et al., 2017] propose the first variance-reduced algorithm called SAG and show that by incorporating new gradient estimators into SGD one can possibly achieve the linear convergence rate for strongly convex problems. Then this variance reduction direction is followed by many works such as [Shalev-Shwartz and Zhang, 2013; Mairal, 2013; Johnson and Zhang, 2013; Defazio et al., 2014; Mairal, 2015; Nguyen et al., 2017]. Particularly, SAG [Le Roux et al., 2012] uses a biased gradient estimator while SAGA [Defazio et al., 2014] modifies it to an unbiased estimator and provides better convergence results. [Johnson and Zhang, 2013] propose a novel unbiased stochastic variance reduced gradient (SVRG) method which directly incorporates the full gradient term ∇f(x) into SGD. More specifically, each epoch of SVRG starts with the computation of the full gradient ∇f(˜x) at a snapshot point ˜x ∈ Rn and then runs SGD for a fixed number of steps using the modified stochastic gradient estimator

i.e., xt+1 = xt - η˜∇t, where i is randomly picked from {1, 2, . . . , n}. In particular, if each full gradient ∇f(˜x) (which requires n stochastic gradient computations) at the snapshot point ˜x is reused for n iterations (i.e., ˜x is changed after every n iterations), then the amortized stochastic gradient computations for each iteration is the same as SGD. Note that E[˜∇t] = ∇f(xt) is an unbiased estimator, and its variance E[∥˜∇t - ∇f(xt)∥2 ] ≤ 4L(f(xt) - f(x∗ ) + f(˜x)-f(x∗ )) is reduced as the algorithm converges xt, ˜x → x∗ , while the variance term is uncontrollable for plain SGD where ˜∇t = ∇fi(xt). [Johnson and Zhang, 2013] also show that SVRG obtains the linear convergence O((n + Lµ ) log 1ϵ ) which can be better than the sublinear convergence rate O( σ2 µϵ ) of plain SGD, for strongly convex problems. The SVRG gradient estimator (2) is adopted in many algorithms (e.g., [Xiao and Zhang, 2014; Allen-Zhu and Yuan, 2015; Lei and Jordan, 2016; Allen-Zhu and Hazan, 2016; Reddi et al., 2016a; Reddi et al., 2016b; Lei et al., 2017; Li and Li, 2018; Zhou et al., 2018; Ge et al., 2019; Kovalev et al., 2020; Li and Li, 2022]) and also is used in our SIFAR.

The aforementioned variance-reduced methods are not accelerated and hence they do not achieve the optimal convergence rates for convex finite-sum problem (1). See the nonaccelerated variance-reduced algorithms listed in the first part of Table 1, i.e., SAG, SVRG, SAGA and SVRG ++ , they do not achieve the accelerated rates, i.e., Lµ vs. √ Lµ (strongly

convex case) and Lϵ vs. √ Lϵ (general convex case). Note

that we do not list the SCSG [Lei and Jordan, 2016] and SARAH [Nguyen et al., 2017] in Table 1 since SCSG requires an additional bounded variance assumption (without this assumption, its result is the same as SVRG and SAGA) and SARAH uses E[∥∇f (̂ x)∥2 ] ≤ ϵ as the convergence criterion which can not be directly converted to E[f(̂ x) - f(x∗ )] ≤ ϵ. SARAH is usually used for solving nonconvex problems where the convergence criterion is typically the norm of gradient (e.g., [Fang et al., 2018; Wang et al., 2018; Pham et al., 2019; Li, 2019; Li et al., 2021b; Li et al., 2021a]). Also both SCSG and SARAH are non-accelerated methods and thus do not achieve the optimal convergence results. Therefore, much recent research effort has been devoted to the design of accelerated gradient methods (e.g., [Nesterov, 2004; Beck and Teboulle, 2009; Lan, 2012; Allen-Zhu and Orecchia, 2014; Su et al., 2014; Lin et al., 2015; Allen-Zhu, 2017; Lan and Zhou, 2018; Lan et al., 2019; Li and Li, 2020; Li et al., 2020]). As shown in Table 1, for strongly convex finite-sum problems, existing accelerated methods such as RPDG [Lan and Zhou, 2015], Katyusha [Allen-Zhu, 2017], Varag [Lan et al., 2019] and our SIFAR are optimal since their convergence results are O((n + √ nL µ ) log 1ϵ ) matching the lower bound Ω((n + √ nL µ ) log 1ϵ ) given by [Lan and Zhou, 2015].

However, for general (non-strongly) convex finite-sum problems, all previous accelerated methods do not achieve the optimal convergence result. In particular, Varag [Lan et al., 2019] obtains the current best result O(nmin{log 1ϵ , log n}+ √ nL ϵ ), while the lower bound in this general convex case is Ω(n + √ nL ϵ ) provided by [Woodworth and Srebro, 2016]. More importantly, for large-scale problems where the number of data samples n is very large, or the convergence error ϵ is not very small, then the convergence result of Varag is O(n log 1ϵ ) which is not optimal since the lower bound is Ω(n) (see Table 2). Note that the case of large-scale problems or the case of moderate convergence error often exists in machine learning applications. We show that our SIFAR takes an important step towards the ultimate limit of accelerated methods and it is the first algorithm to achieve the optimal convergence rate O(n) in this case matching the lower bound Ω(n). See Tables 1 and 2 for more details.

2 Our Contributions

In this paper, we mainly focus on further improving the convergence result in order to close the gap between the upper and lower bound. We propose a novel loopless accelerated variance-reduced gradient method, called SIFAR (Algorithm 1), for solving both general convex and strongly convex finite-sum problems given in the form of (1). Tables 1 and 2 summarize the convergence results of previous algorithms and SIFAR.

Now, we highlight the following results achieved by SIFAR:

• For general convex problems, SIFAR obtains the rate O(nmin {1 + log 1 ϵ√n , log √n} + √ nL ϵ ) for finding an ϵ-approximate solution of problem (1), which improves previous best result O(nmin{log 1ϵ , logn} + √ nL ϵ ) given by Varag [Lan et al., 2019] (see the 'general convex' column of Table 1). Moreover, for a very wide range of ϵ, i.e., ϵ ∈ (0, L n log2 √n ]∪[ 1 √n , +∞), or the number of data samples n ∈ (0, L ϵ log2 √n ] ∪ [ 1 ϵ2 , +∞), SIFAR can exactly achieve the

Table 2: Direct accelerated stochastic algorithms for general convex setting with respect to ϵ

optimal convergence result O(n+ √ nL ϵ ) matching the lower

2016] (see Table 1 and its Footnote 2).

• In particular, we would like to point out that none of previous algorithms with/without acceleration can obtain the optimal result O(n) for finite-sum problems (1) where the number of data samples is very large or the convergence error is not very small, SIFAR is the first algorithm that achieves the optimal result O(n) for these typical machine learning problems (see the second column of Table 2 and its Remark).
• We also note that SIFAR is the first loopless direct accelerated stochastic algorithm for solving general convex finitesum problems, while previous accelerated stochastic algorithms use indirect approaches (RPDG, Catalyst, Katyusha) and/or use inconvenient double-loop algorithmic structures (Katyusha ns , Varag) (see Table 1). Moreover, by exploiting the loopless structure of SIFAR, we provide a novel dynamic multi-stage convergence analysis which is the key for improving previous results to the optimal rates.
• For strongly convex finite-sum problems (i.e., under strong convexity Assumption 2), we also prove that SIFAR achieves the optimal convergence rate O((n + √ nL µ ) log 1ϵ ) matching the lower bound Ω((n+ √ nL µ ) log 1ϵ ) provided by

[Lan and Zhou, 2015] (see Table 1).

• Moreover, the convergence guarantee of SIFAR is the last iterate convergence, i.e., guarantee for wT (see Corollaries 1 and 2) unlike previous average iterates convergence, i.e., guarantee for ¯wT = 1 T ∑T -1 t=0 qtwt for some distribution q.
• Finally, the numerical experiments show that SIFAR converges faster than the previous state-of-the-art Varag [Lan et al., 2019], validating our theoretical results and confirming the practical superiority of SIFAR.

3 Preliminaries

Notation: Let [n] denote the set {1, 2, · · · , n} and ∥·∥ denote the Euclidean norm for a vector and the spectral norm for a matrix. Let ⟨u, v⟩ denote the inner product of two vectors u and v. We use O(·) and Ω(·) to hide the absolute constant. We will write x∗ := argminx∈Rd f(x).

For convex problems, one typically uses the function value gap as the convergence criterion.

Definition 1. A point ̂ x is called an ϵ-approximate solution for problem (1) if E[f(̂ x) - f (x∗ )] ≤ ϵ.

To show the convergence results, we assume the following standard smoothness assumption for the component functions fis in (1).

Assumption 1 (L-smoothness). Functions fi : Rd → R are convex and L-smooth such that

for some L ≥ 0 and all i ∈ [n].

It is easy to see that f(x) = 1n ∑ni=1 fi(x) is also Lsmooth under Assumption 1.

Algorithm 1 SIFAR: SImple Faster Accelerated varianceReduced gradient

Input: initial point x0, parameters {pt}, {θt}, {ηt}, {αt}

• 1: w0 = ¯x0 = x0 = x0
• 2: for t = 0, 1, 2, . . . , T -1 do
• 3: xt = θtxt + (1 - θt)wt
• 4: Randomly pick i ∈ {1, 2, . . . , n}
• 5: ˜∇t =∇fi(xt ) -∇fi(wt) +∇f(wt)
• 6: xt+1 = 1 1+µηt (xt + µηtxt ) - ηt αt ˜∇t
• 7: ¯xt+1 = θtxt+1 + (1 - θt)wt
• 8: wt+1 = {¯xt+1 with probability pt wt with probability 1-pt

9: end for

Output: wT

For considering the strongly convex setting, we assume the following Assumption 2.

Assumption 2 (µ-strong convexity). A function f : Rd →R is µ-strongly convex such that

for some µ ≥ 0.

Note that the strong convexity is only corresponding to the average function f in (1), is not needed for the component functions fis.

4 SIFARAlgorithm

In this section, we describe the simple SIFAR method in Algorithm 1. SIFAR uses the SVRG gradient estimator (2) (see Line 5 of Algorithm 1) and two interpolation steps (momentum) (see Line 3 and Line 7 of Algorithm 1). Line 6 of Algorithm 1 is a gradient update step.

Although previous accelerated stochastic algorithms such as Katyusha/Katyusha ns [Allen-Zhu, 2017] and Varag [Lan et al., 2019] also adopt the SVRG gradient estimator combined with momentum steps, SIFAR enjoys a simpler loopless algorithmic structure. Note that the previous loopless SVRG/Katyusha algorithms provided in [Kovalev et al., 2020] only solve the strongly convex case (µ > 0). Here, our loopless algorithm SIFAR can deal with both general convex (µ = 0) and strongly convex (µ > 0) problems, and the SIFAR algorithm itself is also different and more concise than the loopless algorithms in [Kovalev et al., 2020]. Moreover, for general convex problems (µ = 0), SIFAR provides a new state-of-the-art convergence result which improves all previous results.

In each iteration t, the stochastic gradient estimator ˜∇t of SIFAR (Line 5 of Algorithm 1) uses the gradient information of only one randomly sampled function fi. Note that for the last term ∇f(wt), it reuses previous ∇f(wt-1) with probability 1 - pt-1 or needs to compute the full gradient ∇f(¯xt) with probability pt-1 (see Line 8 of Algorithm 1). Thus we know that SIFAR uses (n + 2)pt-1 + 2(1 - pt-1) stochastic gradients in expectation for iteration t. In particular, if pt ≡ 1n , then SIFAR only uses constant stochastic gradients for each iteration which maintains the same computational cost as SGD. The snapshot point wt is updated in the last Line 8 of Algorithm 1, it is a probabilistic step which is the key part for removing double-loop structures to obtain a simple loopless algorithm, similar to [Kovalev et al., 2020; Li et al., 2021a]. However, we propose a new dynamic multistage convergence analysis which uses a dynamic control of the probability {pt} in Line 8, unlike directly fixing it to a constant pt ≡ p as in [Kovalev et al., 2020]. To the best of our knowledge, this is the first time that a loopless algorithm uses a dynamic change of {pt}.

5 Convergence Results for SIFAR

In this section, we present two main convergence theorems of SIFAR (Algorithm 1) for solving finite-sum problems (1), i.e., Theorem 1 (general convex setting in Section 5.1) and Theorem 2 (strongly convex setting in Section 5.2). Subsequently, we formulate two Corollaries 1-2 from Theorems 12 for providing the detailed convergence results. The detailed proofs for Theorems 1-2 and Corollaries 1-2 are deferred to the appendix.

5.1 General convex setting

In this section, we provide the main convergence theorem of SIFAR for general convex problems and then obtain a corollary for providing the detailed convergence result. Note that if we fix the probability pt in Line 8 of Algorithm 1 to a constant p, then the update of wt follows from a geometric distribution Geom(p). For a geometric distribution N ∼ Geom(p), i.e., N = k with probability (1 - p)k p for k = 0, 1, 2, . . . (after k failures until the first success), we know that E[N] = 1-p p . In the first stage of SIFAR, we indeed use constant probability pt ≡ p = 1 n+1 . Let t1 be the first time such that w changes to ¯x, i.e., wt1+1 = ¯xt1+1 and wt1 = wt1-1 = · · · = w0. Thus t1 ∼ Geom(p) and E[t1] = n. Note that this first stage where we fix pt ≡ p is similar to loopless SVRG [Kovalev et al., 2020], SCSG [Lei and Jordan, 2016] and PAGE [Li et al., 2021a]. The difference is that our SIFAR will use a dynamic change of pt after the first stage, while previous algorithms always keep fixing the probability pt ≡ p.

Theorem 1 (General convex case). Suppose that Assumption 1 holds. For 0 ≤ t ≤ t1, let pt ≡ 1 n+1 , θt ≡ 1 - 1 2√n , ηt ≤ 1 L(1+1/(1-θt)) and αt = θt. For t > t1, let pt = max{ 4 t-t1+3√n , 4 n+3 }, θt = 2 pt(t-t1+3√n) , ηt ≤ 1 3L and αt = θt. Then the following equation holds for SIFAR (Algorithm 1) for any iteration t > t1 + 1:

According to Theorem 1, we can obtain a detailed convergence result in the following Corollary 1.

Corollary 1 (General convex case). Suppose that Assumption 1 holds. Choose the parameters {pt}, {θt}, {ηt}, {αt} as stated in Theorem 1. Then SIFAR (Algorithm 1) can find an ϵ-approximate solution for problem (1) such that

within T iterations, where

and the number of stochastic gradient computations can be bounded by

Remark: From the choice of probability {pt} in Theorem 1, we know that there are three stages of SIFAR: i) the first stage pt ≡ 1 n+1 for 0 ≤ t ≤ t1; ii) the second stage pt = 4 t-t1+3√n for t1 < t ≤ t1 +n+3-3√n; iii) the third stage pt ≡ 4 n+3 for t > t1 + n + 3 - 3√n. This novel multi-stage convergence analysis is key part for the improvement of SIFAR. Roughly speaking, the number of stochastic gradient computations in the first stage is #grad = O(n), in the second stage is #grad = O(nmin { log 1 ϵ√n , log √n}), and in the third stage is #grad = O(√ nL ϵ ). Note that the guarantee of SIFAR is the last iterate convergence unlike previous average iterates convergence. Also note that all parameter settings {pt}, {θt}, {ηt}, {αt} of SIFAR in Theorem 1 do not require the value of ϵ in advance. The convergence rate of SIFAR will automatically switch to different results as stated in Table 2.

5.2 Strongly convex setting

In this section, we provide the main convergence theorem of SIFAR for strongly convex problems (µ > 0 in Assumption 2) and then obtain a corollary for providing the detailed convergence result.

Theorem 2 (Strongly convex case). Suppose that Assumptions 1 and 2 hold. For any t ≥ 0, let pt ≡ p, θt ≡ θ = 1 2 min{1, √ µ pL }, ηt ≤ 1 Lθt(1+1/(1-θt)) and αt = 1 + µηt. Then the following equation holds for SIFAR (Algorithm 1) for any iteration t ≥ 0:

Similarly, according to Theorem 2, we can obtain a detailed convergence result in the following Corollary 2.

Corollary 2 (Strongly convex case). Suppose that Assumptions 1 and 2 hold. Choose the parameters {pt}, {θt}, {ηt}, {αt} as stated in Theorem 2. Then SIFAR (Algorithm 1) can find an ϵ-approximate solution for problem (1) such that

within T iterations, where

Moreover, by choosing p = 1n and recalling that θ = 12 min{1, √ µ pL }, the number of stochastic gradient computations can be bounded by

Remark: In this strongly convex case, the parameter setting of SIFAR in Theorem 2 is simpler than the general convex case in Theorem 1. Here, the choice of probability {pt} can be fixed to a constant p and {θt} also can be chosen as a constant θ. Then according to Theorem 2, we know that {ηt} and {αt} also reduce to constant values. Thus there is only one stage in this strongly convex case rather than three stages in previous general convex case. Also here the function value decreases in an exponential rate, i.e., E[Φt] ≤ (1 - 4pθ 5 )tΦ0 (see (5) in Theorem 2). It is easy to see that the number of iterations T can be bounded by O(· log 1ϵ ) for finding an ϵ-approximate solution E[f(wT ) - f(x∗ )] ≤ ϵ. Then, by choosing p = 1n (thus each iteration only computes constant stochastic gradients in expectation), the number of total stochastic gradient computations can be bounded by #grad = O( max {n, √ nL µ } log 1ϵ ). This convergence result is optimal which matches the lower bound Ω((n + √ nL µ ) log 1ϵ ) given by [Lan and Zhou, 2015] (see Table 1). Note that all parameter settings {pt}, {θt}, {ηt}, {αt} of SIFAR in Theorem 2 also do not require the value of ϵ in advance.

5.3 Proof sketch for general convex case (Theorem 1)

Now, we provide the proof sketch of Theorem 1. As we discussed in the Remark at the end of Section 5.1, we know that there are three stages of SIFAR. First, we provide a key lemma for the first stage.

Lemma 1. Suppose Assumption 1 holds. For 0 ≤ t ≤ t1, let pt ≡ p, θt ≡ θ, ηt ≤ 1 L(1+1/(1-θt)) and αt = θt. Then the following equation holds for SIFAR (Algorithm 1):

E[f (wt1+1) - f (x∗ )]

According to the update formula of wt in the Line 8 of Algorithm 1, we know that E[t1] = 1-p p . Thus if we let pt ≡ p = 1 n+1 in the first stage of SIFAR (i.e., for 0 ≤ t ≤ t1), then E[t1] = n. The choice of parameters in Lemma 1 with p = 1 n+1 is the same as the first stage of Theorem 1.

After the first stage, for any iteration t > t1, we provide the following technical lemma which describes the change of function value between two adjacent iterations.

Lemma 2. Suppose Assumption 1 holds. Choose stepsize ηt ≤ 1 L(1+1/(1-θt)) and αt = θt for any t ≥ 0. Then the following equation holds for SIFAR (Algorithm 1) for any iteration t ≥ 0:

According to (7), in order to get a recursion formula, we need to show that(1 - ptθt)ηt

by further choosing appropriate parameters {pt} and {θt}. In particular, choosing pt = max{ 4 t-t1+3√n , 4 n+3 } and θt = 2 pt(t-t1+3√n) for t > t1 (same as in Theorem 1) can satisfy (8) for any t > t1 + 1. Combining this choice of {pt} and {θt} with Lemma 2 and summing up from iteration t1 + 1 to t, we obtain the following Lemma 3.

Lemma 3. Suppose Assumption 1 holds. For t > t1, let pt = max{ 4 t-t1+3√n , 4 n+3 }, θt = 2 pt(t-t1+3√n) , ηt ≤ 1 3L and αt = θt. Then the following equation holds for SIFAR (Algorithm 1) for any iteration t > t1 + 1:

Also note that we can bound the term f(x0) - f(x∗ ) in (6) as f(x0) - f(x∗ ) ≤ L2 ∥x0 - x ∗ ∥2 according to the L-smoothness of f (Assumption 1). Now, we combine Lemma 1 and Lemma 3 to finish the proof for the main Theorem 1, i.e., by plugging (6) into (9) and plugging in the value of parameters, we can obtain, for any iteration t > t1 + 1,

6 Experiments

In this section, we present the numerical experiments of SIFAR (Algorithm 1) compared with previous state-of-the-art Varag [Lan et al., 2019]. We also present the standard gradient descent (GD) as a benchmark for demonstrating the performance of these algorithms. The theoretical convergence results of these algorithms can be found in Table 1.

In the experiments, we consider the following logistic regression problem:

where {ai, bi}ni=1 ∈ Rd × {±1} are data samples. All datasets used in our experiments are downloaded from LIBSVM [Chang and Lin, 2011]. We also point out that we directly use the parameter settings according to the theoretical convergence theorems or corollaries of these algorithms, i.e., we do not tune any hyperparameters. Note that for the logistic function in (10), one can precompute the smoothness parameter L satisfying Assumption 1, i.e., L ≤ 1/4 if the data samples are normalized. Given the parameter L, we are ready to set all other hyperparameters for GD (see Corollary 2.1.2 in [Nesterov, 2004]), for Varag (see Theorem 1 in [Lan et al., 2019]) and for SIFAR (see our Theorem 1). Note that all of these three algorithms only require L for setting their (hyper)parameters.

In Figure 1, the x-axis and y-axis represent the number of data passes (i.e., we compute n stochastic gradients for each data pass) and the training loss, respectively. The numerical results presented in Figure 1 are conducted on different datasets. Each plot corresponds to one dataset (six datasets in total). The experimental results show that SIFAR indeed converges faster than Varag [Lan et al., 2019] in the earlier stage (moderate convergence error), validating our theoretical results (see the second column of Table 2 and its Remark). More importantly, SIFAR is the first accelerated algorithm which can obtain the optimal convergence result O(n) in this range. Besides, SIFAR also enjoys a simpler loopless algorithmic structure while Varag uses an double-loop structure.

7 Conclusion

In this paper, we propose a faster loopless accelerated variance-reduced gradient method SIFAR, for solving both general convex and strongly convex finite-sum problems. The proposed SIFAR takes an important step towards the ultimate limit of accelerated methods to close the gap between the upper and lower bound. In particular, SIFAR achieves the first optimal convergence rate O(n) matching the lower bound Ω(n) for large-scale general convex problems. Besides, it also achieves the optimal convergence rate O((n + √ nL µ ) log 1ϵ ) matching the lower bound Ω((n + √ nL µ ) log 1ϵ ) for strongly convex problems. Moreover, we provide a novel dynamic multi-stage convergence analysis utilizing the simpler loopless algorithmic structure, which is the key for improving previous results to the optimal rates. Numerical experiments validate our theoretical results and confirm the practical superiority of SIFAR. Our new theoretical rates and convergence analysis can also lead to key improvements for other related distributed and federated optimization problems, e.g., [Li and Richt´arik, 2020; Li and Richt´arik, 2021; Zhao et al., 2021; Zhao et al., 2024; Bao et al., 2025].

Acknowledgments

This research was supported by the Singapore Ministry of Education (MOE) Academic Research Fund (AcRF) Tier 1 grant.