論文の概要: Robust methods for high-dimensional linear learning
- arxiv url: http://arxiv.org/abs/2208.05447v1
- Date: Wed, 10 Aug 2022 17:00:41 GMT
- ステータス: 処理完了
- システム内更新日: 2022-08-11 12:37:41.867040
- Title: Robust methods for high-dimensional linear learning
- Title(参考訳): 高次元線形学習のためのロバスト手法
- Authors: Ibrahim Merad and St\'ephane Ga\"iffas
- Abstract要約: 統計的に頑健で計算効率の良い線形学習法を高次元バッチ設定で提案する。
バニラスパース、グループスパース、低ランク行列回復など、いくつかのアプリケーションでフレームワークをインスタンス化する。
バニラ $s$-sparsity の場合、重いテールと $eta$-corruption の下で $slog (d)/n$ レートに達することができます。
- 参考スコア(独自算出の注目度): 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We propose statistically robust and computationally efficient linear learning
methods in the high-dimensional batch setting, where the number of features $d$
may exceed the sample size $n$. We employ, in a generic learning setting, two
algorithms depending on whether the considered loss function is
gradient-Lipschitz or not. Then, we instantiate our framework on several
applications including vanilla sparse, group-sparse and low-rank matrix
recovery. This leads, for each application, to efficient and robust learning
algorithms, that reach near-optimal estimation rates under heavy-tailed
distributions and the presence of outliers. For vanilla $s$-sparsity, we are
able to reach the $s\log (d)/n$ rate under heavy-tails and $\eta$-corruption,
at a computational cost comparable to that of non-robust analogs. We provide an
efficient implementation of our algorithms in an open-source $\mathtt{Python}$
library called $\mathtt{linlearn}$, by means of which we carry out numerical
experiments which confirm our theoretical findings together with a comparison
to other recent approaches proposed in the literature.
- Abstract(参考訳): 高次元バッチ設定において統計的にロバストで計算効率の良い線形学習法を提案する。
一般学習環境では,損失関数が勾配リプシッツであるか否かに応じて2つのアルゴリズムを用いる。
次に,vanilla sparse,group-sparse,low-rank matrix recoveryなど,いくつかのアプリケーションでフレームワークをインスタンス化する。
これにより、各アプリケーションに対して、重み付き分布と外れ値の存在下で最適に近い推定率に達する効率的で堅牢な学習アルゴリズムが導かれる。
バニラ$sparsityの場合、非ロバストアナログと同等の計算コストで、ヘビーテールと\eta$-coruptionの下で$s\log (d)/n$レートに達することができる。
我々は,論文で提案されている他の手法との比較とともに,理論的な結果を確認する数値実験を行うことにより,オープンソース$\matht{Python}$ライブラリ$\mathtt{linlearn}$でアルゴリズムの効率的な実装を提供する。
関連論文リスト
- Robust Sparse Estimation for Gaussians with Optimal Error under Huber Contamination [42.526664955704746]
本研究では,平均推定,PCA,線形回帰に着目したハマー汚染モデルにおけるスパース推定タスクについて検討する。
それぞれのタスクに対して、最適なエラー保証を備えた最初のサンプルと計算効率の良い頑健な推定器を与える。
技術レベルでは、スパース方式における新しい多次元フィルタリング法を開発し、他の応用を見出すことができる。
論文 参考訳(メタデータ) (2024-03-15T15:51:27Z) - Robust Second-Order Nonconvex Optimization and Its Application to Low Rank Matrix Sensing [47.32366699399839]
近似第二エピシロン依存(SOSP)の発見は、よく研究され基礎的な問題である。
本稿では,低次元センサマシン最適化問題に適用する。
論文 参考訳(メタデータ) (2024-03-12T01:27:44Z) - Computational-Statistical Gaps for Improper Learning in Sparse Linear Regression [4.396860522241307]
疎線形回帰の効率的な学習アルゴリズムは, 負のスパイクを持つスパースPCA問題を解くのに有効であることを示す。
我々は,低次および統計的クエリの低い境界を減らしたスパース問題に対して補う。
論文 参考訳(メタデータ) (2024-02-21T19:55:01Z) - 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) - Differentially-Private Hierarchical Clustering with Provable
Approximation Guarantees [79.59010418610625]
階層クラスタリングのための微分プライベート近似アルゴリズムについて検討する。
例えば、$epsilon$-DPアルゴリズムは入力データセットに対して$O(|V|2/epsilon)$-additiveエラーを示さなければならない。
本稿では,ブロックを正確に復元する1+o(1)$近似アルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-01-31T19:14:30Z) - Communication-Efficient Adam-Type Algorithms for Distributed Data Mining [93.50424502011626]
我々はスケッチを利用した新しい分散Adam型アルゴリズムのクラス(例:SketchedAMSGrad)を提案する。
我々の新しいアルゴリズムは、反復毎に$O(frac1sqrtnT + frac1(k/d)2 T)$の高速収束率を$O(k log(d))$の通信コストで達成する。
論文 参考訳(メタデータ) (2022-10-14T01:42:05Z) - 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) - Linear Algorithms for Nonparametric Multiclass Probability Estimation [0.0]
アンサンブル学習によってクラス確率を推定するために,サポートベクトルマシン (wSVM) が開発された。
計算効率と推定精度の面でwSVMをさらに向上するために,ベースライン学習とOVA学習という2つの新しい学習手法を提案する。
論文 参考訳(メタデータ) (2022-05-25T03:15:22Z) - Under-bagging Nearest Neighbors for Imbalanced Classification [63.026765294759876]
我々は,不均衡な分類問題に対して,textitunder-bagging $k$-NN (textitunder-bagging $k$-NN) というアンサンブル学習アルゴリズムを提案する。
論文 参考訳(メタデータ) (2021-09-01T14:10:38Z) - Randomized Exploration for Reinforcement Learning with General Value
Function Approximation [122.70803181751135]
本稿では,ランダム化最小二乗値反復(RLSVI)アルゴリズムに着想を得たモデルレス強化学習アルゴリズムを提案する。
提案アルゴリズムは,スカラーノイズを用いたトレーニングデータを簡易に摂動させることにより,探索を促進する。
我々はこの理論を、既知の困難な探査課題にまたがる実証的な評価で補完する。
論文 参考訳(メタデータ) (2021-06-15T02:23:07Z) - Learning Sparse Classifiers: Continuous and Mixed Integer Optimization
Perspectives [10.291482850329892]
混合整数計画法(MIP)は、(最適に) $ell_0$-正規化回帰問題を解くために用いられる。
数分で5万ドルの機能を処理できる正確なアルゴリズムと、$papprox6$でインスタンスに対処できる近似アルゴリズムの2つのクラスを提案する。
さらに,$ell$-regularizedsに対する新しい推定誤差境界を提案する。
論文 参考訳(メタデータ) (2020-01-17T18:47:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。