论文检索

Theory · Learning Theory

Mehryar Mohri, Yutao Zhong

The choice of loss function in classification involves a fundamental trade-off: smooth losses (like Cross-Entropy) enable fast optimization rates but yield slow square-root consistency bounds, while piecewise-linear losses (like Hinge) offer fast linear consistency rates but suffer from non-differentiability. We propose *Linear-Core (LC) Surrogates*, a new family of convex loss functions that resolve this tension by stitching a linear core to a smooth tail. We prove that these surrogates are differentiable everywhere while retaining strict linear $H$-consistency bounds, effectively combining the optimization benefits of smoothness with the statistical efficiency of margin-based losses. In the structured prediction setting, we show that this smoothness unlocks a massive computational and energy advantage: it allows for an unbiased stochastic gradient estimator that bypasses the quadratic complexity $O(|\mathcal{Y}|^2)$ of exact inference (e.g., Viterbi). Empirically, our method achieves a *23$\times$ speedup* over Structured SVMs on large-vocabulary sequence tagging tasks and demonstrates superior robustness to instance-dependent label noise, outperforming Cross-Entropy by *2.6\%* on corrupted CIFAR-10.

Theory · Probabilistic Methods

Qiaoyu Liang, Haohua Chen, Zihan Zhu, Michael Evans

From a statistical evidence perspective, we establish some asymptotic optimality properties of certain multiple testing rules based on the relative belief ratio (Evans, 2015). Under the two-groups model with an additive 0-1 loss and within a Bayesian decision theoretic asymptotic framework of Bogdan et al. (2011), we show that relative belief multiple testing rules induced by a simple one-group light-tailed normal prior with a single hyperparameter achieve the same asymptotic Bayes risk as the Bayes oracle benchmark. This risk is the minimum achievable in this asymptotic framework. Despite originating from a different starting point, the evidential relative belief approach enjoys oracle properties. The relative belief multiple testing approach is fundamentally different from existing Bayesian multiple testing procedures, virtually all induced by more complex heavy-tailed one-group global-local shrinkage priors using purely posterior-based inferences (Datta & Ghosh, 2013; Ghosh et al., 2016; Bhadra et al., 2017; Ghosh & Chakrabarti, 2017; Qin & Ghosh, 2025). By measuring statistical evidence via both the prior and posterior, the relative belief approach reveals an alternative new inferential paradigm for attaining asymptotic Bayes optimality under sparsity, one that does not rely on developing increasingly elaborate priors.

Theory · Everything Else

Tao Wang, Xiaoting Zhong

Distributional learning problems optimize discrepancies between probability measures, including optimal transport or Sinkhorn divergence, yet are typically optimized using Euclidean first-order methods in parameter space. We show this mismatch is structural rather than algorithmic. We introduce geometry-misalignment, a local condition number that measures distortion between Euclidean geometry and the intrinsic geometry induced by a distributional objective. For a broad class of problems, we establish lower bounds demonstrating that Euclidean first-order methods incur an unavoidable convergence slowdown proportional to misalignment, even under intrinsic strong convexity and smoothness. We further prove geometry-aware preconditioned methods attain matching upper bounds independent of misalignment, yielding a sharp separation between Euclidean optimization and geometry-aware optimization. Beyond convergence rates, we show geometry-misalignment induces an optimization-dependent excess risk term under finite budgets, directly linking optimization geometry with statistical efficiency. We develop a geometry-calibrated optimization framework that estimates misalignment and selectively activates geometry-aware updates when necessary. Experiments on distribution matching for domain adaptation validate the theory, with improvements concentrated in high-misalignment regimes and negligible overhead.

Applications · Language, Speech and Dialog

Masataka Yoneda, Yusuke Matsushita, Go Kamoda, Kohei Suenaga, Takuya Akiba, Masaki Waga, Sho Yokoi

