The Stochastic Gradient Descent method (SGD) and its stochastic variants have
become methods of choice for solving finite-sum optimization problems arising
from machine learning and data science thanks to their ability to handle
large-scale applications and big datasets. In the last decades, researchers
have made substantial effort to study the theoretical performance of SGD and
its shuffling variants. However, only limited work has investigated its
shuffling momentum variants, including shuffling heavy-ball momentum schemes
for non-convex problems and Nesterov's momentum for convex settings. In this
work, we extend the analysis of the shuffling momentum gradient method
developed in [Tran et al (2021)] to both finite-sum convex and strongly convex
optimization problems. We provide the first analysis of shuffling
momentum-based methods for the strongly convex setting, attaining a convergence
rate of $O(1/nT^2)$, where $n$ is the number of samples and $T$ is the number
of training epochs. Our analysis is a state-of-the-art, matching the best rates
of existing shuffling stochastic gradient algorithms in the literature.

本文通过对分类的动量渐变法的分析，对有限和强凸优化问题进行了研究，并取得了与现有文献中最好成绩相匹配的结果。

用于凸优化的 Shuffling Momentum Gradient 算法

Shuffling Momentum Gradient Algorithm for Convex Optimization

In this paper, we study the lower complexity bounds for finite-sum
optimization problems, where the objective is the average of $n$ individual
component functions. We consider Proximal Incremental First-order (PIFO)
algorithms which have access to the gradient and proximal oracles for each
component function. To incorporate loopless methods, we also allow PIFO
algorithms to obtain the full gradient infrequently. We develop a novel
approach to constructing the hard instances, which partitions the tridiagonal
matrix of classical examples into $n$ groups. This construction is friendly to
the analysis of PIFO algorithms. Based on this construction, we establish the
lower complexity bounds for finite-sum minimax optimization problems when the
objective is convex-concave or nonconvex-strongly-concave and the class of
component functions is $L$-average smooth. Most of these bounds are nearly
matched by existing upper bounds up to log factors. We can also derive similar
lower bounds for finite-sum minimization problems as previous work under both
smoothness and average smoothness assumptions. Our lower bounds imply that
proximal oracles for smooth functions are not much more powerful than gradient
oracles.

本文研究了有限和优化问题的下限复杂度界限，并基于分组的新方法构造了硬实例，从而建立了有限和最大最小优化问题的下限复杂度界限。

有限和优化问题的下限复杂度：结果与构造

Lower Complexity Bounds of Finite-Sum Optimization Problems: The Results  and Construction

In this paper, we propose a unified convergence analysis for a class of
generic shuffling-type gradient methods for solving finite-sum optimization
problems. Our analysis works with any sampling without replacement strategy and
covers many known variants such as randomized reshuffling, deterministic or
randomized single permutation, and cyclic and incremental gradient schemes. We
focus on two different settings: strongly convex and nonconvex problems, but
also discuss the non-strongly convex case. Our main contribution consists of
new non-asymptotic and asymptotic convergence rates for a wide class of
shuffling-type gradient methods in both nonconvex and convex settings. We also
study uniformly randomized shuffling variants with different learning rates and
model assumptions. While our rate in the nonconvex case is new and
significantly improved over existing works under standard assumptions, the rate
on the strongly convex one matches the existing best-known rates prior to this
paper up to a constant factor without imposing a bounded gradient condition.
Finally, we empirically illustrate our theoretical results via two numerical
examples: nonconvex logistic regression and neural network training examples.
As byproducts, our results suggest some appropriate choices for diminishing
learning rates in certain shuffling variants.

本文提出了一种适用于解决有限和优化问题的通用洗牌型梯度方法的统一收敛分析，涵盖了许多已知的变体，并在非凸和凸设置中提出了新的非渐近和渐近收敛速度。

一种针对洗牌式梯度方法的统一收敛分析

A Unified Convergence Analysis for Shuffling-Type Gradient Methods

Large-scale nonconvex optimization problems are ubiquitous in modern machine
learning, and among practitioners interested in solving them, Stochastic
Gradient Descent (SGD) reigns supreme. We revisit the analysis of SGD in the
nonconvex setting and propose a new variant of the recently introduced expected
smoothness assumption which governs the behaviour of the second moment of the
stochastic gradient. We show that our assumption is both more general and more
reasonable than assumptions made in all prior work. Moreover, our results yield
the optimal $\mathcal{O}(\varepsilon^{-4})$ rate for finding a stationary point
of nonconvex smooth functions, and recover the optimal
$\mathcal{O}(\varepsilon^{-1})$ rate for finding a global solution if the
Polyak-{\L}ojasiewicz condition is satisfied. We compare against convergence
rates under convexity and prove a theorem on the convergence of SGD under
Quadratic Functional Growth and convexity, which might be of independent
interest. Moreover, we perform our analysis in a framework which allows for a
detailed study of the effects of a wide array of sampling strategies and
minibatch sizes for finite-sum optimization problems. We corroborate our
theoretical results with experiments on real and synthetic data.

本篇论文使用类似于期望光滑性假设的新方法来研究随机梯度下降法在非凸优化中的收敛率，并在考虑多种采样策略和小批量大小的情况下，探讨有限和优化问题的影响。