论文检索

Deep Learning · Foundation Models

Sicheng Liu, Xunkai Li, Daohan Su, Ru Zhang, Hongchao Qin, Rong-Hua Li, Guoren Wang

Graph Foundation Models (GFMs) have achieved remarkable success in generalizing across diverse domains. However, they mainly focus on Text-Attributed Graphs (TAGs), leaving Multimodal-Attributed Graphs (MAGs) largely untapped. Developing Multimodal Graph Foundation Models (MGFMs) allows for leveraging the rich multimodal information in MAGs, and extends applicability to broader types of downstream tasks. While recent MGFMs integrate diverse modality information, our empirical investigation reveals two fundamental limitations of existing MGFMs: (1)they fail to explicitly model modality interaction, essential for capturing intricate cross-modal semantics beyond simple aggregation, and (2)they exhibit sub-optimal modality alignment, which is critical for bridging the significant semantic disparity between distinct modal spaces. To address these challenges, we propose PLANET (graPh topoLogy-aware modAlity iNteraction and alignmEnT), a novel framework employing a Divide-and-Conquer strategy to decouple modality interaction and alignment across distinct granularities. At the embedding granularity, (1)Embedding-wise Domain Gating (EDG) performs local semantic enrichment by adaptively infusing topology-aware cross-modal context, achieving modality interaction. At the node granularity, (2)Node-wise Discretization Retrieval (NDR) ensures global modality alignment by constructing a Discretized Semantic Representation Space (DSRS) to bridge modality gaps. Extensive experiments demonstrate that PLANET significantly outperforms state-of-the-art baselines across diverse graph-centric and multimodal generative tasks.

Probabilistic Methods · Monte Carlo and Sampling Methods

Wei Guo, Yuchen Zhu, Xiaochen Du, Juno Nam, Yongxin Chen, Rafael Gomez-Bombarelli, Guan-Horng Liu, Molei Tao, Jaemoo Choi

Learning discrete neural samplers is challenging due to the lack of gradients and combinatorial complexity. While stochastic optimal control (SOC) and Schrödinger bridge (SB) provide principled solutions, efficient SOC solvers like adjoint matching (AM), which excel in continuous domains, remain unexplored for discrete spaces. We bridge this gap by revealing that the core mechanism of AM is *state-space agnostic*, and introduce **discrete ASBS**, a unified framework that extends AM and adjoint Schrödinger bridge sampler (ASBS) to discrete spaces. Theoretically, we analyze the optimality conditions of the discrete SB problem and its connection to SOC, identifying a necessary cyclic group structure on the state space to enable this extension. Empirically, discrete ASBS achieves competitive sample quality with significant advantages in training efficiency and scalability.

Theory · Reinforcement Learning and Planning

Haoqun Cao, Tengyang Xie

Behavior cloning is a fundamental paradigm in machine learning, enabling policy learning from expert demonstrations across robotics, autonomous driving, and generative models. Autoregressive models like transformer have proven remarkably effective, from large language models (LLMs) to vision-language-action systems (VLAs). However, applying autoregressive models to continuous control requires discretizing actions through quantization, a practice widely adopted yet poorly understood theoretically. This paper provides theoretical foundations for this practice. We analyze how quantization error propagates along the horizon and interacts with statistical sample complexity. We show that behavior cloning with quantized actions and log-loss achieves optimal sample complexity—matching existing lower bounds—and incurs only polynomial horizon dependence on quantization error, provided the dynamics are stable and the policy satisfies a probabilistic smoothness condition. We further characterize when different quantization schemes satisfy or violate these requirements, and propose a model-based augmentation that provably improves the error bound without requiring policy smoothness. Finally, we establish fundamental limits that jointly capture the effects of quantization error and statistical complexity.

Deep Learning · Generative Models and Autoencoders

Xianglu Wang, Bangxian Han, Hu Ding

Diffusion models have achieved state-of-the-art performance in image generation tasks. However, training powerful diffusion models remains time-consuming, which limits their practical deployment. In this paper, we revisit the learning dynamics of diffusion models through the lens of *spectral bias*, a phenomenon in which deep neural networks prioritize learning low-frequency modes. Through an empirical analysis of diffusion training, we observe that diffusion models exhibit a **dual** spectral bias. First, over training iterations, they fit low-frequency components earlier than high-frequency details. Second, along the diffusion timesteps, early denoising steps mainly reconstruct coarse low-frequency content, while high-frequency details emerge in later steps. Motivated by this observation, we propose Frequency-aware Patch Selection **(FaPS)**, a general and fast training method for diffusion models that can be applied to both UNet and DiT backbones. Specifically, FaPS introduces a *frequency-aware gating* that adaptively selects image patches based on their frequency information and focuses computation only on the selected patches. Since the selection decisions are discrete and thus non-differentiable, we model the gating as a stochastic policy network and optimize it end-to-end using a policy gradient method. Our experiments demonstrate that FaPS achieves up to $\mathbf{3}\times$ faster training while maintaining comparable or superior generation quality, and improves the performance of diffusion models in limited-data settings.