We present an ultra-fast and flexible search algorithm that enables search over trillion-scale natural language corpora in under 0.3 seconds while handling semantic variations (substitution, insertion, and deletion). Our approach employs string matching based on suffix arrays that scales well with corpus size. To mitigate the combinatorial explosion induced by the semantic relaxation of queries, our method is built on two key algorithmic ideas: fast exact lookup enabled by a disk-aware design, and dynamic corpus-aware pruning. We theoretically show that the proposed method suppresses exponential growth in the search space with respect to query length by leveraging statistical properties of natural language. In experiments on FineWeb-Edu (1.4T tokens), we show that our method achieves significantly lower search latency than existing methods: infini-gram, infini-gram mini, and SoftMatcha. As a practical application, we demonstrate that our method identifies benchmark contamination in training corpora, unidentified by existing approaches. We also provide an online demo of fast, soft search across corpora in six languages.

Optimization · Zero-order and Black-box Optimization

Yanchi Li, Jiao Liu, Wenyin Gong, Qiong Gu, Yue Zhao, Yew Soon ONG

Evolutionary multi-tasking accelerates black-box optimization via knowledge transfer but falters in scenarios involving many low-similarity tasks. We identify this scalability barrier as the *Multi-Task Curse*, driven by evaluation budget dispersion and negative transfer. To overcome this, we propose MES-RET (*M*any-task *E*volution *S*trategy with *R*eward-weighted *E*valuation and *T*ransfer), which combats budget dispersion via a reward-weighted evaluation scheme that guarantees superior expected improvement, while simultaneously mitigating negative transfer through a robust reward-weighted aggregation of mean and covariance statistics, ensuring a safe fallback to independent evolution. Furthermore, to handle neural dimensional mismatches in many-task policy search, we introduce a semantic parameter alignment strategy that bridges heterogeneous state-action spaces. Extensive experiments on synthetic benchmarks, real-world engineering problems, and reinforcement learning tasks demonstrate that MES-RET consistently outperforms state-of-the-art methods, notably enabling skill transfer across morphologically distinct policies.

Wei Yuan, Zixuan Shao, Shuhui Wang

Constraint-based causal discovery relies on conditional independence (CI) tests whose reliability degrades as conditioning sets grow, particularly in hub-dominated graphs. Existing methods constrain adjacency or global structure, but leave conditioning-set dimensionality uncontrolled. In this paper, we propose Ordering-Constrained Markov Blanket discovery (OCMB), a paradigm that treats conditioning-set dimensionality as a first-class constraint. OCMB decouples discovery into two stages: lightweight global ordering estimation providing directional priors, followed by local Markov blanket validation within small, ordering-constrained candidate sets. By enforcing directional constraints before any CI test, OCMB ensures bounded conditioning sets even with hub nodes. We show that OCMB recovers correct parent sets provided a high-recall ordering assumption holds, without requiring the ordering to be globally correct. Experiments demonstrate that OCMB significantly improves precision and robustness over constraint-based and hybrid methods in high-dimensional regimes where conventional CI-based approaches fail.

Deep Learning · Foundation Models

Qifan Yu, Xinyu Ma, Zhijian Zhuo, Minrui Wang, Deyi Liu, Shiyi Zhan, Yiyuan Ma, liang xiang, Xingyan Bin, Di He

Progressive Learning (PL) reduces pre-training computational overhead by gradually increasing model scale. While prior work has extensively explored depth expansion, width expansion remains significantly understudied, with the few existing methods limited to the early stages of training. However, expanding width during the mid-stage is essential for maximizing computational savings, yet it remains a formidable challenge due to severe training instabilities. Empirically, we show that naive initialization at this stage disrupts activation statistics, triggering loss spikes, while copy-based initialization introduces gradient symmetry that hinders feature diversity. To address these issues, we propose **SPARKLING** (balancing **S**ignal **P**reservation **A**nd symmet**R**y brea**K**ing for width-progressive **L**earn**ING**), a novel framework for mid-stage width expansion. Our method achieves signal preservation via RMS-scale consistency, stabilizing activation statistics during expansion. Symmetry breaking is ensured through asymmetric optimizer state resetting and learning rate re-warmup. Extensive experiments on Mixture-of-Experts (MoE) models demonstrate that, across multiple width axes and optimizer families, SPARKLING consistently outperforms training from scratch and reduces training cost by up to 35% under $2\times$ width expansion.

