論文の概要: Grouped Variable Selection with Discrete Optimization: Computational and
Statistical Perspectives
- arxiv url: http://arxiv.org/abs/2104.07084v1
- Date: Wed, 14 Apr 2021 19:21:59 GMT
- ステータス: 処理完了
- システム内更新日: 2021-04-16 15:07:32.980571
- Title: Grouped Variable Selection with Discrete Optimization: Computational and
Statistical Perspectives
- Title（参考訳）: 離散最適化によるグループ変数選択:計算と統計の展望
- Authors: Hussein Hazimeh, Rahul Mazumder, Peter Radchenko
- Abstract要約: 本稿では,離散数理最適化に基づくグループ変数選択のための新しいアルゴリズムフレームワークを提案する。
本手法は,スパースプログラミングを用いた高次元線形回帰法と非加法モデリングの両方を網羅する。
提案手法は,関連する混合整数問題(mip)を解き,最適性が証明できるスタンドアロンの分岐・境界(bnb)フレームワークに基づいている。
- 参考スコア（独自算出の注目度）: 9.593208961737572
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We present a new algorithmic framework for grouped variable selection that is
based on discrete mathematical optimization. While there exist several
appealing approaches based on convex relaxations and nonconvex heuristics, we
focus on optimal solutions for the $\ell_0$-regularized formulation, a problem
that is relatively unexplored due to computational challenges. Our methodology
covers both high-dimensional linear regression and nonparametric sparse
additive modeling with smooth components. Our algorithmic framework consists of
approximate and exact algorithms. The approximate algorithms are based on
coordinate descent and local search, with runtimes comparable to popular sparse
learning algorithms. Our exact algorithm is based on a standalone
branch-and-bound (BnB) framework, which can solve the associated mixed integer
programming (MIP) problem to certified optimality. By exploiting the problem
structure, our custom BnB algorithm can solve to optimality problem instances
with $5 \times 10^6$ features in minutes to hours -- over $1000$ times larger
than what is currently possible using state-of-the-art commercial MIP solvers.
We also explore statistical properties of the $\ell_0$-based estimators. We
demonstrate, theoretically and empirically, that our proposed estimators have
an edge over popular group-sparse estimators in terms of statistical
performance in various regimes.
- Abstract（参考訳）: 本稿では,離散数理最適化に基づくグループ変数選択のための新しいアルゴリズムフレームワークを提案する。
凸緩和と非凸ヒューリスティックに基づくいくつかの魅力的なアプローチが存在するが、計算上の課題により比較的未解決な問題である $\ell_0$-regularized formula の最適解に焦点を当てている。
本研究では,高次元線形回帰法と平滑成分を用いた非パラメトリックスパース加法モデリングについて述べる。
我々のアルゴリズムフレームワークは近似と厳密なアルゴリズムで構成されている。
近似アルゴリズムは座標降下と局所探索に基づいており、ランタイムは一般的なスパース学習アルゴリズムに匹敵する。
提案手法は,関連する混合整数計画問題(mip)を解き,最適性が証明できるスタンドアロンの分岐・境界(bnb)フレームワークに基づいている。
我々のカスタムBnBアルゴリズムは、問題構造を利用することにより、現在最先端の商用MIP解決器で実現されているものよりも1,000ドル以上、分から数時間で5ドル=10^6$の機能を持つ最適性問題インスタンスを解くことができる。
また、$\ell_0$ ベースの推定器の統計特性についても検討する。
我々は,理論上,実証的に,提案した推定器が,様々な制度における統計的性能の観点から,一般的なグループスパース推定器よりも優位であることを示す。
関連論文リスト
- Approximation Algorithms for Combinatorial Optimization with Predictions [3.7235228254732524]
従来のアルゴリズムの近似保証よりも高い精度で予測を行う。
我々のアルゴリズムは、完璧な予測が得られたときに最適解を生成する。
この種の問題全体に対して最適なアプローチを示すが、個々の問題の特定の構造的特性を利用して改善された境界を求める可能性はある。
論文 参考訳（メタデータ） (2024-11-25T17:31:34Z) - Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
我々は、様々な武器の報酬間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
特に、様々な武器の報酬の間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
論文 参考訳（メタデータ） (2023-12-19T13:17:43Z) - A unified consensus-based parallel ADMM algorithm for high-dimensional
regression with combined regularizations [3.280169909938912]
並列交互乗算器 (ADMM) は大規模分散データセットの処理に有効であることが広く認識されている。
提案アルゴリズムは,財務事例の信頼性,安定性,スケーラビリティを示す。
論文 参考訳（メタデータ） (2023-11-21T03:30:38Z) - Fast Optimal Locally Private Mean Estimation via Random Projections [58.603579803010796]
ユークリッド球における高次元ベクトルの局所的プライベート平均推定の問題について検討する。
プライベート平均推定のための新しいアルゴリズムフレームワークであるProjUnitを提案する。
各ランダム化器はその入力をランダムな低次元部分空間に投影し、結果を正規化し、最適なアルゴリズムを実行する。
論文 参考訳（メタデータ） (2023-06-07T14:07:35Z) - Portfolio optimization with discrete simulated annealing [0.0]
離散凸関数と非凸コスト関数の存在下で最適なポートフォリオを求めるための整数最適化法を提案する。
これにより、与えられた品質でソリューションを実現できる。
論文 参考訳（メタデータ） (2022-10-03T10:39:05Z) - Efficient semidefinite-programming-based inference for binary and
multi-class MRFs [83.09715052229782]
分割関数やMAP推定をペアワイズMRFで効率的に計算する手法を提案する。
一般のバイナリMRFから完全多クラス設定への半定緩和を拡張し、解法を用いて再び効率的に解けるようなコンパクトな半定緩和を開発する。
論文 参考訳（メタデータ） (2020-12-04T15:36:29Z) - Online Model Selection for Reinforcement Learning with Function
Approximation [50.008542459050155]
我々は、$tildeO(L5/6 T2/3)$ regretで最適な複雑性に適応するメタアルゴリズムを提案する。
また、メタアルゴリズムは、インスタンス依存の後悔境界を著しく改善することを示す。
論文 参考訳（メタデータ） (2020-11-19T10:00:54Z) - Adaptive Sampling for Best Policy Identification in Markov Decision
Processes [79.4957965474334]
本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。
最先端アルゴリズムの利点を論じ、解説する。
論文 参考訳（メタデータ） (2020-09-28T15:22:24Z) - Alternating Direction Method of Multipliers for Quantization [15.62692130672419]
量子化のための乗算器の交互方向法(texttADMM-Q$)アルゴリズムの性能について検討する。
不正確な更新ルールを処理できる$texttADMM-Q$のいくつかのバリエーションを開発しています。
提案手法の有効性を実証的に評価した。
論文 参考訳（メタデータ） (2020-09-08T01:58:02Z) - Private Stochastic Convex Optimization: Optimal Rates in Linear Time [74.47681868973598]
本研究では,凸損失関数の分布から得られた個体群損失を最小化する問題について検討する。
Bassilyらによる最近の研究は、$n$のサンプルを与えられた過剰な人口損失の最適境界を確立している。
本稿では,余剰損失に対する最適境界を達成するとともに,$O(minn, n2/d)$グラデーション計算を用いて凸最適化アルゴリズムを導出する2つの新しい手法について述べる。
論文 参考訳（メタデータ） (2020-05-10T19:52:03Z) - Learning Sparse Classifiers: Continuous and Mixed Integer Optimization
Perspectives [10.291482850329892]
混合整数計画法(MIP)は、(最適に) $ell_0$-正規化回帰問題を解くために用いられる。
数分で5万ドルの機能を処理できる正確なアルゴリズムと、$papprox6$でインスタンスに対処できる近似アルゴリズムの2つのクラスを提案する。
さらに,$ell$-regularizedsに対する新しい推定誤差境界を提案する。
論文 参考訳（メタデータ） (2020-01-17T18:47:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。