论文检索

Deep Learning · Everything Else

Andries Rosseau, Robert Müller, Ann Nowe

Continual training of deep neural networks under non-stationarity often leads to a progressive loss of plasticity, eventually limiting further learning. We define plasticity loss as the network’s diminishing ability to make reliable progress under gradient descent updates in all output-space directions, and identify departures from dynamical isometry (i.e., drift of the layer-wise Jacobian singular values away from one) as a key mechanism driving this loss. We first revisit a class of networks that are isometric almost-everywhere while remaining universal Lipschitz function approximators, demonstrating that isometry is compatible with expressive nonlinear function classes. Turning to more general architectures, we study an efficient isometry-promoting regularization scheme for continual learning. We analyze its interaction with common activation functions, and reveal a mechanism by which it can reactivate dead ReLU units. To integrate this regularization with adaptive optimization, we propose AdamO, an Adam-style optimizer that decouples isometric regularization from gradient updates, analogous to AdamW. Finally, we evaluate our methods in supervised and reinforcement learning settings designed to induce plasticity loss and show that they effectively preserve plasticity while also yielding strong performance.

Theory · Learning Theory

Andrea Della Vecchia, Damir Filipovic

This paper investigates theoretical and methodological foundations for stochastic optimal control (SOC) in discrete time. We start formulating the control problem in a general dynamic programming framework, introducing the mathematical structure needed for a detailed convergence analysis. The associate value function is estimated through a sequence of approximations combining nonparametric regression methods and Monte Carlo subsampling. The regression step is performed within reproducing kernel Hilbert spaces (RKHSs), exploiting the classical KRR algorithm, while Monte Carlo sampling methods are introduced to estimate the continuation value. To assess the accuracy of our value function estimator, we propose a natural error decomposition and rigorously control the resulting error terms at each time step. We then analyze how this error propagates backward in time-from maturity to the initial stage-a relatively underexplored aspect of the SOC literature. Finally, we illustrate how our analysis naturally applies to a key financial application: the pricing of American options.

Applications · Time Series

Aoyu Liu, Liming Wei, YAYING ZHANG

Most spatio-temporal forecasting models assume in-distribution data and can degrade sharply under non-stationary environments. Existing methods for handling distribution shift largely rely on discrete graph inference, making it difficult to disentangle universal dynamics from environment-specific changes and to respect the continuous physical nature of spatio-temporal fields. To this end, we propose STPDE, a general framework that reformulates spatio-temporal dynamics as the evolution of inhomogeneous partial differential equations. STPDE explicitly decomposes dynamics into an Invariant Diffusion Operator that captures universal mechanisms and an Environment Basis Manifold that parameterizes local heterogeneous media. We show that the Green's function of the Laplacian can be effectively approximated by linear attention, enabling global diffusion at scale. Combined with stochastic environment perturbations, STPDE improves robustness under heterogeneous and shifting environments. Extensive experiments on in-distribution forecasting, out-of-distribution generalization, few-shot cross-city transfer, and continual learning demonstrate consistent improvements over state-of-the-art baselines with competitive computational efficiency.

Deep Learning · Algorithms

Tianren Zhang, Xiangxin Li, Minghao Xiao, Guanyu Chen, Feng Chen

Deep networks often exhibit a preference for "simple" solutions, and such a simplicity bias is widely believed to play a key role in generalization. Yet a broadly applicable, quantitative measure of simplicity remains elusive. We introduce _polynomial representations_ as a distribution-aware, low-dimensional surrogate for neural functions: we approximate a network’s predictive behavior along data-dependent interpolation paths using orthogonal polynomial bases, yielding a compact functional representation. We show that the _effective degree_ of this representation serves as a practical simplicity metric that is predictive of generalization across tasks and architectures, and consistently outperforms existing generalization proxies such as sharpness. Finally, polynomial representations naturally yield a _differentiable_ simplicity regularizer, which consistently improves generalization in image and text classification, fine-tuning contrastive vision–language models, and reinforcement learning.

Social Aspects · Accountability, Transparency, and Interpretability