General Machine Learning · Kernel methods

Louis Allain, Sébastien Da Veiga, Brian Staber

Conformal prediction (CP) is a distribution-free method to construct reliable prediction intervals that has gained significant attention in recent years. Despite its success and various proposed extensions, a significant practical feature which has been overlooked in previous research is the potential skewed nature of the noise, or of the residuals when the predictive model exhibits bias. In this work, we leverage recent developments in CP to propose a new asymmetric procedure that bridges the gap between skewed and non-skewed noise distributions, while still maintaining adaptivity of the prediction intervals. We introduce a new statistical learning problem to construct adaptive and asymmetric prediction bands, with a unique feature based on a penalty which promotes symmetry: when the penalty intensity varies, the intervals smoothly change from symmetric to asymmetric ones. This statistical learning problem is based on reproducing kernel Hilbert spaces and the recently introduced kernel sum-of-squares framework. First, we establish representer theorems to make our problem tractable in practice, and derive dual formulations which are essential for scalability to larger datasets. Second, the intensity of the penalty is chosen using a novel data-driven method which automatically identifies the symmetric nature of the noise. We show that consenting to some asymmetry can let the learned prediction bands better adapt to small sample regimes, outliers or biased predictive models. Finally, our experiments illustrate the efficiency of such penalized kernel sum-of-squares to construct adaptive prediction bands.

General Machine Learning · Transfer, Multitask and Meta-learning

Guanglong Sun, Hongwei Yan, Liyuan Wang, Zhiqi KANG, Shuang Cui, Hang Su, Jun Zhu, Yi Zhong

To cope with uncertain changes of the external world, intelligent systems must continually learn from complex, evolving environments and respond in real time. This ability, collectively known as general continual learning (GCL), encapsulates practical challenges such as online datastreams and blurry task boundaries. Although leveraging pretrained models (PTMs) has greatly advanced conventional continual learning (CL), these methods remain limited in reconciling the diverse and temporally mixed information along a single pass, resulting in sub-optimal GCL performance. Inspired by meta-plasticity and reconstructive memory in neuroscience, we introduce here an innovative approach named **Me**ta **Po**st-Refinement (MePo) for PTMs-based GCL. This approach constructs pseudo task sequences from pretraining data and develops a bi-level meta-learning paradigm to refine the pretrained backbone, which serves as a prolonged pretraining phase but greatly facilitates rapid adaptation of representation learning to downstream GCL tasks. MePo further initializes a meta covariance matrix as the reference geometry of pretrained representation space, enabling GCL to exploit second-order statistics for robust output alignment. MePo serves as a plug-in strategy that achieves significant performance gains across a variety of GCL benchmarks and pretrained checkpoints in a rehearsal-free manner (e.g., 15.10%, 13.36%, and 12.56% on CIFAR-100, ImageNet-R, and CUB-200 under Sup-21/1K).

Probabilistic Methods · Everything Else

Sacha Braun, David Holzmüller, Michael Jordan, Francis Bach

Evaluating conditional coverage remains one of the most persistent challenges in assessing the reliability of predictive systems. Although conformal methods can give guarantees on marginal coverage, no method can guarantee to produce sets with correct conditional coverage, leaving practitioners without a clear way to interpret local deviations. To overcome sample-inefficiency and overfitting issues of existing metrics, we cast conditional coverage estimation as a classification problem. Conditional coverage is violated if and only if any classifier can achieve lower risk than the target coverage. Through the choice of a (proper) loss function, the resulting risk difference gives a conservative estimate of natural miscoverage measures such as L1 and L2 distance, and can even separate the effects of over- and under-coverage, as well as handle non-constant target coverages. We call the resulting family of metrics excess risk of the target coverage (ERT). We show experimentally that the use of modern classifiers provides much higher statistical power than simple classifiers underlying established metrics like CovGap. Additionally, we use our metric to benchmark different conformal prediction methods. Finally, we release an open-source package for ERT as well as previous conditional coverage metrics. Together, these contributions provide a new lens for understanding, diagnosing, and improving the conditional reliability of predictive systems.

