論文の概要: Centered Permutation Prefixes for SGD with Random Reshuffling: Sharp Rates, Hölder Geometry, and Composite Proximal Extensions
- arxiv url: http://arxiv.org/abs/2609.04578v1
- Date: Fri, 04 Sep 2026 00:17:04 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-09-07 18:15:23.867011
- Title: Centered Permutation Prefixes for SGD with Random Reshuffling: Sharp Rates, Hölder Geometry, and Composite Proximal Extensions
- Title（参考訳）: ランダムリシャッフルによるSGDの集中的置換前フィックス:シャープレート、ヘルダー幾何、および複合近近拡張
- Abstract要約: 最後のエポックな [ mathbb Ey_K-xdagger|2 ] =widetilde O!left(T-2+n2T), qquadright T=nK$ を証明する。
また, 有限和 [F(x)=frac1nsum_i=1n f_i(x) に対して, ランダムリシャッフルによる二次数勾配勾配の解析を行った。
- 参考スコア（独自算出の注目度）: 3.099125946219227
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study stochastic gradient descent with random reshuffling for finite sums \[ F(x)=\frac1n\sum_{i=1}^n f_i(x). \] For fresh reshuffling with a constant component stepsize, if each $f_i$ has an $L$-Lipschitz gradient and the average $F$ is $μ$-strongly convex with a Lipschitz-continuous Hessian, we prove the last-epoch rate \[ \mathbb E[F(y_K)-F(x_\star)] =\widetilde O\!\left(T^{-2}+n^2T^{-3}\right), \qquad T=nK, \] matching the known quadratic lower bound in its $(n,K)$-dependence. The components may be nonconvex, and no componentwise Hessian continuity or separate bounded-iterate assumption is required. More generally, a $ν$-Hölder-continuous average Hessian adds only $\widetilde O(n^{1+ν}T^{-2-2ν})$, so every $ν\ge 1/2$ preserves the quadratic rate. Under convex components, a decreasing-stepsize result removes the large-epoch requirement and recovers the same two-term scale once $nK$ exceeds the condition-number scale. We also analyze epoch-wise ProxRR for $\mathcal P=F+ψ$. Writing $x^\dagger$ for the composite minimizer and $β_\star=\|\nabla F(x^\dagger)\|$, we prove \[ \mathbb E\|y_K-x^\dagger\|^2 =\widetilde O\!\left( \frac{β_\star^2}{K^2} +T^{-2}+n^2T^{-3} +n^{1+ν}T^{-2-2ν} \right). \] For $ν\ge 1/2$, we show that the $β_\star^2/K^2$ splitting term is unavoidable and obtain a matching lower bound up to logarithms in the stated constant-stepsize regime.
- Abstract（参考訳）: 有限和 \[F(x)=\frac1n\sum_{i=1}^n f_i(x) に対するランダム再シャッフルによる確率勾配降下について検討する。
f_i$ が $L$-Lipschitz 勾配を持ち、平均$F$ が $μ$-strongly convex with a Lipschitz-continuous Hessian であるなら、最後のエポックレート \[ \mathbb E[F(y_K)-F(x_\star)] =\widetilde O\!
\left(T^{-2}+n^2T^{-3}\right), \qquad T=nK, \] は、既知の二次下界を$(n,K)$-dependenceで一致する。
成分は非凸であり、成分的にヘッセン連続性や別の有界イテレート仮定は不要である。
より一般に、$ν$-Hölder-連続平均 Hessian は$\widetilde O(n^{1+ν}T^{-2-2ν})$のみを加算するので、すべての $ν\ge 1/2$ は二次数率を保存する。
凸成分の下では、ステップサイズが小さくなると大きなエポックな要求が取り除かれ、nK$が条件数を超えると同じ2項のスケールが回復する。
また, epoch-wise ProxRR を $\mathcal P=F+\$ に対して解析する。
合成最小値に対して$x^\dagger$と$β_\star=\|\nabla F(x^\dagger)\|$を書くと、 \[ \mathbb E\|y_K-x^\dagger\|^2 =\widetilde O\!
\left( \frac{β_\star^2}{K^2} +T^{-2}+n^2T^{-3} +n^{1+ν}T^{-2ν} \right)。
\]$ν\ge 1/2$ に対して、$β_\star^2/K^2$ 分裂項は避けられないことを示し、従って定段制における対数に一致する下界を得る。
関連論文リスト
- Sharp Minimax Regret for Infinite-Memory Logistic Prediction [55.29259818039367]
Lag $j$はスケール$r_j$の予測に影響を与え、$n_T,j=T-j+1$の予測ラウンドに入る。
すべての要約可能なエンベロープに対して、局所化された混合は$cR_T(r)leq C_T(r)$を証明する。
指数関数やエンベロープの場合、有限サンプル条件の下では、トープリッツ・デサインの逆は$cR_T(r)geq c_T(r)$である。
論文 参考訳（メタデータ） (2026-08-27T01:31:46Z) - Solving Stochastic Fixed-Point Equations with High Probability [22.376855234542813]
オラクルの不動点方程式 $mathbfT(mathbfx) = mathbfx$ をノルム空間上で研究する。
本稿では,2次スムーズなバナッハ空間に対する分散還元段階Halpern法であるVR-GHALを紹介する。
論文 参考訳（メタデータ） (2026-07-10T04:59:20Z) - Rényi exponent landscape of multipartite entanglement in free-fermion systems [51.56484100374058]
我々は、Rényi tripartite information $I_3() が小フェルミ運動量での質的に $exclusion-dependent scaling を示すことを示した。
I_m(n)/I_m(1) sim zm-1 to 0$ for all integer $n geq 2$, so the leading von Neumann signal can builded from integer Rényi data。
論文 参考訳（メタデータ） (2026-03-09T22:27:00Z) - Convergence Rate for the Last Iterate of Stochastic Gradient Descent Schemes [0.0]
Fdelta が凸であるときに SHB が$F_*$ で一定運動量に達することを証明した。
また、Fdelta が凸であるときに SHB が$F_*$ の運動量を得ることを示す。
論文 参考訳（メタデータ） (2025-07-09T20:59:23Z) - Sharp Gap-Dependent Variance-Aware Regret Bounds for Tabular MDPs [54.28273395444243]
我々は,モノトニック値 Omega (MVP) アルゴリズムが,差分を考慮した差分依存残差境界を$tildeOleft(left(sum_Delta_h(s,a)>0 fracH2 log K land MathttVar_maxtextc$。
論文 参考訳（メタデータ） (2025-06-06T20:33:57Z) - Non-Convex Tensor Recovery from Local Measurements [22.688595434116777]
本論文は, テンソル全体の検知が不可能な設定により, テンソル圧縮センシングモデルを提案する。
ScaleAlt-PGD-Alt-DMinが$mathcal O(log frac1epsilon)$を達成し、サンプルを$mathcal Oleftに改善することを証明する。
論文 参考訳（メタデータ） (2024-12-23T05:04:56Z) - Efficient Continual Finite-Sum Minimization [52.5238287567572]
連続有限サム最小化(continuous finite-sum minimization)と呼ばれる有限サム最小化の鍵となるツイストを提案する。
我々のアプローチは$mathcalO(n/epsilon)$ FOs that $mathrmStochasticGradientDescent$で大幅に改善されます。
また、$mathcalOleft(n/epsilonalpharight)$ complexity gradient for $alpha 1/4$という自然な一階法は存在しないことを証明し、この方法の第一階法がほぼ密であることを示す。
論文 参考訳（メタデータ） (2024-06-07T08:26:31Z) - On the $O(\frac{\sqrt{d}}{T^{1/4}})$ Convergence Rate of RMSProp and Its Momentum Extension Measured by $\ell_1$ Norm [54.28350823319057]
本稿では、RMSPropとその運動量拡張を考察し、$frac1Tsum_k=1Tの収束速度を確立する。
我々の収束率は、次元$d$を除くすべての係数に関して下界と一致する。
収束率は$frac1Tsum_k=1Tと類似していると考えられる。
論文 参考訳（メタデータ） (2024-02-01T07:21:32Z) - Low-degree learning and the metric entropy of polynomials [44.99833362998488]
少なくとも$Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon)は2辺の推定値$c(1-varepsilon)2dlogを満たす。
論文 参考訳（メタデータ） (2022-03-17T23:52:08Z) - On the Self-Penalization Phenomenon in Feature Selection [69.16452769334367]
カーネル群に基づく暗黙の空間性誘導機構について述べる。
アプリケーションとしては、この疎結合誘導機構を使用して、特徴選択に一貫性のあるアルゴリズムを構築します。
論文 参考訳（メタデータ） (2021-10-12T09:36:41Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。