Zakk Heile, Hayden McTavish, Varun Babbar, Margo Seltzer, Cynthia Rudin

Standard machine learning pipelines often admit many near-optimal models. These “Rashomon sets” pose a range of challenges and opportunities for uncertainty-aware, robust decision making. They allow users to incorporate domain knowledge and preferences that would otherwise be difficult to specify directly in an objective, and they quantify diversity among valid models for a given training dataset and objective function. However, computation of Rashomon sets, even for simple, interpretable model classes such as sparse decision trees, continues to require immense memory and runtime resources. We present PRAXIS, an algorithm to approximate this Rashomon set with orders of magnitude improvement in runtime and memory usage. We validate that PRAXIS regularly recovers almost all of the full Rashomon set. PRAXIS allows researchers and practitioners to scalably model the Rashomon set for real-world datasets.

Theory · Everything Else

Kaiwen Liu, Seba Daniela Villalobos, Qin Zhang

We study the correlation clustering problem in the node-arrival data stream model. Unlike previous work, where the stream consists of the graph's edges, we focus on the setting in which the stream contains only the nodes. This model better reflects many real-world scenarios in which the data stream naturally consists of raw objects (e.g., images, tweets, or websites), and the similar/dissimilar edges are derived through a similarity function. We present *C*$^4$*Approx*, the first streaming algorithm that approximates the cost of correlation clustering using sublinear space in the number of nodes and a constant number of passes. We further complement this result with lower bounds. Experiments on real-world datasets show that by storing only 2\% of the nodes, our algorithm achieves performance comparable to the classic *Pivot* algorithm and the more recent *PrunedPivot* algorithm.

Probabilistic Methods · Monte Carlo and Sampling Methods

Sanghyeok Choi, Sarthak Mittal, Víctor Elvira, Jinkyoo Park, Esmeralda S. Whitammer

This paper proposes a synergy of amortised and particle-based methods for sampling from distributions defined by unnormalised density functions. We state a connection between sequential Monte Carlo (SMC) and neural sequential samplers trained by maximum-entropy reinforcement learning (MaxEnt RL), wherein learnt sampling policies and value functions define proposal kernels and twist functions. Exploiting this connection, we introduce an off-policy RL training procedure for the sampler that uses samples from SMC -- using the learnt sampler as a proposal -- as a behaviour policy that better explores the target distribution. We describe techniques for stable joint training of proposals and twist functions and an adaptive weight tempering scheme to reduce training signal variance. Furthermore, building upon past attempts to use experience replay to guide the training of neural samplers, we derive a way to combine historical samples with annealed importance sampling weights within a replay buffer. On synthetic multi-modal targets (in both continuous and discrete spaces) and the Boltzmann distribution of alanine dipeptide conformations, we demonstrate improvements in approximating the true distribution as well as training stability compared to both amortised and Monte Carlo methods.

Theory · Reinforcement Learning and Planning

Orin Levy, Aviv Rosenberg, Alon Peled-Cohen, Yishay Mansour

We introduce OPO-CMDP, the first policy optimization algorithm for stochastic Contextual Markov Decision Process (CMDPs) under general offline function approximation. Our approach achieves a high probability regret bound of $\widetilde{O}(H^4\sqrt{T|S||A|\log(|\mathcal{F}||\mathcal{P}|)}),$ where $S$ and $A$ denote the state and action spaces, $H$ the horizon length, $T$ the number of episodes, and $\mathcal{F}, \mathcal{P}$ the finite function classes used to approximate the losses and dynamics, respectively. This is the first regret bound with optimal dependence on $|S|$ and $|A|$, directly improving the current state-of-the-art (Qian, Hu, and Simchi-Levi, 2024). These results demonstrate that optimistic policy optimization provides a natural, computationally superior and theoretically near-optimal path for solving CMDPs.

Social Aspects · Accountability, Transparency, and Interpretability

David Rundel, Fabian Fumagalli, Maximilian Muschalik, Bernd Bischl, Matthias Feurer