Probabilistic Methods · Monte Carlo and Sampling Methods

Xiaoyu Wang, Jonathan Huggins

Stochastic gradient Langevin dynamics combined with Gibbs updates (SGLD-Gibbs) provides a highly scalable approach to approximate Bayesian inference in latent variable models. However, it remains unclear how to tune the algorithm's hyperparameters in a principled manner to ensure the uncertainty estimates are statistically meaningful. In this work, we address this gap in tuning guidance by developing a statistical scaling limit theory for SGLD-Gibbs. We derive a joint asymptotic limit for the global parameters and latent variables under appropriate space-time rescaling. We show that global parameters converge to a diffusion-type limit, while individual latent variables converge to a jump process reflecting their intermittent Gibbs updates. This joint jump-diffusion structure reveals how latent-variable randomness contributes to the stationary distribution of the global parameters. We leverage our results to provide explicit guidance on hyperparameter tuning for SGLD-Gibbs that ensures meaningful uncertainty quantification. Our empirical results show that SGLD-Gibbs with our tuning guidance leads to better parameter estimates and uncertainty quantification than stochastic variational inference.

Theory · Domain Adaptation and Transfer Learning

Chenghan Xie, Jose Blanchet, Renyuan Xu

Estimating the difference of two Stein's score functions is a fundamental problem in generative modeling. In particular, score differences arise naturally in transfer learning, where the score difference provides the mechanism for adapting a pre-trained model to a new target distribution, and in diffusion model-based post-training methods such as discriminator guidance. Existing estimators for score differences in these settings either lack of statistical consistency or are difficult to scale up in high-dimensions. We propose a statistically consistent and scalable estimator for score differences based on Sobolev regularization, which plays a crucial role in ensuring consistency and stablizing the training in the small-sample regime. Mathematically, we establish a convergence rate of $\tilde{\mathcal{O}}(n^{-\frac{s-1}{d+2s-2}})$ where $d$ is the dimension and $s$ denotes the smoothness of the underlying densities, and provide a minimax lower bound of $\tilde{\Omega}(n^{-\frac{2(s-1)}{d+2s}})$ (in mean-squared error). Empirically, our estimator exhibits significantly improved stability in small-sample regimes compared to existing methods. We demonstrate its effectiveness on real-world tasks, including transfer learning for ECG signal generation, where it substantially outperforms non-regularized score difference estimators in downstream classification performance.

Deep Learning · Large Language Models

Yangxinyu Xie, Tao Wang, Soham Mallick, Yan Sun, Georgy Noarov, Mengxin Yu, Tanwi Mallick, Edgar Dobriban

While LLMs have seen substantial improvement in reasoning capabilities, they also sometimes overthink, generating unnecessary reasoning steps, particularly under uncertainty, given ill-posed or ambiguous queries. We introduce statistically principled early stopping methods that monitor uncertainty signals during generation to mitigate this issue. Our first approach is nonparametric and provides finite-sample guarantees on the probability of halting too early on well-posed queries. Our second approach is parametric: it models inter-arrival times of uncertainty keywords as a renewal process and applies sequential testing for stopping. We conduct empirical evaluations on reasoning tasks across several domains and models. Our results indicate that uncertainty-aware early stopping can improve both efficiency and reliability in LLM reasoning. The performance varies across domains, and we observe especially significant gains for math reasoning.

Social Aspects · Accountability, Transparency, and Interpretability

Jiadong Lou, Wenxin Rong, Li Chen, Xing Gao, Rui Zhang, Xu Yuan

