論文の概要: Optimality in Mean Estimation: Beyond Worst-Case, Beyond Sub-Gaussian,
and Beyond $1+\alpha$ Moments
- arxiv url: http://arxiv.org/abs/2311.12784v1
- Date: Tue, 21 Nov 2023 18:50:38 GMT
- ステータス: 処理完了
- システム内更新日: 2023-11-22 23:26:11.389009
- Title: Optimality in Mean Estimation: Beyond Worst-Case, Beyond Sub-Gaussian,
and Beyond $1+\alpha$ Moments
- Title（参考訳）: 平均推定における最適性:最悪のケースを超えて、サブゲージを超えて、1+\alpha$ moments以上
- Authors: Trung Dang, Jasper C.H. Lee, Maoyuan Song, Paul Valiant
- Abstract要約: 本稿では,アルゴリズムの微細な最適性を分析するための新しい定義フレームワークを提案する。
平均値の中央値は近傍最適であり, 一定の要因が得られている。
定数係数のずれのない近傍分離推定器を見つけることは自由である。
- 参考スコア（独自算出の注目度）: 10.889739958035536
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: There is growing interest in improving our algorithmic understanding of
fundamental statistical problems such as mean estimation, driven by the goal of
understanding the limits of what we can extract from valuable data. The state
of the art results for mean estimation in $\mathbb{R}$ are 1) the optimal
sub-Gaussian mean estimator by [LV22], with the tight sub-Gaussian constant for
all distributions with finite but unknown variance, and 2) the analysis of the
median-of-means algorithm by [BCL13] and a lower bound by [DLLO16],
characterizing the big-O optimal errors for distributions for which only a
$1+\alpha$ moment exists for $\alpha \in (0,1)$. Both results, however, are
optimal only in the worst case. We initiate the fine-grained study of the mean
estimation problem: Can algorithms leverage useful features of the input
distribution to beat the sub-Gaussian rate, without explicit knowledge of such
features?
We resolve this question with an unexpectedly nuanced answer: "Yes in limited
regimes, but in general no". For any distribution $p$ with a finite mean, we
construct a distribution $q$ whose mean is well-separated from $p$'s, yet $p$
and $q$ are not distinguishable with high probability, and $q$ further
preserves $p$'s moments up to constants. The main consequence is that no
reasonable estimator can asymptotically achieve better than the sub-Gaussian
error rate for any distribution, matching the worst-case result of [LV22]. More
generally, we introduce a new definitional framework to analyze the
fine-grained optimality of algorithms, which we call "neighborhood optimality",
interpolating between the unattainably strong "instance optimality" and the
trivially weak "admissibility" definitions. Applying the new framework, we show
that median-of-means is neighborhood optimal, up to constant factors. It is
open to find a neighborhood-optimal estimator without constant factor
slackness.
- Abstract（参考訳）: 価値あるデータから何を抽出するかの限界を理解することを目標に、平均推定のような基本的な統計問題に対するアルゴリズム的理解の改善に関心が高まっている。
$\mathbb{R}$における平均推定のためのアート結果の状態は
1) 有限であるが未知の分散を持つすべての分布に対する厳密な準ガウス定数を持つ[LV22]による最適ガウス平均推定器
2)[BCL13]による平均値アルゴリズムと[DLLO16]による下限値の解析により,$\alpha \in (0,1)$に対して1+\alpha$のモーメントしか存在しない分布に対する大O最適誤差を特徴づける。
しかし、どちらの結果も最悪の場合にのみ最適である。
アルゴリズムは、入力分布の有用な特徴を利用して、これらの特徴を明示的に知ることなく、サブガウス率を破ることができるか?
我々はこの問題を予期せぬほど微妙な答えで解決する:「限定的な体制ではそうだが、一般的にはノーだ」。
有限平均を持つ任意の分布 $p$ に対して、平均は $p$ から十分に分離されているが、$p$ と $q$ は高い確率で区別できない分布 $q$ を構築し、$q$ はさらに $p$'s moments を定数まで保存する。
主な結果は、[lv22]の最悪の結果に合致した、任意の分布のサブガウス誤差率よりも漸近的に達成できないということである。
より一般的に、我々は「隣接最適性」と呼ばれるアルゴリズムのきめ細かい最適性を分析するための新しい定義フレームワークを導入し、不確定に強い「インスタンス最適性」と自明に弱い「許容可能性」の定義を補間する。
新しい枠組みを適用すると、平均値中央値は、一定要素までの近傍最適であることが示される。
定数係数のずれのない近傍最適推定器を見つけることはオープンである。
関連論文リスト
- Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳（メタデータ） (2024-02-14T07:52:00Z) - Optimal score estimation via empirical Bayes smoothing [13.685846094715364]
未知確率分布$rho*$のスコア関数を$n$独立分布および$d$次元における同一分布観測から推定する問題について検討する。
ガウスカーネルに基づく正規化スコア推定器は、一致するミニマックス下界によって最適に示され、この値が得られることを示す。
論文 参考訳（メタデータ） (2024-02-12T16:17:40Z) - $L^1$ Estimation: On the Optimality of Linear Estimators [70.75102576909295]
この研究は、条件中央値の線型性を誘導する$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) - General Gaussian Noise Mechanisms and Their Optimality for Unbiased Mean
Estimation [58.03500081540042]
プライベート平均推定に対する古典的なアプローチは、真の平均を計算し、バイアスのないがおそらく相関のあるガウスノイズを加えることである。
すべての入力データセットに対して、集中的な差分プライバシーを満たす非バイアス平均推定器が、少なくとも多くのエラーをもたらすことを示す。
論文 参考訳（メタデータ） (2023-01-31T18:47:42Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - Robust Sparse Mean Estimation via Sum of Squares [42.526664955704746]
本研究では,高次元スパース平均推定の問題点を,逆数外乱の$epsilon$-fractionの存在下で検討する。
我々のアルゴリズムは、サム・オブ・スクエア(Sum-of-Squares)ベースのアルゴリズムアプローチに従う。
論文 参考訳（メタデータ） (2022-06-07T16:49:54Z) - Near-Optimal High Probability Complexity Bounds for Non-Smooth
Stochastic Optimization with Heavy-Tailed Noise [63.304196997102494]
アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。
既存の非滑らか凸最適化法は、負のパワーまたは対数的な信頼度に依存する境界の複雑さを持つ。
クリッピングを用いた2つの勾配法に対して, 新たなステップサイズルールを提案する。
論文 参考訳（メタデータ） (2021-06-10T17:54:21Z) - Optimal Sub-Gaussian Mean Estimation in $\mathbb{R}$ [5.457150493905064]
ガウス下収束を考慮した新しい推定器を提案する。
我々の推定器はその分散に関する事前の知識を必要としない。
我々の推定器の構成と分析は、他の問題に一般化可能なフレームワークを提供する。
論文 参考訳（メタデータ） (2020-11-17T02:47:24Z) - Robust estimation via generalized quasi-gradients [28.292300073453877]
最近提案されたロバスト推定問題の多くが効率的に解ける理由を示す。
我々は「一般化された準次数」の存在を識別する
一般化された準勾配が存在することを示し、効率的なアルゴリズムを構築する。
論文 参考訳（メタデータ） (2020-05-28T15:14:33Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。