Pierre-Louis Cauvin, Panayotis Mertikopoulos

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.

Optimization · Discrete and Combinatorial Optimization

Aravind Srinivasan, Arushi Srinivasan, Jiayi Wu

We study the \maxecc\ problem, where given an edge-colored hypergraph with $k$ colors and edge size $r$, we seek to color the vertices of the graph in order to maximize the number of satisfied edges (edges having the same color as their extremities): this is an effective mechanism for clustering (coloring) objects based on their multi-way interactions with one another in a system, providing significant applications in machine learning, clustering, and data mining. We exponentially improve upon the approximation ratio of an existing algorithm, by Crane et al. present in ICML 2025, to $\frac{1}{r+1}$, present another novel dependent-rounding algorithm with an approximation ratio of $1/ \lceil \frac{k}{2}\rceil$, and modify the initial algorithm via analytical scaling techniques in order to achieve an approximation factor of $(1-e^{-r})/r$. We then apply our scaling algorithm to graph \maxecc\ and improve the best-known approximation factor for all hypergraphs: in particular, our algorithm provides an approximation factor of $0.43$ as opposed to the previously-known $0.38$ factor for graphs.

Social Aspects · Fairness

Samuel Gruffaz, Gabriel Singer, Olivier VO VAN, Nicolas Vayatis, Argyris Kalogeratos

In many machine learning applications acquiring reliable ground-truth labels is costly, or unfeasible, leading practitioners to rely on crowdsourcing and aggregation of noisy human annotations. When labels are subjective, however, aggregation may amplify individual biases, particularly with respect to sensitive attributes, raising fairness concerns. Despite this, fairness in crowdsourced aggregation remains largely unexplored, with no existing convergence guarantees and only limited post-processing approaches for enforcing $\varepsilon$-fairness under demographic parity. We address this gap by analyzing fairness properties of crowdsourcing aggregation methods within the $\varepsilon$-fairness framework, focusing on Majority Voting and Optimal Bayesian aggregation. In the small-crowd regime, we derive an upper bound on the fairness gap of Majority Voting in terms of the individual annotators’ fairness gaps. We further show that the fairness gap of the aggregated consensus converges exponentially fast to that of the ground truth under interpretable conditions. Since the ground truth itself may still be unfair, we generalize a state-of-the-art multiclass fairness post-processing algorithm from the continuous to the discrete setting, enabling the enforcement of strict demographic parity constraints for any aggregation rule. Experiments on both synthetic and real-world datasets demonstrate the effectiveness of our approach and corroborate the theoretical insights.

Deep Learning · Graph Neural Networks

Chendi Qian, Christopher Morris, Stefanie Jegelka, Christian Sohler

There has been a growing interest in using neural networks, especially message-passing neural networks (MPNNs), to solve hard combinatorial optimization problems heuristically. However, existing learning-based approaches for hard combinatorial optimization tasks often rely on supervised training data, reinforcement learning, or gradient estimators, leading to significant computational overhead, unstable training, or a lack of provable performance guarantees. In contrast, classical approximation algorithms offer such performance guarantees under worst-case inputs but are non-differentiable and unable to adaptively exploit structural regularities in natural input distributions. We address this dichotomy with the fundamental example of Uniform Facility Location (UniFL), a variant of the combinatorial facility location problem with applications in clustering, data summarization, logistics and supply chain design. We develop a fully differentiable MPNN model that embeds approximation-algorithmic principles while avoiding the need for solver supervision or discrete relaxations. Our approach admits provable approximation and size generalization guarantees to much larger instances than seen during training. Empirically, we show that our approach outperforms standard non-learned approximation algorithms in terms of solution quality, closing the gap with computationally intensive integer linear programming approaches. Overall, this work provides a step toward bridging learning-based methods and approximation algorithms for discrete optimization.

Applications · Robotics

Lukas Lao Beyer, Sertac Karaman

