Stochastic Gradient Optimization Techniques

Derniers papiers

• Shuffling the Data, Stretching the Step-size: Sharper Bias in constant step-size SGD

  Konstantinos Emmanouilidis, Emmanouil-Vasileios Vlatakis-Gkaragkounis, Rene Vidal · 14 avril 2026

  From adversarial robustness to multi-agent learning, many machine learning tasks can be cast as finite-sum min-max optimization or, more generally, as variational inequality problems (VIPs). Owing to their simplicity and scalability, stochastic gradient methods with constant step size are widely use…

• Online Covariance Estimation in Averaged SGD: Improved Batch-Mean Rates and Minimax Optimality via Trajectory Regression

  Yijin Ni, Xiaoming Huo · 14 avril 2026

  We study online covariance matrix estimation for Polyak--Ruppert averaged stochastic gradient descent (SGD). The online batch-means estimator of Zhu, Chen and Wu (2023) achieves an operator-norm convergence rate of $O(n^{-(1-\alpha)/4})$, which yields $O(n^{-1/8})$ at the optimal learning-rate expon…

• SHANG++: Robust Stochastic Acceleration under Multiplicative Noise

  Yaxin Yu, Long Chen, Minfu Feng · 14 avril 2026

  Under the multiplicative noise scaling (MNS) condition, original Nesterov acceleration is provably sensitive to noise and may diverge when gradient noise overwhelms the signal. In this paper, we develop two accelerated stochastic gradient descent methods by discretizing the Hessian-driven Nesterov a…

• Last-Iterate Convergence of Randomized Kaczmarz and SGD with Greedy Step Size

  Micha{\l} Derezi\'nski, Xiaoyu Dong · 14 avril 2026

  We study last-iterate convergence of SGD with greedy step size over smooth quadratics in the interpolation regime, a setting which captures the classical Randomized Kaczmarz algorithm as well as other popular iterative linear system solvers. For these methods, we show that the $t$-th iterate attains…

• Query Lower Bounds for Diffusion Sampling

  Zhiyang Xun, Eric Price · 14 avril 2026

  Diffusion models generate samples by iteratively querying learned score estimates. A rapidly growing literature focuses on accelerating sampling by minimizing the number of score evaluations, yet the information-theoretic limits of such acceleration remain unclear. In this work, we establish the f…

• Continuous-time Online Learning via Mean-Field Neural Networks: Regret Analysis in Diffusion Environments

  Erhan Bayraktar, Bingyan Han, Ziqing Zhang · 14 avril 2026

  We study continuous-time online learning where data are generated by a diffusion process with unknown coefficients. The learner employs a two-layer neural network, continuously updating its parameters in a non-anticipative manner. The mean-field limit of the learning dynamics corresponds to a stocha…

• Heterogeneous Connectivity in Sparse Networks: Fan-in Profiles, Gradient Hierarchy, and Topological Equilibria

  Nikodem Tomczak · 14 avril 2026

  Profiled Sparse Networks (PSN) replace uniform connectivity with deterministic, heterogeneous fan-in profiles defined by continuous, nonlinear functions, creating neurons with both dense and sparse receptive fields. We benchmark PSN across four classification datasets spanning vision and tabular dom…

• Universality of first-order methods on random and deterministic matrices

  Nicola Gorini, Chris Jones, Dmitriy Kunisky, Lucas Pesenti · 14 avril 2026

  General first-order methods (GFOM) are a flexible class of iterative algorithms which update a state vector by matrix-vector multiplications and entrywise nonlinearities. A long line of work has sought to understand the large-n dynamics of GFOM, mostly focusing on "very random" input matrices and th…

• Tail-Aware Information-Theoretic Generalization for RLHF and SGLD

  Huiming Zhang, Binghan Li, Wan Tian, Qiang Sun · 14 avril 2026

  Classical information-theoretic generalization bounds typically control the generalization gap through KL-based mutual information and therefore rely on boundedness or sub-Gaussian tails via the moment generating function (MGF). In many modern pipelines, such as robust learning, RLHF, and stochastic…

• Generating Hadamard matrices with transformers

  Geordie Williamson, Oded Yacobi, Paul Zinn-Justin · 14 avril 2026

  We present a new method for constructing Hadamard matrices that combines transformer neural networks with local search in the PatternBoost framework. Our approach is designed for extremely sparse combinatorial search problems and is particularly effective for Hadamard matrices of Goethals--Seidel ty…

• Byzantine-Robust Distributed SGD: A Unified Analysis and Tight Error Bounds

  Boyuan Ruan, Xiaoyu Wang, Ya-Feng Liu · 14 avril 2026

  Byzantine-robust distributed optimization relies on robust aggregation rules to mitigate the influence of malicious Byzantine workers. Despite the proliferation of such rules, a unified convergence analysis framework that accommodates general data heterogeneity is lacking. In this work, we provide a…

• Generalization and Scaling Laws for Mixture-of-Experts Transformers

  Mansour Zoubeirou a Mayaki · 13 avril 2026

  We develop a theory of generalization and scaling for Mixture-of-Experts (MoE) Transformers that cleanly separates \emph{active} per-input capacity from routing combinatorics. By conditioning on fixed routing patterns and union-bounding across them, we derive a sup-norm covering-number bound whose m…

