論文の概要: The Trimmed Lasso: Sparse Recovery Guarantees and Practical Optimization
by the Generalized Soft-Min Penalty
- arxiv url: http://arxiv.org/abs/2005.09021v3
- Date: Thu, 17 Jun 2021 21:44:57 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-01 23:22:59.267235
- Title: The Trimmed Lasso: Sparse Recovery Guarantees and Practical Optimization
by the Generalized Soft-Min Penalty
- Title（参考訳）: Trimmed Lasso:スパースリカバリ保証と一般ソフトミン罰の実践的最適化
- Authors: Tal Amir, Ronen Basri, Boaz Nadler
- Abstract要約: 本稿では,古典ラッソと一般パターンを補間するスパース近似あるいは最良部分集合の解法を提案する。
我々は、一般的なソフトミンペナルティを計算するためにスパースタイムを導出する。
- 参考スコア（独自算出の注目度）: 14.85926834924458
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We present a new approach to solve the sparse approximation or best subset
selection problem, namely find a $k$-sparse vector ${\bf x}\in\mathbb{R}^d$
that minimizes the $\ell_2$ residual $\lVert A{\bf x}-{\bf y} \rVert_2$. We
consider a regularized approach, whereby this residual is penalized by the
non-convex $\textit{trimmed lasso}$, defined as the $\ell_1$-norm of ${\bf x}$
excluding its $k$ largest-magnitude entries. We prove that the trimmed lasso
has several appealing theoretical properties, and in particular derive sparse
recovery guarantees assuming successful optimization of the penalized
objective. Next, we show empirically that directly optimizing this objective
can be quite challenging. Instead, we propose a surrogate for the trimmed
lasso, called the $\textit{generalized soft-min}$. This penalty smoothly
interpolates between the classical lasso and the trimmed lasso, while taking
into account all possible $k$-sparse patterns. The generalized soft-min penalty
involves summation over $\binom{d}{k}$ terms, yet we derive a polynomial-time
algorithm to compute it. This, in turn, yields a practical method for the
original sparse approximation problem. Via simulations, we demonstrate its
competitive performance compared to current state of the art.
- Abstract（参考訳）: すなわち、$k$-スパースベクトル ${\bf x}\in\mathbb{r}^d$ を見つけ、$\ell_2$ 残余 $\lvert a{\bf x}-{\bf y} \rvert_2$ を最小化する。
我々は、この残差が非凸の$\textit{trimmed lasso}$でペナルティ化され、その$k$の最大マグニチュードエントリを除いて$\ell_1$-norm of ${\bf x}$と定義される正規化アプローチを考える。
トリミングしたラッソにはいくつかの魅力的な理論的性質があることを証明し、特に厳格化目的の最適化が成功すると仮定してスパースリカバリの保証を導出する。
次に,この目的を直接最適化することは極めて困難であることを示す。
代わりに、$\textit{ generalized soft-min}$ と呼ばれるトリミングされたラッソの代名詞を提案する。
このペナルティは古典ラッソとトリミングラッソの間を円滑に補間し、可能なすべての$k$スパースパターンを考慮に入れている。
一般化されたソフトミンペナルティは、$\binom{d}{k}$項の和を含むが、多項式時間アルゴリズムを導出して計算する。
これにより、元のスパース近似問題の実用的な方法が得られる。
シミュレーションにより,現在の技術と比較して,その競争性能を実証する。
関連論文リスト
- Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳（メタデータ） (2024-02-14T07:52:00Z) - Revisiting Inexact Fixed-Point Iterations for Min-Max Problems: Stochasticity and Structured Nonconvexity [18.427215139020632]
1L 1$は、マルチレベルなCarloイテレーションであっても、最先端の問題を改善するために使用できることを示す。
解に関する唯一のホールドが新しい1L 1$理論である場合、不正確なハルパーネス推定器を1L 1$で解析する。
論文 参考訳（メタデータ） (2024-02-07T18:22:41Z) - Certified Multi-Fidelity Zeroth-Order Optimization [4.450536872346658]
様々な近似レベルで関数を$f$で評価できる多要素ゼロ階最適化の問題を考察する。
我々は、MFDOOアルゴリズムの証明された変種を提案し、そのコスト複雑性を任意のリプシッツ関数$f$に対して有界に導出する。
また、このアルゴリズムがほぼ最適コストの複雑さを持つことを示す$f$-dependent lower boundも証明する。
論文 参考訳（メタデータ） (2023-08-02T07:20:37Z) - An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue
Optimization Problems [76.2042837251496]
相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。
注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。
本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
論文 参考訳（メタデータ） (2023-06-30T08:34:29Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - Saddle Point Optimization with Approximate Minimization Oracle [8.680676599607125]
サドル点最適化に対する主要なアプローチである$min_xmax_y f(x, y)$は、GAN(Generative Adversarial Network)によって一般化される勾配に基づくアプローチである。
対照的に、最小化問題を解くオラクルのみに依存する代替手法を解析する。
我々のアプローチでは、近似解 $x'$ と $y'$ to $min_x'f(x', y)$ を与えられた点 $(x, y)$ に配置し、これらの近似解 $(x', y)$ に更新する。
論文 参考訳（メタデータ） (2021-03-29T23:03:24Z) - 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) - Revisiting Modified Greedy Algorithm for Monotone Submodular
Maximization with a Knapsack Constraint [75.85952446237599]
修正されたグリードアルゴリズムは、近似係数が0.305$であることを示す。
最適なデータ依存上界を導出する。
また、分岐やバウンドといったアルゴリズムの効率を大幅に改善するためにも使うことができる。
論文 参考訳（メタデータ） (2020-08-12T15:40:21Z) - Stochastic Bandits with Linear Constraints [69.757694218456]
制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。
楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-17T22:32:19Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。