Nearly Instance-Optimal Parameter Recovery from Many Trajectories via Hellinger Localization

• URL: http://arxiv.org/abs/2510.06434v1
• Date: Tue, 07 Oct 2025 20:12:04 GMT
• Title: Nearly Instance-Optimal Parameter Recovery from Many Trajectories via Hellinger Localization
• Authors: Eliot Shekhtman, Yichen Zhou, Ingvar Ziemann, Nikolai Matni, Stephen Tu,
• Abstract summary: We extend the scope of instance-optimal rates in multi-trajectory settings via the Hellinger localization framework.<n>We instantiate our framework across four diverse case studies.<n>Our bounds nearly match the instance-optimal rates from normality, substantially improving over standard reductions.
• Score: 19.74516565968901
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Learning from temporally-correlated data is a core facet of modern machine learning. Yet our understanding of sequential learning remains incomplete, particularly in the multi-trajectory setting where data consists of many independent realizations of a time-indexed stochastic process. This important regime both reflects modern training pipelines such as for large foundation models, and offers the potential for learning without the typical mixing assumptions made in the single-trajectory case. However, instance-optimal bounds are known only for least-squares regression with dependent covariates; for more general models or loss functions, the only broadly applicable guarantees result from a reduction to either i.i.d. learning, with effective sample size scaling only in the number of trajectories, or an existing single-trajectory result when each individual trajectory mixes, with effective sample size scaling as the full data budget deflated by the mixing-time. In this work, we significantly broaden the scope of instance-optimal rates in multi-trajectory settings via the Hellinger localization framework, a general approach for maximum likelihood estimation. Our method proceeds by first controlling the squared Hellinger distance at the path-measure level via a reduction to i.i.d. learning, followed by localization as a quadratic form in parameter space weighted by the trajectory Fisher information. This yields instance-optimal bounds that scale with the full data budget under a broad set of conditions. We instantiate our framework across four diverse case studies: a simple mixture of Markov chains, dependent linear regression under non-Gaussian noise, generalized linear models with non-monotonic activations, and linear-attention sequence models. In all cases, our bounds nearly match the instance-optimal rates from asymptotic normality, substantially improving over standard reductions.

Related papers

• Generalized Linear Bandits: Almost Optimal Regret with One-Pass Update [60.414548453838506]
  We study the generalized linear bandit (GLB) problem, a contextual multi-armed bandit framework that extends the classical linear model by incorporating a non-linear link function.<n>GLBs are widely applicable to real-world scenarios, but their non-linear nature introduces significant challenges in achieving both computational and statistical efficiency.<n>We propose a jointly efficient algorithm that attains a nearly optimal regret bound with $mathcalO(1)$ time and space complexities per round.
  arXiv  Detail & Related papers  (2025-07-16T02:24:21Z)
• Discretization-free Multicalibration through Loss Minimization over Tree Ensembles [22.276913140687725]
  We propose a discretization-free multicalibration method over an ensemble of depth-two decision trees.<n>Our algorithm provably achieves multicalibration, provided that the data distribution satisfies a technical condition we term as loss saturation.
  arXiv  Detail & Related papers  (2025-05-23T03:29:58Z)
• Learning with Imperfect Models: When Multi-step Prediction Mitigates Compounding Error [25.387541996071093]
  Compounding error, where small prediction mistakes accumulate over time, presents a major challenge in learning-based control.<n>One approach to mitigate compounding error is to train multi-step predictors directly, rather than relying on autoregressive rollout of a single-step model.<n>We show that when the model class is well-specified and accurately captures the system dynamics, single-step models achieve lower prediction error.<n>On the other hand, when the model class is misspecified due to partial observability, direct multi-step predictors can significantly reduce bias and thus outperform single-step approaches.
  arXiv  Detail & Related papers  (2025-04-02T14:18:52Z)
• Learning with Shared Representations: Statistical Rates and Efficient Algorithms [13.643155483461028]
  Collaborative learning through latent shared representations enables heterogeneous clients to train personalized models with enhanced performance while reducing sample size.<n>Despite its empirical success and extensive research, the theoretical understanding of statistical error rates remains incomplete, even for shared representations constrained to low-dimensional linear subspaces.
  arXiv  Detail & Related papers  (2024-09-07T21:53:01Z)