Deep learning methods have vastly expanded the capabilities of motion planning in robotics applications, as learning priors from large-scale data has been shown to be essential in capturing the highly complex behavior required for solving tasks such as manipulation or navigation for autonomous vehicles. At the same time, model-based planning algorithms based on search or optimization remain an essential tool due to their flexibility, efficiency, and the ability to incorporate domain knowledge via expert-designed algorithms and objective functions. We propose a new generative framework to unify these two paradigms. First, we learn an autoencoder with a high compression ratio and a latent space of hierarchically ordered, discrete-valued tokens. Leveraging both the dimensionality reduction and the hierarchical coarse-to-fine structure learned by this autoencoder, we then perform motion planning by directly searching in the latent space of tokens. This search can optimize arbitrary objective functions specified at test time, providing a large degree of flexibility while maintaining efficiency and producing realistic solutions by relying on the generative capabilities of the highly compressed autoencoder. We evaluate our method on nuPlan and the Waymo Open Motion Dataset, showing how latent space search can be used for a variety of guided behavior generation tasks, achieving strong performance for closed-loop motion planning and multi-agent guided scenario synthesis without requiring any task-specific training.

Semih Cayci

Ill-conditioned kernel matrices and loss landscapes can make first-order methods for training neural networks converge slowly. We establish non-asymptotic convergence bounds for the Gauss–Newton method in both under- and overparameterized regimes, showing it avoids these conditioning bottlenecks. In the underparameterized setting, Gauss–Newton gradient flow in parameter space induces a Riemannian gradient flow on a low-dimensional submanifold of function space. Using tools from Riemannian optimization, we show that, under an appropriate output scaling, the loss satisfies geodesic Polyak–Lojasiewicz and Lipschitz-smoothness conditions, implying geometric convergence to the optimal in-class predictor at an explicit rate independent of Gram-matrix conditioning. In the overparameterized setting, we identify adaptive, curvature-aware regularization schedules and prove fast geometric convergence to a global optimum for both Gauss–Newton gradient flow and discrete-time Gauss–Newton iterates, with rates independent of the minimum eigenvalue of the neural tangent kernel and, locally, independent of the strong-convexity modulus. Overall, Gauss–Newton can be provably faster in ill-conditioned regimes where first-order methods slow down.

Optimization · Discrete and Combinatorial Optimization

Tae-Hoon Lee, Min-Soo Kim

Primal heuristics play a crucial role in quickly finding feasible solutions for NP-hard integer linear programming (ILP). Although $\textit{end-to-end learning}$-based primal heuristics (E2EPH) have recently been proposed, they are typically unable to independently generate feasible solutions. To address this challenge, we propose RL-SPH, a novel reinforcement learning-based start primal heuristic capable of independently generating feasible solutions, even for ILP involving non-binary integers. Empirically, RL-SPH rapidly obtains high-quality feasible solutions with a 100% feasibility rate, achieving on average a 39× lower primal gap and a 2.3× lower primal integral compared to existing start primal heuristics.

Applications · Everything Else

Youngsung Kim

Differentiable discrete selection uses soft mixtures during training but hard selection at deployment, resulting in a training-inference gap. We decompose this gap into selection gap (method-dependent, reducible) and computation gap (input-dependent, irreducible). Our key finding: the selection gap is determined by forward-pass structure, not backward-pass gradients. Methods using hard selection during training achieve zero selection gap by construction, while mixture methods exhibit gaps even with identical gradient estimators. This occurs because mixtures reward hedging across options, while deployment requires commitment to one. We propose CAGE (Confidence-Adaptive Gate Exploration), which addresses optimization entirely in the backward pass by adapting temperature based on selection confidence. We also identify a critical failure mode: Gumbel-ST suffers 40--50 percentage point accuracy collapse at low temperatures, which CAGE prevents. Experiments on logic gate networks validate the theory: hard selection achieves 98% accuracy with zero gap across all temperatures.

General Machine Learning · Hardware and Software

Anselm Paulus, Andreas René Geist, Vit Musil, Sebastian Hoffmann, Georg Martius

Automatic differentiation (AD) frameworks such as JAX and PyTorch have enabled gradient-based optimization for a wide range of scientific fields. Yet, many ''hard'' primitives in these libraries such as thresholding, Boolean logic, discrete indexing, and sorting operations yield zero or undefined gradients that are not useful for optimization. While numerous ''soft'' relaxations have been proposed that provide informative gradients, the respective implementations are fragmented across projects, making them difficult to combine and compare. This work introduces **SoftJAX** and **SoftTorch**, open-source, feature-complete libraries for *soft differentiable programming*. These libraries provide a variety of soft functions as drop-in replacements for their hard JAX and PyTorch counterparts. This includes (i) elementwise operators such as *clip* or *abs*, (ii) utility methods for manipulating Booleans and indices via fuzzy logic, (iii) axiswise operators such as *sort* or *rank* -- based on optimal transport or permutahedron projections, and (iv) offer full support for straight-through gradient estimation. Overall, SoftJAX and SoftTorch make the toolbox of soft relaxations easily accessible to differentiable programming, as demonstrated through benchmarking and a practical case study.

