論文の概要: Solution-Set Geometry and Regularization Path of a Nonconvexly Regularized Convex Sparse Model
- arxiv url: http://arxiv.org/abs/2311.18438v2
- Date: Fri, 22 Mar 2024 13:26:52 GMT
- ステータス: 処理完了
- システム内更新日: 2024-04-01 03:58:36.738276
- Title: Solution-Set Geometry and Regularization Path of a Nonconvexly Regularized Convex Sparse Model
- Title(参考訳): 非凸正則凸スパースモデルの解集合幾何学と正則化経路
- Authors: Yi Zhang, Isao Yamada,
- Abstract要約: オズボーン一般化ミニマックス幾何学のペナルティ(Osborne generalized minimax geometry penalty)は、正規化された経路の全体二乗性を保存することができる非一意性解である。
LASSOと同様、最小$ell$-norm正規化は、$lambda$.continuouswiseで連続的であることを示す。
- 参考スコア(独自算出の注目度): 8.586951231230596
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The generalized minimax concave (GMC) penalty is a nonconvex sparse regularizer which can preserve the overall-convexity of the regularized least-squares problem. In this paper, we focus on a significant instance of the GMC model termed scaled GMC (sGMC), and present various notable findings on its solution-set geometry and regularization path. Our investigation indicates that while the sGMC penalty is a nonconvex extension of the LASSO penalty (i.e., the $\ell_1$-norm), the sGMC model preserves many celebrated properties of the LASSO model, hence can serve as a less biased surrogate of LASSO without losing its advantages. Specifically, for a fixed regularization parameter $\lambda$, we show that the solution-set geometry, solution uniqueness and sparseness of the sGMC model can be characterized in a similar elegant way to the LASSO model (see, e.g., Osborne et al. 2000, R. J. Tibshirani 2013). For a varying $\lambda$, we prove that the sGMC solution set is a continuous polytope-valued mapping of $\lambda$. Most noticeably, our study indicates that similar to LASSO, the minimum $\ell_2$-norm regularization path of the sGMC model is continuous and piecewise linear in $\lambda$. Based on these theoretical results, an efficient regularization path algorithm is proposed for the sGMC model, extending the well-known least angle regression (LARS) algorithm for LASSO. We prove the correctness and finite termination of the proposed algorithm under a mild assumption, and confirm its correctness-in-general-situation, efficiency, and practical utility through numerical experiments. Many results in this study also contribute to the theoretical research of LASSO.
- Abstract(参考訳): 一般化ミニマックス・コンケーブ(GMC)ペナルティは、非凸スパース正規化器であり、正規化最小二乗問題の全体凸性を維持することができる。
本稿では,スケールドGCC(sGMC)と呼ばれるGMCモデルの重要な事例に着目し,その解集合幾何と正規化経路について,様々な顕著な知見を示す。
本研究は, sGMCペナルティがLASSOペナルティの非凸拡大(すなわち$\ell_1$-norm)であるのに対して, sGMCモデルはLASSOモデルの多くの有望な特性を保ち, その利点を損なうことなく, LASSOの非凸拡大として機能することを示唆している。
具体的には、固定正則化パラメータ $\lambda$ に対して、sGMCモデルの解集合幾何学、解の一意性、スパース性はLASSOモデルと同様のエレガントな方法で特徴づけられることを示す(例:Osborne et al 2000, R. J. Tibshirani 2013)。
様々な$\lambda$に対して、sGMC の解集合が $\lambda$ の連続ポリトープ値写像であることを証明する。
最も顕著な研究は、LASSO と同様、sGMC モデルの最小$\ell_2$-norm正規化パスは $\lambda$ において連続かつ断片線型であることを示している。
これらの理論的な結果に基づき、sGMCモデルに対して効率的な正規化パスアルゴリズムを提案し、LASSOのよく知られた最小角度回帰(LARS)アルゴリズムを拡張した。
本研究では,提案アルゴリズムの正しさと有限終了性を軽微な仮定で証明し,数値実験によりその正しさ,汎用性,有効性,実用性を確認した。
本研究の成果はLASSOの理論研究にも貢献している。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。