Convergence Analysis of STORM Under Different Geometries
STORM is a single-sample stochastic recursive momentum method that avoids periodic full-gradient checkpoints. Prior analyses required a stronger average smoothness assumption and produced suboptimal or logarithmically degraded rates. This paper shows that the original STORM recursion alone achieves the optimal $O(T^{-1/4})$ nonconvex rate, $O(\sigma R/\sqrt{T})$ convex rate, and $O(\sigma^2/(\lambda T))$ strongly convex rate under standard smoothness, by introducing auxiliary sequences and shifted iterates to cancel the estimator bias.
The paper makes a clean and valuable theoretical advance. It removes the average smoothness assumption that pervaded prior STORM analyses, and sharpens earlier rates under average smoothness by eliminating logarithmic factors and large initial batches. The analysis is conceptually elegant---the shifted iterate $z_t$ and the auxiliary gradient sequence $y_t$ cleanly isolate the inherited bias of the momentum estimator. However, the work is purely theoretical: the experiments are stylized, low-dimensional tests, and several optimal schedules (geometric blocks, two-phase stepsizes) require exact prior knowledge of $T$ and problem constants, limiting practical deployment.
The strongest contribution is the nonconvex analysis without average smoothness. By shifting the iterate as $z_t = x_t - \eta \beta e_{t-1}/(1-\beta)$, the authors remove the conditional bias from the recursion: $z_{t+1} = z_t - \eta \nabla F(x_t) - \frac{\eta}{1-\beta}\nu_t$. Standard smoothness then controls $\|\nabla F(x_t) - \nabla F(z_t)\|$ without ever bounding a difference of sampled gradients by the distance between query points. The convex and strongly convex bounds via the auxiliary sequence $y_t$ are similarly transparent and yield optimal last-iterate guarantees.
The main limitation is practical relevance. The stepsize schedules that deliver last-iterate optimality rely on rounded geometric blocks or two-phase decays that are delicate to implement without knowing the time horizon $T$ and constants such as $L$, $\sigma$, $R$, or $\lambda$. The paper offers no guidance for tuning these in practice, nor does it demonstrate the schedules on realistic models. In addition, the experimental section explicitly limits itself to synthetic objectives, stating that it isolates theoretical questions rather than repeating broad benchmarks. While defensible for a theory paper, this means the empirical evidence for the practical value of removing average smoothness is thin.
The comparisons to prior work are careful and accurate. The authors correctly note that Cutkosky and Orabona (2019) retained a logarithmic factor in the nonadaptive guarantee: 'In particular, its guarantee is $O(\log(T)T^{-2/3})$ in expected squared gradient norm, hence $O(\sqrt{\log(T)}T^{-1/3})$ in expected norm.' They also note that Jiang et al. (2024) avoids extra assumptions but uses a large initial batch, and that prior convex analyses require bounded domains or samplewise smoothness. The optimality claims are backed by appropriate lower-bound citations: Arjevani et al. (2023) for nonconvex standard smoothness and Agarwal et al. (2012) for convex and strongly convex settings.
All proofs are provided in full in the appendices, which aids theoretical reproducibility. However, no code, data, or implementation is released. The hyperparameters are analytically derived but depend on $T$, $L$, $\sigma^2$, $\Delta_0$, $R$, $\mu$, and $\lambda$; several schedules, such as the geometric block partition in (25) and the two-phase PL schedule in (13), require exact knowledge of the horizon and problem constants. This would block a direct reproduction on new problems unless the user reverse-engineers the constants, and the absence of code makes it impossible to verify the empirical curves independently.
Stochastic recursive momentum (STORM) achieves fast convergence for nonconvex optimization via the variance reduction effect, but existing analyses rely on the strong average smoothness assumption. In this paper, we study the convergence of STORM for different objectives without average smoothness. We first revisit the results under average smoothness, obtaining the $O(T^{-1/3})$ bound for nonconvex objectives and the $O(\sigma^2/(\mu T))$ bound for last-iterate output under the $\mu$-Polyak--\L{}ojasiewicz~(PL) condition. Without average smoothness, we design an auxiliary sequence and compare the STORM update with it in the analysis. With the help of this sequence, we prove that STORM still attains an $O(T^{-1/4})$ rate for nonconvex objectives, which is optimal under standard smoothness. For convex and $\lambda$-strongly convex objectives, we further prove averaged and last-iterate bounds with optimal rates of $O(\sigma R/\sqrt T)$ and $O(\sigma^2/(\lambda T))$, respectively. All the obtained results use the same STORM recursion with different hyperparameter choices.
Pick a starting point or write your own. Challenges run in the background, so you can keep reading while the AI investigates.
No challenges yet. Disagree with the review? Ask the AI to revisit a specific claim.