論文の概要: Sparse Convex Optimization via Adaptively Regularized Hard Thresholding
- arxiv url: http://arxiv.org/abs/2006.14571v1
- Date: Thu, 25 Jun 2020 17:16:21 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-17 03:39:20.195312
- Title: Sparse Convex Optimization via Adaptively Regularized Hard Thresholding
- Title（参考訳）: 適応正規化ハードThresholdingによるスパース凸最適化
- Authors: Kyriakos Axiotis and Maxim Sviridenko
- Abstract要約: 本稿では,適応正規化ハードThresholding (ARHT) アルゴリズムを提案する。
また、OMP with Replacement (OMPR) for general $f$, under the condition $s > s* frackappa24$。
- 参考スコア（独自算出の注目度）: 17.60502131429094
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The goal of Sparse Convex Optimization is to optimize a convex function $f$
under a sparsity constraint $s\leq s^*\gamma$, where $s^*$ is the target number
of non-zero entries in a feasible solution (sparsity) and $\gamma\geq 1$ is an
approximation factor. There has been a lot of work to analyze the sparsity
guarantees of various algorithms (LASSO, Orthogonal Matching Pursuit (OMP),
Iterative Hard Thresholding (IHT)) in terms of the Restricted Condition Number
$\kappa$. The best known algorithms guarantee to find an approximate solution
of value $f(x^*)+\epsilon$ with the sparsity bound of $\gamma =
O\left(\kappa\min\left\{\log \frac{f(x^0)-f(x^*)}{\epsilon},
\kappa\right\}\right)$, where $x^*$ is the target solution. We present a new
Adaptively Regularized Hard Thresholding (ARHT) algorithm that makes
significant progress on this problem by bringing the bound down to
$\gamma=O(\kappa)$, which has been shown to be tight for a general class of
algorithms including LASSO, OMP, and IHT. This is achieved without significant
sacrifice in the runtime efficiency compared to the fastest known algorithms.
We also provide a new analysis of OMP with Replacement (OMPR) for general $f$,
under the condition $s > s^* \frac{\kappa^2}{4}$, which yields Compressed
Sensing bounds under the Restricted Isometry Property (RIP). When compared to
other Compressed Sensing approaches, it has the advantage of providing a strong
tradeoff between the RIP condition and the solution sparsity, while working for
any general function $f$ that meets the RIP condition.
- Abstract（参考訳）: Sparse Convex Optimization の目標は、余剰制約の下で凸関数 $f$ を最適化することである。$s\leq s^*\gamma$, ここで、$s^*$ は実現可能な解(スパーシティ)におけるゼロでないエントリのターゲット数であり、$\gamma\geq 1$ は近似係数である。
制限条件番号$\kappa$の観点で、様々なアルゴリズム(LASSO, Orthogonal Matching Pursuit (OMP), Iterative Hard Thresholding (IHT))のスパーシビリティ保証を分析する作業が数多く行われている。
最もよく知られたアルゴリズムは、$\gamma = o\left(\kappa\min\left\{\log \frac{f(x^0)-f(x^*)}{\epsilon}, \kappa\right\}\right)$ のスパーシティ境界を持つ値 $f(x^*)+\epsilon$ の近似解を見つけることを保証する。
本稿では,適応正規化ハードThresholding (ARHT) アルゴリズムを提案する。このアルゴリズムは, LASSO, OMP, IHT などのアルゴリズムの一般クラスに対して厳密であることを示す$\gamma=O(\kappa)$に値下げすることで,この問題を大幅に進展させる。
これは、既知のアルゴリズムと比較してランタイム効率を大幅に犠牲にすることなく実現されている。
また, s > s^* \frac{\kappa^2}{4}$ という条件下では, s > s^* \frac{\kappa^2}{4}$ で omp with replacement (ompr) の新たな解析法を提案する。
他の圧縮センシングアプローチと比較すると、rip条件と解スパーシティの間の強いトレードオフを提供し、rip条件を満たす任意の一般的な関数$f$で作業する利点がある。
関連論文リスト
- 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) - Lower Bounds on the Worst-Case Complexity of Efficient Global
Optimization [11.523746174066702]
我々は、その対応する再生核ヒルベルト空間(RKHS)における球の計量エントロピーの観点から、効率的な大域最適化の複雑さに対する統一された下界を導出する。
この下界は、一般に使用される2乗指数核とマタン核の非適応探索アルゴリズムによって達成された上界にほぼ一致することを示す。
論文 参考訳（メタデータ） (2022-09-20T11:57:13Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - Iterative Hard Thresholding with Adaptive Regularization: Sparser
Solutions Without Sacrificing Runtime [17.60502131429094]
本稿では,条件数関数としてスペーサー解を復元する反復型ハードしきい値決定アルゴリズムの簡単な修正を提案する。
提案するアルゴリズムである正規化IHTは、疎度$O(skappa)$の解を返す。
我々のアルゴリズムはARHTよりも大幅に改善され、またスパーシティ$O(skappa)$の解も見つかる。
論文 参考訳（メタデータ） (2022-04-11T19:33:15Z) - Nearly Optimal Policy Optimization with Stable at Any Time Guarantee [53.155554415415445]
citetshani 2020optimisticのポリシーベースのメソッドは、$tildeO(sqrtSAH3K + sqrtAH4K)$である。$S$は状態の数、$A$はアクションの数、$H$は地平線、$K$はエピソードの数、$sqrtSH$は情報理論の下限の$tildeOmega(sqrtSAH)と比べてギャップがある。
論文 参考訳（メタデータ） (2021-12-21T01:54:17Z) - Gaussian Process Bandit Optimization with Few Batches [49.896920704012395]
有限腕バンディットアルゴリズムにインスパイアされたバッチアルゴリズムを導入する。
O(log T)$ batches in time horizon $T$.sqrtTgamma_T)$ using $O(log T)$ batches in time horizon。
さらに,アルゴリズムの修正版を提案し,バッチ数によって後悔がどう影響するかを特徴付ける。
論文 参考訳（メタデータ） (2021-10-15T00:54:04Z) - 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) - Local Search Algorithms for Rank-Constrained Convex Optimization [7.736462653684946]
階数制約付き凸最適化のための欲望と局所探索アルゴリズムを提案する。
我々は、$R$のランク制限条件番号が$kappa$であれば、$A$のランク$O(r*cdot minkappa log fracR(mathbf0)-R(A*)epsilon、kappa2)$と$R(A)leq R(A*)+epsilon$のソリューションが回復できることを示しています。
論文 参考訳（メタデータ） (2021-01-15T18:52:02Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。