Deep Learning · Generative Models and Autoencoders

Guotao Liang, Zhangcheng Wang, Chuang Wang, Juncheng Hu, Haitao Zhou, Junhua Liu, Jing Zhang, Dong Xu, Qian Yu

Scalable Vector Graphics (SVG) animation generation is pivotal for professional design due to their structural editability and resolution independence. However, this task remains challenging as it requires bridging discrete code representations with continuous visual dynamics. Existing optimization-based methods often destroy topological consistency, while general-purpose LLMs rely on rigid CSS/SMIL transformations, failing to model geometry-level non-rigid deformations. To address these limitations, we present VAnim, the first LLM-based framework for open-domain text-to-SVG animation. We reconceptualize animation not as sequence generation, but as Sparse State Updates (SSU) on a persistent SVG DOM tree. This paradigm compresses sequence length by over 9.8x while mathematically guaranteeing topological isomorphism and identity persistence. To enable precise control, we propose an Identification-First Motion Planning mechanism that grounds textual instructions in explicit visual entities. Furthermore, to overcome the non-differentiable nature of SVG rendering, we employ Rendering-Aware Reinforcement Learning via Group Relative Policy Optimization (GRPO). By leveraging a hybrid reward from a state-of-the-art video perception encoder, we align discrete code updates with high-fidelity visual feedback. We also introduce SVGAnim-134k, the first benchmark for vector animation. Extensive experiments demonstrate that VAnim significantly outperforms state-of-the-art baselines in semantic alignment and structural validity, demonstrating a robust capacity for synthesizing high-fidelity non-rigid deformations without requiring explicit temporal consistency constraints.

Theory · Probabilistic Methods

Zhengyan Wan, Yidong Ouyang, Qiang Yao, Liyan Xie, Fang Fang, Hongyuan Zha, Guang Cheng

Discrete flow models offer a powerful framework for learning distributions over discrete state spaces and have demonstrated superior performance compared to the discrete diffusion models. However, their convergence properties and error analysis remain largely unexplored. In this work, we develop a unified framework grounded in stochastic calculus theory to systematically investigate the theoretical properties of discrete flow models. Specifically, by leveraging a Girsanov-type theorem for the path measures of two continuous-time Markov chains (CTMCs), we present a comprehensive error analysis that accounts for both transition rate estimation error and early stopping error. In fact, the estimation error of transition rates has received little attention in existing works. Unlike discrete diffusion models, discrete flow incurs no initialization error caused by truncating the time horizon in the noising process. Building on generator matching and uniformization, we establish non-asymptotic error bounds for distribution estimation without the boundedness condition on oracle transition rates. Furthermore, we derive a faster rate of total variation convergence for the estimated distribution with the boundedness condition, yielding a nearly optimal rate in terms of sample size. Our results provide the first error analysis for discrete flow models. We also study model performance under different settings based on simulation results.

Optimization · Discrete and Combinatorial Optimization

Esha Singh, Dongxia Wu, Chien-Yi Yang, Tajana Rosing, Rose Yu, Yian Ma

Multi-objective combinatorial optimization seeks Pareto-optimal solutions over exponentially large discrete spaces, yet existing methods sacrifice generality, scalability, or theoretical guarantees. We reformulate it as an online learning problem over a decomposed decision space, solving position-wise bandit subproblems via adaptive expert-guided sequential construction. This formulation admits regret bounds of $O(d\sqrt{T \log T})$ depending on subproblem dimensionality \(d\) rather than combinatorial space size. On standard benchmarks, our method achieves 80--98\% of specialized solvers performance while achieving two to three orders of magnitude improvement in sample and computational efficiency over Bayesian optimization methods. On real-world hardware-software co-design for AI accelerators with expensive simulations, we outperform competing methods under fixed evaluation budgets. The advantage grows with problem scale and objective count, establishing bandit optimization over decomposed decision spaces as a principled alternative to surrogate modeling or offline training for multi-objective optimization.

Optimization · Discrete and Combinatorial Optimization

Bin Chen, Shouliang Zhu, Beidan Liu, Yong Zhao, Tianle Pu, Huichun Li, Zhengqiu Zhu