• PACED: Distillation and On-Policy Self-Distillation at the Frontier of Student Competence

  Yuanda Xu, Hejian Sang, Zhengze Zhou, Ran He, Zhipeng Wang · 13 avril 2026

  Standard LLM distillation treats all training problems equally -- wasting compute on problems the student has already mastered or cannot yet solve. We empirically show that this inefficiency has a precise gradient-level signature: the cross-problem gradient signal-to-noise ratio (SNR) follows a bell…

• Spectral-Transport Stability and Benign Overfitting in Interpolating Learning

  Gustav Olaf Yunus Laitinen-Lundstr\"om Fredriksson-Imanov · 13 avril 2026

  We develop a theoretical framework for generalization in the interpolating regime of statistical learning. The central question is why highly overparameterized estimators can attain zero empirical risk while still achieving nontrivial predictive accuracy, and how to characterize the boundary between…

• Adam-HNAG: A Convergent Reformulation of Adam with Accelerated Rate

  Yaxin Yu, Long Chen, Zeyi Xu · 13 avril 2026

  Adam has achieved strong empirical success, but its theory remains incomplete even in the deterministic full-batch setting, largely because adaptive preconditioning and momentum are tightly coupled. In this work, a convergent reformulation of full-batch Adam is developed by combining variable and op…

• Online Quantile Regression for Nonparametric Additive Models

  Haoran Zhan · 13 avril 2026

  This paper introduces a projected functional gradient descent algorithm (P-FGD) for training nonparametric additive quantile regression models in online settings. This algorithm extends the functional stochastic gradient descent framework to the pinball loss. An advantage of P-FGD is that it does no…

• Distributed Online Convex Optimization with Compressed Communication: Optimal Regret and Applications

  Sifan Yang, Dan-Yue Li, Lijun Zhang · 13 avril 2026

  Distributed online convex optimization (D-OCO) is a powerful paradigm for modeling distributed scenarios with streaming data. However, the communication cost between local learners and the central server is substantial in large-scale applications. To alleviate this bottleneck, we initiate the study …

• OASIS: Online Activation Subspace Learning for Memory-Efficient Training

  Sakshi Choudhary, Utkarsh Saxena, Kaushik Roy · 13 avril 2026

  Training large language models (LLMs) is constrained by memory requirements, with activations accounting for a substantial fraction of the total footprint. Existing approaches reduce memory using low-rank weight parameterizations or low-rank gradient subspaces for optimizer states, while activation …

• Sharp description of local minima in the loss landscape of high-dimensional two-layer ReLU neural networks

  Jie Huang, Bruno Loureiro, Stefano Sarao Mannelli · 13 avril 2026

  We study the population loss landscape of two-layer ReLU networks of the form $\sum_{k=1}^K \mathrm{ReLU}(w_k^\top x)$ in a realisable teacher-student setting with Gaussian covariates. We show that local minima admit an exact low-dimensional representation in terms of summary statistics, yielding a …

• AdaCubic: An Adaptive Cubic Regularization Optimizer for Deep Learning

  Ioannis Tsingalis, Constantine Kotropoulos, Corentin Briat · 13 avril 2026

  A novel regularization technique, AdaCubic, is proposed that adapts the weight of the cubic term. The heart of AdaCubic is an auxiliary optimization problem with cubic constraints that dynamically adjusts the weight of the cubic term in Newton's cubic regularized method. We use Hutchinson's method t…

• Continuous-Time Dynamics of the Difference-of-Convex Algorithm

  Yi-Shuai Niu · 9 avril 2026

  We study the continuous-time structure of the difference-of-convex algorithm (DCA) for smooth DC decompositions with a strongly convex component. In dual coordinates, classical DCA is exactly the full-step explicit Euler discretization of a nonlinear autonomous system. This viewpoint motivates a dam…

• CRPS-Optimal Binning for Univariate Conformal Regression

  Paolo Toccaceli · 9 avril 2026

  We propose a method for non-parametric conditional distribution estimation based on partitioning covariate-sorted observations into contiguous bins and using the within-bin empirical CDF as the predictive distribution. Bin boundaries are chosen to minimise the total leave-one-out Continuous Ranked P…

• Stochastic Auto-conditioned Fast Gradient Methods with Optimal Rates

  Yao Ji, Guanghui Lan · 9 avril 2026

  Achieving optimal rates for stochastic composite convex optimization without prior knowledge of problem parameters remains a central challenge. In the deterministic setting, the auto-conditioned fast gradient method has recently been proposed to attain optimal accelerated rates without line-search p…

• Optimal Rates for Pure {\varepsilon}-Differentially Private Stochastic Convex Optimization with Heavy Tails

  Andrew Lowy · 9 avril 2026

  We study stochastic convex optimization (SCO) with heavy-tailed gradients under pure epsilon-differential privacy (DP). Instead of assuming a bound on the worst-case Lipschitz parameter of the loss, we assume only a bounded k-th moment. This assumption allows for unbounded, heavy-tailed stochastic g…

• Drifting Fields are not Conservative

  Leonard Franz, Sebastian Hoffmann, Georg Martius · 9 avril 2026

  Drifting models generate high-quality samples in a single forward pass by transporting generated samples toward the data distribution using a vector valued drift field. We investigate whether this procedure is equivalent to optimizing a scalar loss and find that, in general, it is not: drift fields …