PaperlayerView exact revision on arXiv

Source-linked AI summary

Generalized Optimal Matching Methods for Causal Inference

Nathan Kallus

arXiv:1612.08321v3stat.MLmath.OCmath.STstat.MEstat.TH

TL;DR

The paper develops generalized optimal matching (GOM) to connect and extend matching and weighting methods for causal inference. Its framework yields kernel optimal matching (KOM), which combines matching’s interpretability and model-free consistency with favorable properties associated with regression and doubly robust methods.

  • Problem

    Existing matching and weighting methods for causal inference call for an encompassing framework that clarifies their connections and motivations.

    Source: §1 · p. 2

  • Method

    GOM generalizes a functional-analytical formulation of optimal matching into a framework for matching and weighting methods, including kernel optimal matching (KOM).

    Source: §1 · p. 2

  • Results

    KOM combines model-free consistency with parametric-rate estimation under correct specification, and has favorable robustness and efficiency properties in augmented weighted estimation.

    Source: §1 · p. 2, §6 · p. 37

  • Takeaways & Limitations

    KOM preserves the unit of analysis and avoids extrapolation while retaining favorable consistency, robustness, and efficiency properties.

    Source: §4.4 · p. 22, §6 · p. 37

    For NNM++, cross-validation can underestimate the Lipschitz constant and requires solving many large quadratic optimization problems.

    Source: §5.1 · p. 31

Abstract

from arXiv · show

We develop an encompassing framework for matching, covariate balancing, and doubly-robust methods for causal inference from observational data called generalized optimal matching (GOM). The framework is given by generalizing a new functional-analytical formulation of optimal matching, giving rise to the class of GOM methods, for which we provide a single unified theory to analyze tractability, consistency, and efficiency. Many commonly used existing methods are included in GOM and, using their GOM interpretation, can be extended to optimally and automatically trade off balance for variance and outperform their standard counterparts. As a subclass, GOM gives rise to kernel optimal matching (KOM), which, as supported by new theoretical and empirical results, is notable for combining many of the positive properties of other methods in one. KOM, which is solved as a linearly-constrained convex-quadratic optimization problem, inherits both the interpretability and model-free consistency of matching but can also achieve the $\sqrt{n}$-consistency of well-specified regression and the efficiency and robustness of doubly robust methods. In settings of limited overlap, KOM enables a very transparent method for interval estimation for partial identification and robust coverage. We demonstrate these benefits in examples with both synthetic and real data

1. Introduction.

The paper unifies matching, covariate balancing, and related causal-inference methods through generalized optimal matching (GOM), with a theory for their properties. It also develops kernel optimal matching (KOM), which combines features of matching, regression, and doubly robust methods and supports interval estimation when overlap is limited.

1. Introduction.

  • GOM provides a unified framework and theory connecting matching, weighting, and related causal-inference methods, while enabling new methods that trade balance against variance.Its theory addresses tractability and consistency.Source: §1 · p. 2
  • Many existing methods, including nearest-neighbor matching, optimal caliper matching, coarsened exact matching, near-fine balance, and linear regression adjustment, are instances of GOM.The framework also yields extensions that automatically trade balance for variance and can outperform standard matching counterparts.Source: §1 · p. 2
  • KOM combines matching’s interpretability and model-free consistency with regression’s parametric-rate consistency and doubly robust methods’ efficiency and robustness.The paper also establishes favorable robustness and efficiency properties for augmented weighted estimation and for KOM used before regression.Source: §1 · pp. 2–3
  • With limited overlap, KOM supports transparent interval estimates for partial identification and robust coverage.The paper demonstrates its benefits using synthetic and real data.Source: §1 · p. 3

2. Re-interpreting Optimal Matching.

The section formulates estimation of the sample average treatment effect on the treated using weighted controls and decomposes its conditional error into bias and variance. It then interprets optimal matching as minimizing worst-case error under specific assumptions about outcomes and allowable weights.

2.1. Setting.

  • The setup assumes weak mean-ignorability and overlap, and focuses on estimating the sample average treatment effect on the treated with honest weights based on covariates and treatment assignments.The section also introduces augmented weighting using an outcome regression estimate.Source: §2.1 · pp. 4–5

2.2. Decomposing the Conditional Mean Squared Error.

  • The conditional mean squared error separates into a conditional bias term and a variance term, which must be balanced to minimize estimator risk.The bias is B(W; f0); the variance term depends on the weights and conditional outcome variances.Source: §2.2 · p. 5
  • Nearest-neighbor and one-to-one matching select control weights from matches, with replacement allowed for nearest-neighbor matching but not one-to-one matching.The resulting weights correspond, respectively, to a control multisubset or to a subset of cardinality equal to the treated sample size.Source: §2.2 · p. 6

