论文检索

Theory · Learning Theory

Ruoxin Yuan, Lijun Ding

Exact sparse methods based on $\ell_0$ constraints are increasingly used for interpretable and scalable time series modeling, where one aims to recover a small set of informative lags/factors while maintaining strong predictive performance and low computational cost. Despite their empirical success, finite-sample and computational guarantees for such methods under temporal dependence remain limited. In this paper, we study $\ell_0$-constrained least squares for time series generated by $\alpha$-mixing stationary Gaussian processes with sparse coefficients. We establish high-probability restricted strong convexity/smoothness (RSC/RSS) for the empirical quadratic loss. Leveraging these conditions, we derive nonasymptotic statistical guarantees and computational complexities for a series of exact sparse methods, including iterative hard thresholding (IHT). We apply our theoretical results to Gaussian vector autoregressive (VAR) models and obtain new guarantees. Experiments on synthetic sparse VAR models and real-world mobility time series demonstrate that exact sparse methods recover lag structure more accurately and interpretably than some classical methods, while achieving comparable prediction error with substantially lower computational cost.

Deep Learning · Theory

Fabiola Ricci, Claudia Merger, Sebastian Goldt

Neural networks trained with gradient-based methods exhibit a strong simplicity bias, learning simpler statistical features of their data before moving to more complex features. In this work, we study this bias from a Fourier perspective, motivated by the approximate translation-invariance and the characteristic power spectra of natural images. We first show experimentally that simple neural networks trained on image classification tasks first rely on amplitude information -- related to pair-wise correlations between pixels -- before exploiting phase information, which encodes edges and higher-order correlations. To explain this phenomenon, we introduce a synthetic data model for translation-invariant inputs that allows precise control over the amplitudes and phases while remaining tractable. We rigorously establish that for isotropic and high-dimensional inputs, classifying them by relying only phase information is a genuinely hard task: online stochastic gradient descent cannot distinguish the structured inputs from noise within $n \ll N^3$ steps, but needs at least $n \gg N^3 \log^2{N}$ steps. In contrast, we prove that for non-isotropic inputs with power-law spectra, the existence of a dominant principal subspace can dramatically accelerate the speed of learning, even if the Fourier amplitudes are shared among classes and do not help with classification. Simulations with two-layer networks trained on textures, and with deep convolutional networks on ImageNet confirm this non-trivial interaction between amplitudes and phases, providing mechanistic insight into how deep neural networks can learn natural image distributions efficiently.

Deep Learning · Large Language Models

Guanning Zeng, Zhaoyi Zhou, Daman Arora, Andrea Zanette

Reinforcement Learning with Verifiable Rewards (RLVR) has emerged as a powerful paradigm for post-training large reasoning models (LRMs) using policy-gradient methods such as GRPO. To stabilize training, these methods typically center trajectory rewards by subtracting the empirical mean for each prompt. Statistically, this centering acts as a control variate (or baseline), reducing the variance of the policy-gradient estimator. Typically, the mean reward is estimated using per-prompt empirical averages for each prompt in a batch. Drawing inspiration from Stein’s paradox, we propose using \emph{shrinkage estimators} that combine \emph{per-prompt} and \emph{across-prompt} means to improve the overall per-prompt mean estimation accuracy---particularly in the low-generation regime typical of RLVR. Theoretically, we construct a shrinkage-based baseline that provably yields lower-variance policy-gradient estimators across algorithms. Our proposed baseline serves as a drop-in replacement for existing per-prompt mean baselines, requiring no additional hyper-parameters or computation. Empirically, shrinkage baselines consistently outperform standard empirical-mean baselines, leading to lower-variance gradient updates and improved training stability.

Deep Learning · Large Language Models

Shengxuan Qiu, Haochen Huang, Shuzhang Zhong, Pengfei Zuo, Meng Li

Scaling test-time compute with multi-path chain-of-thought can improve reasoning accuracy, but its gains hinge on an effective exploration–exploitation trade-off. Existing methods handle this trade-off in rigid ways: tree-structured search hard-codes exploration via brittle expansion rules that disrupt post-trained reasoning, while parallel reasoning over-explores redundant hypothesis paths and relies on a weak answer selection strategy. Driven by the insight that the optimal balance is *phase-dependent* and that correct vs. incorrect paths often *diverge only at late stages*, we reconceptualize test-time scaling as a dynamic *expand–reduce* control problem over a pool of hypothesis paths. We introduce **HyPER**, a *training-free online control policy* for MoE multi-path decoding that reallocates compute under a fixed budget using lightweight path statistics. HyPER features (i) an *online controller* that shifts from exploration to exploitation as the hypothesis pool evolves, (ii) an MoE-based token-level refinement primitive for efficient *generation-time exploitation* without full-path resampling, and (iii) a length- and confidence-aware aggregation rule to bridge the existence–selection gap for reliable *answer-time exploitation*. Extensive experimental results across four MoE models and diverse benchmarks demonstrate HyPER consistently achieves the accuracy–compute Pareto frontier, outperforming prior-art methods by 8-10% while reducing token consumption by 25-40%.