Shapley values are a principled attribution measure widely used in interpretable machine learning, but their exact computation scales exponentially with the number of players, motivating a wide range of approximation methods based on value-function evaluations of sampled coalitions. This raises the question of whether approximation accuracy can be improved by *adaptively* selecting coalitions for evaluation based on previous outcomes. This is particularly relevant in settings where the value function is costly, and the number of evaluations is severely limited, such as retraining-based feature importance, data valuation, and hyperparameter importance. For this purpose, we propose $\texttt{ShaplEIG}$, a Bayesian experimental design approach that approximates the expensive value function via a Gaussian process surrogate and adaptively selects coalitions based on their expected information gain about the Shapley values. Since Shapley values are a linear function of the value function, we show that the expected information gain is available in *closed form* and *efficiently* computable. In extensive experiments across diverse costly applications, our method consistently improves estimation accuracy over state-of-the-art baselines.

Farzaneh Heidari, Guillaume Rabusseau

Shapley values are a widely used tool for attributing importance and interactions among input variables in black-box models, but their computation involves a function defined over an exponentially large space of subsets. We propose TN-SHAP-G, a framework that exploits structure in graph-structured inputs to compute Shapley values and higher-order interaction indices efficiently. Given a predictor and a fixed masking scheme, TN-SHAP-G learns a compact, graph-aligned multilinear surrogate that approximates the masked-input behavior, represented as a tensor network whose topology mirrors the input graph. Once trained from a small number of oracle queries, the surrogate enables deterministic recovery of first- and higher-order Shapley indices via the multilinear extension, without additional model queries or Monte Carlo variance. Experiments on molecular benchmarks show that the learned factorization closely matches exact Shapley values on small graphs and scales efficiently to larger graphs where sampling-based methods become infeasible.

Deep Learning · Generative Models and Autoencoders

Daniel Geyfman, Felix Draxler, Jan Groeneveld, Hyunsoo Lee, Theofanis Karaletsos, Stephan Mandt

Test-time guidance is a widely used mechanism for steering pre-trained diffusion models toward outcomes specified by a reward function. Existing approaches, however, focus on reward maximization rather than sampling from the true Bayesian posterior, leading to miscalibrated inference. In this work, we show that common test-time guidance methods do not recover the correct posterior distribution and identify the structural approximations responsible for this failure. We then propose consistent alternative estimators that enable calibrated sampling from the Bayesian posterior. Across Bayesian inference and inverse problems, our approach yields substantially improved posterior calibration.

Theory · Learning Theory

Arshia Soltani Moakhar, Faraz Ghahremani, Kiarash Banihashem, MohammadTaghi Hajiaghayi

Decision tree learning has long been a central topic in theoretical computer science, driven by its practical importance. A fundamental and widely used method for decision tree construction is the top-down greedy heuristic, which recursively splits on the most influential variable. Despite its empirical success, theoretical analysis of this heuristic has been limited. A recent breakthrough by Blanc et al. (ITCS, 2020) provided the first rigorous theoretical guarantees for the greedy approach, but only under the uniform distribution. We extend this analysis to the more general and practically relevant setting of arbitrary product distributions. Our main result shows that for any function $f$ computable by an optimal decision tree of size $s$, maximum depth $D_{\text{opt}}$, and average depth $\Delta_{\text{opt}}$, the greedy heuristic constructs an $\epsilon$-approximating tree whose size grows at most with $\exp\bigl(\Delta_{\text{opt}} D_{\text{opt}} \log(e/\epsilon)\bigr)$. In the special case where the optimal tree is a full binary tree, this bound improves upon the bound of Blanc et al. and holds under a strictly broader class of distributions. Moreover, we present an algorithm based on the top-down greedy heuristic that is entirely **parameter-free**—it requires no prior knowledge of the optimal tree's size or depth—offering a practical advantage over Blanc et al.'s method.

Probabilistic Methods · Bayesian Models and Methods

Weifeng Zhang, Wenyuan Zhao, Amir Hossein Rahmati, Yucheng Wang, Zhiyuan Wang, Chao Tian, Xiaoning Qian

