CS Paper Radar

Learning Conditional Expectation Operators via Functional Newton Updates

Thiago Ramos, Alek Fröhlich, Daniel Perazzo, Massimiliano Pontil

cs.LG stat.ML ·submitted 2026-09-28 16:48 UTC · v1

Abstract

We introduce the Functional Spectral-Newton Method (FSNM) for learning the leading singular structure of a conditional expectation operator without fixing a basis or reproducing kernel Hilbert space. FSNM fits a low-rank representation of the centered joint-to-product density ratio kernel by alternating functional Newton updates. Each update reduces to a preconditioned regression, which we approximate with vector-valued regression trees in a stagewise boosting procedure. At the population level, we establish descent and an $O(1/T)$ best-iterate block-stationarity rate under a relative weak-learner accuracy condition, and show that every nondegenerate local minimum over the full centered $L^2$ spaces is a globally optimal rank-$d$ approximation. Synthetic experiments show that FSNM recovers a low-rank density ratio and its leading spectral structure, and that the same learned kernel can answer multiple conditional queries without refitting.

Closest papers

Nearest neighbours by meaning across the whole index.

Kernel Methods for Learning Operators with Multiple Inputs and Outputs

cs.LG math.STstat.ML ·2026-08-12 ·Adrien Weihs, Chunyang Liao, Jingmin Sun, Hayden Schaeffer
similarity 0.63
Abstract

Learning mappings between infinite-dimensional objects is a central challenge in scientific machine learning. We introduce a general kernel-based encoder-decoder framework for operator learning that separates observation, representation, learning, and reconstruction. We develop this framework for multi-input, multi-output operator learning, where operators map between products of potentially distinct function spaces. Our approximation theory shows that, although the number of inputs and outputs can increase, the convergence rate is governed by the most challenging constituent approximation problem rather than the overall problem dimension. The framework leads to practical kernel methods with closed-form training and inference, combining mathematical tractability with computational efficiency. We further specialize the approach to multiple operator learning by introducing KernelMO, a family of kernel methods with complementary operator-valued and product-space formulations. Across five families of parametric partial differential equations, the proposed methods achieve competitive or state-of-the-art predictive accuracy while reducing training and inference costs relative to neural operator architectures and deep learning based models, offering an efficient and lightweight alternative.

0.04

Learning under Target Shift: Optimal Density Ratio Estimation and Importance-Weighted Regression

cs.LG stat.ML ·2026-09-14 ·Ren-Rui Liu, Zheng-Chu Guo
similarity 0.63
Abstract

We study density ratio estimation and importance-weighted regression under target shift with continuous outputs. Under target shift, the conditional distribution of the inputs given the outputs remains invariant across the training and test distributions, while the output marginal distribution may change. Although this problem has been extensively studied for discrete outputs, the continuous setting is substantially less understood: the importance weights are determined by an unknown density ratio function, for which existing estimation methods lack explicit finite-sample convergence rates. We propose a spectral regularization method in a reproducing kernel Hilbert space (RKHS) for estimating the continuous density ratio from labeled training samples and unlabeled test inputs. Under a source condition with regularity parameter $ι>0$, we establish high-probability finite-sample guarantees and show that the estimator achieves the capacity-independent minimax-optimal RKHS-norm rate $O(n_η^{-ι/(2ι+2)})$. We then incorporate the estimated density ratio into importance-weighted regression and characterize the propagation of density-ratio estimation error to the final predictor. When sufficiently many samples are available for density ratio estimation, the resulting regression estimator attains the minimax-optimal rates of standard kernel regression. These results establish a finite-sample theory for continuous density ratio estimation and importance-weighted learning under target shift.

0.28

Random Projections for Spectral Algorithms: Optimal Rates in Sobolev Norms

cs.LG stat.ML ·2026-10-22 ·Caixing Wang, Yue Wang
similarity 0.62
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

Provably Efficient Representation Learning for Low-Rank CMDPs

cs.LG ·2026-11-05 ·Kaixuan Liu, Guojun Xiong, Shengpu Tang, Wanyun Si, Jian Li
theory similarity 0.62
Abstract

We study representation learning in low-rank Constrained Markov Decision Processes (CMDPs), where both value and reward functions are approximated by a set of unknown representation vectors, and the transition dynamics admit a low-rank factorization. The objective is to maximize expected cumulative rewards while complying with constraints on the expected cumulative utility. To achieve this, we propose \texttt{MFRLC} (Model-Free Representation Learning for Low-Rank CMDP), a model-free algorithm that uses a primal-dual scheme to effectively balance reward regret and constraint violations. To the best of our knowledge, \texttt{MFRLC} is the first representation-learning method for low-rank CMDPs that combines the Least-Squares Value Iteration with Upper Confidence Bound (LSVI-UCB) and primal-dual techniques. \texttt{MFRLC} further enhances value function estimation with bonuses for function approximation and learns the mapping from representations to value functions directly, avoiding explicit estimation of the transition kernel. We prove that, with high probability, \texttt{MFRLC} achieves $\widetilde O(K^{3/4})$ reward regret and cumulative constraint violation over $K$ deployment rounds, independent of the size of the state space. To our knowledge, these are the first sublinear regret and violation guarantees for CMDPs with unknown features.

