论文检索

Theory · Optimization

Jinyi Huang, Jinlong Lei, Guodong Shi

Distributionally Robust Optimization (DRO) is widely used to improve model robustness, with existing methods addressing either geometric perturbations (e.g., input shifts) or statistical contamination (e.g., heavy-tailed noise and outliers) effectively. However, these uncertainty sources often co-exist. Coupling them through a single divergence or optimal transport constraint conflates geometric displacement with loss-based outlierness, which often leads to the discarding of informative high-leverage samples. We introduce nested DRO, a bilevel formulation that combines optimal transport with an outer $\\phi$-divergence constraint to decouple geometric smoothing from statistical robustness. We prove that this structure naturally induces a geometry-invariant, loss-based reweighting mechanism that separates outlier suppression from transport-induced regularization. We derive a tractable strong dual for the resulting non-convex problem and show its equivalence to variance-regularized risk minimization, providing a rigorous theoretical justification for reweighting gains as a natural consequence of dualization. Empirical results on synthetic and real datasets demonstrate that nested DRO consistently outperforms geometry-coupled DRO baselines, particularly under heavy-tailed contamination where preserving high-leverage structure is crucial.

Theory · Optimization

Yuyang Wang, Felix Wang, Zedong Wang, Ijay Narang, Yuzhou Wang, Siva Maguluri

Constant-stepsize stochastic approximation is widely used in learning for computational efficiency. For a fixed stepsize, the iterates typically admit a stationary distribution that is rarely tractable. Prior work shows that as the stepsize $\alpha \downarrow 0$, the centered-and-scaled steady state converges weakly to a Gaussian limit. However, for fixed $\alpha$, this weak convergence offers no usable error bound for approximating the steady-state by its Gaussian limit. This paper provides explicit, non-asymptotic error bounds for fixed $\alpha$. We study (i) stochastic gradient descent on smooth strongly convex objectives, (ii) linear SA, and (iii) contractive nonlinear SA, and we treat both i.i.d. and Markovian noise models to ensure broad applicability. Our main results first give dimension- and stepsize-dependent, explicit bounds in Wasserstein distance between the centered-scaled steady state and its Gaussian limit, with errors that vanish as $\alpha \downarrow 0$. We further derive sharp tail control, comparing the steady-state tail probability to Gaussian tails with an explicit error term that decays in both the deviation level and $\alpha$. Our analysis combines steady-state Stein's method with moment bounds on the SA iterations, and uses Poisson equation techniques to manage temporal dependence in the Markovian noise setting. We adapt the same toolkit to SGD with general convex objectives and suggest non-Gaussian limiting behavior, which is validated in numerical experiments.

Deep Learning · Robustness

Zheng Wang, Yi Zhang, Siddartha Khastgir, carsten maple, Xingyu Zhao

Deep learning (DL) models, despite their remarkable success, remain vulnerable to small input perturbations that can cause erroneous outputs, motivating probabilistic robustness (PR) as a complementary notion to adversarial robustness (AR) for stochastic reliability assessment. However, existing PR formulations assume a fixed, known perturbation distribution, which is often unavailable or misspecified in practice. To address this limitation, we propose non-parametric probabilistic robustness (NPPR), a more conservative PR estimator over an admissible family of perturbation distributions. We instantiate NPPR with a tractable estimator (GMM-based) that supports four dependency structures (independent, label-, input-, and joint-dependent perturbations). We show that NPPR provably interpolates between AR and PR. Experiments on CIFAR-10/100 and TinyImageNet across multiple architectures show that NPPR yields consistently lower (more conservative) PR estimates than PR computed under common assumed distributions (e.g., Gaussian/Uniform), with up to 40\% reduction in representative settings.

Theory · Learning Theory

Hossein Taheri, Avishek Ghosh, Arya Mazumdar

Continual learning, the ability of a model to adapt to an ongoing sequence of tasks without forgetting earlier ones, is a central goal of artificial intelligence. To better understand its underlying mechanisms, we study the limitations of continual learning in a tractable yet representative setting. Specifically, we analyze one-hidden-layer quadratic neural networks trained by gradient descent on a sequence of XOR-cluster datasets with Gaussian noise, where different tasks correspond to clusters with orthogonal means. Our analysis is based on a tight characterization of gradient descent dynamics for the training loss, which yields explicit bounds on the rate of train-time forgetting as functions of the number of iterations, sample size, number of tasks, and hidden-layer width. We then leverage an algorithmic stability framework to bound the generalization gap, leading to corresponding guarantees on test-time forgetting. Together, our results provide the first closed-form guarantees for forgetting in continual learning with neural networks and show how key problem parameters jointly govern forgetting dynamics. Numerical experiments corroborate our theoretical results.

