論文の概要: Convergence under Lipschitz smoothness of ease-controlled Random
Reshuffling gradient Algorithms
- arxiv url: http://arxiv.org/abs/2212.01848v1
- Date: Sun, 4 Dec 2022 15:26:36 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-06 19:13:50.986819
- Title: Convergence under Lipschitz smoothness of ease-controlled Random
Reshuffling gradient Algorithms
- Title（参考訳）: 自由制御ランダムリシャッフル勾配アルゴリズムのリプシッツ平滑性による収束
- Authors: Giampaolo Liuzzi, Laura Palagi and Ruggiero Seccia
- Abstract要約: 非常に多くの滑らかで非単調な勾配関数の平均を最小化することを検討する。
我々は、IG/RR反復をウォッチドッグルールと、収束を保証するために散発的にのみ活性化するラインサーチの導関数を用いて制御する、モノトーンまたはノンモノトーンの2つの弱いスキームを定義する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider minimizing the average of a very large number of smooth and
possibly non-convex functions. This optimization problem has deserved much
attention in the past years due to the many applications in different fields,
the most challenging being training Machine Learning models. Widely used
approaches for solving this problem are mini-batch gradient methods which, at
each iteration, update the decision vector moving along the gradient of a
mini-batch of the component functions. We consider the Incremental Gradient
(IG) and the Random reshuffling (RR) methods which proceed in cycles, picking
batches in a fixed order or by reshuffling the order after each epoch.
Convergence properties of these schemes have been proved under different
assumptions, usually quite strong. We aim to define ease-controlled
modifications of the IG/RR schemes, which require a light additional
computational effort and can be proved to converge under very weak and standard
assumptions. In particular, we define two algorithmic schemes, monotone or
non-monotone, in which the IG/RR iteration is controlled by using a watchdog
rule and a derivative-free line search that activates only sporadically to
guarantee convergence. The two schemes also allow controlling the updating of
the stepsize used in the main IG/RR iteration, avoiding the use of preset
rules. We prove convergence under the lonely assumption of Lipschitz continuity
of the gradients of the component functions and perform extensive computational
analysis using Deep Neural Architectures and a benchmark of datasets. We
compare our implementation with both full batch gradient methods and online
standard implementation of IG/RR methods, proving that the computational effort
is comparable with the corresponding online methods and that the control on the
learning rate may allow faster decrease.
- Abstract（参考訳）: 非常に多くの滑らかかつ非凸関数の平均を最小化することを検討する。
この最適化問題は、さまざまな分野のアプリケーションが多いため、ここ数年で多くの注目を集めており、最も難しいのは機械学習モデルのトレーニングである。
この問題を解決するために広く使われているアプローチはミニバッチ勾配法であり、各イテレーションでコンポーネント関数のミニバッチの勾配に沿って移動する決定ベクトルを更新する。
漸進勾配 (ig) とランダムリシャッフル法 (rr) は周期的に進行し, バッチを一定の順序で選択するか, または各エポックの後の順序を再シャッフルすることによって検討する。
これらのスキームの収束性は異なる仮定の下で証明され、通常は非常に強い。
IG/RRスキームの緩和制御的な修正は, 計算作業の軽量化と, 非常に弱い標準仮定の下で収束することが証明できる。
特に、モノトーンまたは非モノトーンという2つのアルゴリズムスキームを定義し、ig/rr反復をウォッチドッグ規則と、収束を保証するために散発的にのみ活性化するデリバティブフリーライン探索を用いて制御する。
この2つのスキームは、メインIG/RRイテレーションで使用されるステップサイズの更新を制御でき、プリセットルールの使用を避けることができる。
コンポーネント関数の勾配のリプシッツ連続性の孤独な仮定の下で収束を証明し、深層ニューラルネットワークとデータセットのベンチマークを用いて広範な計算解析を行う。
我々は,本手法を全バッチ勾配法と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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。