cs.LGApr 24, 2026

Complex Stochastic Gradient Descent and Directional Bias in Reproducing Kernel Hilbert Spaces

Authors: Natanael Alpay, Emeric Battaglia

Abstract

Stochastic Gradient Descent (SGD) is a known stochastic iterative method popular for large-scale convex optimization problems due to its simple implementation and scalability. Some objectives, such as those found in complex-valued neural networks, benefit from updates like in SGD and Gradient Descent (GD) with a newly defined ``gradient'' that allows for complex parameters. This complex variant of the SGD/GD methods has already been proposed, but convergence guarantees without analyticity constraints have not yet been provided. We propose a variant of SGD (complex SGD) that allows for complex parameters, and we provide convergence guarantees under assumptions that parallel those from the real setting. Notably, these results extend to GD as well, and with the same set of assumptions, we confirm that some directional bias results extend from the real to the complex setting for kernel regression problems. We provide empirical results demonstrating the efficacy of the complex SGD in kernel regression problems utilizing complex reproducing kernel Hilbert spaces. In particular, we demonstrate we may recover superoscillation functions and Blaschke products from the Fock Space and Hardy Space, respectively, as the optimal functions for a particular choice of a loss function.

Explore similar work

CardsList
Nov 14, 2025math.OC

Non-Euclidean SGD for Structured Optimization: Unified Analysis and Improved Rates

Recently, several instances of non-Euclidean SGD, including SignSGD, Lion, and Muon, have attracted significant interest from the optimization community due to their practical success in training deep neural networks. Consequently, a number of works have attempted to explain this success by developing theoretical convergence analyses. Unfortunately, these results cannot properly justify the superior performance of these methods, as they could not beat the convergence rate of vanilla Euclidean SGD. We resolve this important open problem by developing a new unified convergence analysis under the structured smoothness and gradient noise assumption. In particular, our results indicate that non-Euclidean SGD (i) can exploit the sparsity or low-rank structure of the upper bounds on the Hessian and gradient noise, (ii) can provably benefit from popular algorithmic tools such as extrapolation or momentum variance reduction, and (iii) can match the state-of-the-art convergence rates of adaptive and more complex optimization algorithms such as AdaGrad and Shampoo.
Dmitry Kovalev, Ekaterina Borodich
Stochastic Gradient DescentOptimization Convergence AnalysisImprovement
AskPDF
Jun 22, 2026math.ST

Generalized nonparametric regression in reproducing kernel Hilbert spaces: Consistency and rates of convergence

We develop a comprehensive theory for regularized M-estimation in reproducing kernel Hilbert spaces. Under mild conditions on the loss we establish existence and measurability of the estimator, covering a wide range of convex and non-convex losses, including bounded robust losses. We further prove sharp rates of convergence with an explicit bias-variance decomposition governed by a novel complexity measure. We show that the variance is independent of misspecification, while the bias depends on a source condition parameter known in the learning literature. For tensor product Sobolev spaces we obtain new rates that connect to spaces of functions with dominating mixed smoothness, substantially extending existing results and explaining why these estimators circumvent the curse of dimensionality. Our methodology, combining elements from both functional analysis and empirical process theory, allows for an asymptotic linearisation of the objective function that avoids both closed-form solutions and global Lipschitz assumptions, and may be of independent interest. The estimators are implemented in C++ and theory is supported by numerical experiments.
Ioannis Kalogridis
Kernel Hilbert SpacesExponential FamilyRegressionConvex LossOptimization Convergence AnalysisAsymptotics+1
AskPDF
Sep 13, 2024math.ST

Improved Finite-Particle Convergence Rates for Stein Variational Gradient Descent

We provide finite-particle convergence rates for the Stein Variational Gradient Descent (SVGD) algorithm in the Kernelized Stein Discrepancy (KSD\mathsf{KSD}) and Wasserstein-2 metrics. Our key insight is that the time derivative of the relative entropy between the joint density of NN particle locations and the NN-fold product target measure, starting from a regular initial distribution, splits into a dominant negative part' proportional to $N$ times the expected $\mathsf{KSD}^2$ and a smaller positive part'. This observation leads to KSD\mathsf{KSD} rates of order 1/N1/\sqrt{N}, in both continuous and discrete time, providing a near optimal (in the sense of matching the corresponding i.i.d. rates) double exponential improvement over the recent result by Shi and Mackey (2024). Under mild assumptions on the kernel and potential, these bounds also grow polynomially in the dimension dd. By adding a bilinear component to the kernel, the above approach is used to further obtain Wasserstein-2 convergence in continuous time. For the case of `bilinear + Matérn' kernels, we derive Wasserstein-2 rates that exhibit a curse-of-dimensionality similar to the i.i.d. setting. We also obtain marginal convergence and long-time propagation of chaos results for the time-averaged particle laws.
Sayan Banerjee, Krishnakumar Balasubramanian, Promit Ghosal
Maximum Mean DiscrepancyOptimization Convergence AnalysisGradient DescentRate-Distortion Theory
AskPDF