论文检索

Theory · Everything Else

Felix Laarmann, Andreas Pauly, Sebastian Buschjäger, Andrea Bommert, Jakob Rehof

We present a general framework for synthesizing search spaces of parametric functions, along with strategies for traversing these spaces to find optima. We formalize an algebraic theory for the categorical model of parametric functions in finite combinatory logic with predicates (FCLP). Based on a component-oriented synthesis framework for FCLP we automate composition from given components and search for parametric functions. Components are language-agnostic and may be instantiated as any implementation of parametric functions, e.g., as PyTorch modules. A proof-of-concept implementation demonstrates how to represent more specific concepts, such as neural architecture search and hyperparameter optimization, within the framework.

General Machine Learning · Online Learning, Active Learning and Bandits

Tuo Liu, Edgar Dobriban, Francesco Orabona

Online conformal prediction (OCP) seeks prediction intervals that achieve long-run $1-\alpha$ coverage for arbitrary (possibly adversarial) data streams, while remaining as informative as possible. Existing OCP methods often require manual learning-rate tuning to work well, and may also require algorithm-specific analyses. Here, we develop a general regret-to-coverage theory for interval-valued OCP based on the $(1-\alpha)$-pinball loss. Our first contribution is to identify *linearized regret* as a key notion, showing that controlling it implies coverage bounds for any online algorithm. This relies on a black-box reduction that depends only on the Fenchel conjugate of an upper bound on the linearized regret. Building on this theory, we propose UP-OCP, a parameter-free method for OCP, via a reduction to a two-asset portfolio selection problem, leveraging universal portfolio algorithms. We show strong finite-time bounds on the miscoverage of UP-OCP, even for polynomially growing predictions. Extensive experiments support that UP-OCP delivers consistently better size/coverage trade-offs than prior online conformal baselines.

Applications · Everything Else

Arnav Shah, Junzhe Li, Parsa Idehpour, Adibvafa Fallahpour, Brandon Wang, Sukjun Hwang, BO WANG, Patrick Hsu, Hani Goodarzi, Albert Gu

Genomic foundation models have the potential to decode DNA syntax, yet face a fundamental tradeoff. Standard subword tokenizers fragment biologically meaningful motifs such as codons and regulatory elements, while nucleotide-level models preserve biological coherence but incur prohibitive computational costs for long contexts. We introduce dnaHNet, a state-of-the-art tokenizer-free autoregressive model that segments and models genomic sequences end to end. Using a differentiable dynamic chunking mechanism, dnaHNet compresses raw nucleotides into latent tokens adaptively, balancing compression with predictive accuracy. Pretrained on prokaryotic genomes, dnaHNet outperforms leading architectures including StripedHyena2 in scaling and efficiency. This recursive chunking yields quadratic FLOP reductions, enabling $>3 \times$ inference speedup over Transformers. On zero-shot tasks, dnaHNet achieves superior performance in predicting protein variant fitness and gene essentiality, while automatically discovering hierarchical biological structures without supervision. These results establish dnaHNet as a scalable, interpretable framework for next-generation genomic modeling.

Applications · Chemistry, Physics, and Earth Sciences

Jules Berman, Tobias Blickhan, Benjamin Peherstorfer

In existing works on population dynamics inference, there is a focus on flows arising from vector fields that are the gradients of scalar potentials. Among all admissible flows that are compatible with the population dynamic, gradient flows are optimal in a specific sense: they minimize kinetic energy. The selection of fields based on different criteria corresponds to a gauge freedom when determining population dynamics, which we leverage in this work. We propose Non-Gradient Inference Flows (NGIF), an algorithm to infer non-gradient population dynamics using a weak formulation of the continuity equation. This allows us to parameterize with general vector fields as well as choose other selection criteria beyond minimal energy. We demonstrate on a variety of low- and high-dimensional physics problems that this more general approach improves distributional accuracy over gradient-restricted baselines and better captures non-potential transport.

