論文の概要: Bounding the expected run-time of nonconvex optimization with early stopping

• arxiv url: http://arxiv.org/abs/2002.08856v4
• Date: Wed, 22 Jul 2020 17:56:23 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-30 06:14:13.465219
• Title: Bounding the expected run-time of nonconvex optimization with early stopping
• Title（参考訳）: 早期停止による非凸最適化の期待実行時間制限
• Authors: Thomas Flynn, Kwang Min Yu, Abid Malik, Nicolas D'Imperio, Shinjae Yoo
• Abstract要約: 本研究は,検証関数に基づく早期停止を用いた勾配に基づく最適化アルゴリズムの収束性について検討する。 我々は、この停止規則が適切に定義されていることを保証する条件を導出し、この基準を満たすのに必要なイテレーション数と勾配評価の期待値のバウンダリを提供する。
• 参考スコア（独自算出の注目度）: 2.7648976108201815
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This work examines the convergence of stochastic gradient-based optimization algorithms that use early stopping based on a validation function. The form of early stopping we consider is that optimization terminates when the norm of the gradient of a validation function falls below a threshold. We derive conditions that guarantee this stopping rule is well-defined, and provide bounds on the expected number of iterations and gradient evaluations needed to meet this criterion. The guarantee accounts for the distance between the training and validation sets, measured with the Wasserstein distance. We develop the approach in the general setting of a first-order optimization algorithm, with possibly biased update directions subject to a geometric drift condition. We then derive bounds on the expected running time for early stopping variants of several algorithms, including stochastic gradient descent (SGD), decentralized SGD (DSGD), and the stochastic variance reduced gradient (SVRG) algorithm. Finally, we consider the generalization properties of the iterate returned by early stopping.
• Abstract（参考訳）: 本研究は,検証関数に基づいて早期停止を利用する確率勾配に基づく最適化アルゴリズムの収束性について検討する。 私たちが考える早期停止の形式は、検証関数の勾配のノルムがしきい値を下回ると最適化が終了することである。 この停止規則が明確に定義されていることを保証した条件を導出し、この基準を満たすために必要なイテレーション数と勾配評価の境界を提供する。 保証は、ワッサーシュタイン距離で測定されたトレーニングセットと検証セットの間の距離を説明する。 我々は,幾何ドリフト条件下での更新方向の偏りを考慮し,一階最適化アルゴリズムの一般設定におけるアプローチを開発する。 次に、確率勾配降下(SGD)、分散SGD(DSGD)、確率分散還元勾配(SVRG)アルゴリズムなど、いくつかのアルゴリズムの早期停止変種に対する予測実行時間に基づいて境界を導出する。 最後に,早期停止時に返却されるイテレートの一般化特性について考察する。

関連論文リスト

• The Reinforce Policy Gradient Algorithm Revisited [7.894349646617293]
  文献からReinforce Policy gradientアルゴリズムを再検討する。 本稿では,基本アルゴリズムの大幅な拡張を提案する。 この新しいアルゴリズムの収束の証明を提供する。
  論文  参考訳（メタデータ） (2023-10-08T04:05:13Z)
• Variance reduction techniques for stochastic proximal point algorithms [5.374800961359305]
  そこで本研究では,近点アルゴリズムにおける分散低減手法の統一化研究を提案する。 我々は,SVRG,SAGA,およびそれらの変種の近位バージョンを提供するために特定可能な,汎用的近位アルゴリズムを提案する。 本実験は, 勾配法よりも近似分散還元法の利点を実証する。
  論文  参考訳（メタデータ） (2023-08-18T05:11:50Z)
• Parameter-free projected gradient descent [0.0]
  我々は、射影勾配 Descent (PGD) を用いて、閉凸集合上の凸関数を最小化する問題を考える。 本稿では,AdaGradのパラメータフリーバージョンを提案する。これは初期化と最適化の距離に適応し,下位段階の平方ノルムの和に適応する。 提案アルゴリズムはプロジェクションステップを処理でき、リスタートを伴わず、従来のPGDと比較して軌道に沿ってリウィーディングや追加評価を行うことができる。
  論文  参考訳（メタデータ） (2023-05-31T07:22:44Z)
• Random-reshuffled SARAH does not need a full gradient computations [61.85897464405715]
  StochAstic Recursive grAdientritHm (SARAH)アルゴリズムは、Gradient Descent (SGD)アルゴリズムのばらつき低減版である。 本稿では,完全勾配の必要性を除去する。 集約された勾配は、SARAHアルゴリズムの完全な勾配の見積もりとなる。
  論文  参考訳（メタデータ） (2021-11-26T06:00:44Z)
• Distributed stochastic optimization with large delays [59.95552973784946]
  大規模最適化問題を解決する最も広く使われている手法の1つは、分散非同期勾配勾配(DASGD)である。 DASGDは同じ遅延仮定の下で大域的最適実装モデルに収束することを示す。
  論文  参考訳（メタデータ） (2021-07-06T21:59:49Z)
• High-probability Bounds for Non-Convex Stochastic Optimization with Heavy Tails [55.561406656549686]
  我々は、勾配推定が末尾を持つ可能性のある一階アルゴリズムを用いたヒルベルト非最適化を考える。 本研究では, 勾配, 運動量, 正規化勾配勾配の収束を高確率臨界点に収束させることと, 円滑な損失に対する最もよく知られた繰り返しを示す。
  論文  参考訳（メタデータ） (2021-06-28T00:17:01Z)
• ROOT-SGD: Sharp Nonasymptotics and Near-Optimal Asymptotics in a Single Algorithm [71.13558000599839]
  第一次アルゴリズムを用いて,厳密な凸と滑らかな非制約最適化問題の解法について検討する。 我々は,過去の勾配を平均化し,実装が容易な小説「Recursive One-Over-T SGD」を考案した。 有限サンプル, 漸近感覚, 感覚の両面において, 最先端の性能を同時に達成できることを実証する。
  論文  参考訳（メタデータ） (2020-08-28T14:46:56Z)
• Sequential Quadratic Optimization for Nonlinear Equality Constrained Stochastic Optimization [10.017195276758454]
  この設定では、客観的関数と微分値を明示的に計算することは難しそうだと仮定する。 最先端のライン探索SQPアルゴリズムをモデルとした決定論的設定のためのアルゴリズムを提案する。 数値実験の結果は,提案手法の実用性を示すものである。
  論文  参考訳（メタデータ） (2020-07-20T23:04:26Z)
• Private Stochastic Non-Convex Optimization: Adaptive Algorithms and Tighter Generalization Bounds [72.63031036770425]
  有界非次元最適化のための差分プライベート(DP)アルゴリズムを提案する。 標準勾配法に対する経験的優位性について,2つの一般的なディープラーニング手法を実証する。
  論文  参考訳（メタデータ） (2020-06-24T06:01:24Z)
• Convergence of adaptive algorithms for weakly convex constrained optimization [59.36386973876765]
  モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。 我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
  論文  参考訳（メタデータ） (2020-06-11T17:43:19Z)
• Non-asymptotic bounds for stochastic optimization with biased noisy gradient oracles [8.655294504286635]
  関数の測定値が推定誤差を持つ設定を捉えるために,バイアス付き勾配オラクルを導入する。 提案するオラクルは,例えば,独立分散シミュレーションと同一分散シミュレーションのバッチによるリスク計測推定の実践的な状況にある。
  論文  参考訳（メタデータ） (2020-02-26T12:53:04Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。