論文の概要: An Exponentially Increasing Step-size for Parameter Estimation in Statistical Models

• arxiv url: http://arxiv.org/abs/2205.07999v1
• Date: Mon, 16 May 2022 21:36:22 GMT
• ステータス: 処理完了
• システム内更新日: 2022-05-18 13:27:51.440234
• Title: An Exponentially Increasing Step-size for Parameter Estimation in Statistical Models
• Title（参考訳）: 統計的モデルにおけるパラメータ推定のための指数的ステップサイズ増加
• Authors: Nhat Ho and Tongzheng Ren and Sujay Sanghavi and Purnamrita Sarkar and Rachel Ward
• Abstract要約: 本稿では,ガウス降下(GD)アルゴリズムのステップサイズを指数関数的に増加させることを提案する。 次に、非正規統計モデルの下でパラメータ推定を解くためのEGDアルゴリズムについて検討する。 EGDアルゴリズムの総計算複雑性は、非正則統計モデルにおけるパラメータ推定の解法として、GDよりも最適で指数関数的に安価である。
• 参考スコア（独自算出の注目度）: 37.63410634069547
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Using gradient descent (GD) with fixed or decaying step-size is standard practice in unconstrained optimization problems. However, when the loss function is only locally convex, such a step-size schedule artificially slows GD down as it cannot explore the flat curvature of the loss function. To overcome that issue, we propose to exponentially increase the step-size of the GD algorithm. Under homogeneous assumptions on the loss function, we demonstrate that the iterates of the proposed \emph{exponential step size gradient descent} (EGD) algorithm converge linearly to the optimal solution. Leveraging that optimization insight, we then consider using the EGD algorithm for solving parameter estimation under non-regular statistical models whose the loss function becomes locally convex when the sample size goes to infinity. We demonstrate that the EGD iterates reach the final statistical radius within the true parameter after a logarithmic number of iterations, which is in stark contrast to a \emph{polynomial} number of iterations of the GD algorithm. Therefore, the total computational complexity of the EGD algorithm is \emph{optimal} and exponentially cheaper than that of the GD for solving parameter estimation in non-regular statistical models. To the best of our knowledge, it resolves a long-standing gap between statistical and algorithmic computational complexities of parameter estimation in non-regular statistical models. Finally, we provide targeted applications of the general theory to several classes of statistical models, including generalized linear models with polynomial link functions and location Gaussian mixture models.
• Abstract（参考訳）: 固定あるいは減衰するステップサイズを持つ勾配降下(GD)を用いることは、制約のない最適化問題において標準的なプラクティスである。 しかし、損失関数が局所凸である場合、そのようなステップサイズのスケジュールは損失関数の平坦な曲率を探索できないため、gdを人工的に遅くする。 そこで本研究では,GDアルゴリズムのステップサイズを指数関数的に増加させることを提案する。 損失関数の均質な仮定の下では、提案した \emph{exponential step size gradient} (EGD) アルゴリズムの反復が最適解に線形に収束することを示した。 この最適化の知見を生かして、サンプルサイズが無限大となると、損失関数が局所凸となる非正則統計モデルの下でパラメータ推定を解くためのEGDアルゴリズムを検討する。 我々は,GDアルゴリズムの反復数であるemph{polynomial}数とは対照的に,EGDの反復は対数的な反復数の後,真のパラメータ内の最終的な統計的半径に達することを示した。 したがって、EGDアルゴリズムの総計算複雑性は \emph{optimal} であり、非正規統計モデルにおけるパラメータ推定の解法として GD よりも指数関数的に安価である。 我々の知る限りでは、非正規統計モデルにおけるパラメータ推定の統計量とアルゴリズム計算の複雑さの間の長年のギャップを解消する。 最後に、多項式リンク関数を持つ一般化線形モデルや位置ガウス混合モデルなど、統計モデルのいくつかのクラスに対する一般理論のターゲット応用を提案する。

関連論文リスト

• Accelerated zero-order SGD under high-order smoothness and overparameterized regime [79.85163929026146]
  凸最適化問題を解くための新しい勾配のないアルゴリズムを提案する。 このような問題は医学、物理学、機械学習で発生する。 両種類の雑音下で提案アルゴリズムの収束保証を行う。
  論文  参考訳（メタデータ） (2024-11-21T10:26:17Z)
• Differentially Private Optimization with Sparse Gradients [60.853074897282625]
  微分プライベート(DP)最適化問題を個人勾配の空間性の下で検討する。 これに基づいて、スパース勾配の凸最適化にほぼ最適な速度で純粋および近似DPアルゴリズムを得る。
  論文  参考訳（メタデータ） (2024-04-16T20:01:10Z)