Designing heuristics for combinatorial optimization problems (COPs) is a fundamental yet challenging task that traditionally requires extensive domain expertise. Recently, Large Language Model (LLM)-based Automated Heuristic Design (AHD) has shown promise in autonomously generating heuristic components with minimal human intervention. However, most existing LLM-based AHD methods enforce fixed algorithmic templates to ensure executability, which confines the search to component-level tuning and limits system-level algorithmic expressiveness. To enable open-ended solver synthesis beyond rigid templates, we propose Automated Algorithm Design via Evolutionary Program Trees (A$_2$DEPT), which treats LLMs as system-level algorithm architects. A$_2$DEPT explores the vast program space via a tree-structured evolutionary search with \textit{hybrid selection} and \textit{hierarchical operators}, enabling iterative refinement of complete algorithms. To make open-ended generation practical, we enforce executability with a lightweight program-maintenance loop that performs feedback-driven repair. In experiments, A$_2$DEPT consistently outperforms state-of-the-art baselines across standard and highly constrained benchmarks, reducing the optimality gap by an average of 9.8\%. Our work implies that system-level algorithm synthesis is a viable and scalable paradigm for LLM-driven optimization.

Deep Learning · Large Language Models

Yubing Ren, Ping Guo, Yanan Cao

Large generative models raise growing concerns about provenance, misinformation, and impersonation. Digital watermarking offers a principled solution, yet extending it to natural language remains challenging due to text discreteness and sensitivity to semantic perturbations. Existing text watermarking methods either operate at the token level requiring white-box access and remaining fragile to paraphrasing, or at the sentence level, which supports black-box deployment but suffers from low Watermark Success Rate (WSR). We show that low WSR in sentence-level watermarking primarily stems from low injection success probability caused by a mismatch between posterior embedding distributions and semantic accept regions. Based on this insight, we propose \textbf{X-Guard}, a geometry-aware sentence-level watermarking framework that improves injection success by jointly optimizing embedding distributions and semantic space partitioning. X-Guard learns a more isotropic embedding space and introduces \textbf{A$^2$PQ}, a centroid-aligned partitioning scheme that approximately equalizes probability mass across regions. Extensive experiments across multiple models, languages, and attack settings demonstrate that X-Guard consistently improves robustness while preserving text fluency and practical deployability.

Deep Learning · Generative Models and Autoencoders

Etrit Haxholli, Yeti Z. Gurbuz, Oğul Can, Eli Waxman

Discrete flow matching, a recent framework for modeling categorical data, has shown competitive performance with autoregressive models. However, unlike continuous flow matching, the rectification strategy cannot be applied due to the stochasticity of discrete paths, necessitating alternative methods to minimize state transitions. We propose a dynamic-optimal-transport-like minimization objective and derive its Kantorovich formulation for discrete flows with convex interpolants, where transport cost depends solely on inter-state similarity and can be optimized via minibatch strategies. We show that such methods can reduce the number of transitions up to 8 times (1024 to 128) to reach the same generative perplexity without compromising diversity. Additionally, path nondeterminism in discrete flows precludes an instantaneous change-of-variables analogue, preventing precise probability estimation available to continuous flows. We therefore propose two upper bounds on perplexity, enabling principled training, evaluation and model comparison. Finally, we introduce Multimask Flows which outperform masked flows in generative perplexity without compromising diversity, particularly when utilizing minibatch Optimal Transport.

Deep Learning · Large Language Models

Tianhao Gao, Jun Fang, Xiaohui Zhang, Zhiyuan Liu, Chao Liu, Pengzhang Liu, Qixia Jiang

Recent advances have empowered large language models (LLMs) with remarkable fine-grained instruction-following capabilities in text generation tasks. However, embedding methods typically rely solely on the hidden state of the input's last token, limiting their ability to capture complete semantic signals distributed across the full output tokens. Moreover, existing discrete-to-continuous re-encoding approaches introduce semantic discontinuity. To address these limitations, we propose $\textbf{InstEmb}$, a novel instruction following embedding framework. InstEmb jointly optimizes two key aspects: (1) Input-Intrinsic semantic information, achieved by employing contrastive learning focused on the representation of the last input token, and (2) Output-Aware semantic information, captured through representation self-distillation leveraging learnable look-ahead tokens without introducing additional decoding latency. Additionally, we introduce $\textbf{Dual-Anchor Alignment Pooling (DAAP)}$, explicitly aligned with our dual training objectives. Extensive experiments demonstrate that InstEmb achieves state-of-the-art performance across multiple instruction following benchmarks without benchmark-specific supervised data.