論文の概要: State evolution beyond first-order methods I: Rigorous predictions and finite-sample guarantees

• arxiv url: http://arxiv.org/abs/2507.19611v1
• Date: Fri, 25 Jul 2025 18:28:09 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-07-29 16:23:55.775969
• Title: State evolution beyond first-order methods I: Rigorous predictions and finite-sample guarantees
• Title（参考訳）: 一階法を超えた状態進化 I:厳密な予測と有限サンプル保証
• Authors: Michael Celentano, Chen Cheng, Ashwin Pananjady, Kabir Aladin Verchand,
• Abstract要約: 確率データを用いた高次元非最適化問題のクラス上で反復アルゴリズムの正確な解析を行うためのツールボックスを開発する。 我々は、更新が座標的に分離できない場合でも維持できる厳格な状態の進化を確立する。 その過程で、関連する問題に有用な技術ツールキットを開発する。
• 参考スコア（独自算出の注目度）: 7.515612316198177
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We develop a toolbox for exact analysis of iterative algorithms on a class of high-dimensional nonconvex optimization problems with random data. While prior work has shown that low-dimensional statistics of (generalized) first-order methods can be predicted by a deterministic recursion known as state evolution, our focus is on developing such a prediction for a more general class of algorithms. We provide a state evolution for any method whose iterations are given by (possibly interleaved) first-order and saddle point updates, showing two main results. First, we establish a rigorous state evolution prediction that holds even when the updates are not coordinate-wise separable. Second, we establish finite-sample guarantees bounding the deviation of the empirical updates from the established state evolution. In the process, we develop a technical toolkit that may prove useful in related problems. One component of this toolkit is a general Hilbert space lifting technique to prove existence and uniqueness of a convenient parameterization of the state evolution. Another component of the toolkit combines a generic application of Bolthausen's conditioning method with a sequential variant of Gordon's Gaussian comparison inequality, and provides additional ingredients that enable a general finite-sample analysis.
• Abstract（参考訳）: ランダムデータを用いた高次元非凸最適化問題のクラス上で反復アルゴリズムの正確な解析を行うためのツールボックスを開発する。 先行研究により、(一般化された)一階法の低次元統計は、状態進化と呼ばれる決定論的再帰によって予測できることが示されているが、我々の焦点は、より一般的なアルゴリズムのクラスに対するそのような予測の開発である。 我々は、反復が(おそらくインターリーブされた)1次点とサドル点の更新によって与えられる任意のメソッドに対して状態進化を与え、2つの主要な結果を示す。 まず、更新が座標的に分離できない場合でも保持できる厳密な状態進化予測を確立する。 第2に、確立された状態進化からの経験的更新の逸脱を境界とする有限サンプルを保証する。 その過程で、関連する問題に有用な技術ツールキットを開発する。 このツールキットの1つの構成要素は、状態進化の便利なパラメータ化の存在と特異性を証明する一般的なヒルベルト空間リフト技術である。 このツールキットの別の構成要素は、ボルソーゼンの条件付け法の一般的な応用とゴードンのガウス比較の不等式(英語版)の逐次変種を組み合わせて、一般的な有限サンプル解析を可能にする追加の材料を提供する。

関連論文リスト

• Conformal Generative Modeling with Improved Sample Efficiency through Sequential Greedy Filtering [55.15192437680943]
  生成モデルは出力に対する厳密な統計的保証を欠いている。 厳密な統計的保証を満たす予測セットを生成する逐次共形予測法を提案する。 このことは、高い確率で予測セットが少なくとも1つの許容可能な(または有効な)例を含むことを保証している。
  論文  参考訳（メタデータ） (2024-10-02T15:26:52Z)
• Almost-sure convergence of iterates and multipliers in stochastic sequential quadratic optimization [21.022322975077653]
  等式制約付き連続最適化問題の解法が近年注目されている。 収束保証は、ゼロを測定するための勾配の期待値に制限されている。 また,SQPアルゴリズムにより生成した予備値,ラグランジュ測度,ステーション測度に対する新たなほぼ収束保証を証明した。
  論文  参考訳（メタデータ） (2023-08-07T16:03:40Z)