Theory · Probabilistic Methods

Dario Rancati, Jan Maas, Francesco Locatello

Diffusion-based models on continuous spaces have seen substantial recent progress through the mathematical framework of gradient flows, leveraging the Wasserstein-2 (${W}_2$) metric via the Jordan-Kinderlehrer-Otto (JKO) scheme. Despite the increasing popularity of diffusion models on discrete spaces using continuous-time Markov chains, a parallel theoretical framework based on gradient flows has remained elusive due to intrinsic challenges in translating the ${W}_2$ distance directly into these settings. In this work, we propose the first successful approach addressing these challenges, leveraging an appropriate metric $W_K$ on the simplex of probability distributions, which enables us to interpret widely used discrete diffusion paths, such as the discrete heat equation, as gradient flows of specific free-energy functionals. Through this theoretical insight, we introduce a novel methodology for learning diffusion dynamics over discrete spaces, which recovers the underlying functional directly by leveraging first-order optimality conditions for the JKO scheme. The resulting method optimizes a simple quadratic loss, trains extremely fast, does not require individual sample trajectories, and only needs a numerical preprocessing computing $W_K$-geodesics. We validate our method through extensive numerical experiments on synthetic data, showing that we can recover the underlying functional for a variety of graph classes.

Theory · Probabilistic Methods

Tal Wagner

We study query time bounds for the fundamental problem of estimating the kernel mean $\frac1{|X|}\sum_{x\in X}\mathbf{\mathrm{k}}(x,y)$ of a query $y$ in a finite dataset $X\subset\mathbb{R}^d$ up to a prescribed additive error $\varepsilon$. The best known bounds for the Gaussian kernel are $O(d/\varepsilon^2)$, $\widetilde O(d+1/\varepsilon^4)$, and $\widetilde O(d+\Delta^2/\varepsilon^2)$, where $\Delta$ is the diameter of a region containing the points. We prove the new bound $\tilde O(d+\varepsilon\Delta^2+1/\varepsilon^3)$, which improves over the previous ones in regimes with small error $\varepsilon$ and intermediate diameter $\Delta$. At the center of our proof is a new fast spherical embedding theorem in the sense introduced by Bartal, Recht and Schulman (2011), which limits the embedded data diameter while preserving local Euclidean distances and avoiding ``distance collapse'' at larger scales. This fast embedding theorem may be of independent interest.

Deep Learning · Large Language Models

Yangfu Li, Yuning Gong, Hongjian Zhan, Teng Li, Yuanhuiyi Lyu, Tianyi Chen, Qi Liu, Ziyuan Huang, Zhihang Zhong, DanDan Zheng 等

Despite the success of LVLMs, general optimization objectives (e.g., standard MLE) fail to constrain visual trajectories, leading to language bias and hallucination. To mitigate this, current methods introduce geometric priors from visual experts as additional supervision. However, we observe that such supervision is typically suboptimal: *it is biased toward geometric precision and offers limited reasoning utility*. To bridge this gap, we propose Perceptual Flow Network (PFlowNet), which eschews rigid alignment with the expert priors and achieves interpretable yet more effective visual reasoning. Specifically, PFlowNet decouples perception from reasoning to establish a self-conditioned generation process. Based on this, it integrates *multi-dimensional rewards* with *vicinal geometric shaping* via variational reinforcement learning, thereby facilitating reasoning-oriented perceptual behaviors while preserving visual reliability. PFlowNet delivers a provable performance guarantee and competitive empirical results, particularly setting new SOTA records on V* Bench (90.6%) and MME-RealWorld-lite (67.0%).

Theory · Optimization

Anming Gu, Juno Kim

