論文の概要: Learning Sparse Classifiers: Continuous and Mixed Integer Optimization
Perspectives
- arxiv url: http://arxiv.org/abs/2001.06471v2
- Date: Sun, 6 Jun 2021 17:38:09 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-10 10:08:02.521920
- Title: Learning Sparse Classifiers: Continuous and Mixed Integer Optimization
Perspectives
- Title（参考訳）: スパース分類器の学習:連続および混合整数最適化の視点
- Authors: Antoine Dedieu, Hussein Hazimeh, Rahul Mazumder
- Abstract要約: 混合整数計画法(MIP)は、(最適に) $ell_0$-正規化回帰問題を解くために用いられる。
数分で5万ドルの機能を処理できる正確なアルゴリズムと、$papprox6$でインスタンスに対処できる近似アルゴリズムの2つのクラスを提案する。
さらに,$ell$-regularizedsに対する新しい推定誤差境界を提案する。
- 参考スコア（独自算出の注目度）: 10.291482850329892
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider a discrete optimization formulation for learning sparse
classifiers, where the outcome depends upon a linear combination of a small
subset of features. Recent work has shown that mixed integer programming (MIP)
can be used to solve (to optimality) $\ell_0$-regularized regression problems
at scales much larger than what was conventionally considered possible. Despite
their usefulness, MIP-based global optimization approaches are significantly
slower compared to the relatively mature algorithms for $\ell_1$-regularization
and heuristics for nonconvex regularized problems. We aim to bridge this gap in
computation times by developing new MIP-based algorithms for
$\ell_0$-regularized classification. We propose two classes of scalable
algorithms: an exact algorithm that can handle $p\approx 50,000$ features in a
few minutes, and approximate algorithms that can address instances with
$p\approx 10^6$ in times comparable to the fast $\ell_1$-based algorithms. Our
exact algorithm is based on the novel idea of \textsl{integrality generation},
which solves the original problem (with $p$ binary variables) via a sequence of
mixed integer programs that involve a small number of binary variables. Our
approximate algorithms are based on coordinate descent and local combinatorial
search. In addition, we present new estimation error bounds for a class of
$\ell_0$-regularized estimators. Experiments on real and synthetic data
demonstrate that our approach leads to models with considerably improved
statistical performance (especially, variable selection) when compared to
competing methods.
- Abstract（参考訳）: スパース分類器を学習するための離散最適化の定式化について検討し、その結果は少数の特徴集合の線形結合に依存する。
最近の研究で、混合整数計画法(MIP)は、従来考えられていたよりもはるかに大きいスケールで(最適に)$\ell_0$-regularized回帰問題を解けることが示されている。
その有用性にもかかわらず、MIPベースのグローバル最適化アプローチは、非凸正規化問題に対する$\ell_1$-regularizationとヒューリスティックスの比較的成熟したアルゴリズムと比較して、大幅に遅い。
このギャップを計算時間で埋めるために,$\ell_0$-regularized 分類のための新しい MIP ベースのアルゴリズムを開発する。
数分で$p\approx 50,000$の機能を処理できる正確なアルゴリズムと、$p\approx 10^6$のインスタンスを高速な$\ell_1$のアルゴリズムに匹敵する速さで処理できる近似アルゴリズムの2つのクラスを提案する。
我々の正確なアルゴリズムは、少数のバイナリ変数を含む混合整数プログラムの列を通じて元の問題を($$p$のバイナリ変数で)解決する「textsl{integrality generation}」という新しいアイデアに基づいている。
近似アルゴリズムは座標降下と局所組合せ探索に基づいている。
さらに、$\ell_0$-regularized estimatorのクラスに対する新しい推定誤差境界を提案する。
実データおよび合成データを用いた実験により,本手法は競合手法と比較して,統計的性能(特に変数選択)が著しく向上したモデルに導かれることが示された。
関連論文リスト
- Approximation Algorithms for Preference Aggregation Using CP-Nets [3.337244446073836]
本稿では,条件付き選好ネットワーク(CP-nets)上での選好を集約する近似アルゴリズムの設計と解析について述べる。
その焦点は、一般に最適な解が指数関数的な大きさであることが知られている、いわゆる「エンフスワップ」よりも、優先的な選好を集約することである。
論文 参考訳（メタデータ） (2023-12-14T17:31:38Z) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳（メタデータ） (2023-07-24T14:37:22Z) - An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue
Optimization Problems [76.2042837251496]
相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。
注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。
本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
論文 参考訳（メタデータ） (2023-06-30T08:34:29Z) - Private estimation algorithms for stochastic block models and mixture
models [63.07482515700984]
効率的なプライベート推定アルゴリズムを設計するための一般的なツール。
最初の効率的な$(epsilon, delta)$-differentially private algorithm for both weak recovery and exact recovery。
論文 参考訳（メタデータ） (2023-01-11T09:12:28Z) - Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean
Estimation [58.24280149662003]
本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。
我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
論文 参考訳（メタデータ） (2021-06-16T03:34:14Z) - Grouped Variable Selection with Discrete Optimization: Computational and
Statistical Perspectives [9.593208961737572]
本稿では,離散数理最適化に基づくグループ変数選択のための新しいアルゴリズムフレームワークを提案する。
本手法は,スパースプログラミングを用いた高次元線形回帰法と非加法モデリングの両方を網羅する。
提案手法は,関連する混合整数問題(mip)を解き,最適性が証明できるスタンドアロンの分岐・境界(bnb)フレームワークに基づいている。
論文 参考訳（メタデータ） (2021-04-14T19:21:59Z) - Online Model Selection for Reinforcement Learning with Function
Approximation [50.008542459050155]
我々は、$tildeO(L5/6 T2/3)$ regretで最適な複雑性に適応するメタアルゴリズムを提案する。
また、メタアルゴリズムは、インスタンス依存の後悔境界を著しく改善することを示す。
論文 参考訳（メタデータ） (2020-11-19T10:00:54Z) - Practical and Parallelizable Algorithms for Non-Monotone Submodular
Maximization with Size Constraint [20.104148319012854]
サイズ制約に関して、必ずしも単調ではない部分モジュラ函数に対して存在および並列化可能である。
最適な適応性とほぼ最適な複雑性クエリを持つアルゴリズムによって達成される最適な近似係数を、0.193 - varepsilon$に改善する。
論文 参考訳（メタデータ） (2020-09-03T22:43:55Z) - A new heuristic algorithm for fast k-segmentation [0.0]
文献には$k$-segmentationの厳密で近似的な方法が存在する。
本稿では,既存の手法を改善するために,新しいアルゴリズムを提案する。
計算コストのごく一部で正確な手法と競合するアキュラシーを提供することを実証的に見出した。
論文 参考訳（メタデータ） (2020-09-02T04:50:17Z) - Private Stochastic Convex Optimization: Optimal Rates in Linear Time [74.47681868973598]
本研究では,凸損失関数の分布から得られた個体群損失を最小化する問題について検討する。
Bassilyらによる最近の研究は、$n$のサンプルを与えられた過剰な人口損失の最適境界を確立している。
本稿では,余剰損失に対する最適境界を達成するとともに,$O(minn, n2/d)$グラデーション計算を用いて凸最適化アルゴリズムを導出する2つの新しい手法について述べる。
論文 参考訳（メタデータ） (2020-05-10T19:52:03Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。