論文の概要: Sharp Convergence Rates for Matching Pursuit
- arxiv url: http://arxiv.org/abs/2307.07679v2
- Date: Tue, 25 Jul 2023 17:12:57 GMT
- ステータス: 処理完了
- システム内更新日: 2023-07-26 20:23:16.989894
- Title: Sharp Convergence Rates for Matching Pursuit
- Title(参考訳): マッチングにおけるシャープ収束率
- Authors: Jason M. Klusowski, Jonathan W. Siegel
- Abstract要約: 辞書からの要素の疎線型結合により対象関数を近似するためのマッチング探索の限界,すなわち純粋欲求アルゴリズムについて検討する。
我々は,既存の最上界が著しく改善できないことを示す最悪の事例辞書を構築した。
- 参考スコア(独自算出の注目度): 18.351254916713305
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study the fundamental limits of matching pursuit, or the pure greedy
algorithm, for approximating a target function by a sparse linear combination
of elements from a dictionary. When the target function is contained in the
variation space corresponding to the dictionary, many impressive works over the
past few decades have obtained upper and lower bounds on the error of matching
pursuit, but they do not match. The main contribution of this paper is to close
this gap and obtain a sharp characterization of the decay rate of matching
pursuit. Specifically, we construct a worst case dictionary which shows that
the existing best upper bound cannot be significantly improved. It turns out
that, unlike other greedy algorithm variants, the converge rate is suboptimal
and is determined by the solution to a certain non-linear equation. This
enables us to conclude that any amount of shrinkage improves matching pursuit
in the worst case.
- Abstract(参考訳): 辞書の要素のスパース線形結合によって対象関数を近似するためのマッチング追従法(pure greedy algorithm)の基本的な限界について検討する。
対象関数が辞書に対応する変動空間に含まれる場合、過去数十年にわたって多くの印象的な著作が一致追尾の誤差の上限を上下に設定してきたが、それらは一致していない。
本論文の主な貢献は, このギャップを閉じて, マッチング追従の減衰率を鋭く評価することである。
具体的には,既存の最上界を著しく改善できないことを示す最悪の事例辞書を構築した。
他のグリーディアルゴリズムの変種とは異なり、収束率は準最適であり、ある非線型方程式の解によって決定される。
これにより、最悪の場合において、任意の量の縮小が一致追尾を改善すると結論付けることができる。
関連論文リスト
- On the Last-Iterate Convergence of Shuffling Gradient Methods [25.831462008050387]
対象値に関して勾配法をシャッフルする際の最終点収束率を示す。
我々の結果は、(ほぼ)既存のラストイテレートの下限と一致するか、あるいは、平均的なイテレートの前の最高の上限と同速である。
論文 参考訳(メタデータ) (2024-03-12T15:01:17Z) - Faster Convergence with Multiway Preferences [99.68922143784306]
本稿では,符号関数に基づく比較フィードバックモデルについて考察し,バッチとマルチウェイの比較による収束率の解析を行う。
本研究は,マルチウェイ選好による凸最適化の問題を初めて研究し,最適収束率を解析するものである。
論文 参考訳(メタデータ) (2023-12-19T01:52:13Z) - Bayesian sparsity and class sparsity priors for dictionary learning and
coding [0.0]
本稿では,辞書マッチングプロセスを容易にする作業フローを提案する。
本稿では,辞書マッチングに関係のない部分辞書の同定を支援するため,ベイズ型データ駆動型グループ空間符号化手法を提案する。
辞書圧縮誤差を補正し、新規なグループ間隔プロモーションを用いて元の辞書をデフレートする効果を図示する。
論文 参考訳(メタデータ) (2023-09-02T17:54:23Z) - Deep Probabilistic Graph Matching [72.6690550634166]
本稿では,マッチング制約を伴わずに,元のQAPに適合する深層学習ベースのグラフマッチングフレームワークを提案する。
提案手法は,一般的な3つのベンチマーク(Pascal VOC,Wilow Object,SPair-71k)で評価され,すべてのベンチマークにおいて過去の最先端よりも優れていた。
論文 参考訳(メタデータ) (2022-01-05T13:37:27Z) - Mean-based Best Arm Identification in Stochastic Bandits under Reward
Contamination [80.53485617514707]
本稿では,ギャップベースアルゴリズムと逐次除去に基づく2つのアルゴリズムを提案する。
具体的には、ギャップベースのアルゴリズムでは、サンプルの複雑さは定数要素まで最適であり、連続的な除去では対数因子まで最適である。
論文 参考訳(メタデータ) (2021-11-14T21:49:58Z) - Automatic Vocabulary and Graph Verification for Accurate Loop Closure
Detection [21.862978912891677]
Bag-of-Words (BoW)は、機能と関連付け、ループを検出する視覚語彙を構築する。
本稿では,ノードの半径と特徴記述子のドリフトを比較することで,自然な収束基準を提案する。
本稿では,候補ループの検証のための新しいトポロジカルグラフ検証手法を提案する。
論文 参考訳(メタデータ) (2021-07-30T13:19:33Z) - Determinantal Beam Search [75.84501052642361]
ビームサーチは、ニューラルシーケンスモデルをデコードするためのゴーツー戦略である。
複数のソリューションを要求するユースケースでは、多様あるいは代表的なセットがしばしば望まれる。
ビームサーチを一連の部分決定問題として繰り返し行うことにより、アルゴリズムを多種多様なサブセット選択プロセスに変換することができる。
論文 参考訳(メタデータ) (2021-06-14T13:01:46Z) - Provably Convergent Working Set Algorithm for Non-Convex Regularized
Regression [0.0]
本稿では、収束保証付き非正則正規化器のためのワーキングセットアルゴリズムを提案する。
その結果,ブロックコーディネートや勾配ソルバの完全解法と比較して高い利得を示した。
論文 参考訳(メタデータ) (2020-06-24T07:40:31Z) - Exploiting Higher Order Smoothness in Derivative-free Optimization and
Continuous Bandits [99.70167985955352]
強凸関数のゼロ次最適化問題について検討する。
予測勾配降下アルゴリズムのランダム化近似を考察する。
その結果,0次アルゴリズムはサンプルの複雑性や問題パラメータの点でほぼ最適であることが示唆された。
論文 参考訳(メタデータ) (2020-06-14T10:42:23Z) - Consistency of a Recurrent Language Model With Respect to Incomplete
Decoding [67.54760086239514]
逐次言語モデルから無限長のシーケンスを受信する問題について検討する。
不整合に対処する2つの対策として、トップkと核サンプリングの一貫性のある変種と、自己終端の繰り返し言語モデルを提案する。
論文 参考訳(メタデータ) (2020-02-06T19:56:15Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。