General Machine Learning · Methodology

Terry Tong, Yu Feng, Surbhi Goel, Dan Roth

Large language models can solve algorithmic problems either through direct natural language (NL) reasoning or by generating executable code delegated to an external solver. However, little progress has been made on **understanding why**. Comparing NL reasoning and solver-based pipelines directly is ill-posed: they differ simultaneously in representation space and execution mechanism. We introduce a three-route framework that makes this comparison tractable by introducing an intermediary step---code generation with LLM-based execution. This enables our empirical analysis, which shows a statistically significant gap supporting code $>$ NL by +28.9\% across 48 different algorithmic tasks and 6 models. A statistical analysis indicates that natural-language reasoning does not provide additional decision-relevant information beyond what is already captured by code representations. Consequently, replacing NL traces with code traces incurs minimal performance loss while enabling deterministic execution. A systematic comparison of LLM-based reasoning and external execution further shows that execution, rather than trace representation, is the primary performance bottleneck.

Yakun Wang, Leyang Wang, Song Liu, Taiji Suzuki

Flow-based methods have achieved significant success in various generative modeling tasks, capturing nuanced details within complex data distributions. However, few existing works have exploited this unique capability to resolve fine-grained structural details beyond generation tasks. This paper presents a flow-inspired framework for representation learning. First, we demonstrate that a rectified flow trained using independent coupling is zero everywhere at $t=0.5$ if and only if the source and target distributions are identical. We term this property the \emph{zero-flow criterion}. Second, we show that this criterion can certify conditional independence, thereby extracting \emph{sufficient information} from the data. Third, we translate this criterion into a tractable, simulation-free loss function that enables learning amortized Markov blankets in graphical models and latent representations in self-supervised learning tasks. Experiments on both simulated and real-world datasets demonstrate the effectiveness of our approach.

Theory · Online Learning and Bandits

Joongkyu Lee, Min-hwan Oh

We study optimal experimental design for multinomial logit (MNL) bandits, where an agent repeatedly selects a subset of $K$ items from a ground set of size $N$ and observes single-choice feedback. Unlike linear or generalized linear bandits, MNL bandits have a combinatorial action space, which makes classical optimal design approaches and naive optimization over all subsets computationally intractable. We propose a computationally efficient optimal design framework for MNL models that achieves both statistical efficiency and scalability through two complementary approaches: (i) an exact or certified-approximate reformulation of the design oracle as a $0$-$1$ mixed-integer linear program (MILP) with solver-certified early stopping, and (ii) a fully polynomial-time lifted design that replaces the nonlinear objective with a tractable surrogate. Using the Kiefer-Wolfowitz equivalence theorem, we establish near G-optimality guarantees and characterize the induced statistical-computational trade-offs. As an application, we develop a best assortment identification algorithm for MNL bandits with linear utilities and non-uniform revenues, and prove an instance-dependent sample complexity of $\tilde{\mathcal{O}}\big(\frac{d \log N}{\Delta^2}\big)$, where $d$ is the feature dimension, $N$ is the number of arms, and $\Delta$ is the minimum revenue gap.

Probabilistic Methods · Everything Else

Mengqi Chen, Thomas Berrett, Theodoros Damoulas, Michele Caprio

Distributionally robust optimisation (DRO) minimises the worst-case expected loss over an ambiguity set that can capture distributional shifts in out-of-sample environments. While Huber (linear-vacuous) contamination is a classical minimal-assumption model for an $\varepsilon$-fraction of arbitrary perturbations, including it in an ambiguity set can make the worst-case risk infinite and the DRO objective vacuous unless one imposes strong boundedness or support assumptions. We address these challenges by introducing bulk-calibrated credal ambiguity sets: we learn a high-mass bulk set from data while considering contamination inside the bulk and bounding the remaining tail contribution separately. This leads to a closed-form, finite $\mathrm{mean}+\sup$ robust objective and tractable linear or second-order cone programs for common losses and bulk geometries. Through this framework, we highlight and exploit the equivalence between the imprecise probability (IP) notion of upper expectation and the worst-case risk, demonstrating how IP credal sets translate into DRO objectives with interpretable tolerance levels. Experiments on heavy-tailed inventory control, geographically shifted house-price regression, and demographically shifted text classification show competitive robustness-accuracy trade-offs and efficient optimisation times, using Bayesian, frequentist, or empirical reference distributions.

