論文の概要: Piecewise Linearity of Min-Norm Solution Map of a Nonconvexly Regularized Convex Sparse Model

• arxiv url: http://arxiv.org/abs/2311.18438v3
• Date: Tue, 12 Nov 2024 15:57:13 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-13 13:16:03.985381
• Title: Piecewise Linearity of Min-Norm Solution Map of a Nonconvexly Regularized Convex Sparse Model
• Title（参考訳）: 非凸正則凸スパースモデルのミニノーム解写像の最適線形性
• Authors: Yi Zhang, Isao Yamada,
• Abstract要約: 本稿では,各直線領域における定数空間パターン $mathbfx_star(mathbfy,da)$ について検討する。 各線形ゾーンにおける $mathbfx_star(mathbfy,da)$ の閉形式式を反復的に計算する。
• 参考スコア（独自算出の注目度）: 8.586951231230596
• License:
• Abstract: It is well known that the minimum $\ell_2$-norm solution of the convex LASSO model, say $\mathbf{x}_{\star}$, is a continuous piecewise linear function of the regularization parameter $\lambda$, and its signed sparsity pattern is constant within each linear piece. The current study is an extension of this classic result, proving that the aforementioned properties extend to the min-norm solution map $\mathbf{x}_{\star}(\mathbf{y},\lambda)$, where $\mathbf{y}$ is the observed signal, for a generalization of LASSO termed the scaled generalized minimax concave (sGMC) model. The sGMC model adopts a nonconvex debiased variant of the $\ell_1$-norm as sparse regularizer, but its objective function is overall-convex. Based on the geometric properties of $\mathbf{x}_{\star}(\mathbf{y},\lambda)$, we propose an extension of the least angle regression (LARS) algorithm, which iteratively computes the closed-form expression of $\mathbf{x}_{\star}(\mathbf{y},\lambda)$ in each linear zone. Under suitable conditions, the proposed algorithm provably obtains the whole solution map $\mathbf{x}_{\star}(\mathbf{y},\lambda)$ within finite iterations. Notably, our proof techniques for establishing continuity and piecewise linearity of $\mathbf{x}_{\star}(\mathbf{y},\lambda)$ are novel, and they lead to two side contributions: (a) our proofs establish continuity of the sGMC solution set as a set-valued mapping of $(\mathbf{y},\lambda)$; (b) to prove piecewise linearity and piecewise constant sparsity pattern of $\mathbf{x}_{\star}(\mathbf{y},\lambda)$, we do not require any assumption that previous work relies on (whereas to prove some additional properties of $\mathbf{x}_{\star}(\mathbf{y},\lambda)$, we use a different set of assumptions from previous work).
• Abstract（参考訳）: 凸 LASSO モデルの最小$\ell_2$-norm 解、例えば $\mathbf{x}_{\star}$ が正規化パラメータ $\lambda$ の連続部分線型関数であることはよく知られている。 現在の研究は、この古典的な結果の拡張であり、上記の性質がミンノルム解写像 $\mathbf{x}_{\star}(\mathbf{y},\lambda)$, ここで、$\mathbf{y}$ は観測信号であり、LASSO の一般化はスケール化された一般化されたミニマックス凹体 (sGMC) モデル (scaled generalized minimax concave) と呼ばれる。 sGMCモデルはスパース正則化器として$\ell_1$-normの非凸デバイアス付き変種を採用するが、その目的関数は全体凸である。 我々は、$\mathbf{x}_{\star}(\mathbf{y},\lambda)$の幾何学的性質に基づいて、各線形ゾーンにおける$\mathbf{x}_{\star}(\mathbf{y},\lambda)$の閉形式式を反復的に計算する最小角度回帰(LARS)アルゴリズムの拡張を提案する。 適切な条件下では、提案アルゴリズムは有限反復の内の解写像 $\mathbf{x}_{\star}(\mathbf{y},\lambda)$ を証明的に得る。 特に、$\mathbf{x}_{\star}(\mathbf{y},\lambda)$ の連続性と個性線形性を確立するための証明手法は新規であり、これらは2つの側面に寄与する。 a) 証明は、sGMC の解集合の連続性を $(\mathbf{y},\lambda)$; の集合値写像として確立する。 (b)$\mathbf{x}_{\star}(\mathbf{y},\lambda)$の断片的線形性と断片的定数空間パターンを証明するために、以前の作業が依存する仮定は一切必要としない(ただし、$\mathbf{x}_{\star}(\mathbf{y},\lambda)$のいくつかの追加特性を証明するためには、以前の作業とは異なる仮定を用いる)。