2.3. Re-interpreting Optimal Matching.

  • Under zero residual variance and a Lipschitz restriction on the outcome function, optimal matching is equivalent to choosing simplex weights that minimize worst-case conditional mean squared error.The minimax interpretation applies to nearest-neighbor and one-to-one matching.Source: §2.3 · p. 6
  • Among bounded simplex weights, optimal matching minimizes worst-case error over Lipschitz functions, even when weights are allowed to be continuous rather than integer multiples.The interpretation depends on restrictions on the outcome function, weight space, and residual variance.Source: §2.3 · p. 7

3. Generalizing Optimal Matching.

The section generalizes optimal matching by expressing balance as a bound on bias and combining it with variance in an optimization objective. This produces GOM methods that encompass existing approaches, admit tractability and consistency results, and include methods that automatically trade off balance and variance.

3. Generalizing Optimal Matching.

  • GOM extends optimal matching by generalizing restrictions on outcome functions, allowable weights, and residual variance to produce methods that minimize estimation error.The framework includes new matching methods such as KOM.Source: §3 · p. 8, §3.3 · p. 10

3.1. Generalizing Balance.

  • A bias-dual-norm imbalance metric measures the largest bias over outcome functions bounded by a chosen magnitude, generalizing balance beyond Lipschitz functions.The boundedness condition makes the metric finite and well-defined.Source: §3.1 · pp. 8–9

3.2. The Balance-Variance Trade-o↵.

  • Adding a squared-weight penalty to imbalance directly trades balance against variance, unlike nearest-neighbor matching, which optimizes balance alone.In the example, tuning the penalty can significantly improve conditional mean squared error; one-to-one matching is not on the efficient frontier.Source: §3.2 · pp. 9–10

3.3. Generalized Optimal Matching Methods.

  • GOM(W, k·k, λ) minimizes squared imbalance plus λ times the squared weight norm, with λ controlling the balance-variance tradeoff.Nearest-neighbor matching and one-to-one matching arise as special cases, and no matching is obtained at λ = 1 for specified weight spaces.Source: §3.3 · pp. 10–11

3.4. Tractability.

  • For simplex weights, GOM is convex and polynomial-time solvable to arbitrary precision given an evaluation oracle for its imbalance objective.The considered simplex cases can be formulated as linearly constrained convex-quadratic problems; subset-based formulations are generally NP-hard.Source: §3.4 · p. 12

3.5. Existing Matching Methods as GOM.

  • Nearest-neighbor matching, optimal caliper matching, coarsened exact matching, near-fine balance, and regression adjustment are included in GOM.GOM interpretations yield extensions such as NNM++ and CEM++ that automatically trade balance against variance.Source: §3.5 · pp. 12–13

3.6. Consistency.

  • For GOM consistency under the stated assumptions, the general result requires correct specification, while the KOM extension establishes model-free consistency under additional estimation conditions.The paper also extends the result to the augmented weighting estimator.Source: §3.6 · p. 14

4. Kernel Optimal Matching.

This section develops kernel optimal matching and semi-kernel extensions within GOM, covering balance, theory, automatic regularization, robust estimation, and partial-identification intervals. It also addresses exact-balance conditions, data-driven kernel selection, performance in a low-overlap IHDP study, and practical use.

4. Kernel Optimal Matching.

  • On simplex weights, KOM is a linearly constrained convex-quadratic problem solvable in polynomial time, and its Bayesian interpretation exactly minimizes posterior CMSE.KOM++ selects λ by minimizing the negative log marginal likelihood and setting λ to the estimated noise-to-function-variance ratio; this data-dependent choice is not strictly honest, though the paper reports low CMSE in examples and real-data analysis.Source: §4 · pp. 16–17

4.2. Consistency.

  • Under the stated assumptions, KOM achieves n^-1/2 consistency when the regression function lies in the RKHS, and consistency under misspecification with a C0-universal kernel.For augmented kernel weighted estimation, the results also cover regression-estimation error: with an RKHS-consistent adjustment, only irreducible residual error remains; universal kernels can preserve consistency when the adjustment is inconsistent, while correct specification can yield a parametric rate.Source: §4.2 · pp. 18–19