The mean-field Langevin dynamics (MFLD) minimizes an entropy-regularized nonlinear convex functional on the Wasserstein space over $\mathbb{R}^d$, and has gained attention recently as a model for the gradient descent dynamics of interacting particle systems such as infinite-width two-layer neural networks. However, many problems of interest have constrained domains, which are not solved by existing mean-field algorithms due to the global diffusion term. We study the optimization of probability measures constrained to a convex subset of $\mathbb{R}^d$ by proposing the \emph{mirror mean-field Langevin dynamics} (MMFLD), an extension of MFLD to the mirror Langevin framework. We obtain linear convergence guarantees for the continuous MMFLD via a uniform log-Sobolev inequality, and uniform-in-time propagation of chaos results for its time- and particle-discretized counterpart.

Mingchen Ma, Guyang Cao, Jelena Diakonikolas, Ilias Diakonikolas

We study the problem of learning a drifting concept in the presence of Massart noise. In this framework, an online learner has access to a history of independent samples whose labels are noisy versions of a target concept that may change from round to round. The goal is to output, in each round, a hypothesis with small prediction error. We study the complexity of this learning problem for the fundamental class of margin-separable linear classifiers (halfspaces). On the positive side, we give a computationally efficient learner achieving error $\eta + \tilde O(\Delta^{1/3}/\gamma)$, where $\eta$ upper bounds the Massart noise rate, $\Delta$ is the drift rate, and $\gamma$ is the margin. Interestingly, in the realizable setting, an adaptation of our techniques yields an efficient learner with an improved error rate over prior work. On the lower-bound side, we provide formal evidence of an information-computation tradeoff, strongly suggesting that our algorithm's performance is essentially optimal. Specifically, while the information-theoretically optimal error scales with $\Delta^{1/2}$, we prove that $\Delta^{1/3}$-scaling is unavoidable for low-degree polynomial tests, even in the special case of random classification noise.

Probabilistic Methods · Variational Inference

Safa Messaoud, Skander Charni, Elaa Bouazza, Ali Pourghasemi, Halima Bensmail

Computing the differential entropy of distributions known only up to a normalization constant is a long-standing challenge with broad theoretical and practical significance. While variational inference is the most scalable approach for density approximation _from samples_, its potential in settings where _only the unnormalized density_ is available remains largely under-explored. The central difficulty lies in constructing variational distributions that simultaneously ($i$) exploit the structure of the unnormalized density, ($ii$) are expressive enough to capture complex target distributions, ($iii$) remain computationally tractable, and ($iv$) support efficient sampling. Recently, \citet{messaoud2024s} introduced _P-SVGD_, a particle-based variational method that leverages Stein Variational Gradient Descent dynamics, satisfies all of these constraints and demonstrates promising results in low-dimensional setups. We show, however, that _P-SVGD_ does not scale to high dimensions due to _fundamental algorithmic flaws_: ($i$) misdiagnosed sensitivity to \textit{SVGD} hyperparameters, ($ii$) violation of the global invertibility assumption in the entropy derivation, ($iii$) omission of a critical trace-of-Hessian term, ($iv$) along with suboptimal heuristics, including a divergence-based sampling check that induces mode collapse and loose informal bounds with no practical value. These issues severely limit both the correctness and the scalability of the approach. We propose _MET-SVGD_, a principled extension of _P-SVGD_ that addresses these flaws by providing a general framework for \textit{SVGD} hyperparameters selection with global invertibility and convergence guarantees. This enabled more accurate and scalable entropy estimation in high-dimensional settings. Empirically, in entropy estimation benchmarks, _MET-SVGD_ achieves accuracy improvements of up to 12$\times$ and 16$\times$ over _P-SVGD_ and baselines from the _SVGD_ literature, respectively. On CIFAR-10 Energy-Based image generation, it improves FID by $80.4$% compared to _P-SVGD_ and achieves 64$\times$ higher training stability. In Maximum-Entropy reinforcement learning, _MET-SVGD_ yields up to $16$% better returns than _P-SVGD_. We will make our code publicly available at https://tinyurl.com/2esyfx8j.

Deep Learning · Generative Models and Autoencoders