• Joint Graph Learning and Model Fitting in Laplacian Regularized Stratified Models [5.933030735757292]
  ラプラシア正規化成層モデル(Laplacian regularized Stratified Model、LRSM)は、サブプロブレムの明示的または暗黙的なネットワーク構造を利用するモデルである。 本稿では,LRSMにおけるグラフ重みの重要性と感度を示し,その感度が任意に大きいことを示す。 本稿では,1つの最適化問題を解くことで,モデルパラメータを適合させながらグラフを共同学習する汎用的手法を提案する。
  論文  参考訳（メタデータ） (2023-05-04T06:06:29Z)
• Gaussian process regression and conditional Karhunen-Lo\'{e}ve models for data assimilation in inverse problems [68.8204255655161]
  偏微分方程式モデルにおけるデータ同化とパラメータ推定のためのモデル逆アルゴリズムCKLEMAPを提案する。 CKLEMAP法は標準的なMAP法に比べてスケーラビリティがよい。
  論文  参考訳（メタデータ） (2023-01-26T18:14:12Z)
• Stochastic Mirror Descent for Large-Scale Sparse Recovery [13.500750042707407]
  本稿では,2次近似の高次元スパースパラメータの統計的推定への応用について論じる。 提案アルゴリズムは, 回帰器分布の弱い仮定の下で, 推定誤差の最適収束を実現する。
  論文  参考訳（メタデータ） (2022-10-23T23:23:23Z)
• Improving Computational Complexity in Statistical Models with Second-Order Information [32.64382185990981]
  パラメトリック統計モデルにおけるパラメータ推定のための正規化勾配降下法(NormGD)について検討する。 我々は、NormGDアルゴリズムが最終的な統計的半径に達するために最適な計算量$mathcalO(n)$を達成することを示した。 この計算複雑性は、固定ステップサイズ勾配勾配アルゴリズムよりも安価である。
  論文  参考訳（メタデータ） (2022-02-09T01:32:50Z)
• Nonconvex Stochastic Scaled-Gradient Descent and Generalized Eigenvector Problems [98.34292831923335]
  オンライン相関解析の問題から,emphStochastic Scaled-Gradient Descent (SSD)アルゴリズムを提案する。 我々はこれらのアイデアをオンライン相関解析に適用し、局所収束率を正規性に比例した最適な1時間スケールのアルゴリズムを初めて導いた。
  論文  参考訳（メタデータ） (2021-12-29T18:46:52Z)
• Last iterate convergence of SGD for Least-Squares in the Interpolation regime [19.05750582096579]
  基本最小二乗構成におけるノイズレスモデルについて検討する。 最適予測器が完全に入力に適合すると仮定し、$langletheta_*, phi(X) rangle = Y$, ここで$phi(X)$は無限次元の非線型特徴写像を表す。
  論文  参考訳（メタデータ） (2021-02-05T14:02:20Z)
• Balancing Rates and Variance via Adaptive Batch-Size for Stochastic Optimization Problems [120.21685755278509]
  本研究は,ステップサイズの減衰が正確な収束に必要であるという事実と,一定のステップサイズがエラーまでの時間でより速く学習するという事実のバランスをとることを目的とする。 ステップサイズのミニバッチを最初から修正するのではなく,パラメータを適応的に進化させることを提案する。
  論文  参考訳（メタデータ） (2020-07-02T16:02:02Z)
• Instability, Computational Efficiency and Statistical Accuracy [101.32305022521024]
  我々は,人口レベルでのアルゴリズムの決定論的収束率と,$n$サンプルに基づく経験的対象に適用した場合の(不安定性)の間の相互作用に基づいて,統計的精度を得るフレームワークを開発する。 本稿では,ガウス混合推定,非線形回帰モデル,情報的非応答モデルなど,いくつかの具体的なモデルに対する一般結果の応用について述べる。
  論文  参考訳（メタデータ） (2020-05-22T22:30:52Z)
• Statistical Inference for Model Parameters in Stochastic Gradient Descent [45.29532403359099]
  勾配降下係数(SGD)は,その計算効率とメモリ効率から,大規模データの統計的推定に広く用いられている。 人口減少関数が強い凸であり,一定の条件を満たす場合,SGDに基づく真のモデルパラメータの統計的推測の問題について検討する。
  論文  参考訳（メタデータ） (2016-10-27T07:04:21Z)

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

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