論文の概要: Sharp global convergence guarantees for iterative nonconvex
optimization: A Gaussian process perspective
- arxiv url: http://arxiv.org/abs/2109.09859v1
- Date: Mon, 20 Sep 2021 21:48:19 GMT
- ステータス: 処理完了
- システム内更新日: 2021-09-22 14:08:24.891236
- Title: Sharp global convergence guarantees for iterative nonconvex
optimization: A Gaussian process perspective
- Title（参考訳）: シャープ大域収束保証による反復非凸最適化:ガウス過程の観点から
- Authors: Kabir Aladin Chandrasekher, Ashwin Pananjady, Christos Thrampoulidis
- Abstract要約: 回帰モデルのクラスに対する反復アルゴリズムの収束を解析するための一般的なレシピを開発する。
決定論的には、有限サンプル状態におけるアルゴリズムの収束率と最終的なエラーフロアの両方を正確にキャプチャする。
我々は、更新の交互化に基づく高次アルゴリズムと、下位次数に基づく一次アルゴリズムの両方に対して、鋭い収束率を示す。
- 参考スコア（独自算出の注目度）: 30.524043513721168
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider a general class of regression models with normally distributed
covariates, and the associated nonconvex problem of fitting these models from
data. We develop a general recipe for analyzing the convergence of iterative
algorithms for this task from a random initialization. In particular, provided
each iteration can be written as the solution to a convex optimization problem
satisfying some natural conditions, we leverage Gaussian comparison theorems to
derive a deterministic sequence that provides sharp upper and lower bounds on
the error of the algorithm with sample-splitting. Crucially, this deterministic
sequence accurately captures both the convergence rate of the algorithm and the
eventual error floor in the finite-sample regime, and is distinct from the
commonly used "population" sequence that results from taking the
infinite-sample limit. We apply our general framework to derive several
concrete consequences for parameter estimation in popular statistical models
including phase retrieval and mixtures of regressions. Provided the sample size
scales near-linearly in the dimension, we show sharp global convergence rates
for both higher-order algorithms based on alternating updates and first-order
algorithms based on subgradient descent. These corollaries, in turn, yield
multiple consequences, including: (a) Proof that higher-order algorithms can
converge significantly faster than their first-order counterparts (and
sometimes super-linearly), even if the two share the same population update and
(b) Intricacies in super-linear convergence behavior for higher-order
algorithms, which can be nonstandard (e.g., with exponent 3/2) and sensitive to
the noise level in the problem. We complement these results with extensive
numerical experiments, which show excellent agreement with our theoretical
predictions.
- Abstract（参考訳）: 正規分布共変量を持つ回帰モデルの一般的なクラスと、これらのモデルをデータから適合させる非凸問題を考える。
ランダム初期化から反復アルゴリズムの収束を解析するための一般的な手法を開発した。
特に、各反復がいくつかの自然条件を満たす凸最適化問題の解として書けることを条件として、ガウス比較定理を利用して、サンプル分割によるアルゴリズムの誤差に鋭い上下境界を与える決定論的列を導出する。
この決定論的シーケンスは、有限サンプルレジームにおけるアルゴリズムの収束率と結果誤差階の両方を正確に捉え、無限サンプルリミットを取ることによって得られる一般的な「人口」列とは区別される。
本手法は, 位相検索や回帰の混合など, 一般的な統計モデルにおけるパラメータ推定の具体的結果の導出に応用する。
サンプルサイズスケールを次元で近似すると,交互更新に基づく高次アルゴリズムと下位降下に基づく一階アルゴリズムの両方に対して,鋭い大域収束率を示す。
これらの系図は、次を含む複数の結果をもたらす。
(a)高次アルゴリズムが1次アルゴリズムよりもはるかに早く収束できること(時として超直線的に)は、たとえ2つのアルゴリズムが同じ人口の更新を共有しているとしても証明する。
(b)高次アルゴリズムにおける超線形収束挙動の複雑さは、非標準(指数 3/2 の場合など)であり、問題のノイズレベルに敏感である。
これらの結果を広範な数値実験で補完し,理論的な予測とよく一致した。
関連論文リスト
- Last Iterate Convergence of Incremental Methods and Applications in Continual Learning [10.811735264028348]
連続学習における応用により、漸進的勾配法と漸進的近位法の両方の最後の繰り返しに対する収束保証を得る。
一般化を伴う連続学習のモデルとしての漸進的近位法について検討し,大惨な忘れ込みを防ぐために大量の正規化が不可欠であると主張している。
論文 参考訳（メタデータ） (2024-03-11T16:24:26Z) - High-Probability Bounds for Stochastic Optimization and Variational
Inequalities: the Case of Unbounded Variance [59.211456992422136]
制約の少ない仮定の下で高確率収束結果のアルゴリズムを提案する。
これらの結果は、標準機能クラスに適合しない問題を最適化するために検討された手法の使用を正当化する。
論文 参考訳（メタデータ） (2023-02-02T10:37:23Z) - Robust empirical risk minimization via Newton's method [9.797319790710711]
実験的リスク最小化のためのニュートン法の新しい変種について検討した。
目的関数の勾配と Hessian は、ロバストな推定器に置き換えられる。
また,共役勾配法に基づくニュートン方向のロバストな解を求めるアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-01-30T18:54:54Z) - Stochastic Mirror Descent for Large-Scale Sparse Recovery [13.500750042707407]
本稿では,2次近似の高次元スパースパラメータの統計的推定への応用について論じる。
提案アルゴリズムは, 回帰器分布の弱い仮定の下で, 推定誤差の最適収束を実現する。
論文 参考訳（メタデータ） (2022-10-23T23:23:23Z) - Alternating minimization for generalized rank one matrix sensing: Sharp predictions from a random initialization [5.900674344455754]
ランクランダム行列の特性をdで推定する手法を示す。
鋭い収束は、単一のステップで正確な回復を保証する。
我々の分析は、この問題の他のいくつかの特性も明らかにしている。
論文 参考訳（メタデータ） (2022-07-20T05:31:05Z) - First-Order Algorithms for Nonlinear Generalized Nash Equilibrium
Problems [88.58409977434269]
非線形一般化ナッシュ均衡問題(NGNEP)における平衡計算の問題を考える。
我々の貢献は、2次ペナルティ法と拡張ラグランジアン法に基づく2つの単純な一階アルゴリズムフレームワークを提供することである。
これらのアルゴリズムに対する漸近的理論的保証を提供する。
論文 参考訳（メタデータ） (2022-04-07T00:11:05Z) - Information-Theoretic Generalization Bounds for Iterative
Semi-Supervised Learning [81.1071978288003]
特に,情報理論の原理を用いて,反復型SSLアルゴリズムのエミュレータ一般化誤差の振る舞いを理解することを目的とする。
我々の理論的結果は、クラス条件分散があまり大きくない場合、一般化誤差の上限は反復数とともに単調に減少するが、すぐに飽和することを示している。
論文 参考訳（メタデータ） (2021-10-03T05:38:49Z) - High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。
非滑らか凸最適化の既存の方法は、信頼度に依存した複雑性境界を持つ。
そこで我々は,勾配クリッピングを伴う2つの手法に対して,新たなステップサイズルールを提案する。
論文 参考訳（メタデータ） (2021-06-10T17:54:21Z) - Provably Convergent Working Set Algorithm for Non-Convex Regularized
Regression [0.0]
本稿では、収束保証付き非正則正規化器のためのワーキングセットアルゴリズムを提案する。
その結果,ブロックコーディネートや勾配ソルバの完全解法と比較して高い利得を示した。
論文 参考訳（メタデータ） (2020-06-24T07:40:31Z) - Convergence of adaptive algorithms for weakly convex constrained
optimization [59.36386973876765]
モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。
我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
論文 参考訳（メタデータ） (2020-06-11T17:43:19Z) - Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。
我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。
得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
論文 参考訳（メタデータ） (2020-02-21T17:45:32Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。