Bo Yin, Xiaobin Hu, Xingyu Zhou, Yu HE, Peng-Tao Jiang, Yue Liao, Junwei Zhu, Jiangning Zhang, Ying Tai, Shuicheng YAN

Diffusion models have achieved remarkable success in generative modeling, yet how to effectively adapting large pretrained models to new tasks remains challenging. We revisit the reconstruction behavior of diffusion models during denoising to unveil the underlying frequency–energy mechanism governing this process. Building upon this observation, we propose \textbf{FeRA}, a frequency-driven fine-tuning framework that aligns parameter updates with the intrinsic frequency–energy progression of diffusion. FeRA establishes a comprehensive frequency–energy framework for effective diffusion adaptation fine-tuning, comprising three synergistic components: \textit{(i)} a compact frequency–energy indicator that characterizes the latent’s bandwise energy distribution, \textit{(ii)} a soft frequency router that adaptively fuses multiple frequency-specific adapter experts, and \textit{(iii)} a frequency–energy consistency regularization that stabilizes diffusion optimization and ensures coherent adaptation across bands. Routing operates in both training and inference, with inference-time routing dynamically determined by the latent frequency energy. It integrates seamlessly with adapter-based tuning schemes and generalizes well across diffusion backbones and resolutions. By aligning adaptation with the frequency–energy mechanism, \textbf{FeRA} provides a simple, stable, and compatible paradigm for effective and robust diffusion model adaptation. Codes will be made publicly available.

Social Aspects · Accountability, Transparency, and Interpretability

Xuyang Chen, Xiang Li, Yangxinyu Xie, Qi Long

Watermarking methods embed imperceptible and verifiable signals into text generated by large language models (LLMs). Existing approaches include zero-bit schemes for distinguishing synthetic text from human writing and multi-bit schemes for embedding metadata. However, current multi-bit watermarking methods do not allow selective disclosure: verifying any part of the watermark requires revealing the entire embedded message. This lack of control leads to unnecessary information exposure and raises privacy concerns. We propose Hierarchical Vocabulary Routing, a watermarking framework that enables selective disclosure of embedded metadata. The method recursively partitions the vocabulary and distributes watermark information across hierarchical layers, so that different verifiers can decode only the portions of the payload corresponding to their access level. We show that the proposed scheme preserves the unbiasedness of the underlying sampling process and thus maintains text quality. Experiments demonstrate that our framework supports fine-grained access control while achieving high detection accuracy and low latency.

Theory · Learning Theory

QUOC TUNG LE, Anh Nguyen, Viet Anh Nguyen

Lagrangian Relaxation (LR) is a powerful technique for solving large-scale Mixed Integer Linear Programming (MILP), particularly those with decomposable structures like Vehicle Routing or Unit Commitment. By relaxing coupling constraints, LR enables parallel solving of subproblems and frequently yields tighter dual bounds than standard linear programming relaxations, which is crucial for efficient branch-and-bound pruning. While recent empirical works showed promising results using machine learning to predict these multipliers, a theoretical understanding of such methods remains an open question. In this work, we bridge this gap by analyzing the problem of learning LR through the lens of Data-driven Algorithm Design, i.e., a statistical learning problem over a distribution of problem instances. Our contributions are as follows: first, we derive a generalization bound of $\cO(s^{1.5}/\sqrt{N})$ for the learned multipliers, where $s$ is the number of coupled constraints and $N$ is the sample size. Second, we provide a minimax lower-bound of $\Omega(s/\sqrt{N})$, proving that a linear dependency is unavoidable. Finally, we extend our framework to the problem of learning to warm-start sub-gradient ascent.

General Machine Learning · Everything Else

Xinpeng Lv, Yunxin Mao, Renzhe Xu, Chunyuan Zheng, Haoxuan Li, Yikai Chen, Jinxuan Yang, Wanrong Huang, Yuanlong Chen, Mingyang Geng 等

