論文の概要: A New Random Reshuffling Method for Nonsmooth Nonconvex Finite-sum
Optimization
- arxiv url: http://arxiv.org/abs/2312.01047v1
- Date: Sat, 2 Dec 2023 07:12:00 GMT
- ステータス: 処理完了
- システム内更新日: 2023-12-05 19:28:18.256891
- Title: A New Random Reshuffling Method for Nonsmooth Nonconvex Finite-sum
Optimization
- Title(参考訳): 非滑らかな有限和最適化のための新しいランダムリシャッフル法
- Authors: Xiao Li, Andre Milzarek, Junwen Qiu
- Abstract要約: そこで本研究では,正規写像を用いたリシャッフル法(ノルム点収束法)と呼ばれる新しい最適化アルゴリズムを提案する。
本稿では,提案手法を実証する機械学習の問題点について述べる。
- 参考スコア(独自算出の注目度): 7.096368428610449
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In this work, we propose and study a novel stochastic optimization algorithm,
termed the normal map-based proximal random reshuffling (norm-PRR) method, for
nonsmooth nonconvex finite-sum problems. Random reshuffling techniques are
prevalent and widely utilized in large-scale applications, e.g., in the
training of neural networks. While the convergence behavior and advantageous
acceleration effects of random reshuffling methods are fairly well understood
in the smooth setting, much less seems to be known in the nonsmooth case and
only few proximal-type random reshuffling approaches with provable guarantees
exist.
We establish the iteration complexity ${\cal O}(n^{-1/3}T^{-2/3})$ for
norm-PRR, where $n$ is the number of component functions and $T$ counts the
total number of iteration. We also provide novel asymptotic convergence results
for norm-PRR. Specifically, under the Kurdyka-{\L}ojasiewicz (KL) inequality,
we establish strong limit-point convergence, i.e., the iterates generated by
norm-PRR converge to a single stationary point. Moreover, we derive last
iterate convergence rates of the form ${\cal O}(k^{-p})$; here, $p \in [0, 1]$
depends on the KL exponent $\theta \in [0,1)$ and step size dynamics. Finally,
we present preliminary numerical results on machine learning problems that
demonstrate the efficiency of the proposed method.
- Abstract(参考訳): 本研究では,非滑らかな有限サム問題に対して,正規写像に基づく近位ランダムリシャッフル法(norm-PRR)と呼ばれる新しい確率最適化アルゴリズムを提案する。
ランダムなリシャッフル技術は、ニューラルネットワークのトレーニングなど、大規模アプリケーションで広く利用されている。
ランダムリシャッフル法の収束挙動と有利な加速効果は、滑らかな設定ではよく理解されているが、非スムースの場合ではあまり知られておらず、証明可能な保証を持つ近位型ランダムリシャッフルアプローチはほとんど存在しない。
ノルムPRRに対して反復複雑性を${\cal O}(n^{-1/3}T^{-2/3})$とすると、$n$は成分関数の数であり、$T$は反復の総数である。
また,ノルムPRRに対する新しい漸近収束結果も提供する。
具体的には、Kurtyka-{\L}ojasiewicz (KL)の不等式の下では、強い極限点収束、すなわちノルムPRRによって生成されるイテレートが単一の定常点に収束する。
さらに、最後の反復収束率は${\cal o}(k^{-p})$; ここで、$p \in [0, 1]$ は kl exponent $\theta \in [0,1)$ と step size dynamics に依存する。
最後に,提案手法の有効性を示す機械学習問題に対する予備的な数値結果を示す。
関連論文リスト
- Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳(メタデータ) (2024-02-14T07:52:00Z) - High Probability Guarantees for Random Reshuffling [5.663909018247509]
非行列最適化問題に対処するために、ランダムリシャッフル(mathsfRR$)の勾配法を検討する。
本研究ではまず,$mathsfRR$sサンプリング手順におけるニューラルネットワークの複雑さについて検討する。
そこで我々は,乱数化摂動手順の定常点を含むランダムリシャッフル法(mathsfp$mathsfRR$)を設計する。
論文 参考訳(メタデータ) (2023-11-20T15:17:20Z) - Distributed Random Reshuffling Methods with Improved Convergence [4.497769836711378]
本稿では,GT-RR(Gdient Tracking with Random Reshuffling)とED-RR(Exact Diffusion with Random Reshuffling)の2つの分散ランダムリシャッフル手法を提案する。
論文 参考訳(メタデータ) (2023-06-21T06:05:34Z) - Stochastic Inexact Augmented Lagrangian Method for Nonconvex Expectation
Constrained Optimization [88.0031283949404]
多くの実世界の問題は複雑な非機能的制約を持ち、多くのデータポイントを使用する。
提案手法は,従来最もよく知られた結果で既存手法よりも優れた性能を示す。
論文 参考訳(メタデータ) (2022-12-19T14:48:54Z) - Statistical Inference of Constrained Stochastic Optimization via
Sketched Sequential Quadratic Programming [59.36379287247961]
この問題を解決するために,完全オンライン逐次2次プログラミング(StoSQP)手法を開発した。
最近の数値二階法の設計により、StoSQPは任意のランダムなステップサイズを適応的に選択できる。
また,2次法の計算コストを大幅に削減するため,StoSQPはランダム化反復解法を用いて2次プログラムを不正確に解けるようにした。
論文 参考訳(メタデータ) (2022-05-27T00:34:03Z) - Hessian Averaging in Stochastic Newton Methods Achieves Superlinear
Convergence [69.65563161962245]
ニュートン法を用いて,滑らかで強凸な目的関数を考える。
最適段階において局所収束に遷移する普遍重み付き平均化スキームが存在することを示す。
論文 参考訳(メタデータ) (2022-04-20T07:14:21Z) - Optimal and instance-dependent guarantees for Markovian linear
stochastic approximation [77.84027086542827]
標準スキームの最後の繰り返しの2乗誤差に対して、$t_mathrmmix tfracdn$の非漸近境界を示す。
マルコフ雑音による政策評価について,これらの結果のまとめを導出する。
論文 参考訳(メタデータ) (2021-12-23T18:47:50Z) - Convergence of Random Reshuffling Under The Kurdyka-{\L}ojasiewicz
Inequality [3.960041987749073]
我々はクルディカ・ロジャシエヴィチ(KL)の不等式に基づくステップサイズを小さくした非輝化RRの収束解析を行う。
我々は、KL指数と好適に選択された減少ステップサイズに応じて、対応する収束率を導出する。
また、近位点法に対して同様の強い極限点収束結果を確立する。
論文 参考訳(メタデータ) (2021-10-10T23:20:04Z) - Last iterate convergence of SGD for Least-Squares in the Interpolation
regime [19.05750582096579]
基本最小二乗構成におけるノイズレスモデルについて検討する。
最適予測器が完全に入力に適合すると仮定し、$langletheta_*, phi(X) rangle = Y$, ここで$phi(X)$は無限次元の非線型特徴写像を表す。
論文 参考訳(メタデータ) (2021-02-05T14:02:20Z) - Random Reshuffling: Simple Analysis with Vast Improvements [9.169947558498535]
ランダムリシャッフル(Random Reshuffling, RR)は、データリシャッフルと共に反復降下ステップを利用する有限サム関数を最小化するアルゴリズムである。
論文 参考訳(メタデータ) (2020-06-10T17:57:21Z) - Complexity of Finding Stationary Points of Nonsmooth Nonconvex Functions [84.49087114959872]
非滑らかで非滑らかな関数の定常点を見つけるための最初の非漸近解析を提供する。
特に、アダマール半微分可能函数(おそらく非滑らか関数の最大のクラス)について研究する。
論文 参考訳(メタデータ) (2020-02-10T23:23:04Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。