Principled uncertainty quantification (UQ) is increasingly recognized as essential for trustworthy artificial general intelligence (AGI). Bayesian Low-Rank Adaptation (LoRA) provides a principled mechanism for uncertainty-aware fine-tuning of large language models (LLMs). However, existing techniques either face scalability constraints, e.g. Laplace-LoRA, or rely on approximate inference schemes that lead to poorly calibrated posterior uncertainty, often manifesting as overconfident predictions under distribution shift. To address this challenge, we propose GPan-LoRA, the first scalable Gaussian Process (GP)-based framework for Bayesian LoRA, which integrates neural network-based sparse GP approximations with amortized variational inference. By preserving the Bayesian function prior and posterior semantics intrinsic to GPs, GPan-LoRA achieves a faithful balance between computational scalability and principled UQ. Empirically, GPan-LoRA produces well-calibrated uncertainty that remains reliable under distribution shift, mitigating overconfident failures while preserving competitive task performance.

Roman Dyachenko, Nikita Gushchin, Kirill Sokolov, Petr Mokrov, Evgeny Burnaev, Aleksandr Korotin

Entropic optimal transport (EOT) in continuous spaces with quadratic cost is a classical tool for solving the domain translation problem. In practice, recent approaches optimize a weak dual EOT objective depending on a single potential, but doing so is computationally not efficient due to the intractable log-partition term. Existing methods typically resolve this obstacle in one of two ways: by significantly restricting the transport family to obtain closed-form normalization (via Gaussian-mixture parameterizations), or by using general neural parameterizations that require simulation-based training procedures. We propose Variational Entropic Optimal Transport (VarEOT), based on an exact variational reformulation of the log-partition $\log \mathbb{E}[\exp(\cdot)]$ as a tractable minimization over an auxiliary positive normalizer. This yields a differentiable learning objective optimized with stochastic gradients and avoids the necessity of MCMC simulations during the training. We provide theoretical guarantees, including finite-sample generalization bounds and approximation results under universal function approximation. Experiments on synthetic data and unpaired image-to-image translation demonstrate competitive or improved translation quality, while comparisons within the solvers that use the same weak dual EOT objective support the benefit of the proposed optimization principle.

Adil Soubki, Miles Cranmer

Symbolic Regression (SR) is the task of finding a closed-form mathematical expression that optimizes some objective. Solving this task is NP-hard. However, SR software routinely discovers accurate, interpretable models without exhaustively searching function space. Motivated by this disconnect between worst-case theory and practical success, we study SR through the lens of *parameterized complexity theory*. In particular, we reanalyze tractability with respect to practically relevant parameters like expression depth, tree size, and number of primitives used. We show that SR is actually fixed-parameter tractable (FPT) under a parametrization over expression depth or tree size, formalizing an explanation for why the bounded-complexity search of popular SR algorithms succeeds. However, SR becomes W[1]-hard when parameterized by the number of variables or primitives used, identifying selection as a source of intractability. We further find lower bounds under the exponential time hypothesis, prove approximation hardness, and rule out polynomial kernels.

Reinforcement Learning · Multi-agent

Luca Viano, Till Freihaut, Emanuele Nevali, Volkan Cevher, Matthieu Geist, Giorgia Ramponi

In this work, we present the first theoretical analysis of multi-agent imitation learning (MAIL) in linear Markov games where both the transition dynamics and each agent's reward function are linear in some given features. We demonstrate that by leveraging this structure, it is possible to replace the state-action level \emph{all policy deviation concentrability coefficient} \citep{freihaut2025rate} with a concentrability coefficient defined at the feature level which can be much smaller than the state-action analog when the features are informative about \emph{states' similarity}. Furthermore, to circumvent the need for any concentrability coefficient, we turn to the interactive setting. We provide the first, computationally efficient, interactive MAIL algorithm for linear Markov games and show that its sample complexity depends only on the dimension of the feature map $d$. Building on these theoretical findings, we propose a deep MAIL interactive algorithm which clearly outperforms BC on games such as Tic-Tac-Toe and Connect4.

Social Aspects · Accountability, Transparency, and Interpretability