Tabular foundation models via pretrained prior-data fitted networks (PFNs) achieve remarkable generalization performance on arbitrary testing tabular data, when sample distributions are independent of the deployed classifiers, i.e., a non-strategic regime. In a variety of real-world scenarios, however, once a classifier is deployed, individuals corresponding to tabular samples strategically manipulate their features to obtain favorable results, inducing feature distribution shifts at deployment, i.e., a strategic regime. As concurrent tabular foundation models exclusively overlook the strategic tabular data, we systematically explore the boundary of PFNs on strategic tabular data, characterizing their theoretical properties and empirical performance towards such a commonly encountered type of tabular data, offering a pioneer analysis on bridging PFNs and the society domain. To be first, we inform that such strategic manipulation creates a mismatch between the grounding, strategic prior and the pretrained prior. Subsequently, the prior mismatch leads to an inevitable posterior prediction bias of current tabular foundation models when applied to strategic environments. To address this challenge, we propose Strategic Prior-data Fitted Network (SPN), a strategy-aware framework that adapts tabular foundation models to strategic environments at inference time. SPN uses in-context learning to approximate post-manipulation inputs and then performs prediction for strategic tabular data. Experiments on real-world and synthetic tabular data show that SPN consistently improves performance and robustness under strategic manipulation compared to both tabular foundation models and classical tabular methods.

Optimization · Zero-order and Black-box Optimization

Junbin Qiu, Zhaowei Hong, Renzhe Xu, Yao Shu

Accurate Zeroth-Order (ZO) Hessian estimation is a cornerstone of derivative-free methods, essential for tasks such as bilevel optimization, Bayesian inference, and uncertainty quantification. However, obtaining a complete suite of low-variance estimators for the Hessian and its inverse in high-dimensional settings remains a significant challenge. To address this, we propose a unified framework that reinterprets ZO Hessian approximation through the lens of single-step Policy Optimization (PO). This perspective establishes a theoretical equivalence between general ZO Hessian estimators and the Hessian of a smoothed PO objective, unifying distinct classical randomized estimators as specific instances of baseline selection. Building on this foundation, we introduce ZoVH, a comprehensive suite of variance-reduced estimators for the full Hessian matrix, its regularized inverse, and the bias-corrected inverse Hessian-gradient product. ZoVH leverages two key techniques: (1) a unique optimal baseline derived to provably minimize variance, and (2) a query reuse strategy that incorporates historical function queries to enhance sample efficiency without inflating costs. Our rigorous theoretical analysis confirms the unbiasedness of the Hessian estimator, validates the variance optimality of our baseline, provides error bounds for the entire ZoVH suite, and establishes convergence guarantees for the resulting curvature-aware ZO algorithm. Extensive empirical results validate our theoretical findings, demonstrating that ZoVH achieves superior estimation accuracy and convergence performance in real-world applications.

Theory · Deep Learning

Erdem Koyuncu

We study compute reduction in neural networks through a unified partial versus full computation view, captured by one-shot magnitude pruning in the static regime and early exit in the adaptive regime. In an asymptotic single-neuron model, we prove a concentration theorem for one-shot magnitude pruning with explicit rates. We also introduce the conditional perceptron for early exit and show that its excess generalization error decays as a power of the compute gap, with an exponent that grows to infinity as the alignment between partial and full computations tends to one. We then extend the analysis to deep networks, characterizing how pruning-induced distortions accumulate with depth and deriving a corresponding compute–accuracy tradeoff for frozen-backbone early exit under a neural network Gaussian process model. Numerical simulations corroborate the predicted scaling laws.

Deep Learning · Large Language Models

Shobhita Sundaram, John Quan, Ariel Kwiatkowski, Kartik Ahuja, Yann Ollivier, Julia Kempe

