論文の概要: Sparse Regression at Scale: Branch-and-Bound rooted in First-Order
Optimization
- arxiv url: http://arxiv.org/abs/2004.06152v2
- Date: Wed, 14 Apr 2021 20:18:21 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-13 23:43:26.895119
- Title: Sparse Regression at Scale: Branch-and-Bound rooted in First-Order
Optimization
- Title（参考訳）: スケールでのスパース回帰:一階最適化に根ざした分岐境界
- Authors: Hussein Hazimeh, Rahul Mazumder, Ali Saab
- Abstract要約: 我々は $ell_0$ 正規化回帰のための新しい正確な MIP フレームワークを提案する。
私たちのフレームワークは、$p sim 107$までスケールでき、少なくとも5,000$xのスピードアップを達成できます。
実装をツールキットL0BnBでオープンソースにしています。
- 参考スコア（独自算出の注目度）: 6.037383467521294
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider the least squares regression problem, penalized with a
combination of the $\ell_{0}$ and squared $\ell_{2}$ penalty functions (a.k.a.
$\ell_0 \ell_2$ regularization). Recent work shows that the resulting
estimators are of key importance in many high-dimensional statistical settings.
However, exact computation of these estimators remains a major challenge.
Indeed, modern exact methods, based on mixed integer programming (MIP), face
difficulties when the number of features $p \sim 10^4$. In this work, we
present a new exact MIP framework for $\ell_0\ell_2$-regularized regression
that can scale to $p \sim 10^7$, achieving speedups of at least $5000$x,
compared to state-of-the-art exact methods. Unlike recent work, which relies on
modern commercial MIP solvers, we design a specialized nonlinear
branch-and-bound (BnB) framework, by critically exploiting the problem
structure. A key distinguishing component in our framework lies in efficiently
solving the node relaxations using a specialized first-order method, based on
coordinate descent (CD). Our CD-based method effectively leverages information
across the BnB nodes, through using warm starts, active sets, and gradient
screening. In addition, we design a novel method for obtaining dual bounds from
primal CD solutions, which certifiably works in high dimensions. Experiments on
synthetic and real high-dimensional datasets demonstrate that our framework is
not only significantly faster than the state of the art, but can also deliver
certifiably optimal solutions to statistically challenging instances that
cannot be handled with existing methods. We open source the implementation
through our toolkit L0BnB.
- Abstract（参考訳）: 最小二乗回帰問題は、$\ell_{0}$ と 2乗$\ell_{2}$ のペナルティ関数(すなわち $\ell_0 \ell_2$ 正規化)を組み合わせてペナルティ化される。
最近の研究は、多くの高次元統計的設定において、結果の見積もりが重要な意味を持つことを示している。
しかし、これらの推定器の正確な計算は依然として大きな課題である。
実際、mixed integer programming (mip) に基づいた現代的な厳密な手法は、機能数が $p \sim 10^4$ である場合に困難に直面する。
本研究では,$\ell_0\ell_2$-regularized regression に対する新たな正確な MIP フレームワークを提案する。
現代の商用MIP解法に依存する最近の研究とは異なり、我々は問題構造を批判的に利用して、特殊な非線形分岐結合(BnB)フレームワークを設計する。
我々のフレームワークにおける重要な差別化要素は、座標降下(CD)に基づく特別な一階法を用いてノード緩和を効率的に解くことである。
我々のCDベースの手法は、暖房開始、アクティブセット、勾配スクリーニングを用いてBnBノードの情報を効果的に活用する。
さらに,本研究では,高次元で確実に機能する原始CD溶液から二重境界を求める新しい手法を設計する。
合成および実高次元データセットの実験により、我々のフレームワークは最先端技術よりもはるかに高速であるだけでなく、既存の手法では扱えない統計的に困難なインスタンスに対して、確実に最適なソリューションを提供できることを示した。
実装をツールキットL0BnBでオープンソースにしています。
関連論文リスト
- Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。
我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。
我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
論文 参考訳（メタデータ） (2024-05-10T09:58:47Z) - A Specialized Semismooth Newton Method for Kernel-Based Optimal
Transport [92.96250725599958]
カーネルベース最適輸送(OT)推定器は、サンプルからOT問題に対処するための代替的機能的推定手順を提供する。
SSN法は, 標準正規性条件下でのグローバル収束率$O (1/sqrtk)$, 局所二次収束率を達成できることを示す。
論文 参考訳（メタデータ） (2023-10-21T18:48:45Z) - Sparse Gaussian Graphical Models with Discrete Optimization:
Computational and Statistical Perspectives [8.403841349300103]
本研究では,無向ガウス図形モデルに基づくスパースグラフの学習問題を考察する。
擬似微分関数の $ell_0$-penalized バージョンに基づく新しい推定器 GraphL0BnB を提案する。
実/合成データセットに関する数値実験により,本手法がほぼ最適に,p = 104$の問題を解けることが示唆された。
論文 参考訳（メタデータ） (2023-07-18T15:49:02Z) - Compressed Sensing: A Discrete Optimization Approach [5.877778007271621]
本稿では, 2次円錐緩和を強化し, 独自の分岐結合アルゴリズムを開発する半定緩和法を提案する。
マルチラベル分類アルゴリズムの構成要素として用いられる場合,提案手法は,ベンチマーク圧縮センシング法よりも高い分類精度を実現する。
論文 参考訳（メタデータ） (2023-06-05T01:29:24Z) - Scalable Optimal Multiway-Split Decision Trees with Constraints [3.092691764363848]
決定変数の個数が$N$とは独立な経路に基づく新しいMIP定式化を提案する。
本フレームワークは, 規則が短いため, 通常の二分木よりも解釈しやすいマルチウェイスプリットツリーを生成する。
我々は,最大1,008,372個のサンプルを含むデータセットについて,既存のMIPベースの決定木モデルでは数千点を超えるデータに対してうまくスケールしないことを示す。
論文 参考訳（メタデータ） (2023-02-14T03:48:48Z) - Pseudonorm Approachability and Applications to Regret Minimization [73.54127663296906]
我々は、高次元 $ell_infty$-approachability 問題を、低次元の擬ノルムアプローチ可能性問題に変換する。
我々は、$ell$や他のノルムに対するアプローチ可能性に関する以前の研究に類似した疑似ノルムアプローチ可能性のアルゴリズム理論を開発する。
論文 参考訳（メタデータ） (2023-02-03T03:19:14Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - Scalable Differentially Private Clustering via Hierarchically Separated
Trees [82.69664595378869]
我々は,最大$O(d3/2log n)cdot OPT + O(k d2 log2 n / epsilon2)$,$epsilon$はプライバシ保証であることを示す。
最悪の場合の保証は、最先端のプライベートクラスタリング手法よりも悪いが、提案するアルゴリズムは実用的である。
論文 参考訳（メタデータ） (2022-06-17T09:24:41Z) - Minimax Optimal Quantization of Linear Models: Information-Theoretic
Limits and Efficient Algorithms [59.724977092582535]
測定から学習した線形モデルの定量化の問題を考える。
この設定の下では、ミニマックスリスクに対する情報理論の下限を導出する。
本稿では,2層ReLUニューラルネットワークに対して,提案手法と上界を拡張可能であることを示す。
論文 参考訳（メタデータ） (2022-02-23T02:39:04Z) - Grouped Variable Selection with Discrete Optimization: Computational and
Statistical Perspectives [9.593208961737572]
本稿では,離散数理最適化に基づくグループ変数選択のための新しいアルゴリズムフレームワークを提案する。
本手法は,スパースプログラミングを用いた高次元線形回帰法と非加法モデリングの両方を網羅する。
提案手法は,関連する混合整数問題(mip)を解き,最適性が証明できるスタンドアロンの分岐・境界(bnb)フレームワークに基づいている。
論文 参考訳（メタデータ） (2021-04-14T19:21:59Z) - Learning Sparse Classifiers: Continuous and Mixed Integer Optimization
Perspectives [10.291482850329892]
混合整数計画法(MIP)は、(最適に) $ell_0$-正規化回帰問題を解くために用いられる。
数分で5万ドルの機能を処理できる正確なアルゴリズムと、$papprox6$でインスタンスに対処できる近似アルゴリズムの2つのクラスを提案する。
さらに,$ell$-regularizedsに対する新しい推定誤差境界を提案する。
論文 参考訳（メタデータ） (2020-01-17T18:47:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。