Gal Pomerants, Yaniv Nikankin, Anja Reusch, Tomer Tsaban, Ora Schueler-Furman, Yonatan Belinkov

Protein sequences are abundant in repeating segments, both as exact copies and as approximate segments with mutations. These repeats are important for protein structure and function, motivating decades of algorithmic work on repeat identification. Recent work has shown that protein language models (PLMs) identify repeats, by examining their behavior in masked-token prediction. To elucidate their internal mechanisms, we investigate how PLMs detect both exact and approximate repeats. We find that the mechanism for approximate repeats functionally subsumes that of exact repeats. We then characterize this mechanism, revealing two main stages: PLMs first build feature representations using both general positional attention heads and biologically specialized components, such as neurons that encode amino-acid similarity. Then, induction heads attend to aligned tokens across repeated segments, promoting the correct answer. Our results reveal how PLMs solve this biological task by combining language-based pattern matching with specialized biological knowledge, thereby establishing a basis for studying more complex evolutionary processes in PLMs.

Social Aspects · Accountability, Transparency, and Interpretability

Jinyang Liu, Munir Hiabu

Interpretable machine learning requires models that are accurate and structurally faithful to the data. Existing explainability methods rely heavily on additive representations (e.g., GAMs, SHAP, functional ANOVA), which can suffer from signal cancellation and extrapolation in presence of strong interactions. We propose Tensor Separation Learning (TSL), a regression model that learns a sum of separable (rank-1) tensor products via an orthogonal greedy algorithm. By enforcing separability, TSL avoids the information loss inherent in additive projections caused by marginalizing higher-order interactions. The learned TSL model can be fully reconstructed from first-order partial dependence functions of its fitted factors. We establish approximation-rate guarantees for functions with bounded mixed $ p $-th order partial derivatives and demonstrate that TSL competes with black-box models on regression benchmarks. Crucially, TSL improves interpretability by factorizing interactions, allowing users to explicitly disentangle the magnitude of an effect from its direction directly via the fitted factors.

Optimization · Discrete and Combinatorial Optimization

Yang Huang, Yifan Zhang, Jian Cheng

We propose an OT-guided sampling framework for solving graph combinatorial optimization through exact multilinear relaxation. Graph combinatorial optimization problems can be written as quadratic unconstrained binary optimization(QUBO). Leveraging a classical result in combinatorial optimization, we obtain a continuous multi-linear relaxation of QUBO that is exact, in the sense that it preserves the optimal binary solutions. The challenge is that the resulting energy landscape is highly nonconvex. We address this by treating the objective as an energy function and optimizing via sampling from the induced Boltzmann distribution to escape poor local optima. Viewing sampling as transporting a simple reference distribution to the target distribution, we use optimal transport to characterize more efficient probability flow and derive a stochastic optimal control problem whose solution yields an optimal sampling dynamics. We parameterize the control policy with graph neural networks to approximate the optimal control. Experiments show improved solution quality and efficiency over strong combinatorial and learning-based baselines.

General Machine Learning · Scalable Algorithms

Miklós Máté Badó, Kristian Fenech

Influence functions are a standard tool for data debugging and unlearning, but they become impractical for **high-query** subset workloads such as large-$K$ cross-validation, repeated resampling, or interactive what-if analysis as each subset query typically requires an expensive inverse-curvature solve. We introduce **Clustered Influence Functions (CiF)**, which turns subset influence into an **amortized subset oracle**. We build a compact cache once by clustering training gradients, solve a damped Generalised Gauss-Newton system only for cluster means, and answer new subset queries by a linear recombination using cluster membership counts. This yields per-query cost of $O(Cp)$ linear in the cache size $C$, and the number of model parameters $p$. We further provide a diagnostic error bound that decomposes approximation error into a **clustering scatter** term and a **solver residual** term, making the accuracy-compute tradeoff explicit through the cache budget and solver tolerance. Evaluations across MNIST, CIFAR-10, show that CiF matches per-query influence rankings while significantly reducing the total runtime in high-$Q$ regimes, enabling influence-based workflows that are otherwise computationally prohibitive.