Gaussian Approximation and Multiplier Bootstrap for Federated Linear Stochastic Approximation

• URL: http://arxiv.org/abs/2605.19629v1
• Date: Tue, 19 May 2026 10:08:01 GMT
• Title: Gaussian Approximation and Multiplier Bootstrap for Federated Linear Stochastic Approximation
• Abstract summary: We establish Berry-Esseen-type bounds for federated linear approximation (LSA)<n>Results provide the first federated Gaussian approximations for LSA that explicitly capture communication-computation trade-offs and heterogeneity-aware error terms.<n>We present results for both (i) constant step size regime and (ii) decreasing step size with an increasing number of local iterations, recovering the recent rates of Bonnerjee et al [2025] as a special case.
• Score: 25.919837824259474
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this paper, we establish Berry-Esseen-type bounds for federated linear stochastic approximation (LSA). Our results provide the first federated Gaussian approximations for LSA that explicitly capture communication-computation trade-offs and heterogeneity-aware error terms, quantifying the effects of local step size, number of local updates, and heterogeneity on convergence rates. We present results for both (i) constant step size regime and (ii) decreasing step size with an increasing number of local iterations, recovering the recent rates of Bonnerjee et al. [2025] as a special case. As a primary application of our results, we develop an online multiplier bootstrap procedure for inference on the last iterate, which avoids explicit estimation of the asymptotic covariance matrix, and obtain non-asymptotic validity guarantees for this procedure.

Related papers

• Inference and Uncertainty Quantification for Streaming $r$-PCA [0.40105987447353786]
  We address two open questions in streaming PCA via Oja's algorithm.<n>We prove a matching lower bound, up to logarithmic factors, across both dense-tail sparse-tail regimes.
  arXiv  Detail & Related papers  (2026-08-18T23:02:28Z)
• Quantized Stochastic Primal-Dual Methods for Distributed Optimization under Relaxed Global Geometry [2.15242029196761]
  We study distributed optimization with gradients and finite-bit communication modeled by random (unbiased) quantization.<n>Under restricted secant inequality (RSI), a constant step-size yields a linear contraction to an explicit neighborhood determined by gradient noise, quantization distortion, and network connectivity.<n>Under PolyakLojasiewicz (PL) inequality, we obtain linear-to-neighborhood convergence in the same quantized setting.
  arXiv  Detail & Related papers  (2026-06-09T18:18:41Z)
• Improved Central Limit Theorem and Bootstrap Approximations for Linear Stochastic Approximation [28.34847294888529]
  We consider the normal approximation by the Gaussian distribution with covariance matrix predicted by the Polyak-Juditsky central limit theorem.<n>We prove a non-asymptotic validity of the multiplier bootstrap procedure for approximating the distribution of the rescaled error of the averaged LSA estimator.
  arXiv  Detail & Related papers  (2025-10-14T10:50:10Z)
• Uncertainty quantification for Markov chain induced martingales with application to temporal difference learning [55.197497603087065]
  We analyze the performance of the Temporal Difference (TD) learning algorithm with linear function approximations.<n>We establish novel and general high-dimensional concentration inequalities and Berry-Esseen bounds for vector-valued martingales induced by Markov chains.
  arXiv  Detail & Related papers  (2025-02-19T15:33:55Z)
• Riemannian Federated Learning via Averaging Gradient Streams [10.533809913888591]
  Federated learning (FL) as a distributed learning paradigm has a significant advantage in addressing large-scale machine learning tasks.<n>This paper presents and analyzes a new efficient server aggregation -- averaging gradient streams, called RFedAGS.<n>We show that the proposed RFedAGS has global convergence and sublinear convergence rate under decaying step sizes cases.
  arXiv  Detail & Related papers  (2024-09-11T12:28:42Z)
• Gaussian Approximation and Multiplier Bootstrap for Polyak-Ruppert Averaged Linear Stochastic Approximation with Applications to TD Learning [15.041074872715752]
  We prove the non-asymptotic validity of the confidence intervals for parameter estimation with LSA based on multiplier bootstraps.<n>We illustrate our findings in the setting of temporal difference learning with linear function approximation.
  arXiv  Detail & Related papers  (2024-05-26T17:43:30Z)
• Adaptive Annealed Importance Sampling with Constant Rate Progress [68.8204255655161]
  Annealed Importance Sampling (AIS) synthesizes weighted samples from an intractable distribution. We propose the Constant Rate AIS algorithm and its efficient implementation for $alpha$-divergences.
  arXiv  Detail & Related papers  (2023-06-27T08:15:28Z)
• Variational sparse inverse Cholesky approximation for latent Gaussian processes via double Kullback-Leibler minimization [6.012173616364571]
  We combine a variational approximation of the posterior with a similar and efficient SIC-restricted Kullback-Leibler-optimal approximation of the prior. For this setting, our variational approximation can be computed via gradient descent in polylogarithmic time per iteration. We provide numerical comparisons showing that the proposed double-Kullback-Leibler-optimal Gaussian-process approximation (DKLGP) can sometimes be vastly more accurate for stationary kernels than alternative approaches.
  arXiv  Detail & Related papers  (2023-01-30T21:50:08Z)
• Posterior and Computational Uncertainty in Gaussian Processes [52.26904059556759]
  Gaussian processes scale prohibitively with the size of the dataset. Many approximation methods have been developed, which inevitably introduce approximation error. This additional source of uncertainty, due to limited computation, is entirely ignored when using the approximate posterior. We develop a new class of methods that provides consistent estimation of the combined uncertainty arising from both the finite number of data observed and the finite amount of computation expended.
  arXiv  Detail & Related papers  (2022-05-30T22:16:25Z)
• On the Convergence of Stochastic Extragradient for Bilinear Games with Restarted Iteration Averaging [96.13485146617322]
  We present an analysis of the ExtraGradient (SEG) method with constant step size, and present variations of the method that yield favorable convergence. We prove that when augmented with averaging, SEG provably converges to the Nash equilibrium, and such a rate is provably accelerated by incorporating a scheduled restarting procedure.
  arXiv  Detail & Related papers  (2021-06-30T17:51:36Z)
• Scalable Variational Gaussian Processes via Harmonic Kernel Decomposition [54.07797071198249]
  We introduce a new scalable variational Gaussian process approximation which provides a high fidelity approximation while retaining general applicability. We demonstrate that, on a range of regression and classification problems, our approach can exploit input space symmetries such as translations and reflections. Notably, our approach achieves state-of-the-art results on CIFAR-10 among pure GP models.
  arXiv  Detail & Related papers  (2021-06-10T18:17:57Z)
• ROOT-SGD: Sharp Nonasymptotics and Near-Optimal Asymptotics in a Single Algorithm [71.13558000599839]
  We study the problem of solving strongly convex and smooth unconstrained optimization problems using first-order algorithms. We devise a novel, referred to as Recursive One-Over-T SGD, based on an easily implementable, averaging of past gradients. We prove that it simultaneously achieves state-of-the-art performance in both a finite-sample, nonasymptotic sense and an sense.
  arXiv  Detail & Related papers  (2020-08-28T14:46:56Z)
• Random extrapolation for primal-dual coordinate descent [61.55967255151027]
  We introduce a randomly extrapolated primal-dual coordinate descent method that adapts to sparsity of the data matrix and the favorable structures of the objective function. We show almost sure convergence of the sequence and optimal sublinear convergence rates for the primal-dual gap and objective values, in the general convex-concave case.
  arXiv  Detail & Related papers  (2020-07-13T17:39:35Z)

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.