Concerns over dataset misuse in deep learning have highlighted the need for effective auditing. Unlike existing intrusive methods that require dataset modifications, which risk model performance and security, we present DataGuard, a non-intrusive framework for quantitative dataset auditing. Specifically, DataGuard integrates three key components: 1) a differential comparison between the target dataset and auxiliary non-training datasets, 2) an information-forensic analysis establishing formal inequalities to distinguish training data; and 3) a multivariate statistical test that translates these discrepancies into rigorous auditing scores. Extensive experiments demonstrate that DataGuard can detect both full and partial dataset usage without false positives while remaining robust under diverse training scenarios, offering a principled, information-theoretic solution for transparent AI development.

Deep Learning · Large Language Models

G M Shahariar, Erfan Shayegani, Ali Nazari, Nael Abu-Ghazaleh

Large Reasoning Models (LRMs) solve complex tasks by generating long Chain-of-Thought (CoT) sequences; however, the emergent dynamics governing reasoning trajectories are not well understood and can lead to inconsistencies and reasoning pathologies. In this work, we propose to approximate LRM's emerging hierarchical reasoning dynamics as a trajectory within a Finite State Machine (FSM) transitioning among six abstract cognitive states. We demonstrate that these states and transitions can be captured in the latent state of the model. We believe that this representation can have different applications in the interpretability and optimization of LRM models. For example, by analyzing the topology of these transitions, we identify statistical shifts in reasoning strategies that help identify effective reasoning chains from those that fail. To illustrate these potential advantages, we propose $Q$-Value guided steering, a training-free inference-time control method that treats reasoning as a planning problem. We estimate the long-horizon utility of state transitions and apply sparse, orthogonal activation steering at sentence boundaries to align the CoT generation with optimal reasoning policies. Experiments across four benchmarks (AIME25, MATH-500, GSM8k, and GPQA Diamond) using three state-of-the-art open reasoning models demonstrate that $Q$-Value steering policy achieves significant performance gains with "surgical'' efficiency, often requiring $25\times$ fewer interventions than greedy and weighted baselines, which suggests that reasoning can be effectively controlled by guiding high-level cognitive dynamics rather than micro-managing token generation.

Deep Learning · Theory

Ruizhe Shi, Minhak Song, Runlong Zhou, Zihan Zhang, Maryam Fazel, Simon Du

We present a fine-grained theoretical analysis of the performance gap between reinforcement learning from human feedback (RLHF) and direct preference optimization (DPO) under a representation gap. Our study decomposes this gap into two sources: an explicit representation gap under exact optimization and an implicit representation gap under finite samples. In the exact optimization setting, we characterize how the relative capacities of the reward and policy model classes influence the final policy qualities. We show that RLHF, DPO, or online DPO can outperform one another depending on type of model mis-specifications. Notably, online DPO can outperform both RLHF and standard DPO when the reward and policy model classes are isomorphic and both mis-specified. In the approximate optimization setting, we provide a concrete construction where the ground-truth reward is implicitly sparse and show that RLHF requires significantly fewer samples than DPO to recover an effective reward model, highlighting a statistical advantage of two-stage learning. Together, these results provide a comprehensive understanding of the performance gap between RLHF and DPO under various settings, and offer practical insights into when each method is preferred.

Deep Learning · Theory

Vicente Mendes, Lorenzo Bardone, Cédric Koller, Jorge Medina Moreira, Vittorio Erba, Emanuele Troiani, Lenka Zdeborova

Many real-world datasets contain hidden structure that cannot be detected by simple linear correlations between input features. For example, latent factors may influence the data in a coordinated way, even though their effect is invisible to covariance-based methods such as PCA. In practice, nonlinear neural networks often succeed in extracting such hidden structure in unsupervised and self-supervised learning. However, constructing a minimal high-dimensional model where this advantage can be rigorously analyzed has remained an open theoretical challenge. We introduce a tractable high-dimensional spiked model with two latent factors: one visible to covariance, and one statistically dependent yet uncorrelated, appearing only in higher-order moments. PCA and linear autoencoders fail to recover the latter, while a minimal nonlinear autoencoder provably extracts both. We analyze both the population risk, and empirical risk minimization. Our model also provides a tractable example where self-supervised test loss is poorly aligned with representation quality: nonlinear autoencoders recover latent structure that linear methods miss, even though their reconstruction loss is higher.