4.3. Kernel Matching to Reduce Model Dependence.

  • With KOM weights, weighted least squares is consistent regardless of the outcome model and achieves parametric rates when the model is correctly specified.The theorem assumes a C0-universal kernel, bounded covariates, and a nonsingular treated-group second-moment matrix.Source: §4.3 · p. 20

4.4. Inference and Partial Identification.

  • KOM supports matching-based standard errors and bootstrap intervals, while its explicit bias bound enables intervals that account for residual imbalance under limited overlap.The bootstrap re-optimizes weights for each resample. Bias is bounded by the RKHS norm of the outcome function times the balance measure; adding standard errors to the resulting interval can provide robust coverage if the function-norm bound is valid.Source: §4.4 · pp. 20–22
  • KOM++ point-estimate CMSE was not substantially better than 1:1M under complete lack of overlap, but robust intervals accounting for bias helped achieve correct coverage.The example eliminated overlap and used KOM++’s marginal-likelihood estimate in the robust interval; little improvement in point estimation was possible in this extreme setting.Source: §4.4 · pp. 23–24, Figure 5 · p. 23

4.5. Semi-Kernel Optimal Matching.

  • Semi-kernel optimal matching combines exact matching on a parametric function class with a nonparametric KOM criterion, including spline-based control of function roughness.The section’s example uses functions with square-integrable Hessians; the associated Beppo-Levi kernel magnitude corresponds to integrated squared derivatives.Source: §4.5 · p. 24
  • SKOM balances all smooth functions and, when feasible, exactly matches linear functions’ sample means; without extrapolation, it requires the treated mean to lie in the controls’ convex hull.If exact mean matching without extrapolation is infeasible, standard KOM instead permits approximate matching; emphasizing linear functions can prioritize first-order discrepancies.Source: §4.5 · p. 25
  • Marginal likelihood can tune both KOM’s kernel and regularization, including length scales, ARD rescalings, covariance structures, and kernel mixtures.When the kernel family is closed under unitary transformations, this selection makes KOM affinely invariant, so covariance studentization is unnecessary.Source: §4.5 · pp. 25–26

4.7. Infant Health and Development Program.

  • In IHDP, KOM++—especially with ARD—had significantly smaller error than other matching and weighting methods, while low overlap made IPW high-MSE and KOM++ weights stable.KOM++ cannot remove bias caused by lack of overlap, but limits extrapolation while accounting for error; 1:1 matching had greater MSE because it balanced less effectively. ARD improves performance by learning a useful representation for balancing.Source: Figure 6 · p. 27, §4.7 · pp. 28–29

4.8. Recommendations for Practical Use.

  • The authors recommend Gaussian or Matérn KOM++ with ARD: these universal kernels provide model-free consistency and, when quadratic is well-specified, little-to-no efficiency loss.The two kernels yield very similar MSEs, while ARD tunes their parameters.Source: §4.8 · pp. 29–30
  • KOM supplies explicit bias bounds for limited-overlap inference; with a universal kernel, its interval estimates protect against nonlinear effects and can remain useful and reliable.The authors caution that checking only mean differences is inadequate when effects are nonlinear.Source: §4.8 · p. 30

5. Existing Matching Methods as GOM.

Many matching methods used in practice are GOM methods, often with λ = 0; selecting λ automatically extends them to reduce estimation error (p11).

5.1. Nearest-Neighbor Matching.

  • NNM is GOM with λ = 0; BVENNM adds a variance penalty, and NNM++ cross-validates λ = σ2/γ2 under homoskedasticity.The authors note that estimating the Lipschitz constant from noisy observations is downward-biased and that NNM++ requires many large quadratic solves.Source: §5.1 · pp. 30–31

5.2. Optimal-Caliper Matching.

  • Optimal-caliper matching is GOM with λ = 0, using simplex weights with replacement and bounded simplex weights without replacement.With replacement, NNM is one of multiple optimal-caliper solutions; without replacement, the methods differ.Source: §5.2 · p. 32

5.3. Coarsened Exact Matching.

  • CEM is GOM with λ = 0, while BVECEM adds a variance penalty and CEM++ estimates λ using an in-sample one-standard-error tuning procedure.The authors characterize CEM's function class as small and use a bisection and nested golden-section search for tuning.Source: §5.3 · pp. 32–33

5.4. Mean matching and near-fine balance.

  • Optimal mean matching minimizes mean-vector distance over control subsets and is GOM; for binary indicators, p = 1 yields optimal near-fine balance.ONFB++ estimates λ to select subset size automatically.Source: §5.4 · pp. 33–34