• Mutual Exclusivity Training and Primitive Augmentation to Induce Compositionality [84.94877848357896]
  最近のデータセットは、標準的なシーケンス・ツー・シーケンスモデルにおける体系的な一般化能力の欠如を露呈している。 本稿では,セq2seqモデルの振る舞いを分析し,相互排他バイアスの欠如と全例を記憶する傾向の2つの要因を同定する。 広範に使用されている2つの構成性データセット上で、標準的なシーケンス・ツー・シーケンスモデルを用いて、経験的改善を示す。
  論文  参考訳（メタデータ） (2022-11-28T17:36:41Z)
• Explicit Second-Order Min-Max Optimization Methods with Optimal Convergence Guarantee [86.05440220344755]
  我々は,非制約のmin-max最適化問題のグローバルなサドル点を求めるために,不正確な正規化ニュートン型手法を提案し,解析する。 提案手法は有界集合内に留まるイテレートを生成し、その反復は制限関数の項で$O(epsilon-2/3)$内の$epsilon$-saddle点に収束することを示す。
  論文  参考訳（メタデータ） (2022-10-23T21:24:37Z)
• Alternating minimization for generalized rank one matrix sensing: Sharp predictions from a random initialization [5.900674344455754]
  ランクランダム行列の特性をdで推定する手法を示す。 鋭い収束は、単一のステップで正確な回復を保証する。 我々の分析は、この問題の他のいくつかの特性も明らかにしている。
  論文  参考訳（メタデータ） (2022-07-20T05:31:05Z)
• End-to-end symbolic regression with transformers [20.172752966322214]
  シンボリック・マグニチュード・レグレッションは、通常、2段階の手順を高速に予測する難しいタスクである。 本稿では,本モデルが情報変換器としてニューラル・ザ・定数にアプローチしていることを示す。
  論文  参考訳（メタデータ） (2022-04-22T06:55:43Z)
• Sharp global convergence guarantees for iterative nonconvex optimization: A Gaussian process perspective [30.524043513721168]
  回帰モデルのクラスに対する反復アルゴリズムの収束を解析するための一般的なレシピを開発する。 決定論的には、有限サンプル状態におけるアルゴリズムの収束率と最終的なエラーフロアの両方を正確にキャプチャする。 我々は、更新の交互化に基づく高次アルゴリズムと、下位次数に基づく一次アルゴリズムの両方に対して、鋭い収束率を示す。
  論文  参考訳（メタデータ） (2021-09-20T21:48:19Z)
• Recent Theoretical Advances in Non-Convex Optimization [56.88981258425256]
  近年、深層ネットワークにおける非最適化アルゴリズムの解析やデータ問題への関心が高まっており、非最適化のための理論的最適化アルゴリズムの最近の結果の概要を概説する。
  論文  参考訳（メタデータ） (2020-12-11T08:28:51Z)
• Random extrapolation for primal-dual coordinate descent [61.55967255151027]
  本稿では,データ行列の疎度と目的関数の好適な構造に適応する,ランダムに外挿した原始-双対座標降下法を提案する。 一般凸凹の場合, 主対差と目的値に対するシーケンスのほぼ確実に収束と最適サブ線形収束率を示す。
  論文  参考訳（メタデータ） (2020-07-13T17:39:35Z)
• When Does Preconditioning Help or Hurt Generalization? [74.25170084614098]
  本稿では,第1次および第2次手法のテキスト単純バイアスが一般化特性の比較にどのように影響するかを示す。 本稿では、バイアス分散トレードオフを管理するためのいくつかのアプローチと、GDとNGDを補間する可能性について論じる。
  論文  参考訳（メタデータ） (2020-06-18T17:57:26Z)
• Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
  このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。 我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。 得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
  論文  参考訳（メタデータ） (2020-02-21T17:45:32Z)

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

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