関連論文リスト

• A Fresh Look at Generalized Category Discovery through Non-negative Matrix Factorization [83.12938977698988]
  Generalized Category Discovery (GCD) は、ラベル付きベースデータを用いて、ベース画像と新規画像の両方を分類することを目的としている。 現在のアプローチでは、コサイン類似性に基づく共起行列 $barA$ の固有の最適化に不適切に対処している。 本稿では,これらの欠陥に対処するNon-Negative Generalized Category Discovery (NN-GCD) フレームワークを提案する。
  論文  参考訳（メタデータ） (2024-10-29T07:24:11Z)
• Efficient Frameworks for Generalized Low-Rank Matrix Bandit Problems [61.85150061213987]
  一般化線形モデル (GLM) フレームワークを用いて, citelu2021low で提案した一般化低ランク行列帯域問題について検討する。 既存のアルゴリズムの計算不可能性と理論的制約を克服するため,まずG-ESTTフレームワークを提案する。 G-ESTT は $tildeO(sqrt(d_1+d_2)3/2Mr3/2T)$ bound of regret を達成でき、G-ESTS は $tildeO を達成できることを示す。
  論文  参考訳（メタデータ） (2024-01-14T14:14:19Z)
• KL-Entropy-Regularized RL with a Generative Model is Minimax Optimal [70.15267479220691]
  モデル強化学習のサンプル複雑性を,生成的分散自由モデルを用いて検討・解析する。 我々の分析は、$varepsilon$が十分小さい場合、$varepsilon$-optimal Policyを見つけるのが、ほぼ最小の最適化であることを示している。
  論文  参考訳（メタデータ） (2022-05-27T19:39:24Z)
• Spike-and-Slab Generalized Additive Models and Scalable Algorithms for High-Dimensional Data [0.0]
  本稿では,高次元データに対応するため,階層型一般化加法モデル(GAM)を提案する。 曲線の適切な縮退と滑らか化関数線型空間と非線形空間の分離に対する平滑化ペナルティを考察する。 2つの決定論的アルゴリズム、EM-Coordinate Descent と EM-Iterative Weighted Least Squares は異なるユーティリティ向けに開発された。
  論文  参考訳（メタデータ） (2021-10-27T14:11:13Z)
• Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learning [52.76230802067506]
  漸進的強化学習における後悔を最小限に抑えるために,新しいモデルフリーアルゴリズムを提案する。 提案アルゴリズムは、2つのQ-ラーニングシーケンスの助けを借りて、初期設定された参照更新ルールを用いる。 初期の分散還元法の設計原理は、他のRL設定とは独立した関心を持つかもしれない。
  論文  参考訳（メタデータ） (2021-10-09T21:13:48Z)
• Structured Stochastic Gradient MCMC [20.68905354115655]
  近似した後方関数形式を仮定しない新しい非パラメトリック変分近似を提案する。 完全なSGMCMCよりも優れた予測可能性と有効試料サイズが得られる。
  論文  参考訳（メタデータ） (2021-07-19T17:18:10Z)
• On the Adversarial Robustness of LASSO Based Feature Selection [72.54211869067979]
  検討されたモデルでは、悪意のある敵がデータセット全体を観察し、レスポンス値やフィーチャーマトリックスを慎重に修正する。 両レベルの最適化問題として、敵の修正戦略を定式化する。 合成および実データを用いた数値的な例は,本手法が効率的かつ効果的であることを示している。
  論文  参考訳（メタデータ） (2020-10-20T05:51:26Z)
• Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal Sample Complexity [67.02490430380415]
  モデルに基づくMARLは、Nash平衡値(NE)を求めるために$tilde O(|S||B|(gamma)-3epsilon-2)$のサンプル複雑性を実現する。 また、アルゴリズムが報酬に依存しない場合、そのようなサンプル境界は最小値(対数因子まで)であり、アルゴリズムは報酬知識のない遷移サンプルを問合せする。
  論文  参考訳（メタデータ） (2020-07-15T03:25:24Z)
• Effective Learning of a GMRF Mixture Model [8.336315962271396]
  我々はGMMをガウスマルコフ確率場混合モデル(GMRF-MM)に限定することを提案する。 各行列の空間パターンが知られているとき、その行列の最大近似(MLE)の効率的な最適化法を提案する。 GMRFとGMRF-MMの両症例でGLASSOの「偏り」はGLASSOよりも優れていた。
  論文  参考訳（メタデータ） (2020-05-18T19:00:14Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。