The Fundamental Limits of Structure-Agnostic Functional Estimation

• URL: http://arxiv.org/abs/2305.04116v2
• Date: Sat, 07 Jun 2025 19:12:28 GMT
• Title: The Fundamental Limits of Structure-Agnostic Functional Estimation
• Authors: Sivaraman Balakrishnan, Edward H. Kennedy, Larry Wasserman,
• Abstract summary: We show that there is a strong sense in which existing first-order methods are optimal.<n>We provide a formalization of the problem of functional estimation with black-box nuisance function estimates.<n>Our results highlight some clear tradeoffs in functional estimation.
• Score: 14.851921205044912
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Many recent developments in causal inference, and functional estimation problems more generally, have been motivated by the fact that classical one-step (first-order) debiasing methods, or their more recent sample-split double machine-learning avatars, can outperform plugin estimators under surprisingly weak conditions. These first-order corrections improve on plugin estimators in a black-box fashion, and consequently are often used in conjunction with powerful off-the-shelf estimation methods. These first-order methods are however provably suboptimal in a minimax sense for functional estimation when the nuisance functions live in Holder-type function spaces. This suboptimality of first-order debiasing has motivated the development of "higher-order" debiasing methods. The resulting estimators are, in some cases, provably optimal over Holder-type spaces, but both the estimators which are minimax-optimal and their analyses are crucially tied to properties of the underlying function space. In this paper we investigate the fundamental limits of structure-agnostic functional estimation, where relatively weak conditions are placed on the underlying nuisance functions. We show that there is a strong sense in which existing first-order methods are optimal. We achieve this goal by providing a formalization of the problem of functional estimation with black-box nuisance function estimates, and deriving minimax lower bounds for this problem. Our results highlight some clear tradeoffs in functional estimation -- if we wish to remain agnostic to the underlying nuisance function spaces, impose only high-level rate conditions, and maintain compatibility with black-box nuisance estimators then first-order methods are optimal. When we have an understanding of the structure of the underlying nuisance functions then carefully constructed higher-order estimators can outperform first-order estimators.

Related papers

• Sharp Structure-Agnostic Lower Bounds for General Functional Estimation [22.228743542695835]
  This paper provides a systematic investigation of the optimal error rates achievable by structure-agnostic estimators.<n>We first show that, for estimating the average treatment effect (ATE), a central parameter in causal inference, doubly robust learning attains optimal structure-agnostic error rates.<n>We then extend our analysis to a general class of functionals that depend on unknown nuisance functions and establish the structure-agnostic optimality of debiased/double machine learning.
  arXiv  Detail & Related papers  (2025-12-19T08:34:05Z)
• Bayesian Optimization for Function-Valued Responses under Min-Max Criteria [0.4258175645355975]
  min-max Functional Bayesian Optimization (MM-FBO) is a framework that directly minimizes the maximum error across the functional domain.<n>We provide two theoretical guarantees: a discretization bound for the worst case objective, and a consistency result showing that as the surrogate becomes accurate and uncertainty vanishes, the acquisition converges to the true min-max objective.
  arXiv  Detail & Related papers  (2025-11-26T20:32:07Z)
• On the Optimal Construction of Unbiased Gradient Estimators for Zeroth-Order Optimization [57.179679246370114]
  A potential limitation of existing methods is the bias inherent in most perturbation estimators unless a stepsize is proposed.<n>We propose a novel family of unbiased gradient scaling estimators that eliminate bias while maintaining favorable construction.
  arXiv  Detail & Related papers  (2025-10-22T18:25:43Z)
• Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity [59.75300530380427]
  We consider the problem of optimizing second-order smooth and strongly convex functions where the algorithm is only accessible to noisy evaluations of the objective function it queries. We provide the first tight characterization for the rate of the minimax simple regret by developing matching upper and lower bounds.
  arXiv  Detail & Related papers  (2024-06-28T02:56:22Z)