5.5. Mixed objectives.

  • Mixed-objective GOM combines balance criteria; methods in [7] correspond to particular combinations of distance and coarsened-balance objectives.The theorem expresses the combined worst-case bias as the sum of the component biases, scaled by the combination weight.Source: §5.5 · pp. 34–35
  • With λ tuned, ONFB++ improves on both ONFB and greedy near-fine balance, while CEM++ improves on CEM in the balance–variance comparisons.The greedy method beats ONFB because its suboptimality induces a larger matched set; Fig. 7 compares CEM and near-fine-balance trade-offs.Source: Figure 7 · p. 35, §5.5 · pp. 35–36

5.6. Regression as GOM.

  • OLS with treatment interactions equals GOM with general weights and a linear-function balance criterion; its ridge version also has a GOM representation.Simplex or subset matching avoids extrapolation, and OLS and mean matching coincide only when exact fine balance is feasible.Source: §5.6 · pp. 36–37

6. Conclusion.

The paper unifies matching and regression methods in a framework that supports balance–variance extensions. It presents KOM as a method combining several desirable properties for causal inference.

6. Conclusion.

  • The framework unifies matching and regression methods and supports extensions that automatically adjust the balance–variance trade-off, improving estimation error relative to standard counterparts.The framework provides a unified theoretical analysis of commonly used methods.Source: §6 · p. 37
  • KOM preserves the unit of analysis without extrapolation and offers model-free consistency, parametric-rate estimation under correct specification, and flexible model selection via empirical Bayes.The paper also reports favorable robustness and efficiency properties for augmented weighted estimation and robustness properties when KOM preprocesses regression.Source: §6 · p. 37

ALGORITHM 1: Cross-Validation Estimation for NNM++

The algorithm uses control data and a regularizer grid, splits controls into folds, and returns weights after optimizing under distance-based constraints.

ALGORITHM 1: Cross-Validation Estimation for NNM++

  • The procedure takes control outcomes, a distance matrix, and a regularizer grid as inputs, then returns weights.Its title identifies it as cross-validation estimation for NNM++.Source: ALGORITHM 1: Cross-Validation… · p. 41
  • It randomly divides the control data into disjoint folds and iterates over the folds.The supplied steps specify a fold count and a loop over k in {1, …, m}.Source: ALGORITHM 1: Cross-Validation… · p. 41
  • For each fold, the procedure imposes distance-based constraints on weights and includes a quadratic objective with a regularization term.The constraints use estimated distance bounds; the supplied objective expressions are incomplete.Source: ALGORITHM 1: Cross-Validation… · p. 41

APPENDIX A: CONNECTIONS TO AND GENERALIZATION OF EQUAL-PERCENT BIAS REDUCTION

The appendix connects matching to equal-percent bias reduction and develops affine-invariance and kernel-based extensions. It also states assumptions and sample-size limits on these guarantees.

APPENDIX A: CONNECTIONS TO AND GENERALIZATION OF EQUAL-PERCENT BIAS REDUCTION

  • EPBR requires equal average reduction in mean-vector discrepancy across covariates, equivalently reducing imbalance for every linear function of covariates.The appendix attributes the definition to.Source: Appendix A · p. 42
  • For proportionally ellipsoidal treatment and control distributions, an affinely invariant method is lin-EPBR comparable to no-matching weights.The appendix restates the result as Theorem 24.Source: Appendix A · p. 42
  • Studentizing the data makes unitarily invariant methods affinely invariant; KOM with fitted scaling is also affinely invariant.The appendix states that methods based on Mahalanobis distance are affinely invariant and gives the preprocessing result in Theorem 25.Source: Appendix A · p. 43
  • Affine-invariant matching only makes sense with more observations than dimensions; when n ≤ d, it is generically data-invariant and does nothing useful.The stated boundary follows from the dimension of the space of linear functions on the data.Source: Appendix A · p. 43
  • With fitted scaling or studentization, KOM is affinely invariant and EPBR for proportionally ellipsoidal data, giving uniform improvement over linear outcomes.The appendix motivates this result as a bridge to guarantees for nonlinear outcomes.Source: Appendix A · p. 43
  • The appendix generalizes EPBR to function families: for a linear subspace, F-EPBR holds exactly when expected bias operators are proportional by a factor in [-1, 1].F-EPBR compares expected bias over every function in the specified family.Source: Appendix A · p. 44
  • For proportionally K-ellipsoidal treatment and control distributions, an affinely invariant method is F-EPBR relative to no-matching weights.This is the kernel-family analogue of the linear EPBR result.Source: Appendix A · p. 44
  • K-affine invariance is limited to non-universal kernels; with a strictly positive-definite kernel, such a method is constant across distinct datasets.The appendix notes that C0-universal kernels are strictly positive definite.Source: Appendix A · pp. 44–45

