論文の概要: Sharp Convergence Rates for Matching Pursuit
- arxiv url: http://arxiv.org/abs/2307.07679v1
- Date: Sat, 15 Jul 2023 01:53:09 GMT
- ステータス: 処理完了
- システム内更新日: 2023-07-18 18:38:01.426717
- 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 convergence rate
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 performance of
matching pursuit. We accomplish this by improving the existing lower bounds to
match the best upper bound. Specifically, we construct a worst case dictionary
which proves that the existing upper bound cannot be 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)の基本的な限界について検討する。
対象関数が辞書に対応する変動空間に含まれる場合、過去数十年にわたって多くの印象的な著作がマッチング追跡の収束率の上限を上下に求めてきたが、それらは一致しない。
本論文の主な貢献は, このギャップを埋めて, マッチング追従性能を鋭く評価することである。
既存の下界を最高の上界に合わせるように改良することでこれを達成します。
具体的には,既存の上限値が改善できないことを示す最悪の事例辞書を構築する。
他のグリーディアルゴリズムの変種とは異なり、収束率は準最適であり、ある非線型方程式の解によって決定される。
これにより、最悪の場合において、任意の量の縮小が一致追尾を改善すると結論付けることができる。
関連論文リスト
- Misspecified $Q$-Learning with Sparse Linear Function Approximation: Tight Bounds on Approximation Error [25.777423855881878]
我々は、$Oleft(Hepsilonright)$-optimal Policyを得ることができることを示す新しい除去アルゴリズムを示す。
我々は上界を$widetildeOmegaleft(Hepsilonright)$-optimality lower boundで補い、この問題の完全な図面を与える。
論文 参考訳（メタデータ） (2024-07-18T15:58:04Z) - Adaptive approximation of monotone functions [0.0]
GreedyBox が任意の関数 $f$ に対して,対数因子まで,最適なサンプル複雑性を実現することを証明した。
おそらく予想通り、GreedyBoxの$Lp(mu)$エラーは、アルゴリズムによって予測されるよりもはるかに高速な$C2$関数で減少する。
論文 参考訳（メタデータ） (2023-09-14T08:56:31Z) - Randomized Block-Coordinate Optimistic Gradient Algorithms for
Root-Finding Problems [8.0153031008486]
大規模設定における非線形方程式の解を近似する2つの新しいアルゴリズムを開発した。
我々は,機械学習における顕著な応用を網羅する大規模有限サム包含のクラスに,本手法を適用した。
論文 参考訳（メタデータ） (2023-01-08T21:46:27Z) - Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$
Geometry [69.24618367447101]
対数要因まで $(varepsilon,delta)$-differently private の最適過剰人口損失は $sqrtlog(d)/n + sqrtd/varepsilon n.$ です。
損失関数がさらなる滑らかさの仮定を満たすとき、余剰損失は$sqrtlog(d)/n + (log(d)/varepsilon n)2/3で上界(対数因子まで)であることが示される。
論文 参考訳（メタデータ） (2021-03-02T06:53:44Z) - Accelerating Optimization and Reinforcement Learning with
Quasi-Stochastic Approximation [2.294014185517203]
本稿では、収束理論を準確率近似に拡張することを目的とする。
強化学習のためのグラデーションフリー最適化とポリシー勾配アルゴリズムへの応用について説明する。
論文 参考訳（メタデータ） (2020-09-30T04:44:45Z) - Revisiting Modified Greedy Algorithm for Monotone Submodular
Maximization with a Knapsack Constraint [75.85952446237599]
修正されたグリードアルゴリズムは、近似係数が0.305$であることを示す。
最適なデータ依存上界を導出する。
また、分岐やバウンドといったアルゴリズムの効率を大幅に改善するためにも使うことができる。
論文 参考訳（メタデータ） (2020-08-12T15:40:21Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z) - Second-Order Information in Non-Convex Stochastic Optimization: Power
and Limitations [54.42518331209581]
私たちは発見するアルゴリズムを見つけます。
epsilon$-approximate stationary point ($|nabla F(x)|le epsilon$) using
$(epsilon,gamma)$surimateランダムランダムポイント。
ここでの私たちの下限は、ノイズのないケースでも新規です。
論文 参考訳（メタデータ） (2020-06-24T04:41:43Z) - Maximizing Determinants under Matroid Constraints [69.25768526213689]
我々は、$det(sum_i in Sv_i v_i v_itop)$が最大になるような基底を$S$$$$M$とする問題を研究する。
この問題は、実験的なデザイン、商品の公平な割り当て、ネットワーク設計、機械学習など、さまざまな分野に現れている。
論文 参考訳（メタデータ） (2020-04-16T19:16:38Z) - Agnostic Q-learning with Function Approximation in Deterministic
Systems: Tight Bounds on Approximation Error and Sample Complexity [94.37110094442136]
本稿では,決定論的システムにおける関数近似を用いたQ$学習の問題について検討する。
もし$delta = Oleft(rho/sqrtdim_Eright)$なら、$Oleft(dim_Eright)$を使って最適なポリシーを見つけることができる。
論文 参考訳（メタデータ） (2020-02-17T18:41:49Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。