Conditional diffusion models appear capable of compositional generalization, i.e., generating convincing samples for out-of-distribution combinations of conditioners, but the mechanisms underlying this ability remain unclear. To make this concrete, we study length generalization, the ability to generate images with more objects than seen during training. In a controlled CLEVR setting (Johnson et al., 2017), we find that length generalization is achievable in some cases but not others, suggesting that models only sometimes learn the underlying compositional structure. We then investigate locality as a structural mechanism for compositional generalization. Prior works proposed score locality as a mechanism for creativity in unconditional diffusion models (Kamb & Ganguli, 2024; Niedoba et al., 2024), but did not address flexible conditioning or compositional generalization. In this paper, we prove an exact equivalence between a specific compositional structure (*conditional projective composition*) (Bradley et al., 2025) and scores with sparse dependencies on both pixels and conditioners (*local conditional scores*). This theory also extends to compositions of concepts (such as style+content) in feature-space. We validate our theory empirically: CLEVR models that succeed at length generalization exhibit local conditional scores, while those that fail do not. Furthermore, we show that a causal intervention explicitly enforcing local conditional scores enables length generalization in a previously failing model. Finally, we investigate feature-space compositionality in color-conditioned CLEVR, and find preliminary evidence of compositional structure and corresponding local mechanisms in SDXL.
论文检索
输入标题、作者或关键词，从 100,903 篇学术成果中精准定位
Diffusion models are distinguished by their exceptional generative performance, particularly in producing high-quality samples through iterative denoising. While current theory suggests that the number of denoising steps required for accurate sample generation should scale linearly with data dimension, this does not reflect the practical efficiency of widely used algorithms like Denoising Diffusion Probabilistic Models (DDPMs). This paper investigates the effectiveness of diffusion models in sampling complex high-dimensional distributions that can be well-approximated by Gaussian Mixture Models (GMMs). For these distributions, our main result shows that DDPM takes at most $\widetilde{O}(1/\varepsilon)$ iterations to attain an $\varepsilon$-accurate distribution in total variation (TV) distance, independent of both the ambient dimension $d$ and the number of components $K$, up to logarithmic factors. Furthermore, this result remains robust to score estimation errors. These findings highlight the remarkable effectiveness of diffusion models in high-dimensional settings given the universal approximation capability of GMMs, and provide theoretical insights into their practical success.
We study the robustness of stochastic mirror descent (SMD) under heavy-tailed noise, focusing on whether the method retains its convergence guarantees when run with infinite-variance stochastic gradient input. To address this question in a principled manner, we begin by introducing a continuous-time model of SMD as a stochastic differential equation (SDE) driven by a centered Lévy noise process with finite $p$-th order moments, $1 < p \leq 2$. This scheme---which we call the Lévy mirror flow (LMF)---arises naturally as the scaling limit of SMD in the presence of heavy-tailed noise. In particular, when $p < 2$---the heavy noise regime---the trajectories of LMF generically exhibit jump discontinuities of arbitrary magnitude which, if frequent enough, lead to infinite variance. Nonetheless, despite this highly singular behavior, we show that LMF attains $\epsilon$-optimality within $\mathcal{O}(\epsilon^{-p/(p-1)})$ time in the convex case, and within $\tilde{\mathcal{O}}(\epsilon^{-1/(p-1)})$ time for (relatively) strongly convex objectives. These guarantees provide a transparent characterization of the impact of frequent long jumps on the convergence of the process, and percolate to a series of matching discrete-time guarantees for several variants of SMD under heavy-tailed noise.
Probabilistic Methods · Monte Carlo and Sampling Methods
History-dependent sampling can reduce long-run Monte Carlo variance by discouraging redundant revisits, but existing schemes typically encode history through empirical measure on finite state spaces, which is infeasible in high-dimensional discrete configuration spaces or ill-posed in continuous domains. We propose *Score-Repellent Monte Carlo* (SRMC) framework that summarizes trajectory history by a fixed, $d$-dimensional running average of score evaluations and converts it into a history-dependent surrogate target via an exponential *score tilt*. The resulting surrogate family is normalization-free in the standard MCMC sense, yielding a generic wrapper: at each iteration, any standard base kernel designed for the target $\pi$ can be run on the current surrogate $\pi_{\theta_n}$ while updating the history online. We analyze the coupled evolution of any estimator and the history recursion using stochastic approximation with controlled Markovian noise, establishing almost sure convergence and a joint central limit theorem. We identify regimes where the asymptotic covariance decreases as the repellence strength $\alpha$ increases, exhibiting a scaling of $O(1/\alpha)$, reproducing near-zero variance effect but now on general state spaces with constant memory. Empirical results across continuous targets and discrete energy-based models demonstrate that SRMC delivers notable improvements in estimator variance and in effectively covering modes in Gaussian mixtures, all while retaining $O(d)$ memory usage and minimal overhead per iteration.
We study the problem of functional retargeting: learning dexterous manipulation policies to track object states from human hand-object demonstrations. We focus on long-horizon, bimanual tasks with articulated objects, which are challenging due to large action space, spatiotemporal discontinuities, and the embodiment gap between human and robot hands. We propose DexMachina, a novel curriculum-based algorithm: the key idea is to use virtual object controllers with decaying strength: an object is first driven automatically towards its target states, such that the policy can gradually learn to take over under motion and contact guidance. We release a simulation benchmark with a diverse set of tasks and dexterous hands, and show that DexMachina significantly outperforms baseline methods. Our algorithm and benchmark enable a functional comparison for hardware designs, and we present key findings informed by quantitative and qualitative results. With the recent surge in dexterous hand development, we hope this work will provide a useful platform for identifying desirable hardware capabilities and lower the barrier for contributing to future research. Videos and more at \url{dexmachina-submission.github.io}
Deep Learning · Theory
We consider supervised learning with $n$ labels and show that layerwise SGD on residual networks can efficiently learn a class of hierarchical models. This model class assumes the existence of an (unknown) label hierarchy $L_1 \subseteq L_2 \subseteq \dots \subseteq L_r = [n]$, where labels in $L_1$ are simple functions of the input, while for $i > 1$, labels in $L_i$ are simple functions of simpler labels. Our class surpasses models that were previously shown to be learnable by deep learning algorithms, in the sense that it reaches the depth limit of efficient learnability. That is, there are models in this class that require polynomial depth to express, whereas previous models can be computed by log-depth circuits. Furthermore, we suggest that learnability of such hierarchical models might eventually form a basis for understanding deep learning. Beyond their natural fit for domains where deep learning excels, we argue that the mere existence of human ``teachers" supports the hypothesis that hierarchical structures are inherently available. By providing granular labels, teachers effectively reveal ``hints'' or ``snippets'' of the internal algorithms used by the brain. We formalize this intuition, showing that in a simplified model where a teacher is partially aware of their internal logic, a hierarchical structure emerges that facilitates efficient learnability.
Probabilistic Methods · Monte Carlo and Sampling Methods
We propose a training-free conditional sampling method for flow matching models based on importance sampling. Because a naïve application of importance sampling suffers from weight degeneracy in high-dimensional settings, we modify and incorporate a resampling technique in sequential Monte Carlo (SMC) during intermediate stages of the generation process. To encourage generated samples to diverge along distinct trajectories, we derive a stochastic flow with adjustable noise strength to replace the deterministic flow at the intermediate stage. Our framework requires no additional training, while providing theoretical guarantees of asymptotic accuracy. Experimentally, our method significantly outperforms existing approaches on conditional sampling tasks for MNIST and CIFAR-10. We further demonstrate the applicability of our approach in higher-dimensional, multimodal settings through text-to-image generation experiments on CelebA-HQ.
Theory · Learning Theory
Foundation models provide strong but biased priors for downstream tasks with limited labeled data. We formalize black-box assisted nonparametric regression where $\|f^*-f_0\|_{L_2(P_X)}\le\delta$ for unknown $\delta$. We characterize the minimax risk, revealing a phase transition at $\delta_c(n)\asymp n^{-\beta/(2\beta+d)}$ with optimal rate $\min\{\delta^2, n^{-2\beta/(2\beta+d)}\}$. Our Safe Black-Box Residual Estimator integrates zero-initialization (a strong inductive bias) with a holdout selection mechanism. This approach achieves the minimax rate while avoiding negative transfer. Experiments on synthetic data, CIFAR-100 (CLIP), and AG News (Qwen3-8B) validate the theory, improving sample efficiency (e.g., CIFAR-100 at $n=2000$: from 59.4\% zero-shot to 66.7\%).
Theory · Game Theory
An AI agent will learn a desired goal more effectively if it does not resist the training process, but many partially learned goals incentivize an AI to avoid further goal updates. We would like goals to be corrigible, meaning they allow requested changes, so that we can confidently correct errors and shut down the AI if necessary. Despite this being a crucial safety property, the existing literature does not specify goals that are both corrigible and competitive with alternatives. We introduce a transformation that constructs a corrigible version of nearly any goal, without sacrificing performance. This is done by eliciting predictions of reward conditional on costlessly preventing updates, and having that target be pursued myopically. These goals are then shown to lead to optimal performance among the class of corrigible goals, incentivize allowing mid-action overrides, disincentivize deliberate self-modification, and induce corrigible behavior in gridworld settings.
General Machine Learning · Scalable Algorithms
Sliced optimal transport (SOT), or sliced Wasserstein (SW) distance, is widely recognized for its statistical and computational scalability. In this work, we further enhance computational scalability by proposing the first method for estimating SW from sample streams, called streaming sliced Wasserstein (Stream-SW). To define Stream-SW, we first introduce a streaming estimator of the one-dimensional Wasserstein distance (1DW). Since the 1DW has a closed-form expression, given by the absolute difference between the quantile functions of the compared distributions, we leverage quantile approximation techniques for sample streams to define a streaming 1DW estimator. By applying the streaming 1DW to all projections, we obtain Stream-SW. The key advantage of Stream-SW is its low memory complexity while providing theoretical guarantees on the approximation error. We demonstrate that Stream-SW achieves a more accurate approximation of SW than random subsampling, with lower memory consumption, when comparing Gaussian distributions and mixtures of Gaussians from streaming samples. Additionally, we conduct experiments on point cloud classification, point cloud gradient flows, and streaming change point detection to further highlight the favorable performance of the proposed Stream-SW.
Deep Learning · Theory
Natural language data follows a power-law distribution, with most knowledge and skills appearing at very low frequency. While a common intuition suggests that reweighting or curating data toward a uniform distribution may help models better learn these long-tail skills, we find a counterintuitive result: across a wide range of compositional reasoning tasks, such as state tracking and multi-step arithmetic, training under power-law distributions consistently outperforms training under uniform distributions. To understand this advantage, we introduce a minimalist skill-composition task and show that learning under a power-law distribution provably requires significantly less training data. Our theoretical analysis reveals that power law sampling induces a beneficial asymmetry that improves the pathological loss landscape, which enables models to first acquire high-frequency skill compositions with low data complexity, which in turn serves as a stepping stone to efficiently learn rare long-tailed skills. Our results offer an alternative perspective on what constitutes an effective data distribution for training models.
Applications · Computer Vision
Multimodal fusion object detection faces a substantial modality gap at the same backbone stage. This makes predefined stage-aligned fusion insufficient for cross-stage interactions. We propose MFH-NAS, a hybrid neural architecture search framework that automatically discovers fusion architectures to better leverage cross-modal complementarity. MFH-NAS searches both local fusion primitives and stage-level fusion connectivity. It targets fusion operator design and fusion stage selection. It couples differentiable search with evolutionary search. Differentiable search learns architecture parameters for local fusion primitives. Evolutionary search explores global fusion topologies, including stage selection and cross-stage connection patterns. The joint search balances exploitation and exploration and mitigates premature convergence. It yields fusion structures that strengthen cross-stage interactions.We evaluate MFH-NAS on three public benchmarks, LLVIP, RGBT-Tiny, and M3FD. MFH-NAS consistently outperforms handcrafted fusion-stage designs and prior stage-searching NAS baselines, improving mAP@0.5 from 85.3% to 88.2% over strong fixed-stage fusion methods and delivering gains across all benchmarks.
We consider the computational problem of compacting Tsetlin Machine (TM) classifiers by reducing the number of propositional clauses while preserving predictive accuracy. TMs trained with limited clause capacity often perform poorly because stochastic optimization cannot reliably find the few precise clauses needed in a vast configuration space. High-quality compact subsets also exist for larger TMs. The main challenge is to extract them. Heuristic pruning does not work for TMs because clauses interact through Boolean logic. A clause is unimportant in isolation, but it becomes critical when others are removed. We formalize compression as the Minimum Discriminating Clause Set (MDCS) problem: find the smallest subset of clauses that preserves the trained model's separation of training samples. We prove that MDCS is NP-hard. We solve MDCS via weighted partial Maximum Satisfiability (MaxSAT). A partition-and-merge strategy allows us to scale to 100K samples. MaxSAT compression significantly outperforms direct training on all but one of 13 datasets at matched capacity, with improvements up to 26 percentage points and a median of 6 percentage points.
General Machine Learning · Everything Else
Randomized linear algebra (RLA) algorithms are essential for scaling scientific computing and machine learning, yet their discovery remains mostly a manual process that requires deep expert knowledge and inspiration. While Reinforcement Learning (RL) offers a pathway to automation, standard approaches struggle with sparse reward landscapes and vast search spaces inherent to high-performing RLA algorithms. We present RL4RLA, a general RL framework that automates the discovery of interpretable, symbolic RLA algorithms. Unlike black-box approaches, our method builds explicit algorithms from basic linear algebra primitives, ensuring verifiable and implementable representations. To enable efficient discovery, we introduce: (1) a numerical curriculum that progressively increments problem difficulty to encode domain-based inductive bias; (2) Monte Carlo Graph Search (MCGS), which optimizes exploration by identifying and merging equivalent partial algorithms. We demonstrate that RL4RLA rediscovers state-of-the-art methods—including sketch-and-precondition solvers, Randomized Kaczmarz, and Newton Sketch—and can be targeted to produce algorithms optimized for specific trade-offs between accuracy, speed, and stability.
Deep Learning · Large Language Models
Large language model (LLM) agents increasingly rely on external tools such as search engines to solve complex, multi-step problems, yet their rollouts are structurally heterogeneous: variations in tool-call number, placement, and outcomes induce distinct behaviors and reward distributions. As a result, policy gradient methods with a single global baseline suffer from *cross-stratum bias*, an "apples-to-oranges" comparison that distorts credit assignment and impedes exploration. To address this issue, we propose *Stratified GRPO*. Its core component, *Stratified Advantage Normalization* (SAN), partitions trajectories into homogeneous strata based on structural properties and computes advantages locally within each stratum, ensuring comparisons only among true peers. We show that SAN eliminates cross-stratum bias, yields conditionally unbiased unit-variance estimates within strata, and preserves the global unbiasedness and unit-variance properties of standard normalization, resulting in a more reliable learning signal. To improve robustness in finite-sample regimes, we further linearly blend SAN with the global estimator. Experiments on factual QA and deep-research agent benchmarks demonstrate that Stratified GRPO consistently outperforms GRPO by up to 12.6 points, achieving higher training rewards, improved training stability, and more effective search policies. These results establish stratification as a principled remedy for structural heterogeneity in RL for LLM search agents.
Deep Learning · Large Language Models
Multimodal large language models (MLLMs) have substantially advanced video misinformation detection through unified multimodal reasoning, but they often rely on fixed-depth inference and place excessive trust in internally generated assumptions, particularly in scenarios where critical evidence is sparse, fragmented, or requires external verification. To address these limitations, we propose FactGuard, an agentic framework for video misinformation detection that formulates verification as an iterative reasoning process built upon MLLMs. FactGuard explicitly assesses task ambiguity and selectively invokes external tools to acquire critical evidence, enabling progressive refinement of reasoning trajectories. To further strengthen this capability, we introduce a two-stage training strategy that combines domain-specific agentic supervised fine-tuning with decision-aware reinforcement learning to optimize tool usage and calibrate risk-sensitive decision making. Extensive experiments on three public benchmarks demonstrate that FactGuard consistently outperforms state-of-the-art methods in both verification accuracy and reliability.
General Machine Learning · Causality
Amortized causal inference via Prior-data Fitted Networks (PFNs) has emerged as a promising paradigm, enabling zero-shot estimation of causal effects without the need for dataset-specific model tuning. However, the principled effectiveness of unified pre-training across general interventional regimes remains an underexplored question. In this paper, we investigate interventions on subsets of variables within Structural Causal Models (SCMs) and identify a fundamental theoretical limitation of current pre-training approaches. Theoretically, we prove that a single observational SCM induces an exponentially large space of interventional distributions, resulting in a phenomenon we term prior uncoverage. Consequently, this uncoverage yields a mismatch between the learned meta-prior and the true grounding prior, leading to unavoidable posterior inconsistency and estimation bias. To address this, we posit that fine-tuning is a fundamental necessity and propose a target-specific strategy named Point-Wise Interventional Fine-tuning (PWF), enabling the local generalization property. We further scale this approach via Meta-Sampling Fine-tuning (MSF) from a budgeted active learning perspective, thereby achieving uniform generalization on any interventional distribution.
Deep Learning · Sequential Models, Time series
Irregular Multivariate Time Series (IMTS) arise naturally in many real-world domains, yet their irregular sampling patterns pose significant challenges for effective modeling. Existing approaches for IMTS fall into two categories: architecture-based and data-based methods. Architecture-based methods require specialized modeling for IMTS, limiting reuse of established Multivariate Time Series (MTS) models, data-based methods convert IMTS into regular time series through imputation or interpolation, often introducing artificial values that distort temporal dynamics. In this work, we propose a novel input-embedding-based approach for modeling the IMTS. Our method preserves the original MTS backbone and operates directly on IMTS. We introduce QuITE (Query-based Irregular Time-series Embedding), a simple yet effective, backbone-agnostic embedding module that enables MTS models to directly process IMTS. QuITE leverages a set of learnable query tokens to aggregate irregular observations via a single self-attention layer, producing fixed-dimensional latent representations. Extensive experiments on real-world benchmarks demonstrate that QuITE consistently improves the performance of existing MTS models, achieving average relative performance gains up to 45.9% across diverse datasets and backbone architectures.
General Machine Learning · Online Learning, Active Learning and Bandits
In reinforcement learning, human preference feedback is emerging as a viable alternative to expert-designed reward functions, which can be difficult to engineer in real-world problems. However, despite the growing importance of preference feedback, how to effectively *elicit* preferences remains a fundamental open problem. This work focuses on the *compatible reward identification* task. The aim is to derive, starting from preference feedback, a reward function compatible with the observed preferences and accurate across the *entire* state-action space, ensuring higher transferability, safety, and interpretability. Indeed, the most common *reinforcement learning from human feedback* objective is to learn the *optimal policy*, requiring accuracy only in the portion of the state-action space that the agent visits. However, this goal cannot provide the same guarantees as compatible reward identification. First, we discuss commonalities and differences between the two goals. Then, we consider deterministic preferences, deriving the minimum number of interactions needed to identify the set of compatible rewards, and showing that using fewer queries may lead to arbitrarily large suboptimality. Finally, we focus on stochastic preferences generated via the Bradley-Terry (BT) model. We introduce the concepts of *query basis* and its *index*, relating them to the problem complexity. Upon this, we discuss the connection between the index of a basis and the BT model, as well as the limitations that the model induces in this setting. Additionally, we devise an algorithm to identify a nearly-optimal query basis with polynomial human query complexity.
General Machine Learning · Everything Else
Strategic classification studies the interaction between decision models and agents who strategically manipulate their features for favorable outcomes. Existing SC frameworks typically rely on the idealized assumption that agents are strictly rational. However, evidence from behavioral economics and psychology consistently shows that real-world decision-making is often shaped by cognitive biases, deviating from pure rationality. To formalize this limitation, we identify and define a new problem setting, termed the behaviorally realistic strategic classification problem, where agents’ strategic manipulations deviate from full rationality due to psychological biases. Motivated by the identified limitation, we propose the Prospect-Guided Strategic Framework (Pro-SF) to address the problem, a principled framework grounded in prospect theory to model and learn under behaviorally realistic strategic responses. Specifically, to capture behaviorally realistic strategic manipulations, our framework reformulates the Stackelberg-style interaction between agents and the decision-maker by incorporating three key mechanisms inspired by prospect theory, including the asymmetry between benefits and costs, different subjective reference points, and non-rational probability distortion. Experiments on synthetic and real-world datasets establish Pro-SF as a behaviorally grounded approach to strategic classification, bridging machine learning and behavioral economics for more reliable deployment in the real world.