CS Paper Radar

Optimization Geometry of Equivalent Brownian RKHS Representations

Mahdi Mohammadigohari, Gustau Camps-Valls

cs.LG ·submitted 2026-09-18 12:28 UTC · v1
theory

Abstract

Equivalent finite parameterizations can represent the same functions and intrinsic norm yet induce different optimization algorithms. We study this effect in a controlled finite Brownian RKHS with nodal, increment, and spectral coordinates. Classical finite-element, RKHS-interpolation, Brownian-covariance, and mixed-boundary DCT identities make the shared hypothesis class, Brownian energy, approximation operator, and coordinate maps explicit. Our main results concern the optimization geometry of this fixed model. With mapped initialization, identical scalar steps, and identical minibatches, nodal and spectral GD/SGD have exactly the same mapped trajectories. Increment GD is an explicit Euler step for the constant Brownian/Sobolev metric, with factor $1/h$. For Brownian-regularized least squares, $κ_2(\mathbf H_{\mathrm{inc}})\le1+A/ρ$, independently of grid resolution $G$ for fixed $A$, $ρ>0$, and the stated normalization. Under the stated standard-Adam convention, the universal orthogonal equivariance group is exactly the signed permutations; the block DCT-VIII transform is not one. Float64 tests over five grids numerically verify the finite identities, mapped one-layer and recursive trajectories, conditioning predictions, and theorem-matched Adam separation. Thus coordinate effects are isolated without changing the represented functions, intrinsic regularizer, or approximation space.

Closest papers

Nearest neighbours by meaning across the whole index.

Projected Riemannian Gradient Descent for the Bures-Wasserstein Barycenter: Dimension-Independent Linear Convergence at Unit Step Size

cs.LG math.OCquant-ph ·2026-09-03 ·A. Afham
similarity 0.61
Abstract · 33 Pages, 3 figures. Comments welcome!

The computation of the Bures-Wasserstein (BW) barycenter of an ensemble of positive definite matrices arises throughout machine learning, optimal transport, and quantum information. Riemannian gradient descent (RGD) at unit step size -- the fixed-point iteration used in practice -- converges rapidly, yet existing analyses present a dichotomy: unit-step guarantees carry worst-case exponential dependence on the dimension, while dimension-independent guarantees require small step sizes that forfeit the empirical speed. We resolve this dichotomy, not by improving the guarantees for unit-step RGD, but by proposing a Projected RGD algorithm that achieves dimension-independent linear convergence at unit step size. The achieved rate, $(1 - κ^{-3/2})$, where $κ$ is the condition number of the ensemble, also polynomially improves on the best small-step guarantee ($κ^{3/2}$ versus $κ^{5/2}$ iteration complexity). The crux is a novel Projection Lemma: clipping the eigenvalues of a positive matrix to an interval $[α, β]$ is the closed-form, non-expansive (1-Lipschitz) BW-metric projection onto the set $\{S : αI \leq S \leq βI\}$ -- a statement which, unlike its known one-sided counterpart, does not follow from convexity. The projection is moreover free: it reuses an eigendecomposition the next iteration must perform in any case, so the projected and unprojected iterations cost the same per step. The same analysis covers the invariant matrix projection problem of Brahmachari et al. (2025), whose fixed-point algorithm we identify as unit-step RGD on a totally geodesic submanifold, thereby extending the dimension-independent guarantee to that setting verbatim.

0.20

Random Projections for Spectral Algorithms: Optimal Rates in Sobolev Norms

cs.LG stat.ML ·2026-10-22 ·Caixing Wang, Yue Wang
similarity 0.61
Abstract

Random projections (RP) offer an effective method for reducing computational and storage overhead while preserving the geometric structure of data. However, existing studies have primarily focused on the optimal generalization performance of specific kernel-regularized algorithms with RP in the well-specified setting and under restrictive conditions. In this paper, we provide a comprehensive and improved analysis of the generalization performance of RP-based spectral algorithms under general conditions \change{without sacrificing statistical efficiency}. By leveraging the embedding property of the reproducing kernel Hilbert space (RKHS) and a refined analysis of the operator similarity, we establish optimal learning rates in Sobolev norms that match the minimax lower bounds up to logarithmic factors. For two common implementations of RP, randomized sketches and Nyström sub-sampling (uniform or leverage-based), we show that the projection dimension required for optimality is proportional to the average or maximal effective dimension, yielding a significant reduction in computational cost while maintaining the statistical efficiency. Our results do not rely on the uniform boundedness assumption on the regression function and are valid across a wide range of source conditions, i.e., $s> α_0-1/β$, where $s,β$, and $α_0$ denote the smoothness index, capacity index, and the embedding index, respectively. In the benign case when $α_0=1/β$, the optimality holds for all $s\in (0,2τ]$ with $τ$ and $γ$ denoting the qualification index and norm index. Experimental results demonstrate both the theoretical validity and the practical effectiveness of the proposed method.