0.16

Generalization Analysis of Distributed Kernel-based Robust Gradient Descent Algorithms

cs.LG stat.MLmath.OAmath.PR ·2026-09-10 ·Jun-Yi Meng, Zheng-Chu Guo, Yuan Mao
hot direction similarity 0.61
Abstract · 40 pages, 4 figures

In this paper, we investigate the generalization performance of distributed gradient descent algorithms in a reproducing kernel Hilbert space under a robust loss function $l_σ$. By exploiting the spectral characterization of gradient descent together with the intrinsic properties of robust loss functions, we establish optimal learning rates for the distributed kernel-based robust gradient descent (DKRGD) algorithm with an appropriately chosen scale parameter $σ$. The proposed parameter choice of $σ$ simultaneously alleviates the saturation phenomenon and guarantees statistical robustness. A key technical contribution is a novel error analysis that provides substantially sharper bounds for products of operators, thereby significantly relaxing existing restrictions on the maximum number of local machines while retaining optimal learning rates. Finally, we develop a communication-efficient strategy that further improves the convergence performance of DKRGD.

0.40

Fast Learning Rates for Physics-Informed Kernel Methods

cs.LG stat.ML ·2026-09-16 ·Luc Brogat-Motte, Joachim Bona-Pellissier, Giacomo Meanti, Lorenzo Rosasco
theory similarity 0.60
Abstract

In physics-informed machine learning, a target function $u^*$ is learned from noisy value observations $y_i=u^*(x_i)+ \varepsilon_i$, together with differential information, given either by noisy observations $d_j=(Du^*)(z_j)+ξ_j$ or by a known physical constraint $Du^*=v$. We consider the setting where $D$ is a linear differential operator and analyze a physics-informed kernel estimator $\hat u$ combining $n$ value observations and $m$ differential observations. In this context, we ask how much can differential information improve predictions, and how does this improvement depend quantitatively on $n$, $m$, and $D$. We prove finite-sample bounds, supported by numerical simulations, revealing a two-regime structure for the prediction error. When $m$ is limited, the rate depends jointly on $n$ and $m$; when $m$ exceeds a problem-dependent threshold, the rate saturates and matches the oracle rate obtained when the perfect constraint $D \hat u = Du^*$ is imposed. Examples are discussed for Sobolev spaces which are reproducing kernel Hilbert spaces and include partial Laplacian constraints on the torus and gradient observations on bounded domains. These examples illustrate the range of possible learning rate improvements --- from the standard nonparametric $n^{-1/4}$ to the parametric rate $n^{-1/2}$. Finally, we derive physically consistent rates in a stronger norm that jointly controls the errors in $\hat u$ and $D\hat u$.

0.54

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.60
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

Revisited Support Vector Machines: A Unified Joint Optimization Framework with Nyström Approximation for Scalable Adaptive Learning

cs.LG ·2026-10-11 ·Nassou Gongon Benjamin, Noulapeu Ngaffo, Patrick Njionou Sadjang
similarity 0.60
Abstract

The theoretical elegance of Support Vector Machines (SVMs), grounded in statistical learning theory, establishes them as a reference for robust classification. However, in the era of Big Data, classical SVMs face two major bottlenecks: the prohibitive cubic complexity $\mathcal{O}(N^3)$ of training and the rigidity of static kernels. Traditional methodologies treat kernel selection as a discrete, "brute-force" GridSearch problem, effectively decoupling the learning of data representation from the optimization of the decision boundary. This paper proposes a paradigm shift with a so-called "Revisited SVM", a unified framework that recasts the learning process as a continuous %bi-level joint optimization problem. We derive a novel objective function $J(α, θ)$ that allows for the simultaneous optimization of dual Lagrange multipliers and kernel hyper-parameters. To solve this challenging non-convex problem efficiently, we introduce a hybrid Block Coordinate Ascent (BCA) algorithm, tightly integrated with Nyström-based low-rank approximation, which drastically reduces computational complexity to $\mathcal{O}(Nm)$. Extensive experiments conducted across four heterogeneous domains (Bioinformatics, Finance, Cybersecurity, and Computer Vision) demonstrate that our approach not only matches but often exceeds exhaustive GridSearch accuracy, while delivering training speedups of up to 100x. Notably, on the complex NSL-KDD intrusion detection dataset, our adaptive kernel approach achieves 96.25\% accuracy compared to a mere 50\% for standard baselines, proving its unique ability to model complex non-linear manifolds in high-dimensional spaces. We validate our results using rigorous statistical tests and provide a theoretical convergence analysis of the proposed algorithm.

0.18