paper-with-me

홈 › Papers

Mini-Batch Covariance, Diffusion Limits, and Oracle Complexity in Stochastic Gradient Descent: A Sampling-Design Perspective

2026-03-02 · Daniel Zantedeschi, Kumar Muthuraman arxiv

Stochastic gradient descent (SGD) is central to simulation optimization, stochastic programming, and online M-estimation, where sampling effort is a decision variable. We study the mini-batch gradient noise as a sampling-design object. Under exchangeable fresh-sampling mini-batches, the conditional covariance given the de Finetti directing measure mu is b^{-1} G_mu(theta), and under identifiability the projected population object is b^{-1} G*(theta) -- projected Fisher information for correctly specified likelihoods, the sandwich partner of the Hessian otherwise. This identification fixes the noise matrix entering the diffusion analysis of constant-step SGD: the raw iterate path has a deterministic fluid limit, and the sqrt(b/eta)-scaled fluctuations satisfy a functional CLT with noise covariance G*; near a nondegenerate optimum the limit is Ornstein-Uhlenbeck, and its Lyapunov covariance scaled by eta/b matches the linearized discrete recursion at leading order. Under a curvature-noise compatibility condition mu_F > 0, we prove 1/N mean-square upper bounds and an i.i.d. parametric Fisher van Trees lower bound of the same rate order, with oracle-complexity guarantees depending on an effective dimension d_eff and condition number kappa_F. Numerical experiments verify the identification and confirm the Lyapunov predictions in direct SGD.

📄 PDF Abstract BibTeX arXiv:2603.02417

Code (0)

등록된 구현이 없습니다.

Similar Papers 제목 키워드 기반

Transfer Learning for Linear Discriminant Analysis with a Shared Classification Signal

2026-07-08 · Yonghan Zhang, Yimeng Fan, Wenya Luo, Jiang Hu arxiv

This paper studies transfer learning for linear discriminant analysis in high-dimensional two-class classification. We consider one target domain and several source domains, where the mean difference in each domain is de…

Transfer Learning

Minimax-Optimal Dimension-Reduced Clustering for High-Dimensional Nonspherical Mixtures

2025-02-04 · Chengzhu Huang, Yuqi Gu

In mixture models, nonspherical (anisotropic) noise within each cluster is widely present in real-world data. We study both the minimax rate and optimal statistical procedure for clustering under high-dimensional nonsphe…

ClusteringDimensionality Reduction

EE-Grad: Exploration and Exploitation for Cost-Efficient Mini-Batch SGD

2017-05-19 · Mehmet A. Donmez, Maxim Raginsky, Andrew C. Singer

We present a generic framework for trading off fidelity and cost in computing stochastic gradients when the costs of acquiring stochastic gradients of different quality are not known a priori. We consider a mini-batch or…

A Diffusion Theory For Deep Learning Dynamics: Stochastic Gradient Descent Exponentially Favors Flat Minima

2020-02-10 · ICLR 2021 1 · Zeke Xie, Issei Sato, Masashi Sugiyama

Stochastic Gradient Descent (SGD) and its variants are mainstream methods for training deep networks in practice. SGD is known to find a flat minimum with a large neighboring region in the parameter space from which each…

Stochastic Optimization

Utilising the CLT Structure in Stochastic Gradient based Sampling : Improved Analysis and Faster Algorithms

2022-06-08 · Aniket Das, Dheeraj Nagaraj, Anant Raj

We consider stochastic approximations of sampling algorithms, such as Stochastic Gradient Langevin Dynamics (SGLD) and the Random Batch Method (RBM) for Interacting Particle Dynamcs (IPD). We observe that the noise intro…