論文の概要: Convergence of the mini-batch SIHT algorithm

• arxiv url: http://arxiv.org/abs/2209.14536v1
• Date: Thu, 29 Sep 2022 03:47:46 GMT
• ステータス: 処理完了
• システム内更新日: 2022-09-30 18:15:04.247329
• Title: Convergence of the mini-batch SIHT algorithm
• Title（参考訳）: ミニバッチSIHTアルゴリズムの収束性
• Authors: Saeed Damadi, Jinglai Shen
• Abstract要約: Iterative Hard Thresholding (IHT)アルゴリズムはスパース最適化の効果的な決定論的アルゴリズムとして広く検討されている。 スパースミニバッチSIHTが生成したシーケンスはスーパーマーチンゲールシーケンスであり、確率1と収束することを示す。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The Iterative Hard Thresholding (IHT) algorithm has been considered extensively as an effective deterministic algorithm for solving sparse optimizations. The IHT algorithm benefits from the information of the batch (full) gradient at each point and this information is a crucial key for the convergence analysis of the generated sequence. However, this strength becomes a weakness when it comes to machine learning and high dimensional statistical applications because calculating the batch gradient at each iteration is computationally expensive or impractical. Fortunately, in these applications the objective function has a summation structure that can be taken advantage of to approximate the batch gradient by the stochastic mini-batch gradient. In this paper, we study the mini-batch Stochastic IHT (SIHT) algorithm for solving the sparse optimizations. As opposed to previous works where increasing and variable mini-batch size is necessary for derivation, we fix the mini-batch size according to a lower bound that we derive and show our work. To prove stochastic convergence of the objective value function we first establish a critical sparse stochastic gradient descent property. Using this stochastic gradient descent property we show that the sequence generated by the stochastic mini-batch SIHT is a supermartingale sequence and converges with probability one. Unlike previous work we do not assume the function to be a restricted strongly convex. To the best of our knowledge, in the regime of sparse optimization, this is the first time in the literature that it is shown that the sequence of the stochastic function values converges with probability one by fixing the mini-batch size for all steps.
• Abstract（参考訳）: Iterative Hard Thresholding (IHT)アルゴリズムはスパース最適化の効果的な決定論的アルゴリズムとして広く検討されている。 IHTアルゴリズムは各点におけるバッチ(フル)勾配の情報から恩恵を受け、この情報は生成されたシーケンスの収束解析において重要な鍵となる。 しかし、各イテレーションでのバッチ勾配の計算は計算コストが高いか非現実的であるため、機械学習や高次元統計応用ではこの強さは弱くなる。 幸いなことに、これらのアプリケーションでは、目的関数は、確率的ミニバッチ勾配によるバッチ勾配を近似するために利用できる和構造を持つ。 本稿では,スパース最適化のためのミニバッチStochastic IHT (SIHT) アルゴリズムについて検討する。 導出に必要となる最小バッチサイズの増加と可変化を必要とする従来の研究とは対照的に、我々は導出する下位境界に従ってミニバッチサイズを固定し、作業を示す。 目的値関数の確率収束を証明するために、まず臨界スパース確率勾配降下特性を確立する。 この確率勾配降下特性を用いて,確率的ミニバッチsihtが生成する列はスーパーマーチンゲール列であり,確率1に収束することを示す。 以前の仕事とは異なり、関数は制限された強い凸であると仮定しない。 我々の知る限り、スパース最適化の状況において、全てのステップのミニバッチサイズを固定することにより確率関数値の列が確率1と収束することが文献で示されているのはこれが初めてである。

関連論文リスト

• Stochastic Optimization for Non-convex Problem with Inexact Hessian Matrix, Gradient, and Function [99.31457740916815]
  信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。 TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
  論文  参考訳（メタデータ） (2023-10-18T10:29:58Z)
• Relationship between Batch Size and Number of Steps Needed for Nonconvex Optimization of Stochastic Gradient Descent using Armijo Line Search [0.8158530638728501]
  本研究では,SGDが深層数値線を用いた場合,他の深層学習ネットワークよりも優れた性能を示す。 その結果,バッチサイズが大きくなるにつれて,SFOに必要なステップ数を推定できることが示唆された。
  論文  参考訳（メタデータ） (2023-07-25T21:59:17Z)
• A Gradient Smoothed Functional Algorithm with Truncated Cauchy Random Perturbations for Stochastic Optimization [10.820943271350442]
  本稿では,雑音の多いコストサンプルに対する期待値であるスムーズな目的関数を最小化するための凸勾配アルゴリズムを提案する。 また,本アルゴリズムは局所最小値への収束を示唆し,レートリリアを回避できることも示している。
  論文  参考訳（メタデータ） (2022-07-30T18:50:36Z)
• STORM+: Fully Adaptive SGD with Momentum for Nonconvex Optimization [74.1615979057429]
  本研究では,スムーズな損失関数に対する期待値である非バッチ最適化問題について検討する。 我々の研究は、学習率と運動量パラメータを適応的に設定する新しいアプローチとともに、STORMアルゴリズムの上に構築されている。
  論文  参考訳（メタデータ） (2021-11-01T15:43:36Z)
• Differentiable Annealed Importance Sampling and the Perils of Gradient Noise [68.44523807580438]
  Annealed importance sample (AIS) と関連するアルゴリズムは、限界推定のための非常に効果的なツールである。 差別性は、目的として限界確率を最適化する可能性を認めるため、望ましい性質である。 我々はメトロポリス・ハスティングスのステップを放棄して微分可能アルゴリズムを提案し、ミニバッチ計算をさらに解き放つ。
  論文  参考訳（メタデータ） (2021-07-21T17:10:14Z)
• Balancing Rates and Variance via Adaptive Batch-Size for Stochastic Optimization Problems [120.21685755278509]
  本研究は,ステップサイズの減衰が正確な収束に必要であるという事実と,一定のステップサイズがエラーまでの時間でより速く学習するという事実のバランスをとることを目的とする。 ステップサイズのミニバッチを最初から修正するのではなく,パラメータを適応的に進化させることを提案する。
  論文  参考訳（メタデータ） (2020-07-02T16:02:02Z)
• On the Almost Sure Convergence of Stochastic Gradient Descent in Non-Convex Problems [75.58134963501094]
  本稿では,勾配降下(SGD)の軌跡を解析する。 我々はSGDが厳格なステップサイズポリシーのために1ドルでサドルポイント/マニフォールドを避けることを示す。
  論文  参考訳（メタデータ） (2020-06-19T14:11:26Z)
• Exploiting Higher Order Smoothness in Derivative-free Optimization and Continuous Bandits [99.70167985955352]
  強凸関数のゼロ次最適化問題について検討する。 予測勾配降下アルゴリズムのランダム化近似を考察する。 その結果,0次アルゴリズムはサンプルの複雑性や問題パラメータの点でほぼ最適であることが示唆された。
  論文  参考訳（メタデータ） (2020-06-14T10:42:23Z)
• Stochastic Proximal Gradient Algorithm with Minibatches. Application to Large Scale Learning Models [2.384873896423002]
  非滑らかな成分を持つ汎用合成対象関数に対する勾配アルゴリズムのミニバッチ変種を開発し解析する。 我々は、最小バッチサイズ$N$に対して、$mathcalO(frac1Nepsilon)$$epsilon-$subityが最適解に期待される二次距離で達成されるような、定数および変数のステップサイズ反復ポリシーの複雑さを提供する。
  論文  参考訳（メタデータ） (2020-03-30T10:43:56Z)

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

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