論文の概要: 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)$のいくつかの追加特性を証明するためには、以前の作業とは異なる仮定を用いる)。

関連論文リスト

• Efficient Continual Finite-Sum Minimization [52.5238287567572]
  連続有限サム最小化(continuous finite-sum minimization)と呼ばれる有限サム最小化の鍵となるツイストを提案する。 我々のアプローチは$mathcalO(n/epsilon)$ FOs that $mathrmStochasticGradientDescent$で大幅に改善されます。 また、$mathcalOleft(n/epsilonalpharight)$ complexity gradient for $alpha 1/4$という自然な一階法は存在しないことを証明し、この方法の第一階法がほぼ密であることを示す。
  論文  参考訳（メタデータ） (2024-06-07T08:26:31Z)
• Provably learning a multi-head attention layer [55.2904547651831]
  マルチヘッドアテンション層は、従来のフィードフォワードモデルとは分離したトランスフォーマーアーキテクチャの重要な構成要素の1つである。 本研究では,ランダムな例から多面的注意層を実証的に学習する研究を開始する。 最悪の場合、$m$に対する指数的依存は避けられないことを示す。
  論文  参考訳（メタデータ） (2024-02-06T15:39:09Z)
• Optimal Estimator for Linear Regression with Shuffled Labels [17.99906229036223]
  本稿では,シャッフルラベルを用いた線形回帰の課題について考察する。 mathbb Rntimes m の $mathbf Y、mathbb Rntimes p の mathbf Pi、mathbb Rptimes m$ の mathbf B、mathbb Rntimes m$ の $mathbf Win mathbb Rntimes m$ である。
  論文  参考訳（メタデータ） (2023-10-02T16:44:47Z)
• A Unified Framework for Uniform Signal Recovery in Nonlinear Generative Compressed Sensing [68.80803866919123]
  非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。 本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。 また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
  論文  参考訳（メタデータ） (2023-09-25T17:54:19Z)
• Accelerated Methods for Riemannian Min-Max Optimization Ensuring Bounded Geometric Penalties [21.141544548229774]
  我々は$min_x max_y f(x, y) という形式で、$mathcalN$ は Hadamard である。 我々は、勾配収束定数を減少させることにより、グローバルな関心が加速されることを示す。
  論文  参考訳（メタデータ） (2023-05-25T15:43:07Z)
• Convergence of a Normal Map-based Prox-SGD Method under the KL Inequality [0.0]
  我々は、$symbol$k$収束問題に対して、新しいマップベースのアルゴリズム(mathsfnorMtext-mathsfSGD$)を提案する。
  論文  参考訳（メタデータ） (2023-05-10T01:12:11Z)
• Learning a Single Neuron with Adversarial Label Noise via Gradient Descent [50.659479930171585]
  モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。 学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
  論文  参考訳（メタデータ） (2022-06-17T17:55:43Z)
• Fast Graph Sampling for Short Video Summarization using Gershgorin Disc Alignment [52.577757919003844]
  高速グラフサンプリングの最近の進歩を利用して,短い動画を複数の段落に効率よく要約する問題について検討する。 実験結果から,本アルゴリズムは最先端の手法と同等の映像要約を実現し,複雑さを大幅に低減した。
  論文  参考訳（メタデータ） (2021-10-21T18:43:00Z)
• Minimax Optimal Regression over Sobolev Spaces via Laplacian Regularization on Neighborhood Graphs [25.597646488273558]
  非パラメトリック回帰に対するグラフに基づくアプローチであるラプラシア平滑化の統計的性質について検討する。 ラプラシアン滑らか化が多様体適応であることを証明する。
  論文  参考訳（メタデータ） (2021-06-03T01:20:41Z)
• Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization [51.23789922123412]
  我々は,バンディットフィードバックを用いてオンライン学習を学習する。 learnerは、コスト/リワード関数が"pseudo-1d"構造を許可するゼロ次オラクルのみにアクセスできる。 我々は、$T$がラウンドの数である任意のアルゴリズムの後悔のために$min(sqrtdT、T3/4)$の下限を示しています。 ランダム化オンライングラデーション下降とカーネル化指数重み法を組み合わせた新しいアルゴリズムsbcalgを提案し,疑似-1d構造を効果的に活用する。
  論文  参考訳（メタデータ） (2021-02-15T08:16:51Z)
• On the Optimal Weighted $\ell_2$ Regularization in Overparameterized Linear Regression [23.467801864841526]
  線形モデル $mathbfy = mathbfX mathbfbeta_star + mathbfepsilon$ with $mathbfXin mathbbRntimes p$ in the overparameterized regime $p>n$ を考える。 予測リスク $mathbbE(y-mathbfxThatmathbfbeta_lambda)2$ in proportional limit $p/n の正確なキャラクタリゼーションを提供する。
  論文  参考訳（メタデータ） (2020-06-10T12:38:43Z)

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

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