Chung and Romano (2013) Exact and Asymptotically Robust Permutation Tests, AOS.
Introduction
- IID.
- IID. と は independent.
- Let and write
\begin{align*}Z = (Z_1, \ldots, Z_N) = (X_1, \ldots, X_m, Y_1, \ldots, Y_n)\end{align*}
- . であるとき, の同時分布は任意の の分布に等しい。ただし, は の permutation.
- をすべての permutation の集合とする。()
- 検定統計量 . 原則的にはパワーが最大になるように を選びたい。
- をすべての permutation について計算し,
\begin{align*}T_{m,n}^{(1)} \le T_{m,n}^{(2)} \le \cdots \le T_{m,n}^{(N!)} \end{align*}
と並べる。
- for a nominal level
- if , if とおく。Tieの場合は論文参照。
- このとき,for any ,
\begin{align*}E_{P,Q}[\phi(Z)] = \alpha \end{align*}
- また, とおく。
Permutation test: Reject if or
- 帰無仮説 where について,permutation testは必ずちょうどの棄却率を有する = Exactness
- が より大きい時に問題が生じる。なぜなら帰無仮説のもとでpermutateしたデータの分布が元のデータの分布と異なるから。
- たとえば 。検定統計量としては 。このとき,permutation testは については検定力がない。
- Neuhaus (1993): by proper studentization of a test statistic, the permutation test can result in asymptotically valid inference even when the underlying distributions are not the same.
- The goal of this paper: we would like to retain the exactness property when , and also have the asymptotic rejection probability be for the more general null hypothesis specifying the parameter.
Robust studentized two-sample test
- を real-valued parameterとする。興味のある帰無仮説は 。
- Assume that and satisfy
\begin{align*}m^{1/2}(\hat \theta_m - \theta(P)) & = \frac{1}{\sqrt{m}}\sum_{i = 1}^m f_P(X_i) + o_P(1) \\ n^{1/2}(\hat \theta_n - \theta(Q)) & = \frac{1}{\sqrt{n}}\sum_{j = 1}^n f_Q(Y_j) + o_P(1) \end{align*}
- また,これと同様のasymptotic linearityが混合分布 からのIIDサンプルについても成り立つと仮定する。
Theorem 2.1: 帰無仮説を , 検定統計量を とする。このとき, の permutation distribution について, が成立する。ただし,, .
- Remark: の真の漸近分布は,平均 ・ 分散 の正規分布。これは の極限と異なる。
Theorem 2.2: と の一致推定量として と が得られるとする。また, とする。このとき, の permutation distribution について, が成立する。
- k-sampleのケース:Theorem 3.1 参照。
Li, Cai & Li (2020) Transfer learning for high-dimensional linear regression: prediction, estimation, and minimax optimality, arXiv.
Introduction
- Target model: , .
- , can be larger than . : number of nonzero elements of . is much smaller than .
- Auxiliary models: , , .
- と は一般的に異なる.しかしもし両者が近い値をとるならば,target model をより効率的に推定できるかもしれない.
- Let . "Informative" auxiliary samples を次の集合で定義する:
\begin{align*} \mathcal{A}_q := \{k : ||\delta^{(k)}||_q \le h \}, \;\; \text{for} \;\; q \in [0,1] \end{align*}
- が小さいほど は informative. が空集合であることも許容.
Estimation with known informative auxiliary samples
- Let .
Oracle trans-Lasso algorithm
- for some
- Let , where for some .
- の probability limit を とする.また, である.
- Parameter space:
- 各 について, i.i.d. Gaussian + i.i.d. sub-Gaussian など仮定し,それらの下で以下を得る:
Theorem 1.
- が空集合の時は右辺は .これは通常のLassoと同じレート.
- ならば転移学習によって効率性が改善する.つまり, のほうが よりはるかに sparse である必要.
Theorem 2.
- Theorem 1 + Theorem 2 => Oracle trans-Lasso は minimax rate optimal.
Unknown Set of Informative Auxiliary Samples
- Let denote the sum of squared prediction error under , and denote an -dimensional simplex.
Oracle trans-Lasso algorithm
- Let be a random subset of .
- Construct candidate sets of , with .
- 各 と を用いて trans-Lasso を回す.その結果を とする.
- Compute Output .
- を空集合にしておくことで,auxiliary sample が完全に uninformative でも結果が(そこまで)悪化しないように保険.
- ならば Oracle trans-Lasso に近い結果が期待できる.
- として すべての組み合わせを考えるのは計算が大変(理論的にはOK??).
- どうやって を決めればいい?
- の構成により, と では前者のほうがより sparse.
- が sparse な -th sample から に追加すればよい.ただし は未知なので と を用いて推定.具体的な手順は論文参照.
諸々の仮定の下で以下を得る:
Theorem 3.
Buhlmann and van de Geer (2011) Section 6.2 Least squares and the Lasso 2/2
6.2.2 続き
- Let , , .
- 明らかに .
Lemma 6.3: On with , .
Proof.
Lemma 6.1 と から,
\begin{align*}2||\mathbf{X}(\hat \beta - \beta^0) ||_2^2/n + 2\lambda || \hat \beta ||_1 \le \lambda ||\hat \beta - \beta^0|| + 2 \lambda || \beta^0 ||_1\end{align*}
また,三角不等式から
\begin{align*} || \hat \beta ||_1 = || \hat \beta_{S_0} ||_1 + || \hat \beta_{S_0^c} ||_1 \ge || \beta_{S_0}^0 ||_1 - || \hat \beta_{S_0} - \beta_{S_0}^0 ||_1 + || \hat \beta_{S_0^c} ||_1 \end{align*}
さらに,, から結果を得る.
- Cauchy-Schwarz inequality から,
- Recall that , .
- ここで,ある について ならば,不等式をさらに進めることができる.
- 一方, はランダムなので上の不等式を満たす を直接仮定することはできない. のある集合上で一様に不等式を満たす を考える.
- Lemma 6.3 から, の上で を満たす.
Compatibility condition: ある と について,.
- Compatibility condition はどのようなときに満たされる?
Theorem 6.1: Compatibility condition + + .
\begin{align*}||\mathbf{X}(\hat \beta - \beta^0) ||_2^2/n \le 4 \lambda^2 s_0 / \phi_0^2, \quad ||\hat \beta - \beta^0||_1 \le 4 \lambda s_0 / \phi_0^2 \end{align*}
Proof.
Lemma 6.3 から
\begin{align*} 2||\mathbf{X}(\hat \beta - \beta^0) ||_2^2/n + \lambda||\hat \beta - \beta^0||_1 & = 2||\mathbf{X}(\hat \beta - \beta^0) ||_2^2/n + \lambda||\hat \beta_{S_0} - \beta^0_{S_0}||_1 + \lambda ||\hat \beta_{S_0^c}||_1 \\ & = 4 \lambda ||\hat \beta_{S_0} - \beta^0_{S_0}||_1 \\ & \le 4 \lambda \sqrt{s_0} ||\hat \beta_{S_0} - \beta^0_{S_0}||_2 \\ & \le 4 \lambda \sqrt{s_0} ||\mathbf{X}(\hat \beta - \beta^0)||_2/(\sqrt{n}\phi_0) \\ & \le ||\mathbf{X}(\hat \beta - \beta^0)||_2^2/n + 4 \lambda^2 s_0/\phi_0^2 \end{align*}
最後の不等式では を使った.
Buhlmann and van de Geer (2011) Section 6.2 Least squares and the Lasso 1/2
6.2.1 Introduction
- , . In matrix notation, .
- は固定, は i.i.d. とする.
For the moment, とおく.
- Least squares estimator:
- このとき,
- とくに, もわかる (as ).
- つまり, と正規化しておけば,各 を (全体としては ) の精度で推定可能.
以降では, と仮定する.
- Active set: , Sparsity index: .
- が既知かつ ならば,上の議論から,推定二乗誤差は になる.
- The Lasso:
\begin{align*}\hat \beta := \arg\min_\beta \left\{ \frac{|| \mathbf{Y} - \mathbf{X}\beta||_2^2}{n} + \lambda ||\beta||_1\right\}\end{align*}
- をうまく () のオーダーで選ぶと...
Oracle Inequality: .
つまり, がわからない場合でも だけの損失で済む.
6.2.2 The result assuming the truth is linear
Lemma 6.1 (Basic Inequality)
.
Proof.
の定義から,
\begin{align*}|| \mathbf{Y} - \mathbf{X}\hat \beta||_2^2/n + \lambda ||\hat \beta||_1 \le || \mathbf{Y} - \mathbf{X}\beta^0||_2^2/n + \lambda ||\beta^0||_1 \end{align*}
また, なので,これを代入すれば結果を得る.
- を empirical process part などと呼ぶ.
- Empirical process part は
\begin{align*}2|\epsilon^\top \mathbf{X}(\hat \beta - \beta^0)|/n \le 2 \left( \max_j |\epsilon^\top \mathbf{X}^{(j)}| \right) ||\hat \beta - \beta^0 ||_1/n\end{align*}
で bound できる.
- 通常, は empirical process part を dominate するように選ぶ.
- とするとき, とおくことで を目指す.
- Let and ().
Lemma 6.2
とする.このとき,任意の について, とおけば,
\begin{align*} \Pr(\mathcal{T}) \ge 1 - 2 \exp[-t^2/2]. \end{align*}
Proof.
仮定から, . したがって,
\begin{align*} \Pr(\mathcal{T}) & = \Pr\left(2 \max_j |\epsilon^\top \mathbf{X}^{(j)}|/n \gt 2 σ \sqrt{\frac{t^2 + 2 \log p}{n}} \right) \\ & = \Pr\left( \max_j |V_j| \gt \sqrt{t^2 + 2 \log p} \right) \\ & \le 2 p \exp \left[ - \frac{t^2 + 2 \log p}{2}\right] = 2 \exp \left[ - \frac{t^2}{2}\right]. \end{align*}*1
Corollary 6.1 (Consistency of the Lasso)
とする.このとき,任意の について, とおく. は の推定量.このとき,少なくとも の確率で
\begin{align*} 2||\mathbf{X}(\hat \beta - \beta^0)||^2_2/n \le 3 \lambda ||\beta^0||_1, \end{align*}
ただし
Proof.
Lemma 6.1 から,
\begin{align*}2 || \mathbf{X}(\hat \beta - \beta^0) ||_2^2/n & \le 4 \epsilon^\top \mathbf{X}(\hat \beta - \beta^0)/n + 2 \lambda ||\beta^0||_1 - 2 \lambda || \hat \beta ||_1 \end{align*}
ここで,もし ならば,三角不等式から
\begin{align*}2 || \mathbf{X}(\hat \beta - \beta^0) ||_2^2/n & \le \lambda || \hat \beta - \beta^0 || + 2 \lambda ||\beta^0||_1 - 2 \lambda || \hat \beta ||_1 \\ & \le 3\lambda ||\beta^0||_1\end{align*}
また,
\begin{align*}\Pr(4 \max_j |\epsilon^\top \mathbf{X}^{(j)}|/n \le \lambda) & = 1 - \Pr\left(4 \max_j |\epsilon^\top \mathbf{X}^{(j)}|/n \gt 4 \hat σ \sqrt{\frac{t^2 + 2 \log p}{n}} \right) \\ & \ge 1 - \Pr\left( \max_j |\epsilon^\top \mathbf{X}^{(j)}|/n \gt \hat σ \sqrt{\frac{t^2 + 2 \log p}{n}}, \hat σ \gt σ \right) - \Pr(\hat σ \le σ) \\ & \ge 1 - 2 \exp[-t^2/2] - \Pr(\hat σ \le σ) \end{align*}
- この結果から, であるとき, ならば Lasso は一致性を持つ.
*1:Chernoff bound + Standard normality
Gold, Lederer & Tao (2020) Inference for high-dimensional instrumental variables regression, JoE.
Introduction
- モデル:
- ,
- Doubly high-dimensional setting: , 両方とも high-dimensional.
- 各 について statistical inference したい.
- van de Geer et al. (2014 AoS)のような二段階のde-biased LASSOを考える.
- Belloni et al. (2018 arXiv)も似たような設定を考えているが,彼らの方法はNeyman orthogonalityに基づいた別の方法.
Two-stage estimation
- For each ,
\begin{align*}y_i & = x_i^\top \beta + u_i \\x_{ij} & = z_i^\top \alpha^{j} + v_{ij}\end{align*}
- Exclusion restriction: , .
- In matrix form,
\begin{align*} \mathbf{y} & = \mathbf{X}\beta + \mathbf{u} \\ \mathbf{X} & = \mathbf{Z}\mathbf{A} + \mathbf{V} \equiv \mathbf{D} + \mathbf{V} \end{align*}
where , , , and .
- for identification.
- Let .
Assumption 2.2: are i.i.d. sub-Gaussian and satisfy .
Assumption 2.4: and are sub-Gaussian.
- First-stage estimator: , , .
- Let .
- Second-stage estimator: .
One-step update
- をOLS推定する場合
, where is the inverse of .
- が非特異行列ならば第二項はOLSの性質によりゼロ.一方, のときは は可逆でないため,
.
.
- が であることを確かめればよい.
- が LASSO のとき, を "desparsified LASSO" や "debiased LASSO" などと呼ぶ.
- IVモデルに対応する one-step update: . は の推定量.
- Lemma 3.1: .
- をどうやって作る? のときは は特異行列.=> Cai et al. (2011 JASA) の CLIME estimator を使う.
Theorem 3.4: いくつかのhigh-level conditionsの下で,.
Two-stage LASSO
- First-stage estimator: .
- Second-stage estimator: .
- 以降は Theorem 3.4 の条件を満たすための tuning parameter の選び方や compatibility condition (see Ch.6, Buhlmann and van de Geer, 2011) などについて.
Lubold, Chandrasekhar & McCormick (2021) Identifying the latent space geometry of network models thorough analysis of curvature, arXiv.
Introduction
- Hoff, Raftery, and Handcock (2002)のlatent space modelでは,あらかじめ次元と距離の定められた潜在空間を基本に,各個人間のconnectionのdpendenceをモデル化している.
- この論文では,その潜在空間の幾何構造自体を推定することを考える.
- 幾何構造の選択がなぜ重要か?
- 例えば二次元のユークリッド空間を考えると,「お互いの距離が等しい4人グループ」が構成できない.
- 例えば球面を潜在空間として考えると,二点間の距離の上限があるので,よりネットワークが形成されやすくなる (McCormick and Zheng 2015 JASA)
- サプライチェーンで離れた上流と下流のネットワークがは形成されにくい.このような場合は双曲空間(hyperbolic space)が合っているはず.
- グラフ:Graph , . is undirected and unweighted.
モデル:
where
リーマン幾何学について
- Killing-Hopf Theorem: 断面曲率(sectionial curvature)*1が一定=>ユークリッド面,球面,双曲面のいずれか
- 点 における接ベクトルの空間を とする.
- また を計量テンソル(リーマン多様体を考えているのでリーマン計量) () とする.
- 断面曲率は以下の式で定義される:
\begin{align}\kappa_m(u,v) = \frac{g_m(R_m(u,v)v, u)}{g_m(u,u)g_m(v,v) - g_m(u,v)^2}\end{align}
このとき, は基底 の取り方に依らない.また,断面曲率は一定だと仮定していたので, としてよい.
- とする.ただし は双線型形式(内積の一般化)
- このとき, 上の二点 の距離は
\begin{align}d_{M^p(\kappa)}(x, y) = \kappa^{-1/2}\cos^{-1}(\kappa Q(x,y))\end{align}
で与えられる.
- 球面 => (標準内積)
- 双曲面 =>
- ここで, の分布関数 のサポートが 個の異なる点 を含むとき,上の式から,距離行列 が与えられたときに双線型形式を対応させる 行列
\begin{align}W_\kappa = \frac{1}{\kappa}\cos(\kappa^{1/2} D) \;\; ( = Q(Z,Z))\end{align}
を定義する.
Proposition 1.1
- The smallest s.t. is .
Proposition 1.2
- for some and some positive .
- for some and some negative .
※The signature of : , where = # of positive eigenvalues, = # of zero eigenvalues, and = # of negative eigenvalues.
- 以上の結果から,距離行列を幾何構造と独立に構成できれば,潜在空間をどの空間に埋め込めるかが判明する.=>グラフの構造からlink formationの確率を計算し,それを距離として用いる.
Mapping Graphs to Manifolds via Distance Matrices
- 単純化のため,個人効果が存在しない場合を考える:.また, のサポートは であるとする.
- 二点 間の距離を で測定する.ただし,
- に属するノードの集合を とすれば, は以下のように推定できる:
\begin{align} \hat p _{k,k'} = \frac{1}{|V_k| \cdot |V_{k'}|} \sum_{(i,j) \in V_k \times V_{k'}} G_{ij} \end{align}
- 距離行列は として推定.
- 個人効果が非ゼロで が連続の一般ケースは省略*2.
Estimating the Curvature and Minimal Latent Dimension
- ユークリッド面の場合は曲率の推定は不要.球面と双曲面の場合についてのみ曲率を推定する.
- ここで,ある について が に埋め込み可能だとする.すると,Prop 1.2から, の最小固有値はゼロ:.
- したがって, がユニークならば
\begin{align}\kappa_0 = \arg\min_{\kappa > 0} |\lambda_1(\kappa W_\kappa)|\end{align}
である.
- 実際には は未知なので, で置き換える.
- 同様に,双曲面の場合はProp 1.2から「上から二番目の固有値がゼロ」であることが条件として得られるので, を最小にすればよい.
- 曲率推定量の一致性 =>Proposition 3.1
- が推定出来たら のランクから を推定する.
以下は幾何構造の選択に関する仮説検定や実証分析.
Kaji, Manresa & Pouliot (2020) An adversarial approach to structural estimation, arXiv.
Introduction
- Genaratice adversarial networks (GAN) を使って経済データをシミュレートして構造推定する.
- GAN = minimax game
genarator: シミュレーションによって仮想データを生成
discriminator: 仮想データと実データを判別
上の minimax 問題を解くことで,実データに最も近い仮想データを生成する generator を作る.
- Goodfellow のオリジナルの GAN では generator と discriminator をどちらもニューラルネットワークで作っていたが,ここでは DGP が明示的に仮定されているので,
generator = structural econometric model
- Discriminator は何でもOK(この論文ではニューラルネットワーク).
Adversarial Estimation Framework
- 尤度関数を直接計算することは困難だがシミュレーションは可能なモデルを考える.
- 観測データ:
- パラメータ: such that
- 疑似データ:. は に依存しない潜在変数 によって決まるとする .
- 例:First-price aucion. ,
- Classification: ; = は真のDGPから生成されたデータと分類, = は疑似データと分類
The adversarial estimator*1
\begin{align} \hat \theta = \arg\min_{\theta \in \Theta} \max_{D \in \mathcal{D}} \frac{1}{n} \sum_{i = 1}^n \log D(X_i) + \frac{1}{m} \sum_{i = 1}^m \log (1 - D(X_i^\theta))\end{align}
- 目的関数は から の間の値に収まる:
- 下限: と が区別できない場合,
- 上限: と が完全に区別できる場合, かつ
- このminimax 問題の population counterpart は
\begin{align} \min_{\theta \in \Theta} \max_{D \in \mathcal{D}} \mathbb{E}_{P_0}[ \log D(X_i)] + \mathbb{E}_{P_\theta}[ \log (1 - D(X_i^\theta))]\end{align}
と表すことができる.
- このとき,内側の に関する最大化問題は明示的に解くことができて
\begin{align} D_\theta(X) := \frac{p_0(X)}{p_0(X) + p_\theta(X)} \end{align}
となる(Goodfellow et al., 2014, Proposition 1).ただし, は の density.
- を として使うとき,上の population 目的関数は と の Jensen-Shannon deivergence に他ならない:
\begin{align} \min_{\theta \in \Theta} \max_{D \in \mathcal{D}} \mathbb{E}_{P_0}[ \log D(X_i)] + \mathbb{E}_{P_\theta}[ \log (1 - D(X_i^\theta))] = \min_{\theta \in \Theta} \text{JS}(P_0 || P_\theta)\end{align}
- さらに, が識別可能ならば が成り立つ(Goodfellow et al., 2014, Theorem 1).
- Example 2 (Logistic discriminator) . このとき, について解いてみると, となる.
- Example 3 (Oracle discriminator) を使って を推定すると
\begin{align} \hat \theta & = \arg\min_{\theta \in \Theta} \text{sample JS}(P_0 || P_\theta)\\& = \arg\min_{\theta \in \Theta} \frac{1}{n} \sum_{i = 1}^n \log \frac{p_0(X_i)}{p_0(X_i) + p_\theta(X_i)} + \frac{1}{m} \sum_{i = 1}^m \log \frac{p_\theta(X_i^\theta)}{p_0(X_i^\theta) + p_\theta(X_i^\theta)}\end{align}
このとき, の下で は効率的(MLEに等しい).
Statistical Properties
- Bauer and Kohler (2019) Definition 2:
定義:Generalized hierarchical interaction model (GHIM)
, , .
= GHIM of order and level
For all , and such that
= GHIM of order and level
For all , , , and such that are GHIM of order and
- Bauer and Kohler (2019) Theorem 1:
- の次元ではなく に依存する.多層ニューラルネットワーク=dimension reduction が備わったノンパラメトリック手法
- Assumption 3: が GHIM of order and finite level . Discriminator のクラス ここで, Buer and Kohler (2019) Thorem 3 と同様の多層ニューラルネットワーク,.
Assumption 3 + regularity conditions
Theorem 5: Hellinger distance between and =
Theorem 6: .
- 尤度関数が明示的に書けないので,Theorem 6 の分散を直接計算することは難しい.この論文ではブートストラップを用いることを提案.