論文の概要: Iteratively Reweighted Least Squares for $\ell_1$-minimization with
Global Linear Convergence Rate
- arxiv url: http://arxiv.org/abs/2012.12250v2
- Date: Fri, 15 Jan 2021 16:12:40 GMT
- ステータス: 処理完了
- システム内更新日: 2021-04-26 07:12:30.348072
- Title: Iteratively Reweighted Least Squares for $\ell_1$-minimization with
Global Linear Convergence Rate
- Title（参考訳）: 大域的線形収束率をもつ$\ell_1$-minimizationのための反復重み付き最小方形
- Authors: Christian K\"ummerle, Claudio Mayrink Verdun, Dominik St\"oger
- Abstract要約: 反復重み付き最小広場(IRLS)は非滑らかな最適化のための重要なアルゴリズム群である。
我々は、$ell_$-minimization に対する IRLS が、グローバルな線形レートを持つスパース解に収束することを証明する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Iteratively Reweighted Least Squares (IRLS), whose history goes back more
than 80 years, represents an important family of algorithms for non-smooth
optimization as it is able to optimize these problems by solving a sequence of
linear systems. In 2010, Daubechies, DeVore, Fornasier, and G\"unt\"urk proved
that IRLS for $\ell_1$-minimization, an optimization program ubiquitous in the
field of compressed sensing, globally converges to a sparse solution. While
this algorithm has been popular in applications in engineering and statistics,
fundamental algorithmic questions have remained unanswered. As a matter of
fact, existing convergence guarantees only provide global convergence without
any rate, except for the case that the support of the underlying signal has
already been identified. In this paper, we prove that IRLS for
$\ell_1$-minimization converges to a sparse solution with a global linear rate.
We support our theory by numerical experiments indicating that our linear rate
essentially captures the correct dimension dependence.
- Abstract（参考訳）: 繰り返し再重み付き最小広場(IRLS)は80年以上の歴史を遡るが、線形系の列を解くことでこれらの問題を最適化できるため、非滑らかな最適化のための重要なアルゴリズム群である。
2010年、daubechies、devore、fornasier、g\"unt\"urkは、圧縮センシングの分野でユビキタスな最適化プログラムである$\ell_1$-minimizationのirlsが、グローバルに疎解に収束することを示した。
このアルゴリズムは工学や統計学の分野で人気があるが、基本的なアルゴリズムの問題は未解決のままである。
実のところ、既存の収束は、基礎となる信号の支持が既に特定されている場合を除いて、いかなるレートも持たないグローバル収束のみを保証している。
本稿では,$\ell_1$-minimization に対する irls が大域的線形率のスパース解に収束することを示す。
我々は線形速度が本質的に正しい次元依存を捉えることを示す数値実験によって理論を支持する。
関連論文リスト
- Online Learning Guided Quasi-Newton Methods with Global Non-Asymptotic Convergence [20.766358513158206]
双対性ギャップの観点から、大域収束率を$O(min1/k,sqrtd/k1.25)$とする。
これらの結果は、外勾配法よりも準ニュートン法の証明可能な利点を示す最初の大域収束結果である。
論文 参考訳（メタデータ） (2024-10-03T16:08:16Z) - A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。
提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
論文 参考訳（メタデータ） (2024-09-07T06:37:23Z) - Stable Nonconvex-Nonconcave Training via Linear Interpolation [51.668052890249726]
本稿では,ニューラルネットワークトレーニングを安定化(大規模)するための原理的手法として,線形アヘッドの理論解析を提案する。
最適化過程の不安定性は、しばしば損失ランドスケープの非単調性によって引き起こされるものであり、非拡張作用素の理論を活用することによって線型性がいかに役立つかを示す。
論文 参考訳（メタデータ） (2023-10-20T12:45:12Z) - Constrained Optimization via Exact Augmented Lagrangian and Randomized
Iterative Sketching [55.28394191394675]
等式制約付き非線形非IBS最適化問題に対する適応的不正確なニュートン法を開発した。
ベンチマーク非線形問題,LVMのデータによる制約付きロジスティック回帰,PDE制約問題において,本手法の優れた性能を示す。
論文 参考訳（メタデータ） (2023-05-28T06:33:37Z) - Globally Convergent Policy Search over Dynamic Filters for Output
Estimation [64.90951294952094]
我々は,大域的に最適な$textitdynamic$ filterに収束する最初の直接ポリシー探索アルゴリズム凸を導入する。
我々は、情報化が前述の優越性を克服していることを示す。
論文 参考訳（メタデータ） (2022-02-23T18:06:20Z) - A framework for bilevel optimization that enables stochastic and global
variance reduction algorithms [17.12280360174073]
双レベル最適化は、他の関数のarg最小値を含む値関数を最小化する問題である。
本稿では, 内部問題の解, 線形系の解, 主変数を同時に発展させる新しい枠組みを提案する。
我々のフレームワークにおけるSAGAアルゴリズムの適応であるSABAは$O(frac1T)$収束率を持ち、Polyak-Lojasciewicz仮定の下で線形収束を達成することを示した。
論文 参考訳（メタデータ） (2022-01-31T18:17:25Z) - PROMPT: Parallel Iterative Algorithm for $\ell_{p}$ norm linear
regression via Majorization Minimization with an application to
semi-supervised graph learning [0.0]
スパースリカバリ,データクラスタリング,半教師付き学習など,いくつかの応用がある。
我々は、MajolizaTion Minimization (PROMPT)による$ell_P$ノルム回帰のための並列反復AlgOrithMを提案する。
論文 参考訳（メタデータ） (2021-10-23T10:19:11Z) - Linear regression with partially mismatched data: local search with
theoretical guarantees [9.398989897176953]
本稿では,予測と応答のペアが部分的に一致しない線形回帰の重要な変種について検討する。
最適化定式化を用いて、基礎となる回帰係数とミスマッチに対応する置換を同時に学習する。
我々は,局所探索アルゴリズムが線形速度でほぼ最適解に収束することを証明した。
論文 参考訳（メタデータ） (2021-06-03T23:32:12Z) - Recent Theoretical Advances in Non-Convex Optimization [56.88981258425256]
近年、深層ネットワークにおける非最適化アルゴリズムの解析やデータ問題への関心が高まっており、非最適化のための理論的最適化アルゴリズムの最近の結果の概要を概説する。
論文 参考訳（メタデータ） (2020-12-11T08:28:51Z) - An Asymptotically Optimal Primal-Dual Incremental Algorithm for
Contextual Linear Bandits [129.1029690825929]
複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。
非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
論文 参考訳（メタデータ） (2020-10-23T09:12:47Z) - Provably Convergent Working Set Algorithm for Non-Convex Regularized
Regression [0.0]
本稿では、収束保証付き非正則正規化器のためのワーキングセットアルゴリズムを提案する。
その結果,ブロックコーディネートや勾配ソルバの完全解法と比較して高い利得を示した。
論文 参考訳（メタデータ） (2020-06-24T07:40:31Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。