• C-Learner: Constrained Learning for Causal Inference [5.395560682099634]
  We propose a novel debiasing approach that achieves the best weighting of both worlds, producing stable plug-in estimates.<n>Our constrained learning framework solves for the best plug-in estimator under the constraint that the first-order error with respect to the plugged-in quantity is zero.
  arXiv  Detail & Related papers  (2024-05-15T16:38:28Z)
• Efficient Model-Free Exploration in Low-Rank MDPs [76.87340323826945]
  Low-Rank Markov Decision Processes offer a simple, yet expressive framework for RL with function approximation. Existing algorithms are either (1) computationally intractable, or (2) reliant upon restrictive statistical assumptions. We propose the first provably sample-efficient algorithm for exploration in Low-Rank MDPs.
  arXiv  Detail & Related papers  (2023-07-08T15:41:48Z)
• Kernel-based off-policy estimation without overlap: Instance optimality beyond semiparametric efficiency [53.90687548731265]
  We study optimal procedures for estimating a linear functional based on observational data. For any convex and symmetric function class $mathcalF$, we derive a non-asymptotic local minimax bound on the mean-squared error.
  arXiv  Detail & Related papers  (2023-01-16T02:57:37Z)
• Nuisance Function Tuning and Sample Splitting for Optimal Doubly Robust Estimation [5.018363990542611]
  We consider the problem of how to estimate nuisance functions to obtain optimal rates of convergence for a doubly robust nonparametric functional. We show that plug-in and first-order biased-corrected estimators can achieve minimax rates of convergence across all H"older smoothness classes of the nuisance functions.
  arXiv  Detail & Related papers  (2022-12-30T18:17:06Z)
• Variance Reduction for Score Functions Using Optimal Baselines [0.0]
  This paper studies baselines, a variance reduction technique for score functions. Motivated primarily by reinforcement learning, we derive for the first time an expression for the optimal state-dependent baseline.
  arXiv  Detail & Related papers  (2022-12-27T19:17:28Z)
• Inference on Strongly Identified Functionals of Weakly Identified Functions [71.42652863687117]
  We study a novel condition for the functional to be strongly identified even when the nuisance function is not. We propose penalized minimax estimators for both the primary and debiasing nuisance functions.
  arXiv  Detail & Related papers  (2022-08-17T13:38:31Z)
• Minimax Kernel Machine Learning for a Class of Doubly Robust Functionals [16.768606469968113]
  We consider a class of doubly robust moment functions originally introduced in (Robins et al., 2008) We demonstrate that this moment function can be used to construct estimating equations for the nuisance functions. The convergence rates of the nuisance functions are analyzed using the modern techniques in statistical learning theory.
  arXiv  Detail & Related papers  (2021-04-07T05:52:15Z)
• Causal Inference Under Unmeasured Confounding With Negative Controls: A Minimax Learning Approach [84.29777236590674]
  We study the estimation of causal parameters when not all confounders are observed and instead negative controls are available. Recent work has shown how these can enable identification and efficient estimation via two so-called bridge functions.
  arXiv  Detail & Related papers  (2021-03-25T17:59:19Z)
• Finite Sample Analysis of Minimax Offline Reinforcement Learning: Completeness, Fast Rates and First-Order Efficiency [83.02999769628593]
  We offer a theoretical characterization of off-policy evaluation (OPE) in reinforcement learning. We show that the minimax approach enables us to achieve a fast rate of convergence for weights and quality functions. We present the first finite-sample result with first-order efficiency in non-tabular environments.
  arXiv  Detail & Related papers  (2021-02-05T03:20:39Z)
• What do you Mean? The Role of the Mean Function in Bayesian Optimisation [0.03305438525880806]
  We show that the rate of convergence can depend sensitively on the choice of mean function. We find that for design dimensions $ge5$ using a constant mean function equal to the worst observed quality value is consistently the best choice.
  arXiv  Detail & Related papers  (2020-04-17T17:10:17Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.