論文の概要: Convergence of ease-controlled Random Reshuffling gradient Algorithms under Lipschitz smoothness
- arxiv url: http://arxiv.org/abs/2212.01848v3
- Date: Mon, 20 May 2024 18:14:56 GMT
- ステータス: 処理完了
- システム内更新日: 2024-05-22 19:40:07.656030
- Title: Convergence of ease-controlled Random Reshuffling gradient Algorithms under Lipschitz smoothness
- Title（参考訳）: リプシッツ平滑性を考慮した簡易制御ランダムリシャッフル勾配アルゴリズムの収束性
- Authors: Ruggiero Seccia, Corrado Coppola, Giampaolo Liuzzi, Laura Palagi,
- Abstract要約: 非常に多くのスムーズで可能な非サイズの関数の平均を考慮し、この問題に対処するために2つの広く最小限のフレームワークを使用します。
IG/RRスキームの簡易制御による修正を定義する。
我々は、完全なバッチ勾配(L-BFGS)とIG/RR手法の実装の両方で実装を証明し、アルゴリズムが同様の計算作業を必要とすることを証明した。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this work, we consider minimizing the average of a very large number of smooth and possibly non-convex functions, and we focus on two widely used minibatch frameworks to tackle this optimization problem: Incremental Gradient (IG) and Random Reshuffling (RR). We define ease-controlled modifications of the IG/RR schemes, which require a light additional computational effort {but} can be proved to converge under {weak} and standard assumptions. In particular, we define two algorithmic schemes in which the IG/RR iteration is controlled by using a watchdog rule and a derivative-free linesearch that activates only sporadically to guarantee convergence. The two schemes differ in the watchdog and the linesearch, which are performed using either a monotonic or a non-monotonic rule. The two schemes also allow controlling the updating of the stepsize used in the main IG/RR iteration, avoiding the use of pre-set rules that may drive the stepsize to zero too fast, reducing the effort in designing effective updating rules of the stepsize. We prove convergence under the mild assumption of Lipschitz continuity of the gradients of the component functions and perform extensive computational analysis using different deep neural architectures and a benchmark of varying-size datasets. We compare our implementation with both a full batch gradient method (i.e. L-BFGS) and an implementation of IG/RR methods, proving that our algorithms require a similar computational effort compared to the other online algorithms and that the control on the learning rate may allow a faster decrease of the objective function.
- Abstract（参考訳）: 本研究では,非常に多くのスムーズかつ非凸関数の平均を最小化することを検討するとともに,この最適化問題に対処するために広く利用されている2つのミニバッチフレームワークであるインクリメンタルグラディエント(IG)とランダムリシャッフル(RR)に焦点を当てる。
我々は IG/RR スキームの緩和制御的な修正を定義するが、これはより軽い計算量 {but} が {weak} と標準仮定の下で収束することを証明できる。
特に、IG/RRイテレーションをウォッチドッグルールと、収束を保証するために散発的にのみ活性化するデリバティブフリーライン探索を用いて制御する2つのアルゴリズムスキームを定義する。
2つのスキームは、モノトニックまたは非モノトニックな規則を用いて実行される、ウォッチドッグとライン検索で異なる。
この2つのスキームは、メインIG/RRイテレーションで使用されるステップサイズの更新を制御でき、ステップサイズをゼロにしすぎてしまうような事前設定ルールの使用を避けることができ、ステップサイズを効果的に更新するルールを設計する労力を減らすことができる。
成分関数の勾配のリプシッツ連続性の軽微な仮定の下で収束性を証明し、異なるディープニューラルネットワークアーキテクチャと様々なサイズデータセットのベンチマークを用いて広範な計算解析を行う。
我々は,本手法を全バッチ勾配法(L-BFGS)とIG/RR法の両方と比較し,我々のアルゴリズムが他のオンラインアルゴリズムと同じような計算作業を必要とすること,学習速度の制御が目的関数の高速化を可能にすることを証明した。
関連論文リスト
- Adaptive and Optimal Second-order Optimistic Methods for Minimax Optimization [32.939120407900035]
私たちのアルゴリズムは、イテレーション毎に1つの線形システムだけを解決する必要のある、単純な更新ルールを備えています。
また,提案アルゴリズムの実用性能を,既存の2次アルゴリズムと比較して評価した。
論文 参考訳（メタデータ） (2024-06-04T06:56:41Z) - Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。
これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
論文 参考訳（メタデータ） (2023-02-01T08:50:48Z) - Differentiable Annealed Importance Sampling and the Perils of Gradient
Noise [68.44523807580438]
Annealed importance sample (AIS) と関連するアルゴリズムは、限界推定のための非常に効果的なツールである。
差別性は、目的として限界確率を最適化する可能性を認めるため、望ましい性質である。
我々はメトロポリス・ハスティングスのステップを放棄して微分可能アルゴリズムを提案し、ミニバッチ計算をさらに解き放つ。
論文 参考訳（メタデータ） (2021-07-21T17:10:14Z) - Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex
Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。
我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。
我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
論文 参考訳（メタデータ） (2021-06-08T15:54:44Z) - Learning Sampling Policy for Faster Derivative Free Optimization [100.27518340593284]
ランダムサンプリングではなく,ZO最適化における摂動を生成するためのサンプリングポリシを学習する,新たな強化学習ベースのZOアルゴリズムを提案する。
その結果,ZO-RLアルゴリズムはサンプリングポリシを学習することでZO勾配の分散を効果的に低減し,既存のZOアルゴリズムよりも高速に収束できることが示唆された。
論文 参考訳（メタデータ） (2021-04-09T14:50:59Z) - AI-SARAH: Adaptive and Implicit Stochastic Recursive Gradient Methods [7.486132958737807]
適応性に対する暗黙的アプローチによる適応分散低減手法を提案する。
有限サム最小化問題に対する収束保証を提供し,局所幾何が許せばサラよりも高速に収束できることを示す。
このアルゴリズムはステップサイズを暗黙的に計算し、関数の局所リプシッツ滑らかさを効率的に推定する。
論文 参考訳（メタデータ） (2021-02-19T01:17:15Z) - Balancing Rates and Variance via Adaptive Batch-Size for Stochastic
Optimization Problems [120.21685755278509]
本研究は,ステップサイズの減衰が正確な収束に必要であるという事実と,一定のステップサイズがエラーまでの時間でより速く学習するという事実のバランスをとることを目的とする。
ステップサイズのミニバッチを最初から修正するのではなく,パラメータを適応的に進化させることを提案する。
論文 参考訳（メタデータ） (2020-07-02T16:02:02Z) - Effective Dimension Adaptive Sketching Methods for Faster Regularized
Least-Squares Optimization [56.05635751529922]
スケッチに基づくL2正規化最小二乗問題の解法を提案する。
我々は、最も人気のあるランダム埋め込みの2つ、すなわちガウス埋め込みとサブサンプリングランダム化アダマール変換(SRHT)を考える。
論文 参考訳（メタデータ） (2020-06-10T15:00:09Z) - A Gradient-Aware Search Algorithm for Constrained Markov Decision
Processes [9.728259735794987]
まず,有限CMDPの双対線型計画における最適化目標が,ラグランジュのペナルティ乗算器に対する一方向線型凸関数であることを証明した。
有限CMDPの最適状態値関数とラグランジュペナルティ乗算器を求めるために,PWLC構造を利用した2レベルグラディエント・アウェア・サーチ(GAS)アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-05-07T19:38:09Z) - Explicit Regularization of Stochastic Gradient Methods through Duality [9.131027490864938]
ランダム化された双対座標の上昇に基づくランダム化されたDykstraスタイルのアルゴリズムを提案する。
座標降下を高速化するために、補間系における既存の勾配法よりも収束特性がよい新しいアルゴリズムを得る。
論文 参考訳（メタデータ） (2020-03-30T20:44:56Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。