論文の概要: Towards Statistical and Computational Complexities of Polyak Step Size Gradient Descent

• arxiv url: http://arxiv.org/abs/2110.07810v1
• Date: Fri, 15 Oct 2021 02:19:50 GMT
• ステータス: 処理完了
• システム内更新日: 2021-10-18 13:19:42.763776
• Title: Towards Statistical and Computational Complexities of Polyak Step Size Gradient Descent
• Title（参考訳）: ポリークステップサイズグラディエントDescenceの統計的・計算複雑度に向けて
• Authors: Tongzheng Ren, Fuheng Cui, Alexia Atsidakou, Sujay Sanghavi and Nhat Ho
• Abstract要約: 本稿では,Polyak段差勾配の統計的および計算的複雑さについて検討する。 一般化線形モデル、混合線形回帰モデル、混合線形回帰モデルという3つの統計的例の下で、我々の一般理論を説明する。
• 参考スコア（独自算出の注目度）: 25.914790328250678
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the statistical and computational complexities of the Polyak step size gradient descent algorithm under generalized smoothness and Lojasiewicz conditions of the population loss function, namely, the limit of the empirical loss function when the sample size goes to infinity, and the stability between the gradients of the empirical and population loss functions, namely, the polynomial growth on the concentration bound between the gradients of sample and population loss functions. We demonstrate that the Polyak step size gradient descent iterates reach a final statistical radius of convergence around the true parameter after logarithmic number of iterations in terms of the sample size. It is computationally cheaper than the polynomial number of iterations on the sample size of the fixed-step size gradient descent algorithm to reach the same final statistical radius when the population loss function is not locally strongly convex. Finally, we illustrate our general theory under three statistical examples: generalized linear model, mixture model, and mixed linear regression model.
• Abstract（参考訳）: 本研究では, 一般平滑性およびロジャシェビッチ条件下でのポリアックステップサイズ勾配降下アルゴリズムの統計的・計算的複雑度, 標本サイズが無限大となる際の経験的損失関数の限界, 経験的損失関数と個体数損失関数の勾配の安定性, 標本の勾配と個体数損失関数の濃度境界における多項式成長について検討した。 本研究では,ポリアックステップの勾配勾配降下が,サンプルサイズの対数的な反復数の後,真のパラメータの周囲の収束の最終的な統計的半径に達することを実証する。 人口損失関数が局所的に強い凸でない場合に同じ最終統計半径に達するように、固定ステップサイズ勾配降下アルゴリズムのサンプルサイズでの反復数の多項式数よりも計算的に安価である。 最後に, 一般化線形モデル, 混合モデル, 混合線形回帰モデルという3つの統計例で一般理論を説明する。

関連論文リスト

• A Mean-Field Analysis of Neural Stochastic Gradient Descent-Ascent for Functional Minimax Optimization [90.87444114491116]
  本稿では,超パラメトリック化された2層ニューラルネットワークの無限次元関数クラス上で定義される最小最適化問題について検討する。 i) 勾配降下指数アルゴリズムの収束と, (ii) ニューラルネットワークの表現学習に対処する。 その結果、ニューラルネットワークによって誘導される特徴表現は、ワッサーシュタイン距離で測定された$O(alpha-1)$で初期表現から逸脱することが許された。
  論文  参考訳（メタデータ） (2024-04-18T16:46:08Z)
• An Exponentially Increasing Step-size for Parameter Estimation in Statistical Models [37.63410634069547]
  本稿では,ガウス降下(GD)アルゴリズムのステップサイズを指数関数的に増加させることを提案する。 次に、非正規統計モデルの下でパラメータ推定を解くためのEGDアルゴリズムについて検討する。 EGDアルゴリズムの総計算複雑性は、非正則統計モデルにおけるパラメータ推定の解法として、GDよりも最適で指数関数的に安価である。
  論文  参考訳（メタデータ） (2022-05-16T21:36:22Z)
• 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)
• Heavy-tailed Streaming Statistical Estimation [58.70341336199497]
  ストリーミング$p$のサンプルから重み付き統計推定の課題を考察する。 そこで我々は,傾きの雑音に対して,よりニュアンスな条件下での傾きの傾きの低下を設計し,より詳細な解析を行う。
  論文  参考訳（メタデータ） (2021-08-25T21:30:27Z)
• Nearest Neighbour Based Estimates of Gradients: Sharp Nonasymptotic Bounds and Applications [0.6445605125467573]
  勾配推定は統計学と学習理論において重要である。 ここでは古典的な回帰設定を考えると、実値の正方形可積分 r.v.$Y$ が予測される。 代替推定法で得られた値に対して, 漸近的境界が改良されることを証明した。
  論文  参考訳（メタデータ） (2020-06-26T15:19:43Z)
• Carath\'eodory Sampling for Stochastic Gradient Descent [79.55586575988292]
  本稿では,Tchakaloff と Carath'eodory の古典的な結果から着想を得た手法を提案する。 我々は、測定値の低減を行う降下ステップを適応的に選択する。 これをBlock Coordinate Descentと組み合わせることで、測定の削減を極めて安価に行えるようにします。
  論文  参考訳（メタデータ） (2020-06-02T17:52:59Z)
• Instability, Computational Efficiency and Statistical Accuracy [101.32305022521024]
  我々は,人口レベルでのアルゴリズムの決定論的収束率と,$n$サンプルに基づく経験的対象に適用した場合の(不安定性)の間の相互作用に基づいて,統計的精度を得るフレームワークを開発する。 本稿では,ガウス混合推定,非線形回帰モデル,情報的非応答モデルなど,いくつかの具体的なモデルに対する一般結果の応用について述べる。
  論文  参考訳（メタデータ） (2020-05-22T22:30:52Z)
• On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and Non-Asymptotic Concentration [115.1954841020189]
  The inequality and non-asymptotic properties of approximation procedure with Polyak-Ruppert averaging。 一定のステップサイズと無限大となる反復数を持つ平均的反復数に対する中心極限定理(CLT)を証明する。
  論文  参考訳（メタデータ） (2020-04-09T17:54:18Z)

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

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