Adversarial Estimation of Assortment Probabilities under Independence Structure

1. Problem Formulation

The paper addresses the challenge of estimating assortment probabilities (joint probabilities of binary outcomes) in high-dimensional settings where the number of items $M$ is large.

• Context: Applications include product bundling, advertising, clinical trials, and causal inference with multiple binary treatments.
• The Challenge: A joint distribution of $M$ binary variables generally requires $2^M - 1$ parameters. Existing methods (e.g., Multinomial Logit) treat every possible assortment as a distinct category, leading to statistical inefficiency and overfitting when $M$ is large.
• Key Assumption: The authors assume the underlying dependence structure is sparse. Specifically, they leverage the Bahadur representation (1959), which decomposes the joint distribution into marginal probabilities and generalized correlation coefficients.
  • Let $Y \in \{0, 1\}^M$. The joint probability is $P(Y=y) = f(y, \alpha, r) \prod \alpha_j^{y_j}(1-\alpha_j)^{1-y_j}$.
  • $\alpha$: Marginal probabilities (nuisance parameters, dimension $M$).
  • $r$: Generalized correlation coefficients (parameters of interest, dimension $p = 2^M - M - 1$).
  • Sparsity: If components are independent, $r=0$. The authors assume $r$ is sparse (only $s \ll p$ non-zero entries), reflecting that only a limited number of interaction effects exist.

2. Methodology

The authors propose a framework to estimate the high-dimensional vector $r$ while treating the lower-dimensional marginal probabilities $\alpha$ as nuisance parameters. They develop three estimators, moving from a baseline to a computationally feasible, rate-optimal solution.

A. Maximum Likelihood Estimator (MLE)

• Approach: Jointly maximize the log-likelihood over $(\alpha, r)$.
• Limitations: The objective function is non-concave in $\alpha$, making optimization computationally intractable. Furthermore, standard MLE fails to exploit sparsity and overfits when $2^M \approx N$.

B. Plug-in Estimator

• Approach:
  1. Estimate $\alpha$ consistently using sample averages ($\hat{\alpha}$).
  2. Plug $\hat{\alpha}$ into the log-likelihood and estimate $r$ via a convex $\ell_1$-regularized program (Lasso).
• Limitations: While computationally feasible, plugging in $\hat{\alpha}$ introduces a "misspecification" error in the score function. Theoretical analysis shows this estimator converges at a rate of $O_p(\sqrt{sM^2/N})$, which is sub-optimal compared to the oracle rate.

C. Regularized Adversarial Estimators

To overcome the sub-optimality of the plug-in approach, the authors propose adversarial estimation, which treats the uncertainty in $\alpha$ as a worst-case scenario.

1. Adversarial Estimator ($\hat{r}_A$):

   • Maximizes the log-likelihood while minimizing over an adversarial set $A(\hat{\alpha})$ containing the true $\alpha$.
   • Pros: Achieves the optimal oracle rate.
   • Cons: Computationally intractable because the inner minimization over $\alpha$ is non-convex and non-concave.

2. First-Order Estimator ($\hat{r}_{FO}$) – The Core Contribution:

   • Approximation: Approximates the non-linear term $W(\alpha, y)$ using a first-order Taylor expansion around $\hat{\alpha}$.
   • Structure: The resulting objective function becomes bilinear (concave in $r$, concave in $\alpha$).
   • Adversarial Set: The set $A(\hat{\alpha})$ is constructed as a hyper-rectangle (product of intervals). Because the objective is concave in $\alpha$, the inner minimization is attained at one of the vertices of the hyper-rectangle.
   • Computational Feasibility: Since the number of vertices is finite ($2^M$ in theory, but effectively handled via the structure), the inner minimization is tractable.
   • Result: This estimator matches the performance of the intractable adversarial estimator while remaining computationally feasible.

D. Extension to Covariates

The framework is extended to conditional probabilities $P(Y|X)$ using localized estimators.

• Marginal probabilities $\alpha(x)$ are estimated via local linear regression.
• The adversarial set is constructed over a class of local linear functions.
• The first-order approximation is applied to both the nuisance function and the correlation coefficients.

3. Key Contributions

1. Novel Estimation Framework: Introduced a method to estimate assortment probabilities that adapts to independence structures via sparsity in Bahadur's generalized correlation coefficients, without requiring pre-specified structural assumptions (unlike factor models).
2. High-Dimensional Adversarial Estimation: Developed a new class of estimators for high-dimensional targets with low-dimensional nuisance parameters. This contrasts with the standard "debiased machine learning" literature, which typically handles low-dimensional targets with high-dimensional nuisances.
3. First-Order Adversarial Estimator: Proposed a computationally tractable estimator that achieves the oracle convergence rate (as if $\alpha$ were known) under mild conditions ($s \gtrsim \log M$).
   • Oracle Rate: $O_p(\sqrt{sM/N})$.
   • Plug-in Rate: $O_p(\sqrt{sM^2/N})$ (slower).
   • First-Order Rate: $O_p(\sqrt{sM/N} + \sqrt{M \log M / N})$.
4. Causal Inference Application: Applied the method to estimate Average Treatment Effects (ATE) with multiple binary treatments. The proposed estimators for Generalized Propensity Scores (GPS) yield substantial finite-sample improvements over Multinomial Logit (MNL) and Nadaraya-Watson estimators.

4. Theoretical Results

• Convergence Rates: The paper establishes that the First-Order estimator ($\hat{r}_{FO}$) attains the optimal rate of convergence $\sqrt{sM/N}$ (plus a negligible nuisance term) when the sparsity level $s$ satisfies $s \gtrsim \log M$.
• Regularity Conditions: The results rely on standard high-dimensional assumptions:
  • Sparsity: The number of non-zero generalized correlations $s$ is small.
  • Restricted Eigenvalue: Ensures the design matrix has sufficient curvature on the sparse support.
  • Moment Conditions: Bounds on the tails of the score functions.
• Asymptotic Normality: In the causal inference application, the authors prove that the resulting ATE estimator is asymptotically normal and achieves the semiparametric efficiency bound, provided the propensity score estimator converges sufficiently fast (which is enabled by the sparsity assumption).

5. Numerical Results

• Simulations:
  • No Covariates: The First-Order estimator ($\hat{r}_{FO}$) consistently outperforms the Plug-in estimator ($\hat{r}_{PI}$) in terms of Root Mean Squared Error (RMSE) and probability estimation accuracy, especially as $M$ increases.
  • With Covariates: Similar improvements are observed in the localized setting.
• Causal Inference: In simulations for ATE estimation with $M=4$ (16 treatment combinations), the proposed method using the First-Order GPS estimator provides coverage ratios much closer to the nominal level (95%) compared to MNL and Nadaraya-Watson estimators, which suffer from bias due to ignoring the independence structure.

6. Significance

This paper makes a significant contribution to high-dimensional statistics and econometrics by:

• Bridging a Gap: It solves the computational intractability of adversarial estimation for high-dimensional parameters, a problem that previously limited the application of such robust methods.
• Efficiency: It demonstrates that exploiting sparsity in dependence structures (rather than just in regression coefficients) leads to substantial gains in estimation efficiency for binary data.
• Practical Utility: The method offers a robust alternative to Multinomial Logit models in settings with many binary choices (e.g., personalized medicine, complex marketing bundles), where traditional models fail due to the "curse of dimensionality."

In summary, the authors provide a theoretically grounded, computationally feasible, and empirically superior method for estimating complex joint distributions of binary variables by leveraging sparsity and adversarial optimization techniques.