Probabilistic Methods · Monte Carlo and Sampling Methods

Jakob Robnik, Reuben Cohn-Gordon, Uros Seljak

Hamiltonian Monte Carlo and underdamped Langevin Monte Carlo are state-of-the-art methods for taking samples from high-dimensional distributions with a differentiable density function. To generate samples, they numerically integrate Hamiltonian or Langevin dynamics. This numerical integration introduces an asymptotic bias in Monte Carlo estimators of expectation values, which can be eliminated by adjusting the dynamics with a Metropolis-Hastings (MH) proposal step. Alternatively, one can trade bias for variance by avoiding MH, and select an integration step size that ensures sufficiently small asymptotic bias, relative to the variance inherent in a finite set of samples. Such \emph{unadjusted} methods often significantly outperform their adjusted counterparts in high-dimensional problems where sampling would otherwise be prohibitively expensive, yet are rarely used in statistical applications due to the absence of an automated way of choosing a step size. We propose just such an automatic tuning scheme that takes a user-provided asymptotic bias tolerance and selects a step size that ensures it. The key to the method is a relationship we establish between the energy change during integration and the asymptotic bias. We show that this procedure rigorously bounds the asymptotic bias for Gaussian target distributions. We then numerically show that the procedure works beyond Gaussians. To demonstrate the practicality of the proposed scheme, we provide a comprehensive comparison of adjusted and unadjusted samplers on Bayesian inference problems and on a statistical physics model in more than one million parameters. With our tuning scheme, the unadjusted methods achieve close to optimal performance, significantly and consistently outperforming their adjusted counterparts.

Deep Learning · Large Language Models

Jiaming Yang, Chenwei Tang, Liangli Zhen, Jiancheng Lv

Key–value (KV) caching is essential for large language model inference, yet its memory overhead poses a critical bottleneck for long-context generation. Existing eviction policies predominantly rely on empirical heuristics, lacking a rigorous theoretical foundation. This work rethinks KV cache eviction through the lens of the Information Bottleneck principle. Under a linear–Gaussian surrogate of attention, we derive a closed-form mutual information objective that characterizes the effective information capacity of a retained KV cache subset. This formulation reveals that a wide range of existing eviction strategies can be interpreted as different approximations of the same capacity-maximization principle. Guided by this insight, we introduce CapKV, a capacity-aware eviction method that directly targets information preservation via a log-determinant approximation using statistical leverage scores. This approach replaces heuristic selection with a theoretically grounded mechanism that preserves the maximum predictive signal. Extensive experiments across multiple models and long-context benchmarks show that CapKV consistently outperforms prior methods, achieving a better trade-off between memory efficiency and generational fidelity.

Probabilistic Methods · Structure Learning

Hannah Sansford, Nick Whiteley, Patrick Rubin-Delanchy

High-dimensionality of data is often regarded as a fundamental statistical impediment in Machine Learning and AI. The purpose of this paper is to clarify, on the contrary, when and how high-dimensionality may be beneficial. In the setting of a general random function model of data we delineate between three notions of dimensionality: *effective dimension* $p_{\mathrm{eff}}$, measuring total variability across feature directions; *correlation rank* $r$, measuring functional complexity across samples; and *latent intrinsic dimension* $d$ of manifold structure hidden in data. Via a generalized Hanson-Wright inequality, we show that increasing $p_{\mathrm{eff}}$ drives a *blessing of dimensionality* phenomenon, whereby data dot-products concentrate about their expectations. In turn, we show that, under mild continuity assumptions (ensuring that features bring additional information as dimension grows), persistence diagrams recover latent homology when $p_{\mathrm{eff}} \in \omega (\log n)$ as $n\to\infty$. Informed by our theory, we revisit the ground-breaking neuroscience discovery of toroidal structure in grid-cell activity made by Gardner et al. (2022): our findings provide the first empirical evidence that this structure is *isometric* to a flat torus model of physical space, suggesting that grid cell activity conveys a geometrically faithful representation of the real world.

General Machine Learning · Methodology

Hanyang Jiang, Yao Xie