RL methods for finetuning large reasoning models stall on datasets with low initial success rates, and thus little training signal. We investigate a fundamental question: Can a pretrained LLM leverage latent knowledge to generate an automated curriculum for problems it cannot solve? We explore this with SOAR: A self-improvement framework designed to surface these pedagogical signals through meta-RL. A teacher model proposes synthetic problems for a student model, and is rewarded with its improvement on a subset of hard problems, thus grounding the curriculum in real student progress rather than proxy rewards. Our study on the hardest subsets of math benchmarks (0/128 success) reveal three core findings. First, it is possible to realize bi-level meta-RL that unlocks learning under sparse, binary rewards by sharpening a latent capacity of pretrained models to generate useful problems. Second, grounded rewards outperform intrinsic rewards used in prior LLM self-play, reliably avoiding the typical instability and diversity collapse modes. Third, the structure and well-posedness of questions are more critical for learning progress than solution correctness. Our results suggest that the ability to generate useful stepping stones does not require the preexisting ability to solve the hard problems, paving a principled path to escape reasoning plateaus without additional curated data.

Deep Learning · Large Language Models

Charles Arnal, Vivien Cabannnes, Taco Cohen, Julia Kempe, REMI MUNOS

While Experience Replay—the practice of storing rollouts and reusing them multiple times during training—is a foundational technique in general RL, it remains largely unexplored in LLM post-training due to the prevailing belief that fresh, on-policy data is essential for high performance. In this work, we challenge this assumption. We present a systematic study of replay buffers for LLM post-training, formalizing the optimal design as a trade-off between staleness-induced variance, sample diversity and the high computational cost of generation. We show that strict on-policy sampling is suboptimal when generation is expensive. Empirically, we show that a well-designed replay buffer can drastically reduce inference compute without degrading -- and in some cases even improving -- final model performance, while preserving policy entropy.

Yunzhen Feng, Julia Kempe, Cheng Zhang, Parag Jain, Anthony Hartshorn

Large reasoning models (LRMs) spend substantial test-time compute on long chain-of-thought (CoT) traces, but what *characterizes* an effective CoT remains unclear. While prior work reports gains from lengthening CoTs and increasing review via appended *wait* tokens, recent studies suggest that shorter thinking can outperform longer traces. We therefore conduct a systematic evaluation across ten LRMs on math and scientific reasoning. Contrary to the “longer-is-better” narrative, we find that both naively using longer CoTs and more review behaviors are associated with *lower* accuracy. As CoT unfolds step by step, token-level metrics can conflate verbosity with process quality. We introduce a graph view of CoT to extract structure and identify a single statistic—the *Failed-Step Fraction* (FSF), the fraction of steps in abandoned branches—that consistently outpredicts length and review ratio for correctness across models. To probe causality, we design two interventions. First, we rank candidate CoTs by each metric at test time, where FSF yields the largest pass@1 gains; second, we edit CoTs to remove failed branches, which significantly improves accuracy, indicating that failed branches bias subsequent reasoning. Taken together, these results characterize effective CoTs as those that *fail less* and support *structure-aware* test-time scaling over indiscriminately generating long CoTs.

Deep Learning · Large Language Models

Tim Tomov, Dominik Fuchsgruber, Stephan Günnemann

In many applications of LLMs, natural language responses often have an underlying structure such as representing discrete labels, numerical values, or graphs. Yet, existing decoding and uncertainty estimation methods operate only in language space and largely disregard structural information. We address this by modeling LLM outputs directly in a task-dependent latent structure. By equipping this structure with a dissimilarity measure, we can compute Bayes-optimal responses. These are not selected from sampled generations but are newly synthesized by combining individual responses in the latent space. Across different tasks, Bayes-optimal responses consistently outperform standard decoding methods like beam search. Moreover, quantifying uncertainty via the induced Bayesian risk captures variations in terms of the latent structure and improves alignment with output quality and correctness. Our decision-theoretic framework is applicable to any problem that admits a latent response structure and enables reliable task-aware LLM predictions.