論文の概要: Query Complexity of Least Absolute Deviation Regression via Robust
Uniform Convergence
- arxiv url: http://arxiv.org/abs/2102.02322v1
- Date: Wed, 3 Feb 2021 22:54:27 GMT
- ステータス: 処理完了
- システム内更新日: 2021-02-05 16:05:44.174787
- Title: Query Complexity of Least Absolute Deviation Regression via Robust
Uniform Convergence
- Title（参考訳）: ロバスト一様収束による最小絶対偏差回帰の問合せ複雑性
- Authors: Xue Chen, Micha{\l} Derezi\'nski
- Abstract要約: 最小絶対偏差回帰のクエリ複雑性は、対数係数まで$Theta(d/epsilon2)$であることを示す。
我々は、経験的損失に対する新しい近似保証である、頑健な一様収束の概念を導入する。
- 参考スコア（独自算出の注目度）: 26.51921319084656
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Consider a regression problem where the learner is given a large collection
of $d$-dimensional data points, but can only query a small subset of the
real-valued labels. How many queries are needed to obtain a $1+\epsilon$
relative error approximation of the optimum? While this problem has been
extensively studied for least squares regression, little is known for other
losses. An important example is least absolute deviation regression ($\ell_1$
regression) which enjoys superior robustness to outliers compared to least
squares. We develop a new framework for analyzing importance sampling methods
in regression problems, which enables us to show that the query complexity of
least absolute deviation regression is $\Theta(d/\epsilon^2)$ up to logarithmic
factors. We further extend our techniques to show the first bounds on the query
complexity for any $\ell_p$ loss with $p\in(1,2)$. As a key novelty in our
analysis, we introduce the notion of robust uniform convergence, which is a new
approximation guarantee for the empirical loss. While it is inspired by uniform
convergence in statistical learning, our approach additionally incorporates a
correction term to avoid unnecessary variance due to outliers. This can be
viewed as a new connection between statistical learning theory and variance
reduction techniques in stochastic optimization, which should be of independent
interest.
- Abstract（参考訳）: 学習者が$d$次元のデータポイントの大規模なコレクションを与えられる回帰問題を考えるが、実数値ラベルの小さなサブセットにのみ問い合わせることができる。
最適値の相対誤差近似を1+\epsilon$で得られるクエリはいくつ必要か?
この問題は少なくとも2乗回帰について広く研究されているが、他の損失についてはほとんど知られていない。
重要な例は、最小偏差回帰($\ell_1$ regression)であり、最小二乗に比べ、アウトレーヤに対して優れた堅牢性を持つ。
回帰問題における重要サンプリング手法を解析するための新しいフレームワークを開発し、最小絶対偏差回帰のクエリ複雑性が対数因子まで$\Theta(d/\epsilon^2)$であることを示す。
さらに、$p\in(1,2)$ の任意の $\ell_p$ 損失に対するクエリの複雑さの最初の境界を示す技術を拡張します。
分析において重要な新規性として、実験損失に対する新たな近似保証である、頑健な一様収束の概念を導入する。
統計的学習における一様収束に着想を得ているが,本手法では,異常値による不必要な分散を避けるために補正項も取り入れている。
これは統計的学習理論と確率的最適化における分散還元手法との新たな関係と見なすことができ、独立興味を持つべきである。
関連論文リスト
- Data subsampling for Poisson regression with pth-root-link [53.63838219437508]
ポアソン回帰のためのデータサブサンプリング手法を開発し解析する。
特に,ポアソン一般化線形モデルと ID-および平方根リンク関数について考察する。
論文 参考訳（メタデータ） (2024-10-30T10:09:05Z) - Robust Capped lp-Norm Support Vector Ordinal Regression [85.84718111830752]
正規回帰は、ラベルが固有の順序を示す特殊な教師付き問題である。
卓越した順序回帰モデルとしてのベクトル順序回帰は、多くの順序回帰タスクで広く使われている。
我々は,新たなモデルであるCapped $ell_p$-Norm Support Vector Ordinal Regression (CSVOR)を導入する。
論文 参考訳（メタデータ） (2024-04-25T13:56:05Z) - Retire: Robust Expectile Regression in High Dimensions [3.9391041278203978]
ペナル化量子化法と期待回帰法は、高次元データの異方性検出に有用な手段を提供する。
我々は,頑健な期待回帰(退職)を提案し,研究する。
提案手法は半平滑なニュートン座標降下アルゴリズムにより効率よく解けることを示す。
論文 参考訳（メタデータ） (2022-12-11T18:03:12Z) - Dimension free ridge regression [10.434481202633458]
我々は、リッジ回帰のバイアスとばらつきの観点から、すなわちデータ上のリッジ回帰を再考し、等価なシーケンスモデルのバイアスとばらつきの観点から、リッジ回帰のバイアスとばらつきを考察する。
新しい応用として、定期的に変化するスペクトルを持つヒルベルト共変量に対して、完全に明示的で鋭い尾根回帰特性を得る。
論文 参考訳（メタデータ） (2022-10-16T16:01:05Z) - Hardness and Algorithms for Robust and Sparse Optimization [17.842787715567436]
スパース線形回帰やロバスト線形回帰といったスパース最適化問題に対するアルゴリズムと制限について検討する。
具体的には、スパース線型回帰問題は$k$-スパースベクトル$xinmathbbRd$を求め、$|Ax-b|$を最小化する。
頑健な線形回帰問題は、少なくとも$k$行を無視する集合$S$と、$|(Ax-b)_S|$を最小化するベクトル$x$を求める。
論文 参考訳（メタデータ） (2022-06-29T01:40:38Z) - Permuted and Unlinked Monotone Regression in $\mathbb{R}^d$: an approach
based on mixture modeling and optimal transport [4.924126492174802]
回帰関数の巡回的単調性の概念は、置換/無リンク回帰モデルにおける同定と推定に十分であることを示す。
我々は,Keefer-Wolfowitz に基づく,計算効率が良く,使いやすいアルゴリズムを開発した。
論文 参考訳（メタデータ） (2022-01-10T18:37:59Z) - Online nonparametric regression with Sobolev kernels [99.12817345416846]
我々は、ソボレフ空間のクラス上の後悔の上限を$W_pbeta(mathcalX)$, $pgeq 2, beta>fracdp$ とする。
上界は minimax regret analysis で支えられ、$beta> fracd2$ または $p=infty$ の場合、これらの値は(本質的に)最適である。
論文 参考訳（メタデータ） (2021-02-06T15:05:14Z) - Outlier-robust sparse/low-rank least-squares regression and robust
matrix completion [1.0878040851637998]
ヘテロジニアス雑音を伴う統計的学習フレームワークにおける高次元最小二乗回帰について検討する。
また, 製品プロセスの新たな応用に基づいて, 行列分解を伴う新しいトレーサリグレス理論を提案する。
論文 参考訳（メタデータ） (2020-12-12T07:42:47Z) - Conditional Uncorrelation and Efficient Non-approximate Subset Selection
in Sparse Regression [72.84177488527398]
相関性の観点からスパース回帰を考察し,条件付き非相関式を提案する。
提案手法により、計算複雑性は、スパース回帰における各候補部分集合に対して$O(frac16k3+mk2+mkd)$から$O(frac16k3+frac12mk2)$に削減される。
論文 参考訳（メタデータ） (2020-09-08T20:32:26Z) - Piecewise Linear Regression via a Difference of Convex Functions [50.89452535187813]
本稿では,データに対する凸関数(DC関数)の差を利用した線形回帰手法を提案する。
実際に実装可能であることを示すとともに,実世界のデータセット上で既存の回帰/分類手法に匹敵する性能を有することを実証的に検証した。
論文 参考訳（メタデータ） (2020-07-05T18:58:47Z) - Least Squares Regression with Markovian Data: Fundamental Limits and
Algorithms [69.45237691598774]
マルコフ連鎖からデータポイントが依存しサンプリングされる最小二乗線形回帰問題について検討する。
この問題を$tau_mathsfmix$という観点から、鋭い情報理論のミニマックス下限を確立する。
本稿では,経験的リプレイに基づくアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-16T04:26:50Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。