論文の概要: 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$正規化されるとき、このアルゴリズムは行列列の最上位固有ベクトルを反復計算し、乗法近似係数を失うことはない。
データ収集プロセスで満たされた場合、平均の任意の(必ずしも半線形ではない)推定器が常に最悪のケース予測誤差を持つことを示す単純な組合せ条件を述べることで、これらの肯定的な結果を補完する。
関連論文リスト
- Obtaining Lower Query Complexities through Lightweight Zeroth-Order Proximal Gradient Algorithms [65.42376001308064]
複素勾配問題に対する2つの分散化ZO推定器を提案する。
我々は、現在最先端の機能複雑性を$mathcalOleft(minfracdn1/2epsilon2, fracdepsilon3right)$から$tildecalOleft(fracdepsilon2right)$に改善する。
論文 参考訳（メタデータ） (2024-10-03T15:04:01Z) - Uncertainty quantification for iterative algorithms in linear models with application to early stopping [4.150180443030652]
本稿では,高次元線形回帰問題における反復アルゴリズムから得られた繰り返し$hbb1,dots,hbbT$について検討する。
解析および提案した推定器は、GD(Gradient Descent)、GD(GD)およびFast Iterative Soft-Thresholding(FISTA)などの加速変種に適用できる。
論文 参考訳（メタデータ） (2024-04-27T10:20:41Z) - Robust Sparse Estimation for Gaussians with Optimal Error under Huber Contamination [42.526664955704746]
本研究では,平均推定,PCA,線形回帰に着目したハマー汚染モデルにおけるスパース推定タスクについて検討する。
それぞれのタスクに対して、最適なエラー保証を備えた最初のサンプルと計算効率の良い頑健な推定器を与える。
技術レベルでは、スパース方式における新しい多次元フィルタリング法を開発し、他の応用を見出すことができる。
論文 参考訳（メタデータ） (2024-03-15T15:51:27Z) - 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) - 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) - Private Stochastic Convex Optimization: Optimal Rates in Linear Time [74.47681868973598]
本研究では,凸損失関数の分布から得られた個体群損失を最小化する問題について検討する。
Bassilyらによる最近の研究は、$n$のサンプルを与えられた過剰な人口損失の最適境界を確立している。
本稿では,余剰損失に対する最適境界を達成するとともに,$O(minn, n2/d)$グラデーション計算を用いて凸最適化アルゴリズムを導出する2つの新しい手法について述べる。
論文 参考訳（メタデータ） (2020-05-10T19:52:03Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。