Online Statistical Inference for Stochastic Optimization via Kiefer-Wolfowitz Methods

• URL: http://arxiv.org/abs/2102.03389v5
• Date: Sun, 10 Dec 2023 02:13:08 GMT
• Title: Online Statistical Inference for Stochastic Optimization via Kiefer-Wolfowitz Methods
• Authors: Xi Chen, Zehua Lai, He Li, Yichen Zhang
• Abstract summary: We first present the distribution for the Polyak-Ruppert-averaging type Kiefer-Wolfowitz (AKW) estimators. The distributional result reflects the trade-off between statistical efficiency and function query complexity.
• Score: 8.890430804063705
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This paper investigates the problem of online statistical inference of model parameters in stochastic optimization problems via the Kiefer-Wolfowitz algorithm with random search directions. We first present the asymptotic distribution for the Polyak-Ruppert-averaging type Kiefer-Wolfowitz (AKW) estimators, whose asymptotic covariance matrices depend on the distribution of search directions and the function-value query complexity. The distributional result reflects the trade-off between statistical efficiency and function query complexity. We further analyze the choice of random search directions to minimize certain summary statistics of the asymptotic covariance matrix. Based on the asymptotic distribution, we conduct online statistical inference by providing two construction procedures of valid confidence intervals.

Related papers

• A general error analysis for randomized low-rank approximation with application to data assimilation [42.57210316104905]
  We propose a framework for the analysis of the low-rank approximation error in Frobenius norm for centered and non-standard matrices. Under minimal assumptions, we derive accurate bounds in expectation and probability. Our bounds have clear interpretations that enable us to derive properties and motivate practical choices.
  arXiv  Detail & Related papers  (2024-05-08T04:51:56Z)
• Statistical Efficiency of Score Matching: The View from Isoperimetry [96.65637602827942]
  We show a tight connection between statistical efficiency of score matching and the isoperimetric properties of the distribution being estimated. We formalize these results both in the sample regime and in the finite regime.
  arXiv  Detail & Related papers  (2022-10-03T06:09:01Z)
• Optimal variance-reduced stochastic approximation in Banach spaces [114.8734960258221]
  We study the problem of estimating the fixed point of a contractive operator defined on a separable Banach space. We establish non-asymptotic bounds for both the operator defect and the estimation error.
  arXiv  Detail & Related papers  (2022-01-21T02:46:57Z)
• A Stochastic Newton Algorithm for Distributed Convex Optimization [62.20732134991661]
  We analyze a Newton algorithm for homogeneous distributed convex optimization, where each machine can calculate gradients of the same population objective. We show that our method can reduce the number, and frequency, of required communication rounds compared to existing methods without hurting performance.
  arXiv  Detail & Related papers  (2021-10-07T17:51:10Z)
• Heavy-tailed Streaming Statistical Estimation [58.70341336199497]
  We consider the task of heavy-tailed statistical estimation given streaming $p$ samples. We design a clipped gradient descent and provide an improved analysis under a more nuanced condition on the noise of gradients.
  arXiv  Detail & Related papers  (2021-08-25T21:30:27Z)
• Statistical optimality and stability of tangent transform algorithms in logit models [6.9827388859232045]
  We provide conditions on the data generating process to derive non-asymptotic upper bounds to the risk incurred by the logistical optima. In particular, we establish local variation of the algorithm without any assumptions on the data-generating process. We explore a special case involving a semi-orthogonal design under which a global convergence is obtained.
  arXiv  Detail & Related papers  (2020-10-25T05:15:13Z)
• Stochastic Saddle-Point Optimization for Wasserstein Barycenters [69.68068088508505]
  We consider the populationimation barycenter problem for random probability measures supported on a finite set of points and generated by an online stream of data. We employ the structure of the problem and obtain a convex-concave saddle-point reformulation of this problem. In the setting when the distribution of random probability measures is discrete, we propose an optimization algorithm and estimate its complexity.
  arXiv  Detail & Related papers  (2020-06-11T19:40:38Z)
• Asymptotic Analysis of an Ensemble of Randomly Projected Linear Discriminants [94.46276668068327]
  In [1], an ensemble of randomly projected linear discriminants is used to classify datasets. We develop a consistent estimator of the misclassification probability as an alternative to the computationally-costly cross-validation estimator. We also demonstrate the use of our estimator for tuning the projection dimension on both real and synthetic data.
  arXiv  Detail & Related papers  (2020-04-17T12:47:04Z)
• Asymptotic Analysis of Sampling Estimators for Randomized Numerical Linear Algebra Algorithms [43.134933182911766]
  We develop an analysis to derive the distribution of RandNLA sampling estimators for the least-squares problem. We identify optimal sampling probabilities based on the Asymptotic Mean Squared Error (AMSE) and the Expected Asymptotic Mean Squared Error (EAMSE) Our theoretical results clarify the role of leverage in the sampling process, and our empirical results demonstrate improvements over existing methods.
  arXiv  Detail & Related papers  (2020-02-24T20:34:50Z)

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.