論文の概要: 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法のオンライン標準法の両方と比較し,計算作業が対応するオンライン手法に匹敵するものであり,学習率の制御が高速化できることを示した。
関連論文リスト
- Stochastic Optimization for Non-convex Problem with Inexact Hessian
Matrix, Gradient, and Function [99.31457740916815]
信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。
TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
論文 参考訳(メタデータ) (2023-10-18T10:29:58Z) - Ordering for Non-Replacement SGD [7.11967773739707]
我々は,アルゴリズムの非置換形式に対する収束率を改善する順序付けを求める。
我々は,強い凸関数と凸関数のステップサイズを一定かつ小さくするための最適順序付けを開発する。
さらに、注文とミニバッチを組み合わせることで、より複雑なニューラルネットワークにも適用できます。
論文 参考訳(メタデータ) (2023-06-28T00:46:58Z) - Cyclic Block Coordinate Descent With Variance Reduction for Composite
Nonconvex Optimization [26.218670461973705]
非漸近勾配ノルム保証を協調する問題の解法を提案する。
本研究は,ニューラルネットの深部学習における循環還元方式の有効性を実証するものである。
論文 参考訳(メタデータ) (2022-12-09T19:17:39Z) - Faster One-Sample Stochastic Conditional Gradient Method for Composite
Convex Minimization [61.26619639722804]
滑らかで非滑らかな項の和として形成される凸有限サム目標を最小化するための条件勾配法(CGM)を提案する。
提案手法は, 平均勾配 (SAG) 推定器を備え, 1回に1回のサンプルしか必要としないが, より高度な分散低減技術と同等の高速収束速度を保証できる。
論文 参考訳(メタデータ) (2022-02-26T19:10:48Z) - Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and
Beyond [63.59034509960994]
シャッフルに基づく変種(ミニバッチと局所ランダムリシャッフル)について検討する。
ポリアック・ロジャシエヴィチ条件を満たす滑らかな函数に対して、これらのシャッフル型不変量(英語版)(shuffling-based variants)がそれらの置換式よりも早く収束することを示す収束境界を得る。
我々は, 同期シャッフル法と呼ばれるアルゴリズムの修正を提案し, ほぼ均一な条件下では, 下界よりも収束速度が速くなった。
論文 参考訳(メタデータ) (2021-10-20T02:25:25Z) - Differentiable Annealed Importance Sampling and the Perils of Gradient
Noise [68.44523807580438]
Annealed importance sample (AIS) と関連するアルゴリズムは、限界推定のための非常に効果的なツールである。
差別性は、目的として限界確率を最適化する可能性を認めるため、望ましい性質である。
我々はメトロポリス・ハスティングスのステップを放棄して微分可能アルゴリズムを提案し、ミニバッチ計算をさらに解き放つ。
論文 参考訳(メタデータ) (2021-07-21T17:10:14Z) - Learning Sampling Policy for Faster Derivative Free Optimization [100.27518340593284]
ランダムサンプリングではなく,ZO最適化における摂動を生成するためのサンプリングポリシを学習する,新たな強化学習ベースのZOアルゴリズムを提案する。
その結果,ZO-RLアルゴリズムはサンプリングポリシを学習することでZO勾配の分散を効果的に低減し,既存のZOアルゴリズムよりも高速に収束できることが示唆された。
論文 参考訳(メタデータ) (2021-04-09T14:50:59Z) - Balancing Rates and Variance via Adaptive Batch-Size for Stochastic
Optimization Problems [120.21685755278509]
本研究は,ステップサイズの減衰が正確な収束に必要であるという事実と,一定のステップサイズがエラーまでの時間でより速く学習するという事実のバランスをとることを目的とする。
ステップサイズのミニバッチを最初から修正するのではなく,パラメータを適応的に進化させることを提案する。
論文 参考訳(メタデータ) (2020-07-02T16:02:02Z) - Explicit Regularization of Stochastic Gradient Methods through Duality [9.131027490864938]
ランダム化された双対座標の上昇に基づくランダム化されたDykstraスタイルのアルゴリズムを提案する。
座標降下を高速化するために、補間系における既存の勾配法よりも収束特性がよい新しいアルゴリズムを得る。
論文 参考訳(メタデータ) (2020-03-30T20:44:56Z) - Stochastic Proximal Gradient Algorithm with Minibatches. Application to
Large Scale Learning Models [2.384873896423002]
非滑らかな成分を持つ汎用合成対象関数に対する勾配アルゴリズムのミニバッチ変種を開発し解析する。
我々は、最小バッチサイズ$N$に対して、$mathcalO(frac1Nepsilon)$$epsilon-$subityが最適解に期待される二次距離で達成されるような、定数および変数のステップサイズ反復ポリシーの複雑さを提供する。
論文 参考訳(メタデータ) (2020-03-30T10:43:56Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。