Reliable uncertainty quantification at unobserved spatial locations is a key challenge in spatial statistics, particularly for complex and heterogeneous datasets. While traditional methods such as Kriging rely on strong distributional assumptions, conformal prediction (CP) offers a distribution-free alternative. However, although non-i.i.d. CP theory is well established for time-series data, a significant gap remains for spatial data, where the lack of a natural ordering and discrete index complicates theoretical guarantees. Existing CP theory for spatial data often relies on exchangeability. We propose Localized Spatial Conformal Prediction (LSCP), a model-agnostic framework that bridges this gap by coupling local quantile regression with conformal calibration. LSCP conditions on spatial neighborhoods to capture local heterogeneity. We show that LSCP retains finite-sample marginal coverage under spatial exchangeability and attains asymptotic conditional coverage under stationarity and spatial mixing. Across synthetic and real datasets, LSCP consistently achieves near-nominal coverage with tighter and more stable prediction intervals than existing methods that fail to capture these spatial dependencies.

General Machine Learning · Scalable Algorithms

Khai Nguyen

Sliced optimal transport (SOT), or sliced Wasserstein (SW) distance, is widely recognized for its statistical and computational scalability. In this work, we further enhance computational scalability by proposing the first method for estimating SW from sample streams, called streaming sliced Wasserstein (Stream-SW). To define Stream-SW, we first introduce a streaming estimator of the one-dimensional Wasserstein distance (1DW). Since the 1DW has a closed-form expression, given by the absolute difference between the quantile functions of the compared distributions, we leverage quantile approximation techniques for sample streams to define a streaming 1DW estimator. By applying the streaming 1DW to all projections, we obtain Stream-SW. The key advantage of Stream-SW is its low memory complexity while providing theoretical guarantees on the approximation error. We demonstrate that Stream-SW achieves a more accurate approximation of SW than random subsampling, with lower memory consumption, when comparing Gaussian distributions and mixtures of Gaussians from streaming samples. Additionally, we conduct experiments on point cloud classification, point cloud gradient flows, and streaming change point detection to further highlight the favorable performance of the proposed Stream-SW.

Deep Learning · Large Language Models

Jiangrui Zhao, Xiaoting Du

Large Language Models demonstrate remarkable syntactic fluency, yet the optimization dynamics governing their acquisition of deep semantic dependencies remain poorly understood. We propose a mechanistic framework that models this learning process as a competition between Surface Statistics and Deep Semantics. Our theoretical analysis identifies a ``Gradient Starvation" phenomenon where the error signals for sparse semantic dependencies are actively suppressed during early optimization. This suppression impedes the learning of structural reasoning and causes its emergence to manifest as a sudden phase transition. Furthermore, this framework offers a mechanistic basis for the effectiveness of Chain-of-Thought (CoT) strategies. By externalizing intermediate reasoning steps into concrete tokens, CoT effectively bypasses the suppression regime inherent to implicit reasoning. We validate these findings across scales ranging from toy transformers to production models (Llama-3.1-8B, Qwen2.5-Coder-7B). Finally, guided by this theory, we propose a topology-aligned contrastive objective that explicitly rectifies the gradient geometry. Experiments on variable binding tasks demonstrate that our method achieves an improvement that is over 2× larger than that obtained via standard cross-entropy fine-tuning.

Deep Learning · Theory

Florian Handke, Dejan Stancevic, Felix Koulischer, Thomas Demeester, Luca Ambrogioni

Diffusion models do not recover semantic structure uniformly over time. Instead, samples transition from semantic ambiguity to class commitment within a narrow regime. Recent theoretical work attributes this transition to dynamical instabilities along class-separating directions, but practical methods to detect and exploit these windows in trained models are still limited. We show that tracking the class-conditional entropy of a latent semantic variable given the noisy state provides a reliable signature of these transition regimes. By restricting the entropy to semantic partitions, the entropy can furthermore resolve semantic decisions at different levels of abstraction. We analyze this behavior in high-dimensional Gaussian mixture models and show that the entropy rate concentrates on the same logarithmic time scale as the speciation symmetry-breaking instability previously identified in variance-preserving diffusion. We validate our method on EDM2-XS and Stable Diffusion 1.5, where class-conditional entropy consistently isolates the noise regimes critical for semantic structure formation. Finally, we use our framework to quantify how guidance redistributes semantic information over time. Together, these results connect information-theoretic and statistical physics perspectives on diffusion and provide a principled basis for time-localized control.

General Machine Learning · Transfer, Multitask and Meta-learning