Deep Learning · Sequential Models, Time series

Chris Cameron, Wangzheng Wang, Nikita Ivanov, Ashmita Bhattacharyya, Didier Chételat, Yingxue Zhang

Looped transformers scale computational depth independent of parameter count by repeatedly applying the same layer. However, training these models over long horizons creates significant optimization challenges. Specifically, it is difficult for looped transformers that start from noise to steer towards a potentially complex output without additional supervision. Diffusion models tackle this issue by corrupting data with varying magnitudes of noise and training the model to reverse it in a single step. However, this process misaligns training and testing behaviour. We introduce Denoising Recursion Models, a method that similarly corrupts data with noise but trains the model to reverse the corruption over multiple recursive steps. This strategy provides a tractable curriculum of intermediate states, while better aligning training with testing and incentivizing non-greedy, forward-looking generation. Through extensive experiments, we showed this approach outperformed the Tiny Recursion Model (TRM) on ARC-AGI, where it recently achieved breakthrough performance.

General Machine Learning · Supervised Learning

Yongxiang Tang, Chao Wang, Jincheng Lu, Yanhua Cheng, Xialong Liu, Peng Jiang

Learning to rank can be cast as a probabilistic modeling problem over permutations, where the goal is to estimate the likelihood of an observed total ordering of items. This formulation naturally involves full-order probabilities of the form $\mathbb{P}(\mathrm{z}_1 < \cdots < \mathrm{z}_n)$, whose exact computation and optimization are intractable due to the factorial growth of the permutation space with respect to list size. We introduce the *Full-Order Bound* (FOB), a tractable lower bound on the probability of an observed ordering, constructed from a subset of ordering constraints that factorizes across items while avoiding low-dimensional surrogate objectives and preserving order-reversal invariance. FOB induces a convex inner tightening problem over latent cut points, which we solve efficiently during training using a *safe-region gradient ascent* (SRGA) procedure. Experiments on synthetic ranking tasks and large-scale learning-to-rank benchmarks show that FOB consistently improves performance over pairwise and listwise surrogates, Plackett--Luce style sequential factorization models, and differentiable sorting baselines. Code is available at [https://anonymous.4open.science/r/FOB_2026-46C4](https://anonymous.4open.science/r/FOB_2026-46C4).

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.

Theory · Deep Learning

Jack T. Parley, Francesco Cagnetta, Matthieu Wyart

Understanding how the structure of language can be learned from sentences alone is a central question in both cognitive science and machine learning. Studies of the internal representations of Large Language Models (LLMs) support their ability to parse text when predicting the next word, while representing semantic notions independently of surface form. Yet, which data statistics make these feats possible, and how much data is required, remain largely unknown. Probabilistic context-free grammars (PCFGs) provide a tractable testbed for studying these questions. However, prior work has focused either on the post-hoc characterization of the parsing-like algorithms used by trained networks; or on the learnability of PCFGs with fixed syntax, where parsing is unnecessary. Here, we *(i)* introduce a tunable class of PCFGs in which both the degree of ambiguity and the correlation structure across scales can be controlled; *(ii)* provide a learning mechanism---an inference algorithm inspired by the structure of deep convolutional networks---that links learnability and sample complexity to specific language statistics; and *(iii)* validate our predictions empirically across deep convolutional and transformer-based architectures. Overall, we propose a unifying framework where correlations at different scales lift local ambiguities, enabling the emergence of hierarchical representations of the data.

General Machine Learning · Unsupervised and Semi-supervised Learning

Zhi Zhou, Ming Yang, Shi-Yu Tian, Kun-Yang Yu, Lan-Zhe Guo, Yu-Feng Li

Test-time adaptation (TTA) aims to adapt models to maintain reliable performance on non-stationary test streams without requiring labeled data. Despite its empirical success, the learnability of TTA under distributional non-stationarity remains unexplored. A key challenge is lacking of a principled theoretical framework that simultaneously aligns with the TTA objective and captures both continuously evolving distribution shifts and intrinsic information constraints. To address this gap, we propose the first theoretical framework for characterizing the learnability of TTA, introducing the notions of $(\epsilon,\delta)$-Recovery Complexity and $(\epsilon,\rho)$-TTA Learnability. Recovery complexity quantifies the minimal time required for a TTA algorithm to recover to a target excess risk following a distribution shift, and is further generalized to define $(\epsilon,\rho)$-TTA Learnability, which measures the long-term reliability of TTA algorithms over non-stationary data streams. Within this framework, we introduce a novel temporally dependent discrete surrogate method that models complex non-stationary test streams, enabling a unified and tractable analysis of both gradual and abrupt distribution shifts. We derive order-wise matching lower and upper bounds on recovery complexity through information-theoretic and optimization-based analysis. Our results uncover fundamental limits of TTA, highlight the intrinsic adaptivity-information trade-off of TTA algorithms, and provide the first unified learnability guarantees that go beyond regret-based perspectives.

Theory · Interpretability and Visualization

Siwei Wang, Yifei Shen, Haoran Sun, Shi Feng, Shang-Hua Teng, Li Dong, Yaru Hao, Wei Chen

Recent reinforcement learning (RL) methods have substantially enhanced the planning capabilities of Large Language Models (LLMs), yet the theoretical basis for their effectiveness remains elusive. In this work, we investigate RL's benefits and limitations through a tractable graph-based abstraction, focusing on policy gradient (PG) and Q-learning methods. Our theoretical analyses reveal that supervised fine-tuning (SFT) may introduce co-occurrence-based spurious solutions, whereas RL achieves correct planning primarily through exploration, underscoring exploration’s role in enabling better generalization. However, we also show that PG suffers from diversity collapse, where output diversity decreases during training and persists even after perfect accuracy is attained. By contrast, Q-learning provides two key advantages: off-policy learning and diversity preservation at convergence. We further demonstrate that careful reward design is necessary to prevent Q-value bias in Q-learning. Finally, applying our framework to the real-world planning benchmark Blocksworld, we confirm that these behaviors manifest in practice.

Hao Wang, Licheng Pan, Yuan Lu, Zhixuan Chu, Xiaoxi Li, Shuting He, Zi Chan, Qingsong Wen, Haoxuan Li, Zhouchen Lin

Training time-series forecast models requires aligning the conditional distribution of model forecasts with that of the label sequence. The standard direct forecast (DF) approach seeks to minimize the conditional negative log-likelihood of the label sequence, typically estimated using the mean squared error. However, this estimation proves to be biased in the presence of label autocorrelation. In this paper, we propose DistDF, which achieves alignment by alternatively minimizing a discrepancy between the conditional forecast and label distributions. Because conditional discrepancies are difficult to estimate from finite time-series observations, we introduce a newly proposed joint-distribution Wasserstein discrepancy for time-series forecasting, which provably upper bounds the conditional discrepancy of interest. This discrepancy admits tractable, differentiable estimation from empirical samples and integrates seamlessly with gradient-based training. Extensive experiments show that DistDF improves the performance diverse forecast models and achieves the state-of-the-art forecasting performance. Code is available at https://anonymous.4open.science/r/DistDF-F66B.

Optimization · Optimization and Learning under Uncertainty

Jiaqi Wen, Jianyi Yang

This paper studies Distributionally Robust Optimization (DRO), a fundamental framework for enhancing the robustness and generalization of statistical learning and optimization. An effective ambiguity set for DRO must involve distributions that remain consistent to the nominal distribution while being diverse enough to account for a variety of potential scenarios. Moreover, it should lead to tractable DRO solutions. To this end, we propose generative model-based ambiguity sets that capture various adversarial distributions beyond the nominal support space while maintaining consistency with the nominal distribution. Building on this generative ambiguity modeling, we propose DRO with Generative Ambiguity Set (GAS-DRO), a tractable DRO algorithm that solves the inner maximization over the parameterized generative model space. We formally establish the stationary convergence performance of GAS-DRO. We implement GAS-DRO with a diffusion model and empirically demonstrate its superior Out-of-Distribution (OOD) generalization performance in ML tasks.

Computer Vision · 3D Rendering & Reconstruction

Yecong Wan, Mingwen Shao, Renlong Wu, Wangmeng Zuo

In this work, we present Color3D, a highly adaptable framework for colorizing both static and dynamic 3D scenes from monochromatic inputs, delivering visually diverse and chromatically vibrant reconstructions with flexible user-guided control. In contrast to existing methods that focus solely on static scenarios and enforce multi-view consistency by averaging color variations which inevitably sacrifice both chromatic richness and controllability, our approach is able to preserve color diversity and steerability while ensuring cross-view and cross-time consistency. In particular, the core insight of our method is to colorize only a single key view and then fine-tune a personalized colorizer to propagate its color to novel views and time steps. Through personalization, the colorizer learns a scene-specific deterministic color mapping underlying the reference view, enabling it to consistently project corresponding colors to the content in novel views and video frames via its inherent inductive bias. Once trained, the personalized colorizer can be applied to infer consistent chrominance for all other images, enabling direct reconstruction of colorful 3D scenes with a dedicated Lab color space Gaussian splatting representation. The proposed framework ingeniously recasts complicated 3D colorization as a more tractable single image paradigm, allowing seamless integration of arbitrary image colorization models with enhanced flexibility and controllability. Extensive experiments across diverse static and dynamic 3D colorization benchmarks substantiate that our method can deliver more consistent and chromatically rich renderings with precise user control. Project Page: https://yecongwan.github.io/Color3D/.

Applications · Genetics, Cell Biology, Health, etc

Nic Fishman, Gokul Gowri, Tanush Kumar, Jiaqi Lu, Valentin De Bortoli, Jonathan Gootenberg, Omar Abudayyeh

Many modern biological assays, including RNA sequencing, yield integer-valued counts that reflect the number of molecules detected. These measurements are often not at the desired resolution: while the unit of interest is typically a single cell, many measurement technologies produce counts aggregated over sets of cells. Although recent generative frameworks such as diffusion and flow matching have been extended to non-Euclidean and discrete settings, it remains unclear how best to model integer-valued data or how to systematically deconvolve aggregated observations. We introduce Count Bridges, a stochastic bridge process on the integers that provides an exact, tractable analogue of diffusion-style models for count data, with closed-form conditionals for efficient training and sampling. We extend this framework to enable direct training from aggregated measurements via an Expectation-Maximization approach that treats unit-level counts as latent variables. We demonstrate state-of-the-art performance on integer distribution matching benchmarks, comparing against flow matching and discrete flow matching baselines across various metrics. We then apply Count Bridges to two large-scale problems in biology: modeling single-cell gene expression data at the nucleotide resolution, with applications to deconvolving bulk RNA-seq, and resolving multicellular spatial transcriptomic spots into single-cell count profiles. Our methods offer a principled foundation for generative modeling and deconvolution of biological count data across scales and modalities.

Theory · Probabilistic Methods

Zijing Ou, Chinmay Pani, Yingzhen Li

Discrete diffusion models have become highly effective across various domains. However, real-world applications often require the generative process to adhere to certain constraints. To this end, we propose a Sequential Monte Carlo (SMC) framework that enables scalable inference-time control of discrete diffusion models through principled importance weighting and optimal proposal construction. Specifically, our approach derives tractable importance weights for a range of intermediate targets and characterises the optimal proposal, for which we develop two practical approximations: a first-order gradient-based approximation and an amortised proposal trained to minimise the log-variance of the importance weights. Empirical results across synthetic tasks, language modelling, biology design, and text-to-image generation demonstrate that our framework enhances controllability and sample quality, highlighting the effectiveness of SMC as a versatile recipe for scaling discrete diffusion models at inference time.

Deep Learning · Theory

Guillaume Braun, Bruno Loureiro, Minh Ha Quang, Masaaki Imaizumi

Scaling laws describe how learning performance improves with data, compute, or training time, and have become a central theme in modern deep learning. We study this phenomenon in a canonical nonlinear model: phase retrieval with anisotropic Gaussian inputs whose covariance spectrum follows a power law. Unlike the isotropic case, where dynamics collapse to a two-dimensional system, anisotropy yields a qualitatively new regime in which an infinite hierarchy of coupled equations governs the evolution of the summary statistics. We develop a tractable reduction that reveals a three-phase trajectory: (i) fast escape from low alignment, (ii) slow convergence of the summary statistics, and (iii) spectral-tail learning in low-variance directions. From this decomposition, we derive explicit scaling laws for the mean-squared error, showing how spectral decay dictates convergence times and error curves. Experiments confirm the predicted phases and exponents. These results provide the first rigorous characterization of scaling laws in nonlinear regression with anisotropic data, highlighting how anisotropy reshapes learning dynamics.