論文の概要: Suboptimality of Constrained Least Squares and Improvements via
Non-Linear Predictors
- arxiv url: http://arxiv.org/abs/2009.09304v2
- Date: Sun, 7 Mar 2021 16:24:01 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-16 21:12:17.601529
- Title: Suboptimality of Constrained Least Squares and Improvements via
Non-Linear Predictors
- Title（参考訳）: 制約付き最小方形の準最適性と非線形予測器による改善
- Authors: Tomas Va\v{s}kevi\v{c}ius and Nikita Zhivotovskiy
- Abstract要約: 有界ユークリッド球における正方形損失に対する予測問題と最良の線形予測器について検討する。
最小二乗推定器に対する$O(d/n)$過剰リスク率を保証するのに十分な分布仮定について論じる。
- 参考スコア（独自算出の注目度）: 3.5788754401889014
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study the problem of predicting as well as the best linear predictor in a
bounded Euclidean ball with respect to the squared loss. When only boundedness
of the data generating distribution is assumed, we establish that the least
squares estimator constrained to a bounded Euclidean ball does not attain the
classical $O(d/n)$ excess risk rate, where $d$ is the dimension of the
covariates and $n$ is the number of samples. In particular, we construct a
bounded distribution such that the constrained least squares estimator incurs
an excess risk of order $\Omega(d^{3/2}/n)$ hence refuting a recent conjecture
of Ohad Shamir [JMLR 2015]. In contrast, we observe that non-linear predictors
can achieve the optimal rate $O(d/n)$ with no assumptions on the distribution
of the covariates. We discuss additional distributional assumptions sufficient
to guarantee an $O(d/n)$ excess risk rate for the least squares estimator.
Among them are certain moment equivalence assumptions often used in the robust
statistics literature. While such assumptions are central in the analysis of
unbounded and heavy-tailed settings, our work indicates that in some cases,
they also rule out unfavorable bounded distributions.
- Abstract（参考訳）: 本研究では, 2乗損失に関して有界ユークリッド球における最適線形予測器と同様に予測の問題について検討する。
データ生成分布の有界性のみを仮定すると、有界ユークリッド球に制約された最小二乗推定器は古典的$o(d/n)$ の過剰なリスク率に達しない、ただし、$d$ は共変数の次元であり、$n$ はサンプルの数である。
特に、制約付き最小二乗推定器が$\omega(d^{3/2}/n)$の過剰なリスクを負うような有界分布を構成するので、ohad shamir [jmlr 2015] の最近の予想を反論する。
対照的に、非線形予測器は共変量の分布を仮定せずに最適なレートであるo(d/n)$を達成することができる。
最小二乗推定器に対する$O(d/n)$過剰リスク率を保証するのに十分な分布仮定について論じる。
それらのなかには、ロバストな統計文献でよく使われるあるモーメント同値仮定がある。
このような仮定は、境界のない設定と重み付き設定の分析の中心であるが、我々の研究は、いくつかのケースでは、不利な境界付き分布も除外していることを示している。
関連論文リスト
- Sparse PCA with Oracle Property [115.72363972222622]
新規な正規化を伴うスパースPCAの半定緩和に基づく推定器群を提案する。
我々は、家族内の別の推定器が、スパースPCAの標準半定緩和よりも、より急激な収束率を達成することを証明した。
論文 参考訳（メタデータ） (2023-12-28T02:52:54Z) - $L^1$ Estimation: On the Optimality of Linear Estimators [64.76492306585168]
この研究は、条件中央値の線型性を誘導する$X$上の唯一の先行分布がガウス分布であることを示している。
特に、条件分布 $P_X|Y=y$ がすべての$y$に対して対称であるなら、$X$ はガウス分布に従う必要がある。
論文 参考訳（メタデータ） (2023-09-17T01:45:13Z) - Estimating Optimal Policy Value in General Linear Contextual Bandits [50.008542459050155]
多くのバンドイット問題において、政策によって達成可能な最大報酬は、前もって不明であることが多い。
我々は,最適政策が学習される前に,サブ線形データ構造における最適政策値を推定する問題を考察する。
V*$で問題依存上界を推定する,より実用的で効率的なアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-02-19T01:09:24Z) - New Lower Bounds for Private Estimation and a Generalized Fingerprinting
Lemma [10.176795938619417]
統計的推定タスクの新たな下限を$(varepsilon, delta)$-differential privacyの制約の下で証明する。
フロベニウスノルムの推定には$Omega(d2)$サンプルが必要であり、スペクトルノルムでは$Omega(d3/2)$サンプルが必要である。
論文 参考訳（メタデータ） (2022-05-17T17:55:10Z) - Robust Linear Predictions: Analyses of Uniform Concentration, Fast Rates
and Model Misspecification [16.0817847880416]
ヒルベルト空間上の様々な線形予測問題を含む統一的なフレームワークを提供する。
誤特定レベル $epsilon$ に対して、これらの推定器は、文献で最もよく知られたレートと一致する、$O(maxleft|mathcalO|1/2n-1/2, |mathcalI|1/2n-1 right+epsilon)$ の誤差率を達成する。
論文 参考訳（メタデータ） (2022-01-06T08:51:08Z) - Optimal policy evaluation using kernel-based temporal difference methods [78.83926562536791]
カーネルヒルベルト空間を用いて、無限水平割引マルコフ報酬過程の値関数を推定する。
我々は、関連するカーネル演算子の固有値に明示的に依存した誤差の非漸近上界を導出する。
MRP のサブクラスに対する minimax の下位境界を証明する。
論文 参考訳（メタデータ） (2021-09-24T14:48:20Z) - Distribution-Free Robust Linear Regression [5.532477732693]
共変体の分布を仮定せずにランダムな設計線形回帰を研究する。
最適部分指数尾を持つオーダー$d/n$の過大なリスクを達成する非線形推定器を構築する。
我々は、Gy"orfi, Kohler, Krzyzak, Walk が原因で、truncated least squares 推定器の古典的境界の最適版を証明した。
論文 参考訳（メタデータ） (2021-02-25T15:10:41Z) - Sharp Statistical Guarantees for Adversarially Robust Gaussian
Classification [54.22421582955454]
逆向きに頑健な分類の過剰リスクに対する最適ミニマックス保証の最初の結果を提供する。
結果はAdvSNR(Adversarial Signal-to-Noise Ratio)の項で述べられており、これは標準的な線形分類と逆数設定との類似の考え方を一般化している。
論文 参考訳（メタデータ） (2020-06-29T21:06:52Z) - Robust Linear Regression: Optimal Rates in Polynomial Time [11.646151402884215]
複数の線形モデルを学習するための頑健で計算効率の良い推定器を得る。
確率変数の独立性の緩和に役立つ解析条件を同定する。
我々の中心となる技術的貢献は、"sum-of-squares"フレームワークにおけるランダム変数の独立性をアルゴリズム的に活用することである。
論文 参考訳（メタデータ） (2020-06-29T17:22:16Z) - Distributionally Robust Bayesian Quadrature Optimization [60.383252534861136]
確率分布が未知な分布の不確実性の下でBQOについて検討する。
標準的なBQOアプローチは、固定されたサンプル集合が与えられたときの真の期待目標のモンテカルロ推定を最大化する。
この目的のために,新しい後方サンプリングに基づくアルゴリズム,すなわち分布的に堅牢なBQO(DRBQO)を提案する。
論文 参考訳（メタデータ） (2020-01-19T12:00:33Z) - Risk of the Least Squares Minimum Norm Estimator under the Spike
Covariance Model [0.0]
パラメータ数$d$が$n$と$fracdn rightarrow infty$に依存するとき、最小ノルム最小二乗推定子のリスクを研究する。
この設定では、最小ノルム最小二乗推定器のリスクは、ヌル推定器のリスクと比較して消える。
論文 参考訳（メタデータ） (2019-12-31T16:58:42Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。