Yavuz Yarici, Ghassan AlRegib

Deploying multimodal models in real-world scenarios requires generalization to new environments where recording conditions differ from training, a challenge known as multimodal domain generalization (MMDG). Standard architectures employ separate encoders for each modality and a fusion module, training the system end-to-end by optimizing on the fused features. In this paper, we identify that such joint optimization causes encoders to exploit cross-modal co-occurrences, statistical relationships between modalities that arise from source-specific recording conditions, rather than learning domain-invariant features. We term this failure mode Fusion Overfitting. To address this, we propose Modality-Entropy Regularization for Domain Generalization (MER-DG), which maximizes the entropy of each encoder's feature distribution to preserve feature diversity. MER-DG is architecture-agnostic and integrates into existing multimodal frameworks as an additive loss term. Extensive experiments on EPIC-Kitchens and HAC benchmarks demonstrate average improvements of ${\sim}5\%$ over standard fusion and ${\sim}2\%$ over state-of-the-art methods.

Probabilistic Methods · Monte Carlo and Sampling Methods

Weihang Xu, Huajie Qian, Wotao Yin, Xinshang Wang

We study simultaneous confidence bounds for aggregated effects over downward-closed subset families of independent statistical tests. The bounds are obtained by bootstrap calibration of the maximum normalized aggregated effect over the relevant subset family, yielding valid post-hoc inference for data-selected subsets and tighter bounds than classical methods that protect all linear contrasts. A central challenge is that the required maximization is a nonlinear combinatorial optimization problem whose exact solution is essential for correct coverage. We address this challenge by casting the problem as a densest subgraph optimization and reformulating it as a linear program, or as a mixed-integer linear program when downward-closed linear constraints are imposed, enabling efficient and exact evaluation. We further characterize the growth regime of the number of tests for which the bootstrap calibration remains valid and illustrate the method on several machine learning applications.

Probabilistic Methods · Spectral Methods

Jian-Feng Cai, Zhuozhi XIAN, Jiaxi Ying

We study the sparse spiked Wigner model, where the goal is to recover an $s$-sparse unit vector $\symbfit{u} \in \mathbb{R}^d$ from a noisy observation $\symbfit{Y} = \beta \symbfit{u} \symbfit{u}^\top + \symbfit{W}$. While the information-theoretic threshold is $\beta = \widetilde{\Omega}(\sqrt{s})$, existing polynomial-time algorithms require $\beta = \widetilde{\Omega}(s)$, yielding a substantial computational-statistical gap. We propose a column thresholding method that attains the $\widetilde{\Omega}(\sqrt{s})$ scaling for both estimation and support recovery under the non-uniformity condition $|| \symbfit{u} ||_\infty = \Omega(1)$. This condition is not merely technical: it explicitly rules out uniform spikes, for which planted-clique-based hardness results apply, and identifies a concrete class of non-uniform spikes where the gap can be closed. Building on this initializer, we further develop a truncated power method that iteratively refines the estimate with provable linear convergence.

Social Aspects · Accountability, Transparency, and Interpretability

Shuhang Lin, Chuhao Zhou, Xiao Lin, Zihan Dong, Kuan Lu, Zhencan Peng, Jie Yin, Dimitris Metaxas

While Conformal Prediction (CP) offers a principled framework for producing prediction sets with statistical guarantees, prior methods suffer from critical limitations in both calibration validity and score discriminability, resulting in violated coverage guarantees and excessively large prediction sets. To address these pitfalls, we propose Conformal Path Reasoning (CPR), a trustworthy KGQA framework with two key innovations. First, we perform query-level conformal calibration over path-level scores, preserving the exchangeability while generating path prediction sets. Second, we introduce the Residual Conformal Value Network (RCVNet), a lightweight module trained via PUCT-guided exploration to learn discriminative path-level nonconformity scores. Experiments on benchmarks show that CPR significantly improves the Empirical Coverage Rate by 34% while reducing average prediction set size by 40% compared to conformal baselines. These results validate the efficacy of CPR in satisfying coverage guarantees with substantially more compact answer sets.

Probabilistic Methods · Bayesian Models and Methods

Tom Sprunck, Marcelo Pereyra, Tobías Liaudat

