Machine Learning (Statistics)
On Finite-sample Concentration of Median of Incomplete U-Statistics
Nong Minh Hieu and Antoine Ledent
Median-of-means (MoM) is a powerful technique that theoretically enables near sub-Gaussian finite-sample rate for parameter estimation when the underlying data distribution is heavy-tailed (e.g., assumed to have only two first finite moments). A recent work has extrapolated this technique to median-of-randomized-U-Statistics (MoRU) and median-of-incomplete-U-Statistics (MoIU) for estimating expectations of heavy-tailed pairwise kernels. In \citet{pmlr-v97-clemencon19a}, a concentration rate that scales like $O(n^{-1/2})$ with sample size has been proven for MoRU. However, despite the computational advantage of the latter, the analysis of finite-sample bound for MoIU remains a significant theoretical challenge. As noted by the authors, a straightforward application of McDiarmid's inequality yields a loose bound of order $O(n^{-1/4})$. In this work, we prove a finite-sample concentration bound for the MoIU
estimator that scales as $O(n^{-1/2})$ with respect to the sample size using a delicate convex decomposition approach. Furthermore, we show that our proof can be seamlessly extended to
geometric median in multivariate settings. Using a Serfling-type argument, we extrapolate our results into a regime where data pairs are selected without replacement across blocks, breaking the usual block-wise independence condition. Then, using a Bernstein-type treatment for U-Statistics, we tighten the dependency of our bounds on the margin $\tau$ from $O(\tau^{-3/2})$ achieved in the previous work to $O(\tau^{-1})$. Finally, we proved anti-concentration results that is applicable for all median
estimators presented in this work to demonstrate that $M\le O(n)$ is an intrinsic restriction on block sizes.
Read the full abstract ▾
Machine Learning (Statistics)
Taming the Loss Landscape of PINNs with Noisy Feynman-Kac Supervision: Operator Preconditioning and Non-Asymptotic Error Bounds
Nathanael Tepakbong, Hanyu Hu, Chengyu Liu et al. (+1 more)
Physics-Informed Neural Networks (PINNs) often train slowly or fail to converge on challenging partial differential equations (PDEs), a behavior recently linked to severely ill-conditioned loss landscapes inherited from the underlying differential operator. We study PINNs augmented with a pointwise data-fidelity term, added at a few points in the domain to the standard residual and boundary losses. We show that this supervision term acts as an operator-level preconditioner: for suitable weights, our comparison bounds guarantee a substantially smaller condition number than under the standard PINN loss, independently of how the pointwise labels are obtained. For a broad class of PDEs admitting a Feynman-Kac (FK) representation, we generate such labels by Monte Carlo averages of the FK functional, resulting in what we call “FK-PINNs", and using the excess risk decomposition approach, we derive non-asymptotic $L^2(\Omega)$-error bounds for FK-PINNs with $\tanh$ activation trained by finitely many steps of gradient descent. Along the way, we establish pseudo-dimension bounds for first- and second-order derivatives of $\tanh$ neural networks, which are of independent interest and, to the best of our knowledge, new. Numerical experiments on Poisson, Schrödinger, mean exit time, and committor problems corroborate the theory, and show that FK-PINNs can successfully solve PDEs for which standard PINNs exhibit severe failure modes.
Read the full abstract ▾
All authors Nathanael Tepakbong, Hanyu Hu, Chengyu Liu, Xiang Zhou
Machine Learning (Statistics) · Cross-listed from cs.CV
A Systematic Benchmark of Intraoperative Ultrasound-to-MR Synthesis for Brain Tumour Surgery
Olga Esteban-Sinovas, Santiago Cepeda, Ignacio Arrese et al. (+1 more)
Intraoperative ultrasound (ioUS) is a versatile, cost-effective modality in
brain tumour surgery, but its interpretation is difficult: acquisition planes are non-standard, artefacts are modality-specific, and its appearance differs markedly from the preoperative MRI on which
surgical-planning tools,
segmentation models and the surgeon's experience rely. Synthesising MRI-like images from ioUS could let this MRI-based infrastructure be reused intraoperatively without an extra scan. Most prior work evaluates a single architecture in isolation; to our knowledge, no
benchmark has spanned architectural paradigms, inference regimes and downstream-task endpoints under a common protocol. We address this gap on the public ReMIND data set (76 patients; 153 paired ioUS/T2w and 104 paired ioUS/FLAIR studies; 60/16 patient-level train/held-out split). Six generators (four GAN baselines: Pix2Pix, SwinPix2Pix, CycleGAN, CUT; the
transformer-augmented ResViT; and the few-step
diffusion model SynDiff) were each trained under four inference regimes (2D, 2.5D, 2D + 3D-refinement, full-3D) and two targets (T2w only; T2w + FLAIR multi-task), yielding 48 experiments. Image-fidelity metrics (SSIM, PSNR, MAE, LPIPS) were complemented by an nnU-Net v2 downstream
segmentation evaluation (tumour and resection cavity) and by subgroup analyses by histological grade and reoperation. No architecture dominated every axis, and, critically, perceptual quality tracked downstream utility most closely (LPIPS, r=-0.66, p<0.001), whereas higher SSIM was associated with worse utility (r=-0.64, p<0.001); SynDiff-2.5D best preserved downstream
segmentation (U_Dice=0.55). Perceptual and downstream-task metrics should therefore be reported alongside or in preference to global SSIM, and architecture choice conditioned on
surgical phase, patient history and clinical objective.
Read the full abstract ▾
All authors Olga Esteban-Sinovas, Santiago Cepeda, Ignacio Arrese, Rosario Sarabia
Machine Learning (Statistics) · Cross-listed from cs.LG
Looped Transformers with Layer Normalization Provably Learn the Power Method
Lyumin Wu, Chenyang Zhang and Yuan Cao
Transformers have achieved remarkable success across a wide range of applications, and a growing body of work suggests that part of their strength comes from their ability to learn and execute algorithmic procedures. However, our understanding of how
transformers learn such
algorithms remains limited, especially in the presence of layer normalization (LN). In this work, we study principal component prediction as a concrete testbed for understanding the training dynamics of
transformers with LN. We prove that a looped linear
transformer with LN, trained by gradient descent, converges to a solution that implements the power method, with each self-
attention layer performing one power iteration. Notably, the model is trained only for principal component prediction, rather than being explicitly supervised to implement the power method. Our finding thus reveals an "algorithmic implicit bias" of looped
transformers with LN: principal-component prediction can in principle be achieved by many mechanisms, yet gradient descent selects one that realizes the power method. We further provide a concrete comparison between
transformers with and without LN: even with layerwise guidance from power iterations, a
transformer without LN cannot exactly learn the power method, whereas the corresponding
transformer with LN can, leading to a provable performance gap in principal component prediction. Our results provide, to our knowledge, the first theoretical analysis of the training dynamics of looped and single-layer
transformers with LN, and shed light on the role of LN in
transformer models.
Read the full abstract ▾
Machine Learning (Statistics)
Spectra-Guided Neural Tucker Factorization
Fusheng Wang and Yikai Hou
This paper proposes Spectra-Guided Neural Tucker Factorization (SG-NTF) for High-Dimensional and Incomplete (HDI) tensor completion. Circumventing discrete representational limits, SG-NTF maps scalar timestamps into a continuous spectral space to abstract temporal periodicities. Concurrently, a Spatio-Temporal Co-Gating (STCG) mechanism explicitly filters latent interactions via multiplicative modulation on spatiotemporal contexts. Evaluations on real-world HDI tensors verify that SG-NTF maintains competitive completion accuracy with parameter efficiency.
Read the full abstract ▾
Statistical Methodology
When Do Generalized Permutation Tests Achieve Optimal Power? A Dispersion Characterization
Yongmin Kim and Ilmun Kim
We study generalized Monte Carlo permutation tests under a non-uniform distribution on permutations. Focusing on the difference-in-means statistic, we introduce two scalar dispersion measures that quantify departures from complete randomization at the individual and pairwise levels. We show that if both dispersions vanish asymptotically, then the conditional permutation distribution converges to its Gaussian
benchmark, the critical value stabilizes, and the test attains optimal Pitman local power. Conversely, if these dispersions fail to vanish, the permutation distribution does not self-average, the critical value need not stabilize, and optimal local power cannot in general be guaranteed. We further show that beyond the standard Pitman local model, suitably chosen non-uniform permutation distributions can strictly dominate the uniform distribution by exploiting nuisance structure in the data.
Read the full abstract ▾
Machine Learning (Statistics) · Cross-listed from cs.LG
A Practical Upper Bound on Selection Bias Effects in Medical Prediction Models
Kara Liu, Maggie Wang and Russ B. Altman
Selection bias is a common and often unavoidable aspect of real-world data that challenges the generalizability of machine learning models. When models trained on biased data are deployed in the broader target population, poor model generalization may lead to real harm, particularly in high-risk settings such as healthcare. This risk highlights the need for practitioners to reliably assess model generalizability prior to deployment. However, existing methods for predicting model performance rely on unrealistic access to the target distribution or knowledge of the selection mechanism causing bias. To address these limitations, we propose a novel upper bound on the worst-case model performance on the target population under the realistic setting where the selection mechanism and the target population data are only partially observed. We demonstrate the validity and practical utility of our method through experiments on fully synthetic data, semi-synthetic data derived from the All of Us Research Program, and real-world selection bias in MIMIC-IV. Our work offers a principled and practical tool to estimate the impact of selection bias in an otherwise intractable setting, thereby enabling practitioners to build safer and more generalizable models in healthcare and beyond.
Read the full abstract ▾
Machine Learning (Statistics) · Cross-listed from cs.LG
GNMR: Runtime Stability Control for Low-Precision Large Language Model Training
Boao Kong, Weichen Jia, Engao Zhang et al. (+6 more)
Training stability is a key bottleneck in low-precision
language model training: efficient low-cost paths can still produce short-lived numerical risks at a small set of operators. We formulate this as runtime stability control and present Gradient Norm-to-Mean Ratio (GNMR), a lightweight controller that compares each recoverable unit's current gradient norm with its historical mean. Together with $\Delta$-GNMR for abrupt short-window increases, GNMR maps local risk signals to bounded recovery actions under a hard $\mathrm{maxO}$ budget and a short lock interval, without changing the numerical format, kernel, or backend recipe. Across activation-quantization stress, DeepSeek-style recipe-level training, and LLaMA-2 13B fine-tuning, GNMR preserves high-fidelity quality with sparse, budgeted recovery. These results support GNMR as a backend-agnostic controller to improve low-precision training stability while preserving low-cost execution.
Read the full abstract ▾
All authors Boao Kong, Weichen Jia, Engao Zhang, Guohong Li, Yonghan Dong, Yao Wang, Yaoyuan Wang, Yunke Peng, Kun Yuan
Machine Learning (Statistics) · Cross-listed from math.OC
In-Expectation Convergence of Stochastic Gradient Methods under Heavy-Tailed Noise
Zijian Liu
Many
stochastic gradient methods are believed not to converge when the noise in
stochastic gradients has only a finite $p$-th moment for $p\in\left(1,2\right)$, a setting known as the heavy-tailed noise assumption. However, some recent studies have found that
Stochastic Gradient Descent ($\textsf{SGD}$), without any modification to its update rule, can surprisingly converge in expectation for convex problems with bounded domains, highlighting the potential of classical
stochastic gradient methods. Inspired by this recent progress, we provide a comprehensive study of
stochastic optimization under heavy-tailed noise and establish new in-expectation convergence results for
Stochastic Mirror Descent ($\textsf{SMD}$) and Accelerated
Stochastic Mirror Descent ($\textsf{ASMD}$) in convex optimization, and for $\textsf{SGD}$ and
Stochastic Gradient Descent with Momentum ($\textsf{SGDM}$) in nonconvex optimization. Notably, our results not only hold without algorithmic changes but also avoid restrictive assumptions, such as bounded domains, imposed in prior work. More importantly, our analysis provides a new, elegant, and powerful framework for studying heavy-tailed
stochastic optimization, opening a new route to understanding first-order
stochastic gradient methods.
Read the full abstract ▾
Machine Learning (Statistics) · Cross-listed from cs.LG
Semi-Supervised Learning with Noisy Proxy Covariates: Generalization Bounds and Distribution Regression
Kwangho Kim and Jisu Kim
In many modern machine learning pipelines, abundant pretrained representations serve as noisy proxy
covariates, while task-specific labels remain scarce. We study semi-supervised regression in this setting, and propose a simple two stage
estimator that learns kernel eigenfeatures from all proxy
covariates and fits a ridge predictor on labeled data. We derive finite sample bounds showing that fast labeled sample rates are recovered when proxy perturbation is controlled and unlabeled proxy
covariates are sufficiently abundant. We also show that distribution regression is a direct special case, with analogous guarantees when the finite bag size is large enough. Experiments show consistent gains over supervised and semi-supervised baselines, especially in low label regimes.
Read the full abstract ▾
Statistics Theory · Cross-listed from cs.DS
Easy, robust approximate message passing for planted spike models
Misha Ivkov and Tselil Schramm
We present a simple and efficient
algorithm for robust approximate message passing (AMP) in the spiked
matrix setting. In particular, let $\varepsilon$ be a sufficiently small constant, and suppose that $X \in \mathbb R^{n \times n}$ is a Gaussian
matrix with a planted rank-$1$ spike, and $E \in \mathbb R^{n \times n}$ is an adversarially chosen
matrix supported on an $\varepsilon n \times \varepsilon n$ principal minor. Let $v_{\mathrm{AMP}}(X)$ be the output of an AMP iteration on the uncorrupted
matrix $X$. We give a procedure that, given access only to the corrupted
matrix $Y = X + E$, computes a vector $v_{\mathrm{ALG}}(Y)$ which is $\tilde{O}(\sqrt{\varepsilon})$-close to $v_{\mathrm{AMP}}(X)$, for any of a class of AMP iterations which includes sparse Principal Component Analysis (PCA), non-negative PCA, and $\mathbb Z_2$ synchronization. Our
algorithm consists of a spectral pre-processing step combined with a robust spectral initialization procedure; given these inputs, we prove that (perhaps surprisingly) AMP is robust out-of-the-box.
Read the full abstract ▾
Statistics Applications · Cross-listed from cs.CR
Stochastic Analysis of Cybersecurity Defense Strategies Under Single Attack Scenario
Song-Kyoo Kim
This research presents a novel
stochastic framework for proactive cybersecurity defense timing under a single attack scenario. The approach models the defense process as a continuous observation mechanism in which the defense instant and the subsequent observation slot follow independent exponential distributions. Laplace-Carson transforms combined with first-excess theory yield the joint detection function that brackets the attack moment. Marginalization under Markovian Poisson arrivals then produces the probability density of the defense moment and conditional expectations of pre-attack and post-attack observation times. These closed-form results enable quantitative assessment of defense timing sensitivity to threat intensity and support precise calibration of observation parameters for low-latency proactive measures. Major contributions include the explicit derivation of marginal distributions and expected values, visualization of defense moment density, and the bridging of
stochastic duel methodology with practical cybersecurity applications.
Read the full abstract ▾
Machine Learning (Statistics) · Cross-listed from math.DS
Continuous Data Assimilation with Learned Surrogate Dynamics
Wenwen Li and Daniel Sanz-Alonso
Continuous data assimilation seeks to estimate the state of a dynamical system from partial observations. In many applications, however, the state dynamics are unknown or prohibitively expensive to simulate at the required resolution, leading to model error. Motivated by this challenge and the increasing adoption of machine learning surrogates in data assimilation, this paper develops a unified finite-dimensional analysis of nudging
algorithms that employ learned surrogate models of the dynamics. We first establish general conditions on the dynamics and observations that guarantee accurate tracking for nudging with the true dynamics model, both in the noise-free and noisy settings. We then show that nudging
algorithms that employ surrogate models retain exponential convergence up to an explicit error floor that quantifies the effects of surrogate approximation error and observation noise. Finally, we analyze surrogate models obtained by learning either the vector field or the short-time solution map of the system, and quantify the amount of training data needed to ensure accurate nudging in the noise-free setting. Numerical experiments support the theory.
Read the full abstract ▾
Statistics Theory
Online Sparse Regression with Expanding Observables
Ying Yang and Fang Yao
Online high-dimensional regression has gained increasing
attention in recent years, yet existing methods typically assume that all candidate features, including important ones, are observed from the outset of data collection. This assumption is often violated in real-world scenarios, where new variables become available gradually as data accumulate. To address this gap, we introduce a novel framework, Recurrent Adaptive Variable Selection (RAVAS), for online regression with expanding observability. RAVAS employs a recurrent procedure that dynamically updates feature selection as both the sample size and the observable feature set grow. The
algorithm is designed to be computationally efficient and
memory-light, relying only on low-dimensional sufficient statistics that are updated online. A key advantage of the method lies in its ability to detect and incorporate important variables that emerge later, thereby mitigating the effect of early-stage missingness. We establish theoretical guarantees on model selection, estimation error, and feature coverage, and develop an adaptive online tuning strategy. Extensive simulations and real-world experiments verify the effectiveness of RAVAS for high-dimensional streaming data.
Read the full abstract ▾
Machine Learning (Statistics) · Cross-listed from math.OC
Constructive interpolation and generalization rates for neural ODEs: a control perspective
Antonio Álvarez-López, Lorenzo Liverani and Enrique Zuazua
We study supervised regression with neural ODEs (NODEs) from a control-theoretic perspective to derive explicit population-risk bounds. We focus on a widely used class of non-autonomous models with constant parameters and explicit time dependence, which we call semi-autonomous NODEs (SA-NODEs). We constructively prove that SA-NODEs are capable of exact interpolation of admissible finite
datasets, and even satisfy a stronger property that we call simultaneous
cell controllability (SCC): their flows can map prescribed disjoint
cells into arbitrarily small target balls. This property is the mechanism that upgrades interpolation into quantitative generalization, by allowing SA-NODEs to emulate piecewise-constant nonparametric
estimators. Consequently, our risk bounds recover the rates of histogram and nearest-neighbor
estimators, provided the network width satisfies a conservative scaling with the sample size. Numerical experiments show that trained SA-NODEs achieve competitive – often lower – test errors than these baselines. Finally, we show that the explicit time dependence is essential. Although two-layer autonomous NODEs can interpolate geometrically nondegenerate
datasets, structural obstructions prevent them from achieving SCC. These limitations, further confirmed numerically, support the view that SA-NODEs provide a minimal effective architecture for learning.
Read the full abstract ▾
Machine Learning (Statistics) · Cross-listed from cs.CL
On the Limits of LLM Adaptability: Impact of Model-Internalized Priors on Annotation Task Performance
Etienne Casanova, Rafal Kocielnik and R. Michael Alvarez
Large
Language Models (LLMs) are increasingly used for zero-shot annotation and LLM-as-a-judge tasks, yet their reliability hinges on how model-internalized priors interact with user-provided instructions. We investigate three dimensions of this interaction: (1) how an LLM's familiarity with data and task definitions relates to performance, (2) whether additional information in
prompts can correct zero-shot errors ("decision stickiness"), and (3) model susceptibility to misaligned task definitions. We introduce Definition-Specific Familiarity (DSF), which measures
alignment between a model's elicited concept and the target definition. Across nine LLMs and six toxicity
datasets (five primary
datasets plus an additional robustness
dataset), DSF predicts annotation performance after controlling for
dataset identity (partial $r=+0.41$). This association remains positive across all prompting conditions tested. In contrast, three common text-memorization metrics show no positive association. We show that prompting has limited corrective power: only 34.8% of zero-shot errors are corrected by additional instructions or examples, with high-confidence errors especially persistent. Misaligned definitions systematically shift predictions without reducing reported confidence, making confidence unreliable for detecting definition-policy mismatch. Together, these findings establish definition
alignment as a practical model-selection criterion and show that better prompting alone cannot substitute for validating model-policy fit.
Read the full abstract ▾
Other Statistics
Extrinsic Analysis on BHV4
Tingan Chen, Garett Ordway and Vic Patrangenaru
One investigates the extrinsic statistical analysis on the space of Billera- Holmes-Vogtmann tree space with four leaves (T4 or BHV4) based on its recently proposed novel representation (see [1])- the Spiky Projective ExcavatedDodecahedron (SPED). Due to the
symmetry of the SPED, the Veronese- Whitney (VW) embeddingwe consider here produces a natural extrinsicmetric for a statistical analysis on BHV4. one derives the exact solution for the VW extrinsic mean and applies this novel method on a yeast genome
dataset to study the phylogenetic trees of four distinct yeast clades.
Read the full abstract ▾
Machine Learning (Statistics) · Cross-listed from cs.LG
Exploiting weight-space symmetries for approximating curvature
Artem Artemev, Rui Xia, Benjamin M. Boyd et al. (+4 more)
Many machine learning techniques rely on approximating a loss function's
curvature, but this is notoriously hard to do at the scale of modern deep networks. Surprisingly, no previous work has exploited the
curvature constraints that arise from well known weight-space
symmetries in loss landscapes. By analytically averaging over group actions that leave the loss invariant, we construct structured Hessian approximations from single gradients that can be tractably estimated, stored, and inverted. The choice of user-specified
symmetry group directly governs the trade-off between approximation accuracy and computational cost. Moreover, our framework provides a unifying theoretical lens for viewing existing methods; in particular, a specific choice of
symmetry group recovers Shampoo/
Muon-like
curvature estimates. We validate our method on a range of network architectures, and deploy it to second-order optimization
benchmarks, including a small
language model. Our
curvature estimation framework might find applications in other machine learning problems such as uncertainty estimation, continual learning, compression/
pruning, training data attribution, and more.
Read the full abstract ▾
All authors Artem Artemev, Rui Xia, Benjamin M. Boyd, Youjing Yu, Felix Dangel, Guillaume Hennequin, Alberto Bernacchia