APPENDIX B: PROOFS

This appendix establishes consistency and rate results for GOM and matched estimators, along with affine and kernel-affine invariance properties. It also develops network-flow connections and proves convexity and computational tractability results, including a null-space reduction for constrained optimization.

Proofs of Thms. 3 and 17

  • Integer min-cost flow recovers nearest-neighbor matching and 1:1 matching, while a bottleneck objective recovers optimal matching with or without replacement.The triangle inequality reduces flow to direct treated-to-control edges; capacity constraints yield one-to-one matches, and the bottleneck objective minimizes the maximal pair distance.Source: Appendix B · pp. 46–48

Proof of Thm. 7

  • The GOM objective is convex, and the proof reduces its optimization to polynomial-time separation and violation checks.The argument uses convexity of the squared weight norm and balance function, then reduces separation on the final constraint to a violation algorithm.Source: Appendix B · pp. 47–48

Proof of Thm. 22

  • The proof shows that GOM weights for the linear-kernel setup equal the weights obtained from the corresponding ridge-regression formulation.It establishes the equality through first-order conditions and the Sherman–Morrison–Woodbury formula, including the zero-penalty limit when the stated matrix is invertible.Source: Appendix B · p. 50

Proof of Thm. 9

  • Under the stated assumptions, the optimal GOM estimator converges to SATT in probability.The proof shows its conditional mean squared error tends to zero almost surely before deriving convergence in L2.Source: Appendix B · p. 51

Proof of Thm. 10

  • For regression-adjusted estimates, the proof decomposes error into balance and residual terms; exact balance eliminates one term, while kernel-norm control makes another O(n^-1/2).The decomposition also includes an estimation residual, and case (c) rewrites the error using the fitted outcome regression.Source: Appendix B · p. 51

Proof of Thm. 13

  • B(W;K)^2=O_p(1/n) and ||W||_2^2=O_p(1/n), yielding variance O_p(1/n) and residual O_p(n^-1/2).In case (a), the balance bias is O(n^-1); Lemma 31 transfers conditional stochastic-order bounds to the nonnegative variables themselves.Source: Appendix B · pp. 52–53

Theorem 14

  • In Theorem 14, case (a) gives hatτ_{W,hatf0} − SATT = Ξ(W) + o_p(n^-1/2), while case (b) bounds the imbalance by O_p(1)O_p(n^-1/2), yielding the result.The proof writes the estimation error as B(W; tilde f0 − hat f0) + B(W; f0 − tilde f0) + Ξ(W).Source: Appendix B · p. 54

Theorem 15

  • The least-squares estimator satisfies τ̂_WLS(W) = τ̂_W − B(W; f̂_0), with B(W; f̂_0) and τ̂_WLS(W) converging to zero in probability; β̃ − β_0 = Op(n^−1/2).Source: Appendix B · pp. 54–55

Theorem 16

  • Theorem 16’s proof converts the linear constraints into a null-space basis and reparameterizes the optimization variable as W′ = NU.This gives an unconstrained variable U for the constrained optimization over weights.Source: Appendix B · p. 56

Theorems 24 and 28

  • The proofs of Theorems 24 and 28 use affine transformations and spherical symmetry to reduce the data to spherical controls and shifted, scaled treated distributions.For Theorem 24, the proof applies this reduction to affinely invariant weights; Theorem 28 follows the same argument for embedded control data.Source: Appendix B · pp. 56–57

Theorems 25 and 29

  • Theorems 25 and 29 establish affine invariance for Algorithm 3 by showing that transformed data preserve its inner products.Under X_A = XA^T + 1_n a^T, the transformed mean and covariance are Aμ̂ + a and AΣ̂A^T, respectively.Source: Appendix B · p. 56

Theorem 26

  • Theorem 26’s proof shows that an affinely invariant W takes the same value on every affinely independent sample as on the (n−1)-dimensional simplex.The proof maps any such sample affinely to the simplex formed by zero and the first n−1 unit vectors.Source: Appendix B · p. 57

Theorem 30

  • Theorem 30’s proof shows that K-affine invariance makes W identical for any two lists of n distinct elements when K is strictly positive definite.Strict positive definiteness makes each list’s kernel sections linearly independent, enabling a bounded nonsingular map between the lists.Source: Appendix B · p. 57
Loading 1612.08321v3…