Modern imaging techniques heavily rely on Bayesian statistical models to address difficult image reconstruction and restoration tasks. This paper addresses the objective evaluation of such models in settings where ground truth is unavailable, with a focus on model selection and misspecification diagnosis. Existing unsupervised model evaluation methods are often unsuitable for computational imaging due to their high computational cost and incompatibility with modern image priors defined implicitly via machine learning models. We herein propose a general methodology for unsupervised model selection and misspecification detection in Bayesian imaging sciences, based on a novel combination of Bayesian cross-validation and data fission, a randomized measurement splitting technique. The approach is compatible with any Bayesian imaging sampler, including diffusion and plug-and-play samplers. We demonstrate the methodology through experiments involving various scoring rules and types of model misspecification, where we achieve excellent selection and detection accuracy with a low computational cost.

Deep Learning · Graph Neural Networks

Simon Forbat, Rainer Gemulla

Mixup is a widely used data augmentation technique that constructs new training examples by interpolating between existing ones. While simple and effective in domains like vision and language, applying mixup to graph data is non-trivial and there is no independent empirical evidence for its effectiveness. To fill this gap, we conducted an extensive evaluation study following a unified, established evaluation protocol for graph classification. In contrast to prior results, we found that none of the state-of-the-art mixup methods yielded statistically significant improvements over the no-mixup baseline. To obtain further insights, we analyzed the graphs generated from these mixup methods from an interpolation perspective. We found that (i) many mixup methods failed to interpolate well, (ii) high interpolation error led to performance degradation, and (iii) even good interpolation properties did not lead to performance improvements. Our findings question the efficacy of existing graph mixup methods and highlight the need for a more rigorous exploration and evaluation.

Applications · Time Series

Daniel Durstewitz, Christoph Jürgen Hemmer, Florian Hess, Charlotte Ricarda Doll, Lukas Eisenmann

Time series (TS) modeling has come a long way from early statistical, mainly linear, approaches to the current trend in TS foundation models. With a lot of hype and industrial demand in this field, it is not always clear how much progress there really is. To advance TS forecasting and analysis to the next level, here we argue that the field needs a *dynamical systems (DS)* perspective. TS of observations from natural or engineered systems almost always originate from some underlying DS, and arguably access to its governing equations would yield theoretically optimal forecasts. This is the promise of *DS reconstruction (DSR)*, a class of ML/AI approaches that aim to infer *surrogate models* of the underlying DS from data. But models based on DS principles offer other profound advantages: Beyond short-term forecasts, they enable to predict the *long-term statistics* of an observed system, which in many practical scenarios may be the more relevant quantities. DS theory furthermore provides domain-independent *theoretical insight into mechanisms* underlying TS generation, and thereby will inform us, e.g., about upper bounds on performance of *any* TS model, generalization into unseen regimes as in tipping points, or potential control strategies. After reviewing some of the central concepts, methods, measures, and models in DS theory and DSR, we will discuss how insights from this field can advance TS modeling in crucial ways, enabling better forecasting with much lower computational and memory footprints. We conclude with a number of specific suggestions for translating insights from DSR into TS modeling.

Theory · Optimization

Deyi Kong, Zaiwei Chen, Shuzhong Zhang, Shancong Mou

In this work, we propose *Natural Hypergradient Descent* (NHGD), a new method for solving bilevel optimization problems. To address the computational bottleneck in hypergradient estimation—namely, the need to compute or approximate Hessian inverses—we exploit the statistical structure of the inner optimization problem and use the empirical Fisher information matrix as an asymptotically consistent surrogate for the Hessian. This design enables a parallel *optimize-and-approximate* framework in which the Hessian-inverse approximation is updated *synchronously* with the stochastic inner optimization, reusing gradient information at negligible additional cost. Our main theoretical contribution establishes high-probability error bounds and sample complexity guarantees for NHGD that match those of state-of-the-art optimize-then-approximate methods, while significantly reducing computational time overhead. Empirical evaluations on representative bilevel learning tasks further demonstrate the practical advantages of NHGD, highlighting its scalability and effectiveness in large-scale machine learning settings.

General Machine Learning · Data

Emmanuel J Candes, Andrew Ilyas, Tijana Zrnic

Obtaining high-quality labeled datasets is often costly, requiring either human annotation or expensive experiments. In theory, powerful pre-trained AI models provide an opportunity to automatically label datasets and save costs. Unfortunately, these models provide no guarantees on their accuracy, making wholesale replacement of manual labeling impractical. In this work, we propose a method for leveraging pre-trained AI models to curate cost-effective and high-quality datasets. In particular, our approach results in probably approximately correct labels: with high probability, the overall labeling error is small. Our method is nonasymptotically valid under minimal assumptions on the dataset or the AI model being studied, and thus enables rigorous yet efficient dataset curation using modern AI models. We demonstrate the benefits of the methodology through text annotation with large language models, image labeling with pre-trained vision models, and protein folding analysis with AlphaFold.