---
title: "随机洗牌算法在凸优化中彻底击败随机梯度下降，理论误区终被破解"
source: "arXiv AI/CL/LG（论文）"
source_tier: "t2"
url: "https://arxiv.org/abs/2606.32005v1"
permalink: "https://feed.astralor.com/items/itm_a465d0213665d997ab2ea34c"
published: "2026-06-30T17:38:22.000Z"
score: 57
channel: "ai"
tags: ["凸优化","理论证明","随机梯度下降","随机洗牌SGD"]
---

# 随机洗牌算法在凸优化中彻底击败随机梯度下降，理论误区终被破解

## 速览

一篇来自arXiv的论文首次证明：在光滑凸优化中，使用随机洗牌的随机梯度下降算法（Shuffling SGD）在任意合理步长和任意有限轮次后，性能均严格优于传统随机梯度下降（SGD）。此前理论认为RR只能在极小的步长下收敛，且收敛速率在轮次较少时弱于SGD，严重偏离实际。本研究彻底消除了这一矛盾，为RR的广泛成功提供了坚实理论依据。

## 关键点

- 传统SGD理论假设数据随机采样，实际中常用随机洗牌（RR）顺序遍历，但RR长期缺乏理论证明。
- 此前理论要求步长≤1/n才能保证RR收敛，且当训练轮数<n时，RR的收敛率反而比SGD差。
- 本研究突破了这些限制，证明RR在任意合理步长和任意轮数下均优于SGD，且收敛速度更快。

## 全文

Stochastic Gradient Descent ($\textsf{SGD}$) is one of the most classical optimization algorithms with favorable theoretical guarantees, yet the practical implementation of $\textsf{SGD}$ differs subtly from its well-known form and is often referred to as Shuffling Stochastic Gradient Descent ($\textsf{Shuffling SGD}$). A particularly popular strategy in $\textsf{Shuffling SGD}$ is Random Reshuffling ($\textsf{RR}$), which has achieved great empirical success across numerous experiments. Despite its strong performance, $\textsf{RR}$ has long been considered a heuristic due to a lack of theoretical support. Over the last decade, people have finally established provable convergence rates for $\textsf{RR}$, thus justifying its observed superiority. However, for smooth convex optimization, two clouds over the convergence theory of $\textsf{RR}$ remain to this day. More precisely, according to the current theory, $\textsf{Shuffling SGD}$ under $\textsf{RR}$ converges only when the stepsize is smaller than a threshold proportional to $1/n$, where $n$ is the number of summands in the objective (or the number of data points). Consequently, the optimally tuned theoretical rate of $\textsf{Shuffling SGD}$ under $\textsf{RR}$ is strictly worse than that of $\textsf{SGD}$ when the number of epochs is smaller than another threshold proportional to $n$. These two restrictions heavily limit the applicability of existing theories and leave a critical mismatch with practice. In this work, for the first time, we prove that $\textsf{RR}$ dominates $\textsf{SGD}$ in smooth convex optimization under any reasonable stepsize after any finite number of epochs, thereby addressing a longstanding open question.

---

引用前请核对原文;本文由星际流动整理:https://feed.astralor.com/items/itm_a465d0213665d997ab2ea34c