Streaming Krylov-Accelerated Stochastic Gradient Descent

• URL: http://arxiv.org/abs/2505.07046v1
• Date: Sun, 11 May 2025 16:36:20 GMT
• Title: Streaming Krylov-Accelerated Stochastic Gradient Descent
• Abstract summary: We present SKA-SGD (Streaming Krylov-Accelerated Gradient Descent), a novel optimization approach.<n>It accelerates convergence for ill-conditioned problems by projecting onto a low-dimensional Krylov subspace.<n> Experimental results demonstrate that SKA-SGD significantly outperforms standard SGD and Adam in convergence rate and final error.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We present SKA-SGD (Streaming Krylov-Accelerated Stochastic Gradient Descent), a novel optimization approach that accelerates convergence for ill-conditioned problems by projecting stochastic gradients onto a low-dimensional Krylov subspace. Directly inspired by recent advances in s-step Conjugate Gradient methods with streaming Gauss-Seidel Gram solvers \cite{dambra2025sstep}, our method extends these techniques to the stochastic optimization domain. Our approach combines three key innovations: (1) projection coefficients computed via a single streaming Gauss-Seidel iteration, which is mathematically equivalent to Modified Gram-Schmidt orthogonalization; (2) a Chebyshev polynomial basis for constructing the Krylov subspace, providing superior numerical stability; and (3) efficient implementation for AMD GPUs using HIP. We prove that our streaming approach achieves a backward error near machine precision with $O(s^2)$ complexity rather than $O(s^3)$, where $s$ is the Krylov subspace dimension. Experimental results demonstrate that SKA-SGD significantly outperforms standard SGD and Adam in convergence rate and final error, particularly for problems with condition numbers exceeding $10^3$. GPU performance analysis reveals a crossover point where communication-avoiding benefits outweigh computational overhead, typically occurring at moderate scale ($p \approx 64$ processors) for problem sizes $n \geq 10^6$.

Related papers

• Scalable Mean-Variance Portfolio Optimization via Subspace Embeddings and GPU-Friendly Nesterov-Accelerated Projected Gradient [0.17188280334580197]
  We develop a sketch-based factor reduction and a Nesterov-accelerated projected gradient algorithm (NPGA) with GPU acceleration.<n>Experiments on synthetic and real equity-return data show that the method preserves objective accuracy while reducing runtime substantially.
  arXiv  Detail & Related papers  (2026-04-03T09:35:05Z)
• Estimation of Toeplitz Covariance Matrices using Overparameterized Gradient Descent [1.7188280334580195]
  We revisit Toeplitz covariance estimation through the lens of simple descent (GD)<n>We show that when $K = P$, GD may converge to suboptimal solutions.<n>We propose an accelerated GD variant with separate learning rates for amplitudes and frequencies.
  arXiv  Detail & Related papers  (2025-11-03T14:07:53Z)
• ReSplat: Learning Recurrent Gaussian Splats [98.14472247275512]
  ReSplat is a feed-forward recurrent Gaussian splatting model that iteratively refines 3D Gaussians without explicitly computing gradients.<n>We introduce a compact reconstruction model that operates in a $16 times$ subsampled space, producing $16 times$ fewer Gaussians than previous per-pixel Gaussian models.<n>Our method achieves state-of-the-art performance while significantly reducing the number of Gaussians and improving the rendering speed.
  arXiv  Detail & Related papers  (2025-10-09T17:59:59Z)
• Second-order Optimization of Gaussian Splats with Importance Sampling [51.95046424364725]
  3D Gaussian Splatting (3DGS) is widely used for novel view rendering due to its high quality and fast inference time.<n>We propose a novel second-order optimization strategy based on Levenberg-Marquardt (LM) and Conjugate Gradient (CG)<n>Our method achieves a $3times$ speedup over standard LM and outperforms Adam by $6times$ when the Gaussian count is low.
  arXiv  Detail & Related papers  (2025-04-17T12:52:08Z)
• Robust Stochastic Optimization via Gradient Quantile Clipping [6.2844649973308835]
  We introduce a quant clipping strategy for Gradient Descent (SGD) We use gradient new outliers as norm clipping chains. We propose an implementation of the algorithm using Huberiles.
  arXiv  Detail & Related papers  (2023-09-29T15:24:48Z)
• Accelerated Quasi-Newton Proximal Extragradient: Faster Rate for Smooth Convex Optimization [26.328847475942894]
  We prove that our method can achieve a convergence rate of $Obigl(minfrac1k2, fracsqrtdlog kk2.5bigr)$, where $d$ is the problem dimension and $k$ is the number of iterations. To the best of our knowledge, this result is the first to demonstrate a provable gain of a quasi-Newton-type method over Nesterov's accelerated gradient.
  arXiv  Detail & Related papers  (2023-06-03T23:31:27Z)
• On Convergence of Incremental Gradient for Non-Convex Smooth Functions [63.51187646914962]
  In machine learning and network optimization, algorithms like shuffle SGD are popular due to minimizing the number of misses and good cache. This paper delves into the convergence properties SGD algorithms with arbitrary data ordering.
  arXiv  Detail & Related papers  (2023-05-30T17:47:27Z)
• Decomposed Diffusion Sampler for Accelerating Large-Scale Inverse Problems [64.29491112653905]
  We propose a novel and efficient diffusion sampling strategy that synergistically combines the diffusion sampling and Krylov subspace methods. Specifically, we prove that if tangent space at a denoised sample by Tweedie's formula forms a Krylov subspace, then the CG with the denoised data ensures the data consistency update to remain in the tangent space. Our proposed method achieves more than 80 times faster inference time than the previous state-of-the-art method.
  arXiv  Detail & Related papers  (2023-03-10T07:42:49Z)
• Stochastic Zeroth order Descent with Structured Directions [10.604744518360464]
  We introduce and analyze Structured Zeroth order Descent (SSZD), a finite difference approach that approximates a gradient on a set $lleq d directions, where $d is the dimension of the ambient space. For convex convex we prove almost sure convergence of functions on $O( (d/l) k-c1/2$)$ for every $c1/2$, which is arbitrarily close to the one of the Gradient Descent (SGD) in terms of one number of iterations.
  arXiv  Detail & Related papers  (2022-06-10T14:00:06Z)
• Improved Convergence Rate of Stochastic Gradient Langevin Dynamics with Variance Reduction and its Application to Optimization [50.83356836818667]
  gradient Langevin Dynamics is one of the most fundamental algorithms to solve non-eps optimization problems. In this paper, we show two variants of this kind, namely the Variance Reduced Langevin Dynamics and the Recursive Gradient Langevin Dynamics.
  arXiv  Detail & Related papers  (2022-03-30T11:39:00Z)
• AdaGDA: Faster Adaptive Gradient Descent Ascent Methods for Minimax Optimization [104.96004056928474]
  We propose a class of faster adaptive gradient descent methods for non-strongly-concave minimax problems. We show that our method reaches a lower sample complexity of $O(kappa2.5epsilon-3)$ with the mini-batch size $O(kappa)$.
  arXiv  Detail & Related papers  (2021-06-30T14:47:09Z)
• Correcting Momentum with Second-order Information [50.992629498861724]
  We develop a new algorithm for non-critical optimization that finds an $O(epsilon)$epsilon point in the optimal product. We validate our results on a variety of large-scale deep learning benchmarks and architectures.
  arXiv  Detail & Related papers  (2021-03-04T19:01:20Z)

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.