論文の概要: Faster Algorithms and Constant Lower Bounds for the Worst-Case Expected
Error
- arxiv url: http://arxiv.org/abs/2112.13832v1
- Date: Mon, 27 Dec 2021 18:47:25 GMT
- ステータス: 処理完了
- システム内更新日: 2021-12-28 17:30:36.596229
- Title: Faster Algorithms and Constant Lower Bounds for the Worst-Case Expected
Error
- Title(参考訳): 最悪の場合の予測誤差に対する高速アルゴリズムと定数下限
- Authors: Jonah Brown-Cohen
- Abstract要約: 目標は、最悪の予測エラーを最小限に抑える推定器を設計することである。
Chen, Valiant および Valiant は、データ値が $ell_infty$-normalized の場合、平均の推定値を計算する時間アルゴリズムが存在することを示した。
本稿では,オンライン凸最適化に基づく最適半線形推定器の近似アルゴリズムを設計する。
- 参考スコア(独自算出の注目度): 0.3997680012976965
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The study of statistical estimation without distributional assumptions on
data values, but with knowledge of data collection methods was recently
introduced by Chen, Valiant and Valiant (NeurIPS 2020). In this framework, the
goal is to design estimators that minimize the worst-case expected error. Here
the expectation is over a known, randomized data collection process from some
population, and the data values corresponding to each element of the population
are assumed to be worst-case.
Chen, Valiant and Valiant show that, when data values are
$\ell_{\infty}$-normalized, there is a polynomial time algorithm to compute an
estimator for the mean with worst-case expected error that is within a factor
$\frac{\pi}{2}$ of the optimum within the natural class of semilinear
estimators. However, their algorithm is based on optimizing a somewhat complex
concave objective function over a constrained set of positive semidefinite
matrices, and thus does not come with explicit runtime guarantees beyond being
polynomial time in the input.
In this paper we design provably efficient algorithms for approximating the
optimal semilinear estimator based on online convex optimization. In the
setting where data values are $\ell_{\infty}$-normalized, our algorithm
achieves a $\frac{\pi}{2}$-approximation by iteratively solving a sequence of
standard SDPs. When data values are $\ell_2$-normalized, our algorithm
iteratively computes the top eigenvector of a sequence of matrices, and does
not lose any multiplicative approximation factor. We complement these positive
results by stating a simple combinatorial condition which, if satisfied by a
data collection process, implies that any (not necessarily semilinear)
estimator for the mean has constant worst-case expected error.
- Abstract(参考訳): データ値の分布的仮定を伴わない統計的推定法の研究が最近, chen, valiant, valiant (neurips 2020) によって紹介された。
このフレームワークでは、最悪のエラーを最小限に抑える推定器を設計することが目標である。
ここでは、一部の個体群から既知のランダム化データ収集プロセスが期待され、個体群の各要素に対応するデータ値が最悪のケースであると仮定する。
Chen, Valiant および Valiant は、データ値が $\ell_{\infty}$-正規化されているとき、半線形推定器の自然クラスにおける最適値の係数 $\frac{\pi}{2}$ 内の最悪の予測誤差の平均に対する推定器を計算する多項式時間アルゴリズムが存在することを示した。
しかし、それらのアルゴリズムは、正の半定値行列の制約付き集合に対して幾分複雑な凸目的関数を最適化することに基づいているため、入力における多項式時間以上の明示的なランタイム保証は持たない。
本稿では,オンライン凸最適化に基づく最適半線形推定器の近似アルゴリズムの設計を行う。
データ値が$\ell_{\infty}$-正規化されている場合、我々のアルゴリズムは標準SDPの列を反復的に解くことによって$\frac{\pi}{2}$-近似を達成する。
データ値が$\ell_2$正規化されるとき、このアルゴリズムは行列列の最上位固有ベクトルを反復計算し、乗法近似係数を失うことはない。
データ収集プロセスで満たされた場合、平均の任意の(必ずしも半線形ではない)推定器が常に最悪のケース予測誤差を持つことを示す単純な組合せ条件を述べることで、これらの肯定的な結果を補完する。
関連論文リスト
- Stochastic Optimization for Non-convex Problem with Inexact Hessian
Matrix, Gradient, and Function [99.31457740916815]
信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。
TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
論文 参考訳(メタデータ) (2023-10-18T10:29:58Z) - Privately Estimating a Gaussian: Efficient, Robust and Optimal [6.901744415870126]
純微分プライバシー(DP)モデルと近似微分プライバシー(DP)モデルの両方において、ガウス分布をプライベートに推定する効率的なアルゴリズムを提供する。
純粋なDP設定では、未知の$d$次元ガウス分布を任意の全変分誤差まで推定する効率的なアルゴリズムを与える。
平均推定の特別な場合、我々のアルゴリズムは$widetilde O(d1.5)$の最適なサンプル複雑性を達成し、以前の作業から$widetilde O(d1.5)$のバウンドを改善する。
論文 参考訳(メタデータ) (2022-12-15T18:27:39Z) - Optimal Randomized Approximations for Matrix based Renyi's Entropy [16.651155375441796]
整数次数$alpha$の場合のランダム近似と非整数$alpha$の場合の直列近似を開発する。
大規模シミュレーションと実世界の応用は、開発した近似の有効性を検証する。
論文 参考訳(メタデータ) (2022-05-16T02:24:52Z) - Improving Computational Complexity in Statistical Models with
Second-Order Information [32.64382185990981]
パラメトリック統計モデルにおけるパラメータ推定のための正規化勾配降下法(NormGD)について検討する。
我々は、NormGDアルゴリズムが最終的な統計的半径に達するために最適な計算量$mathcalO(n)$を達成することを示した。
この計算複雑性は、固定ステップサイズ勾配勾配アルゴリズムよりも安価である。
論文 参考訳(メタデータ) (2022-02-09T01:32:50Z) - Sparse PCA via $l_{2,p}$-Norm Regularization for Unsupervised Feature
Selection [138.97647716793333]
再構成誤差を$l_2,p$ノルム正規化と組み合わせることで,単純かつ効率的な特徴選択手法を提案する。
提案する非教師付きモデルを解くための効率的な最適化アルゴリズムを提案し,アルゴリズムの収束と計算の複雑さを理論的に解析する。
論文 参考訳(メタデータ) (2020-12-29T04:08:38Z) - List-Decodable Mean Estimation in Nearly-PCA Time [50.79691056481693]
高次元におけるリストデコタブル平均推定の基本的な課題について検討する。
我々のアルゴリズムは、すべての$k = O(sqrtd) cup Omega(d)$に対して$widetildeO(ndk)$で実行されます。
我々のアルゴリズムの変種は、すべての$k$に対してランタイム$widetildeO(ndk)$を持ち、リカバリ保証の$O(sqrtlog k)$ Factorを犠牲にしている。
論文 参考訳(メタデータ) (2020-11-19T17:21:37Z) - Online Model Selection for Reinforcement Learning with Function
Approximation [50.008542459050155]
我々は、$tildeO(L5/6 T2/3)$ regretで最適な複雑性に適応するメタアルゴリズムを提案する。
また、メタアルゴリズムは、インスタンス依存の後悔境界を著しく改善することを示す。
論文 参考訳(メタデータ) (2020-11-19T10:00:54Z) - Debiasing Distributed Second Order Optimization with Surrogate Sketching
and Scaled Regularization [101.5159744660701]
分散第2次最適化において、標準的な戦略は、データの小さなスケッチやバッチに基づいて、多くの局所的な見積もりを平均化することである。
本稿では,分散二階法における収束率の理論的および実証的改善を両立させるため,局所的な推定を嫌悪する新しい手法を提案する。
論文 参考訳(メタデータ) (2020-07-02T18:08:14Z) - Median Matrix Completion: from Embarrassment to Optimality [16.667260586938234]
絶対偏差損失を持つ行列の完全性を考察し,中央値行列の推定値を求める。
中央値のいくつかの魅力的な性質にもかかわらず、非滑らかな絶対偏差損失は計算に挑戦する。
そこで我々は,非効率な推定器を(最適に近い)行列補完手順に変換する改良ステップを提案する。
論文 参考訳(メタデータ) (2020-06-18T10:01:22Z) - Optimal Distributed Subsampling for Maximum Quasi-Likelihood Estimators
with Massive Data [20.79270369203348]
既存の手法は主に高い計算効率のために置換されたサブサンプリングに焦点を当てている。
まず,準類似度推定の文脈で最適なサブサンプリング確率を導出する。
我々は,分散サブサンプリングフレームワークを開発し,全データの小さなパーティションで統計を同時に計算する。
論文 参考訳(メタデータ) (2020-05-21T02:46:56Z) - Private Stochastic Convex Optimization: Optimal Rates in Linear Time [74.47681868973598]
本研究では,凸損失関数の分布から得られた個体群損失を最小化する問題について検討する。
Bassilyらによる最近の研究は、$n$のサンプルを与えられた過剰な人口損失の最適境界を確立している。
本稿では,余剰損失に対する最適境界を達成するとともに,$O(minn, n2/d)$グラデーション計算を用いて凸最適化アルゴリズムを導出する2つの新しい手法について述べる。
論文 参考訳(メタデータ) (2020-05-10T19:52:03Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。