0.29

Convergence Rates of Gaussian Process Thompson Sampling for Efficient Global Optimization

cs.LG stat.ML ·2026-10-14 ·Haowei Wang, Yilin Zheng
theoryhot direction similarity 0.58
Abstract

Efficient global optimization aims to identify a global optimum of an expensive black-box function within a limited evaluation budget $N$. We investigate the convergence rates of Gaussian process Thompson sampling (GP-TS) under noiseless observations, assuming a fixed objective function in a reproducing kernel Hilbert space (RKHS). For Matérn kernels with smoothness parameter $ν$ in dimension $d$, we establish a worst-case expected simple-regret upper bound of $O(N^{-ν/d}\sqrt{\log N})$ for both discrete GP-TS on sufficiently fine grids and its continuous counterpart. For the continuous implementation, we develop a nested-grid argument to control posterior sample paths over the entire domain. We further establish matching lower bounds of $Ω(N^{-5/2}\sqrt{\log N})$ for both implementations under a fixed one-dimensional Matérn-$5/2$ kernel, demonstrating that the logarithmic penalty is intrinsic to standard GP-TS in this setting. Motivated by this limitation, we propose Gaussian Process Capped Thompson Sampling (GP-CTS), which caps posterior sample paths using a valid RKHS norm upper bound while preserving optimism. This modification successfully eliminates the logarithmic penalty and achieves the minimax-optimal rate $Θ(N^{-ν/d})$ for both discrete and continuous implementations.

0.28

Common Covariance Geometry and Certification for Brownian Kernel Ladders

cs.LG ·2026-08-25 ·Mahdi Mohammadigohari
similarity 0.58
Abstract

A representation-adaptive kernel class produces, on a fixed sample, a union of reproducing-kernel Hilbert-space ellipsoids rather than one ellipsoid. We introduce the minimum-trace common covariance that dominates the unrestricted empirical union generated by Brownian kernel ladders and develop its statistical, approximation-theoretic, and computational consequences. The covariance value admits exact formulations through absolutely two-summing operators and covariance-dominated multipliers, and it yields a universal Gaussian-complexity bound. A closed last-layer Dirac-trace reduction and a signed Brownian threshold representation convert the generic covariance problem into threshold, graph-coarea, and effective-resistance geometry. These tools give deterministic depth laws, conditional Gaussian reverses, random-design and perturbation transfers, and an exact empirical Kolmogorov-width formula whose leading covariance eigenspaces approximate the complete adaptive ball simultaneously. Finite contact, active semidefinite programs, verified separation, and a convex resistance-design relaxation provide complementary lower and upper certificates. A finite covariance-indexed Brownian path on frozen representations illustrates the distinction between successful covariance certification and predictive selection: all reported path certificates succeed, whereas the locked predictive study misses one predeclared aggregate criterion. The paper thereby identifies one finite-dimensional covariance object linking unrestricted kernel adaptation, Gaussian geometry, common subspaces, and certifiable computation.

0.28

Adaptive Bregman Proximal Stochastic Gradient with a Stabilized Barzilai--Borwein Step Size

cs.LG math.OC ·2026-08-12 ·Chenhan Jin, Shengze Xu, Binghui Xie, Kaiwen Zhou, Fan Jia +2 more
theory similarity 0.58
Abstract

Bregman proximal stochastic gradient (BPSG) methods bring variance-reduced composite optimization to objectives whose geometry is poorly captured by Euclidean smoothness. Their performance, however, remains sensitive to the step size: raw stochastic curvature estimates can fluctuate sharply, whereas line searches add repeated proximal evaluations. We introduce Ada-BPSG, a line-search-free BPSG method that couples the SAGA gradient table with a stabilized Barzilai--Borwein (BB) candidate. A mediant aggregates incremental secant information so that nearly singular local ratios receive little weight, and an explicit safeguard translates the resulting curvature estimate into the bounded step-size sequence required for convergence. This design yields a direct analytical chain from relative smoothness and component-wise variance control to convergence in finite-dimensional normed spaces. We prove an $O(n/K)$ ergodic rate for convex objectives, a restarted linear rate under relative quadratic growth, and an $O(1/K)$ bound for a Bregman proximal residual in the nonconvex setting. On logistic regression and sparse nonnegative matrix factorization, Ada-BPSG combines low objective values with substantially less sensitivity to the initial step size than standard variance-reduced baselines, while avoiding line search.