• Generalization Bounds of Surrogate Policies for Combinatorial Optimization Problems [53.03951222945921]
  We analyze smoothed (perturbed) policies, adding controlled random perturbations to the direction used by the linear oracle.<n>Our main contribution is a generalization bound that decomposes the excess risk into perturbation bias, statistical estimation error, and optimization error.<n>We illustrate the scope of the results on applications such as vehicle scheduling, highlighting how smoothing enables both tractable training and controlled generalization.
  arXiv  Detail & Related papers  (2024-07-24T12:00:30Z)
• Sampling from Gaussian Process Posteriors using Stochastic Gradient Descent [43.097493761380186]
  gradient algorithms are an efficient method of approximately solving linear systems. We show that gradient descent produces accurate predictions, even in cases where it does not converge quickly to the optimum. Experimentally, gradient descent achieves state-of-the-art performance on sufficiently large-scale or ill-conditioned regression tasks.
  arXiv  Detail & Related papers  (2023-06-20T15:07:37Z)
• Aiming towards the minimizers: fast convergence of SGD for overparametrized problems [25.077446336619378]
  We propose a regularity regime which endows the gradient method with the same worst-case complexity as the gradient method. All existing guarantees require the gradient method to take small steps, thereby resulting in a much slower linear rate of convergence. We demonstrate that our condition holds when training sufficiently wide feedforward neural networks with a linear output layer.
  arXiv  Detail & Related papers  (2023-06-05T05:21:01Z)
• Theoretical Characterization of the Generalization Performance of Overfitted Meta-Learning [70.52689048213398]
  This paper studies the performance of overfitted meta-learning under a linear regression model with Gaussian features. We find new and interesting properties that do not exist in single-task linear regression. Our analysis suggests that benign overfitting is more significant and easier to observe when the noise and the diversity/fluctuation of the ground truth of each training task are large.
  arXiv  Detail & Related papers  (2023-04-09T20:36:13Z)
• Compound Batch Normalization for Long-tailed Image Classification [77.42829178064807]
  We propose a compound batch normalization method based on a Gaussian mixture. It can model the feature space more comprehensively and reduce the dominance of head classes. The proposed method outperforms existing methods on long-tailed image classification.
  arXiv  Detail & Related papers  (2022-12-02T07:31:39Z)
• Instance-Dependent Generalization Bounds via Optimal Transport [51.71650746285469]
  Existing generalization bounds fail to explain crucial factors that drive the generalization of modern neural networks. We derive instance-dependent generalization bounds that depend on the local Lipschitz regularity of the learned prediction function in the data space. We empirically analyze our generalization bounds for neural networks, showing that the bound values are meaningful and capture the effect of popular regularization methods during training.
  arXiv  Detail & Related papers  (2022-11-02T16:39:42Z)
• The Role of Pseudo-labels in Self-training Linear Classifiers on High-dimensional Gaussian Mixture Data [3.1274367448459253]
  Self-training (ST) is a simple yet effective semi-supervised learning method. We show that ST improves generalization in different ways depending on the number of iterations.
  arXiv  Detail & Related papers  (2022-05-16T15:02:44Z)
• Attentional-Biased Stochastic Gradient Descent [74.49926199036481]
  We present a provable method (named ABSGD) for addressing the data imbalance or label noise problem in deep learning. Our method is a simple modification to momentum SGD where we assign an individual importance weight to each sample in the mini-batch. ABSGD is flexible enough to combine with other robust losses without any additional cost.
  arXiv  Detail & Related papers  (2020-12-13T03:41:52Z)
• Online stochastic gradient descent on non-convex losses from high-dimensional inference [2.2344764434954256]
  gradient descent (SGD) is a popular algorithm for optimization problems in high-dimensional tasks. In this paper we produce an estimator of non-trivial correlation from data. We illustrate our approach by applying it to a set of tasks such as phase retrieval, and estimation for generalized models.
  arXiv  Detail & Related papers  (2020-03-23T17:34:06Z)

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.