論文の概要: Approximation Algorithms for D-optimal Design

• arxiv url: http://arxiv.org/abs/1802.08372v3
• Date: Thu, 05 Dec 2024 15:29:42 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-12-08 16:57:45.575350
• Title: Approximation Algorithms for D-optimal Design
• Title（参考訳）: D最適設計のための近似アルゴリズム
• Authors: Mohit Singh, Weijun Xie,
• Abstract要約: 実験設計は古典的な統計問題であり、その目的は線形測定から未知の$m$次元ベクトル$beta$を推定することである。 実験的な設計問題に対しては、与えられた$n$実験から$k$を選び、未知のパラメータの最も正確な推定を行うことが目的である。 誤差推定の最も堅牢な尺度の1つとして、推定誤差に対する信頼楕円体の体積を最小化する$D$-optimality criterionについて検討する。
• 参考スコア（独自算出の注目度）: 4.889013411494113
• License:
• Abstract: Experimental design is a classical statistics problem and its aim is to estimate an unknown $m$-dimensional vector $\beta$ from linear measurements where a Gaussian noise is introduced in each measurement. For the combinatorial experimental design problem, the goal is to pick $k$ out of the given $n$ experiments so as to make the most accurate estimate of the unknown parameters, denoted as $\hat{\beta}$. In this paper, we will study one of the most robust measures of error estimation - $D$-optimality criterion, which corresponds to minimizing the volume of the confidence ellipsoid for the estimation error $\beta-\hat{\beta}$. The problem gives rise to two natural variants depending on whether repetitions of experiments are allowed or not. We first propose an approximation algorithm with a $\frac1e$-approximation for the $D$-optimal design problem with and without repetitions, giving the first constant factor approximation for the problem. We then analyze another sampling approximation algorithm and prove that it is $(1-\epsilon)$-approximation if $k\geq \frac{4m}{\epsilon}+\frac{12}{\epsilon^2}\log(\frac{1}{\epsilon})$ for any $\epsilon \in (0,1)$. Finally, for $D$-optimal design with repetitions, we study a different algorithm proposed by literature and show that it can improve this asymptotic approximation ratio.
• Abstract（参考訳）: 実験設計は古典的な統計問題であり、その目的は、ガウスノイズが各測定に導入された線形測定から未知の$m$-dimensional vector $\beta$を推定することである。 組合せ実験設計問題では、与えられた$n$実験から$k$を選び、未知のパラメータの最も正確な推定を$\hat{\beta}$と表す。 本稿では,推定誤差$\beta-\hat{\beta}$に対する信頼楕円体の体積を最小化するD$-optimality criterionについて検討する。 この問題は、実験の繰り返しが許されるか否かによって、2つの自然な変種が生じる。 まず,D$-optimal Design 問題に対して $\frac1e$-approximation を用いた近似アルゴリズムを提案する。 次に、別のサンプリング近似アルゴリズムを分析し、$(1-\epsilon)$-approximation if $k\geq \frac{4m}{\epsilon}+\frac{12}{\epsilon^2}\log(\frac{1}{\epsilon})$ for any $\epsilon \in (0,1)$とする。 最後に、繰り返しを伴うD$-optimal設計に対して、文献によって提案される異なるアルゴリズムについて検討し、この漸近近似比を改善することができることを示す。

関連論文リスト

• Entangled Mean Estimation in High-Dimensions [36.97113089188035]
  信号のサブセットモデルにおける高次元エンタングルド平均推定の課題について検討する。 最適誤差(polylogarithmic factor)は$f(alpha,N) + sqrtD/(alpha N)$であり、$f(alpha,N)$は1次元問題の誤差であり、第二項は準ガウス誤差率である。
  論文  参考訳（メタデータ） (2025-01-09T18:31:35Z)
• Robust Sparse Estimation for Gaussians with Optimal Error under Huber Contamination [42.526664955704746]
  本研究では,平均推定,PCA,線形回帰に着目したハマー汚染モデルにおけるスパース推定タスクについて検討する。 それぞれのタスクに対して、最適なエラー保証を備えた最初のサンプルと計算効率の良い頑健な推定器を与える。 技術レベルでは、スパース方式における新しい多次元フィルタリング法を開発し、他の応用を見出すことができる。
  論文  参考訳（メタデータ） (2024-03-15T15:51:27Z)
• Near-Optimal Algorithms for Gaussians with Huber Contamination: Mean Estimation and Linear Regression [44.13655983242414]
  最適誤差保証付きニア・ニア・ニア・リニア時間アルゴリズムの最初のサンプルを設計する。 堅牢な線形回帰のために、サンプル複雑性$n = tildeO(d/epsilon2)$と、ターゲット回帰器を$ell$-$O(epsilon)$で近似するほぼ線形ランタイムを持つ最初のアルゴリズムを与える。 これは、文献のオープンな疑問に答え、最適なエラー保証を達成するための最初のサンプルとタイムアルゴリズムである。
  論文  参考訳（メタデータ） (2023-12-04T00:31:16Z)
• Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noise [50.64137465792738]
  この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。 我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
  論文  参考訳（メタデータ） (2023-07-13T18:59:28Z)
• An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue Optimization Problems [76.2042837251496]
  相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。 注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。 本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
  論文  参考訳（メタデータ） (2023-06-30T08:34:29Z)
• Data Structures for Density Estimation [66.36971978162461]
  p$のサブリニア数($n$)が与えられた場合、主な結果は$k$のサブリニアで$v_i$を識別する最初のデータ構造になります。 また、Acharyaなどのアルゴリズムの改良版も提供します。
  論文  参考訳（メタデータ） (2023-06-20T06:13:56Z)
• Approximate Function Evaluation via Multi-Armed Bandits [51.146684847667125]
  既知の滑らかな関数 $f$ の値を未知の点 $boldsymbolmu in mathbbRn$ で推定する問題について検討する。 我々は、各座標の重要性に応じてサンプルを学習するインスタンス適応アルゴリズムを設計し、少なくとも1-delta$の確率で$epsilon$の正確な推定値である$f(boldsymbolmu)$を返す。
  論文  参考訳（メタデータ） (2022-03-18T18:50:52Z)
• Robust Estimation for Random Graphs [47.07886511972046]
  我々は、$n$ノード上のErdHos-R'enyiランダムグラフのパラメータ$p$を頑健に推定する問題について検討する。 情報理論の限界であるすべての$gamma 1/2$に対して、同様の精度で非効率なアルゴリズムを与える。
  論文  参考訳（メタデータ） (2021-11-09T18:43:25Z)
• Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimation [58.24280149662003]
  本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。 我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2021-06-16T03:34:14Z)
• Maximizing Determinants under Matroid Constraints [69.25768526213689]
  我々は、$det(sum_i in Sv_i v_i v_itop)$が最大になるような基底を$S$$$$M$とする問題を研究する。 この問題は、実験的なデザイン、商品の公平な割り当て、ネットワーク設計、機械学習など、さまざまな分野に現れている。
  論文  参考訳（メタデータ） (2020-04-16T19:16:38Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。