シャッフルの学習：確率的最適化のためのブロック再配置およびリバーサル・スキーム

概要: 確率的勾配降下法（SGD）に対するシャッフル戦略、すなわち、インクリメンタル勾配、シャッフル・ワンス（shuffle-once）、ランダム・リシフリング（random reshuffling）は、任意のエポック内置換に対して厳密な収束解析によって裏づけられています。特に、ランダム・リシフリングは、巡回（cyclic）およびシャッフル・ワンス方式に比べて最適化定数を改善することが知られています。しかし、既存の理論では、ランダム・リシフリングを超えてさらに最適化定数や安定性を改善する新しいデータ順序付け（データ・オーダリング）方式をどのように設計すべきかについての指針が限られています。本論文では、置換なしSGD（without-replacement SGD）に対して有効なシャッフル規則を見出すために、大規模言語モデル（LLM）に導かれたプログラム進化（program evolution）フレームワークを用いたパイプラインを設計します。この個別の事例から抽象化すると、私たちは2つの基本的な構造要素、すなわち、ブロック・リシフリング（block reshuffling）と、ペア逆転（paired reversal）を同定します。これらの構成要素をそれぞれ解析し、統一されたシャッフルの枠組みのもとで、ブロック・リシフリングが接頭部勾配（prefix-gradient）分散の定数を厳密に減少させることを示し、軽微な条件のもとでランダム・リシフリングに対する確実な改善をもたらすことを証明します。別途、ペア逆転がエポック写像（epoch map）を対称化し、主要なオーダー依存の2次項を打ち消すことで、ステップサイズに対するオーダー感度を二次から三次へと低減することを示します。発見されたアルゴリズムによる数値実験は理論を検証し、凸および非凸のベンチマークにおいて、標準的なシャッフル方式に比べて一貫した利得が得られることを示します。