0.04

Optimal Control of RKHS Diffeomorphic Flows for Classification and Generative Modeling

cs.LG math.NAmath.OC ·2026-11-17 ·Christopher Chukwuemeka, Andreas Mang
benchmark similarity 0.57
Abstract · 55 pages, 21 figures, 16 tables, 6 algorithms

We develop a unified optimal-control framework that solves supervised classification and likelihood-based density estimation with a single diffeomorphic flow whose velocity lives in a reproducing kernel Hilbert space (RKHS); the two tasks share all structure except the objective. Variable projection eliminates the terminal model (a classifier, or a Gaussian-mixture (GMM) reference), leaving a reduced control problem whose gradient comes from an analytic discrete adjoint. The RKHS parameterization makes the flow's divergence exact and deterministic at the cost of one kernel matrix-vector product, avoiding the stochastic trace estimators and potential-flow restrictions of existing continuous normalizing flows. Because the objective and gradient are deterministic, matrix-free reduced Gauss-Newton (GN) and related second-order solvers are practical for both tasks, which we benchmark against a range of first- and second-order optimizers; the learned map is a diffeomorphism with explicitly controlled regularity. In experiments from dimension 2 to 256, the reduced GN solvers use the fewest iterations of any optimizer tested and, together with joint L-BFGS, the least work; a multiscale kernel improves the density fit, and a trainable GMM reference reduces the deformation needed for multimodal transport at comparable likelihood while lowering the likelihood on real data. The full-model solve is quadratic in the particle count and sub-linear in dimension; a control-point reduction makes the particle-count scaling linear at near-lossless accuracy.

0.33

Variation Brownian Kernel Ladders

cs.LG ·2026-08-14 ·Mahdi Mohammadigohari
similarity 0.57
Abstract

Claims about the benefit of depth depend on the complexity assigned to a representation. We introduce the \emph{Variation Brownian Kernel Ladder} (VBKL), a path-atomic function-space framework that separates nonlinear recursive dictionary construction from linear variation superposition. Starting from linear projections, each atom recursively composes unit-ball profiles from the Brownian reproducing kernel Hilbert space; the full VBKL space is then the signed-measure variation hull of the completed dictionary. We identify each recursive dictionary as a union of Brownian pullback RKHS balls and establish variation-controlled Hölder regularity, compactness and attainment, and strict growth with depth under a local non-degeneracy condition whose trace lies in the support of the input measure. For associated finite lower-support architectures, we derive Rademacher and generalization bounds through Brownian quadratic chaos, signed threshold traces, and VC entropy. We also construct two-stage approximants by discretizing the outer measure and the selected outer Brownian profiles, obtaining an $M^{-1/2}+m^{-1/2}$ error bound, a sharp interpolation constant $\sqrt{A/2}$, and at most $2M$ active outer-profile basis contributions per evaluation. Controlled experiments illustrate the approximation mechanisms and indicate a favorable limited-data accuracy--complexity trade-off.

0.04

Resolution-Independent Analysis of Encoder--Decoder Operator Learning via Limiting Kernels

cs.LG stat.MLmath.FAmath.NA ·2026-09-12 ·Lei Shi, Jia-Qi Yang, Ding-Xuan Zhou
similarity 0.56
Abstract · 69 pages

Operator learning is formulated on function spaces, but training data are typically available only through finite-dimensional representations. In encoder--decoder architectures, a matrix-valued kernel on the encoded space induces an operator-valued kernel on the original function spaces, and the corresponding reproducing kernel Hilbert spaces are isometrically isomorphic. As the input and output resolutions increase, the induced kernels converge to a limiting kernel, in the sense of operator-norm convergence of their associated integral operators, allowing regularity assumptions to be stated independently of the encoding resolution. For regularized stochastic gradient descent, we establish upper bounds for decreasing and fixed step sizes, separating the encoding and regularization terms from optimization terms of order \(t^{-θ}\) and \(T^{-θ'}\), respectively, for any \(θ,θ'\in(0,1)\). We further prove lower bounds showing that these encoding-induced terms are generally unavoidable. The analysis is further extended to encoder--decoder neural networks through the limiting neural tangent kernel (NTK), yielding error bounds with an additional finite-width term and polynomial parameter and sample complexity guarantees when the encoding errors decay algebraically. The framework covers matrix-valued kernels constructed from radial and dot product kernels, NTKs arising from wide encoder--decoder neural networks, and encoder--decoder pairs based on Fourier, Legendre polynomial, wavelet, PCA, or pointwise sampling representations.

0.30