Optimization · Zero-order and Black-box Optimization

Yonghan Yang, Ye Yuan, Zipeng Sun, Linfeng Du, Bowei He, Haolun Wu, Can Chen, Xue Liu

Offline black-box optimization aims to discover novel designs with high property scores using only a static dataset, a task fundamentally challenged by the out-of-distribution (OOD) extrapolation problem. Existing approaches typically bifurcate into inverse methods, which struggle with the ill-posed nature of mapping scores to designs, and forward methods, which often lack the distributional expressivity to quantify uncertainty effectively. In this work, we propose \textbf{SPADE} (\textbf{S}upport-\textbf{P}roximity \textbf{A}ugmented \textbf{D}iffusion \textbf{E}stimation), a novel framework that reimagines forward surrogate modeling through the lens of conditional generative modeling. SPADE models the forward likelihood $p(y|\boldsymbol{x})$ using a diffusion model, but with two critical enhancements to tailor it for optimization: (1) a \emph{Calibrated Diffusion Estimation} module that enforces global consistency in statistical moments and pairwise rankings, and (2) a \emph{Support-Proximity Regularization} mechanism that implicitly internalizes the data manifold constraint $p(\boldsymbol{x})$ via kNN-based density estimation. Theoretically, we prove that our regularization is first-order equivalent to maximizing a Bayesian posterior with a valid design prior. Empirically, SPADE achieves state-of-the-art performance across Design-Bench tasks and an LLM data mixture optimization benchmark. Our code is available through the anonymous repo \href{https://anonymous.4open.science/r/diffsurr-icml2026-C4FD/}{here}.

Deep Learning · Generative Models and Autoencoders

Xiaochao Deng, Jie Chen, Xiaogang Deng

Accurately modeling the full distributions of possible states is crucial for understanding statistical properties and enabling reliable predictions in complex, unsteady physical systems. Recently, diffusion models and flow matching have shown promise in these tasks. However, they remain limited in uncovering the general principles of systems from multiple short trajectories across condition space. In addition, they exhibit inferior adaptability to large irregular geometries, particularly in regions with sharp gradients. In this paper, we propose a condition-aware graph flow matching (CGFM) method that combines condition-aware flow matching with a hierarchical graph structure to learn the full distributions of physical systems from incomplete training data. Specifically, CGFM constructs a flow enabling smooth interpolation across physical conditions and parameterizes the graph-conditioned vector field through HieraGraphNet. HieraGraphNet performs message passing across multilevel graphs to capture multi-scale dynamics and facilitate long-range information interactions in physical systems. Moreover, we introduce a topology- and geometry-aware graph coarsening scheme that incorporates topological connectivity and local geometric density to construct reliable coarse graphs. We validate the effectiveness of CGFM on three canonical scenarios across both 2D and 3D dynamics, which demonstrate its superior performance compared with that of state-of-the-art baselines.

Deep Learning · Robustness

Mingzu Liu, Hao Fang, Runmin Cong

Fine-Tuning-as-a-Service (FTaaS) facilitates the customization of Multimodal Large Language Models (MLLMs) but introduces critical backdoor risks via poisoned data. Existing defenses either rely on supervised signals or fail to generalize across diverse trigger types and modalities. In this work, we uncover a universal backdoor fingerprint—**attention allocation divergence**—where poisoned samples disrupt the balanced attention distribution across three functional components: system instructions, vision inputs, and user textual queries, regardless of trigger morphology. Motivated by this insight, we propose **Tri-Component Attention Profiling (TCAP)**, an unsupervised defense framework to filter backdoor samples. TCAP decomposes cross-modal attention maps into the three components, identifies trigger-responsive attention heads via Gaussian Mixture Model (GMM) statistical profiling, and isolates poisoned samples through EM-based vote aggregation. Extensive experiments across diverse MLLM architectures and attack methods demonstrate that TCAP achieves consistently strong performance, establishing it as a robust and practical backdoor defense in MLLMs.