論文の概要: Limits of Approximating the Median Treatment Effect
- arxiv url: http://arxiv.org/abs/2403.10618v1
- Date: Fri, 15 Mar 2024 18:30:06 GMT
- ステータス: 処理完了
- システム内更新日: 2024-03-19 22:34:14.739206
- Title: Limits of Approximating the Median Treatment Effect
- Title(参考訳): 中間処理効果の近似限界
- Authors: Raghavendra Addanki, Siddharth Bhandari,
- Abstract要約: メディア処理効果は推定不可能であり、$mathbfa-b$の値のソート順序に依存する新しい近似の概念を詳述する。
MTEを推定するアルゴリズムはすべて、変数を計算するアルゴリズムの誤差に匹敵する近似誤差が得られることを示す。
- 参考スコア(独自算出の注目度): 5.065947993017158
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Average Treatment Effect (ATE) estimation is a well-studied problem in causal inference. However, it does not necessarily capture the heterogeneity in the data, and several approaches have been proposed to tackle the issue, including estimating the Quantile Treatment Effects. In the finite population setting containing $n$ individuals, with treatment and control values denoted by the potential outcome vectors $\mathbf{a}, \mathbf{b}$, much of the prior work focused on estimating median$(\mathbf{a}) -$ median$(\mathbf{b})$, where median($\mathbf x$) denotes the median value in the sorted ordering of all the values in vector $\mathbf x$. It is known that estimating the difference of medians is easier than the desired estimand of median$(\mathbf{a-b})$, called the Median Treatment Effect (MTE). The fundamental problem of causal inference -- for every individual $i$, we can only observe one of the potential outcome values, i.e., either the value $a_i$ or $b_i$, but not both, makes estimating MTE particularly challenging. In this work, we argue that MTE is not estimable and detail a novel notion of approximation that relies on the sorted order of the values in $\mathbf{a-b}$. Next, we identify a quantity called variability that exactly captures the complexity of MTE estimation. By drawing connections to instance-optimality studied in theoretical computer science, we show that every algorithm for estimating the MTE obtains an approximation error that is no better than the error of an algorithm that computes variability. Finally, we provide a simple linear time algorithm for computing the variability exactly. Unlike much prior work, a particular highlight of our work is that we make no assumptions about how the potential outcome vectors are generated or how they are correlated, except that the potential outcome values are $k$-ary, i.e., take one of $k$ discrete values.
- Abstract(参考訳): 平均治療効果(ATE)推定は因果推論においてよく研究されている問題である。
しかし、これは必ずしもデータの不均一性を捉えるものではなく、量子処理効果を推定するなど、この問題に取り組むためのいくつかのアプローチが提案されている。
n$個人を含む有限集団設定では、潜在的結果ベクトル $\mathbf{a}, \mathbf{b}$ で表される処理と制御値を持つが、以前の研究の多くは、中央値$(\mathbf{a}) -$中央値$(\mathbf{b})$ を推定することに焦点を当てており、中央値($\mathbf x$)はベクトル$\mathbf x$ における全ての値のソート順序の中央値を表す。
中央値の差を推定するのは、中央値(\mathbf{a-b})$よりも容易であることが知られている。
因果推論の根本的な問題は、すべての$i$に対して、潜在的な結果値の1つ、すなわち$a_i$か$b_i$のどちらかしか観察できないことである。
この研究において、MTE は推定可能ではなく、$\mathbf{a-b}$ の値のソート順序に依存する新しい近似の概念を詳述する。
次に、MTE推定の複雑さを正確に捉える可変性という量を特定する。
理論計算機科学で研究されたインスタンス最適性への接続を描画することにより、MTEを推定する全てのアルゴリズムが、可変性を計算するアルゴリズムの誤差に匹敵する近似誤差を得ることを示す。
最後に、変数を正確に計算するための単純な線形時間アルゴリズムを提供する。
多くの先行研究とは異なり、我々の研究の顕著なハイライトは、潜在的な結果ベクトルがどのように生成され、どのように相関するかを仮定することではなく、潜在的な結果値が$k$-ary、すなわち$k$離散値の1つを取ることである。
関連論文リスト
- Rate Analysis of Coupled Distributed Stochastic Approximation for Misspecified Optimization [0.552480439325792]
パラメトリックな特徴を持つ不完全な情報を持つ分散最適化問題として$n$のエージェントを考える。
本稿では,各エージェントが未知パラメータの現在の信念を更新する分散近似アルゴリズムを提案する。
アルゴリズムの性能に影響を与える因子を定量的に解析し、決定変数の平均二乗誤差が$mathcalO(frac1nk)+mathcalOleft(frac1sqrtn (1-rho_w)right)frac1k1.5で有界であることを証明する。
論文 参考訳(メタデータ) (2024-04-21T14:18:49Z) - Near-Optimal Mean Estimation with Unknown, Heteroskedastic Variances [15.990720051907864]
Subset-of-Signalsモデルはヘテロスケダティック平均推定のベンチマークとして機能する。
我々のアルゴリズムは、このオープンな問題を対数的要因に分解する。
たとえ$d=2$であっても、我々の手法は各サンプルのばらつきを知るのに匹敵するレートを可能にします。
論文 参考訳(メタデータ) (2023-12-05T01:13:10Z) - Contextual Combinatorial Bandits with Probabilistically Triggered Arms [55.9237004478033]
確率的に誘発される腕(C$2$MAB-T)を様々な滑らかさ条件下で検討した。
トリガー変調 (TPM) 条件の下では、C$2$-UC-Tアルゴリズムを考案し、後悔すべき$tildeO(dsqrtT)$を導出する。
論文 参考訳(メタデータ) (2023-03-30T02:51:00Z) - Replicable Clustering [57.19013971737493]
我々は,統計学的な$k$-medians,統計学的な$k$-means,統計学的な$k$-centers問題のアルゴリズムをブラックボックス方式で近似ルーチンを用いて提案する。
理論的結果を検証するブラックボックスとしてsklearnの$k$-means++実装を用いた2次元合成分布の実験も行っている。
論文 参考訳(メタデータ) (2023-02-20T23:29:43Z) - Estimating Optimal Policy Value in General Linear Contextual Bandits [50.008542459050155]
多くのバンドイット問題において、政策によって達成可能な最大報酬は、前もって不明であることが多い。
我々は,最適政策が学習される前に,サブ線形データ構造における最適政策値を推定する問題を考察する。
V*$で問題依存上界を推定する,より実用的で効率的なアルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-02-19T01:09:24Z) - Supervised Training of Conditional Monge Maps [107.78770597815242]
最適輸送(OT)理論は、多くの可能な選択の中から確率測度を他のものにマッピングする最も効率的な方法を定義し、選択する一般的な原理を記述している。
本研究では,コンテキスト変数に条件付きOTマップの族を推定するマルチタスク手法であるCondOTを紹介する。
本研究では,CondOTの遺伝的・治療的摂動の任意の組み合わせが単一細胞に与える影響を推測する能力を示す。
論文 参考訳(メタデータ) (2022-06-28T19:34:44Z) - Faster Algorithms and Constant Lower Bounds for the Worst-Case Expected
Error [0.3997680012976965]
目標は、最悪の予測エラーを最小限に抑える推定器を設計することである。
Chen, Valiant および Valiant は、データ値が $ell_infty$-normalized の場合、平均の推定値を計算する時間アルゴリズムが存在することを示した。
本稿では,オンライン凸最適化に基づく最適半線形推定器の近似アルゴリズムを設計する。
論文 参考訳(メタデータ) (2021-12-27T18:47:25Z) - Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean
Estimation [58.24280149662003]
本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。
我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
論文 参考訳(メタデータ) (2021-06-16T03:34:14Z) - 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) - List-Decodable Mean Estimation via Iterative Multi-Filtering [44.805549762166926]
未知の$alpha$-fraction of points in $T$は未知の平均と有界な共分散分布$D$から引き出される。
仮説ベクトルの小さなリストを出力し、その中の少なくとも一方が$D$に近いようにする。
より詳しくは、本アルゴリズムはサンプリングと計算効率が良く、情報理論上の準最適誤差を実現する。
論文 参考訳(メタデータ) (2020-06-18T17:47:37Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。