論文の概要: Dimension-Free Bounds for Generalized First-Order Methods via Gaussian Coupling
- arxiv url: http://arxiv.org/abs/2508.10782v1
- Date: Thu, 14 Aug 2025 16:08:01 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-08-15 22:24:48.399364
- Title: Dimension-Free Bounds for Generalized First-Order Methods via Gaussian Coupling
- Title（参考訳）: ガウス結合による一般化一階法における次元自由境界
- Authors: Galen Reeves,
- Abstract要約: 一般化された一階反復アルゴリズムの有限サンプル上に漸近的でない境界を確立する。
一般化された一階法と条件付きガウス過程の反復関係を明示的に結合する。
この結合は、穏やかなリプシッツ条件とモーメントマッチング条件の下で、厳密で次元自由な境界をもたらす。
- 参考スコア（独自算出の注目度）: 6.402504044106936
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We establish non-asymptotic bounds on the finite-sample behavior of generalized first-order iterative algorithms -- including gradient-based optimization methods and approximate message passing (AMP) -- with Gaussian data matrices and full-memory, non-separable nonlinearities. The central result constructs an explicit coupling between the iterates of a generalized first-order method and a conditionally Gaussian process whose covariance evolves deterministically via a finite-dimensional state evolution recursion. This coupling yields tight, dimension-free bounds under mild Lipschitz and moment-matching conditions. Our analysis departs from classical inductive AMP proofs by employing a direct comparison between the generalized first-order method and the conditionally Gaussian comparison process. This approach provides a unified derivation of AMP theory for Gaussian matrices without relying on separability or asymptotics. A complementary lower bound on the Wasserstein distance demonstrates the sharpness of our upper bounds.
- Abstract（参考訳）: 一般化された一階反復アルゴリズムの有限サンプル挙動(勾配に基づく最適化法と近似メッセージパッシング(AMP)を含む)にガウス的データ行列と完全メモリ非分離非線形性を持つ漸近的境界を確立する。
中心的な結果は、一般化された一階法と有限次元状態の進化再帰を通じて共分散が決定的に進化する条件付きガウス過程の間の明示的な結合を構成する。
この結合は、穏やかなリプシッツ条件とモーメントマッチング条件の下で、厳密で次元自由な境界をもたらす。
解析は、一般化された一階法と条件付きガウス比較法とを直接比較することにより古典的帰納的AMP証明から逸脱する。
このアプローチは、分離性や漸近に頼らずにガウス行列に対するAMP理論の統一的導出を提供する。
ワッサーシュタイン距離の補的下界は、上界の鋭さを示す。
関連論文リスト
- Generalized Gradient Norm Clipping & Non-Euclidean $(L_0,L_1)$-Smoothness [51.302674884611335]
本研究は、急勾配と条件勾配のアプローチを組み合わせることでノルムクリッピングを一般化するハイブリッド非ユークリッド最適化手法を提案する。
本稿では、ディープラーニングのためのアルゴリズムのインスタンス化について論じ、画像分類と言語モデリングにおけるそれらの特性を実証する。
論文 参考訳（メタデータ） (2025-06-02T17:34:29Z) - Entropic Mirror Descent for Linear Systems: Polyak's Stepsize and Implicit Bias [55.72269695392027]
本稿では,線形系を解くためにエントロピックミラー降下を適用することに焦点を当てる。
収束解析の主な課題は、領域の非有界性に起因する。
制限的な仮定を課さずにこれを克服するために、Polyak型階段の変種を導入する。
論文 参考訳（メタデータ） (2025-05-05T12:33:18Z) - Online Learning Guided Curvature Approximation: A Quasi-Newton Method
with Global Non-Asymptotic Superlinear Convergence [22.286753988825048]
非漸近的超線形収束率を明示する最初の大域的収束準ニュートン法を提案する。
古典的準ニュートン法とは異なり、我々はハイブリッド近位外勾配法に基づいてアルゴリズムを構築する。
論文 参考訳（メタデータ） (2023-02-16T20:58:09Z) - Sharp global convergence guarantees for iterative nonconvex
optimization: A Gaussian process perspective [30.524043513721168]
回帰モデルのクラスに対する反復アルゴリズムの収束を解析するための一般的なレシピを開発する。
決定論的には、有限サンプル状態におけるアルゴリズムの収束率と最終的なエラーフロアの両方を正確にキャプチャする。
我々は、更新の交互化に基づく高次アルゴリズムと、下位次数に基づく一次アルゴリズムの両方に対して、鋭い収束率を示す。
論文 参考訳（メタデータ） (2021-09-20T21:48:19Z) - Nonlinear matrix recovery using optimization on the Grassmann manifold [18.655422834567577]
本研究では,列が部分空間の結合などの非線形構造に従う部分観測された高階クラスタリング行列の復元問題について検討する。
交代極限はクルディカ・ロジャシ性質を用いて一意点に収束することを示す。
論文 参考訳（メタデータ） (2021-09-13T16:13:13Z) - Pathwise Conditioning of Gaussian Processes [72.61885354624604]
ガウス過程後部をシミュレーションするための従来のアプローチでは、有限個の入力位置のプロセス値の限界分布からサンプルを抽出する。
この分布中心の特徴づけは、所望のランダムベクトルのサイズで3次スケールする生成戦略をもたらす。
条件付けのこのパスワイズ解釈が、ガウス過程の後部を効率的にサンプリングするのに役立てる近似の一般族をいかに生み出すかを示す。
論文 参考訳（メタデータ） (2020-11-08T17:09:37Z) - ROOT-SGD: Sharp Nonasymptotics and Near-Optimal Asymptotics in a Single Algorithm [71.13558000599839]
第一次アルゴリズムを用いて,厳密な凸と滑らかな非制約最適化問題の解法について検討する。
我々は,過去の勾配を平均化し,実装が容易な小説「Recursive One-Over-T SGD」を考案した。
有限サンプル, 漸近感覚, 感覚の両面において, 最先端の性能を同時に達成できることを実証する。
論文 参考訳（メタデータ） (2020-08-28T14:46:56Z) - Asymptotic Analysis of Conditioned Stochastic Gradient Descent [0.0]
本研究では、勾配方向の事前条件付けに基づいて、条件付きSGDと呼ばれる勾配降下法(SGD)アルゴリズムのクラスについて検討する。
ほぼ確実に、独立した関心を持つかもしれない収束結果が提示される。
論文 参考訳（メタデータ） (2020-06-04T10:08:05Z) - 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) - Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。
我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。
得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
論文 参考訳（メタデータ） (2020-02-21T17:45:32Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。