论文检索

Theory · Learning Theory

SANTANU DAS, Sagnik Chatterjee, jatin batra

In this paper, we tackle a fundamental problem in high-dimensional statistics, namely, learning Single Index Models (SIMs) robustly in the presence of heavy-tailed noise and an adversary that can corrupt a constant fraction of both covariates and responses. Prior research on efficient robust recovery only focuses on monotonic link functions or only limit themselves to Phase Retrieval. Provable efficient robust recovery guarantees for generic nonlinear link functions have remained elusive. In this paper, we obtain the first near-linear time, optimal-sample-complexity robust recovery algorithm for a wide class of nonlinear non-monotonic link functions. Critical to our result is an improved understanding of the squared-loss landscape: we identify a sufficient condition under which a broad class of non linear link functions admit a dimension-independent constant-radius convex basin around the ground truth, establishing statistical identifiability beyond previously known cases. We also leverage second-order Stein's identities to identify a structural condition, that we term Expected Squared Convexity (ESC), that acts as a sufficient condition for spectral initialization techniques to obtain an estimator within the convex basin with error $O(\epsilon^{1/4})$, even under heavy-tailed noise and strong adversarial contamination. This robust initialization technique can be combined with a robust gradient descent phase to break the spectral error barrier, achieving an improved estimation error of $O(\sigma\sqrt{\epsilon})$. Our non-convex optimization framework gives the first efficient sample and time complexity robust recovery results for activation functions such as GeLU and Swish that act as building blocks of modern deep-learning architectures.

Social Aspects · Privacy

Marc Molina Van den bosch, Riccardo Taiello, Albert Aillet, Andrea Protani, Miguel Angel Gonzalez Ballester, Luigi Serio

Differentially private optimization suffers from a fundamental geometric mismatch: deep networks have highly anisotropic loss landscapes, yet DP-SGD injects isotropic noise. Second-order preconditioning can resolve this, but estimating curvature typically requires private data (consuming privacy budget) or public data (introducing distribution shift). We show that the Fisher Information Matrix decouples into *architectural sensitivity*, recoverable via synthetic noise, and *input correlations*, approximable from modality-specific frequency statistics. We propose DP-KFC, which constructs KFAC preconditioners by probing networks with structured synthetic noise, requiring neither private nor public data. Empirically, DP-KFC consistently outperforms DP-SGD and adaptive baselines across diverse modalities in strong privacy regimes ($\varepsilon \leq 3$). DP-KFC matches private-data preconditioners while public-data variants degrade by up to $4.8$ %, showing that curvature can be estimated without consuming privacy budget or introducing distribution shift. This enables privacy-preserving learning in specialized domains (e.g., medical applications) where regulatory constraints make data scarce.

Deep Learning · Large Language Models

Fahim Tajwar, Guanning Zeng, Yueer Zhou, Yuda Song, Daman Arora, Yiding Jiang, Jeff Schneider, Russ Salakhutdinov, Haiwen Feng, Andrea Zanette

Maximum likelihood is fundamental to supervised learning but it cannot be directly applied in correctness-based problems with non-differentiable sampling. In these settings, reinforcement learning (RL) is typically used to maximize expected reward. We show that for binary correctness tasks, expected-reward RL is a first-order approximation of the maximum likelihood objective, yielding vanishing learning signal on low-success inputs. We introduce **Maximum Likelihood Reinforcement Learning (MaxRL)**, a compute-indexed family of sampling-based objectives derived from a pass@k expansion of the likelihood, which interpolates between standard RL and exact maximum likelihood as compute increases. MaxRL admits a simple unbiased policy-gradient estimator whose optimized objective improves with additional compute. Across multiple domains, MaxRL consistently outperforms standard RL and GRPO, achieving higher $pass@1$ and substantially improved $pass@k$.

Deep Learning · Large Language Models

Zhicheng Yang, Zhijiang Guo, Yinya Huang, Yongxin Wang, Wenlei Shi, Yiwei Wang, Xiaodan Liang, Jing Tang

Scaling test-time compute via long Chain-of-Thought unlocks remarkable gains in reasoning capabilities, yet it faces practical limits due to the linear growth of KV cache and quadratic attention complexity. In this paper, we introduce AccordionThinking, an end-to-end framework where LLMs learn to self-regulate the granularity of the reasoning steps through dynamic summarization. This mechanism enables a Fold inference mode, where the model periodically summarizes its thought process and discards former thoughts to reduce dependency on historical tokens. We apply reinforcement learning to incentivize this capability further, uncovering a critical insight: the accuracy gap between the highly efficient Fold mode and the exhaustive Unfold mode progressively narrows and eventually vanishes over the course of training. This phenomenon demonstrates that the model learns to encode essential reasoning information into compact summaries, achieving effective compression of the reasoning context. Our AccordionThinker demonstrates that with learned self-compression, LLMs can tackle complex reasoning tasks with minimal dependency token overhead without compromising solution quality, and it achieves a 3× throughput while maintaining accuracy on a 48GB GPU memory configuration, while the structured step summaries provide a human-readable account of the reasoning process.

Social Aspects · Accountability, Transparency, and Interpretability

Xin Zhang, Zijin Yang, Kejiang Chen, Linfeng Ma, Weiming Zhang, Nenghai Yu

Latent-based watermarks, integrated into the generation process of latent diffusion models (LDMs), simplify detection and attribution of generated images. However, recent black-box forgery attacks, where an attacker needs at least one watermarked image and black-box access to the provider’s model, can embed the provider’s watermark into images not produced by the provider, posing outsized risk to provenance and trust. We propose SemBind, the first defense framework for latent-based watermarks that resists black-box forgery by binding latent signals to image semantics via a learned semantic masker. Trained with contrastive learning, the masker yields near-invariant codes for the same prompt and near-orthogonal codes across prompts; these codes are reshaped and permuted to modulate the target latent before any standard latent-based watermark. SemBind is generally compatible with existing latent-based watermarking schemes and keeps image quality essentially unchanged, while a simple mask-ratio parameter offers a tunable trade-off between anti-forgery strength and robustness. Across four mainstream latent-based watermark methods, our SemBind-enabled anti-forgery variants markedly reduce false acceptance under black-box forgery while providing a controllable robustness--security balance.

Applications · Chemistry, Physics, and Earth Sciences

Ruiqi Shu, Xiaohui Zhong, Mengyao Fang, Ruijian Gou, Tianrun Gao, Hao Li, Xiaomeng Huang

Global ocean modeling is vital for climate science but struggles to balance computational efficiency with accuracy. Traditional numerical solvers are accurate but computationally expensive, while pure deep learning approaches, though fast, often lack physical consistency and long-term stability. To address this, we introduce HybridOM, a framework integrating a lightweight, differentiable numerical solver as a skeleton to enforce physical laws, with a neural network as the flesh to correct subgrid-scale dynamics. To enable efficient high-resolution modeling, we further introduce a physics-informed regional downscaling mechanism based on flux gating. This design achieves the inference efficiency of AI-based methods while preserving the accuracy and robustness of physical models. Extensive experiments on the GLORYS12V1 and OceanBench dataset validate HybridOM's performance in two distinct regimes: long-term subseasonal-to-seasonal simulation and short-term operational forecasting coupled with the FuXi-2.0 weather model. Results demonstrate that HybridOM achieves state-of-the-art accuracy while maintaining physical consistency, offering a robust solution for next-generation ocean digital twins.

General Machine Learning · Clustering

Henri Schmidt, Peter Halmos, Benjamin Raphael

Optimal transport (OT) finds a least cost transport plan between two probability distributions using a cost matrix defined on pairs of points. Unlike standard OT, which infers unstructured pointwise mappings, low-rank optimal transport explicitly constrains the rank of the transport plan to infer latent structure. This improves statistical stability and robustness, yields sharper parametric rates for estimating Wasserstein distances adaptive to the intrinsic rank, and generalizes $K$-means to co-clustering. These advantages, however, come at the cost of a non-convex and NP-hard optimization problem. We introduce transport clustering, an algorithm to compute a low-rank OT plan that reduces low-rank OT to a clustering problem on correspondences obtained from a full-rank *transport registration* step. We prove that this reduction yields polynomial-time, constant-factor approximation algorithms for low-rank OT: specifically, a $(1+\gamma)$ approximation for negative-type metrics and a $(1+\gamma+\sqrt{2\gamma})$ approximation for kernel costs, where $\gamma \in [0,1]$ denotes the approximation ratio of the optimal full-rank solution relative to the low-rank optimal. Empirically, transport clustering outperforms existing low-rank OT solvers on synthetic benchmarks and large-scale, high-dimensional datasets.

Reinforcement Learning · Multi-agent

Guanghao Li, lei yuan, Ruiqi Xue, Hengchang Zhang, Jianhong Wang, Yi-Chen Li, Yang Yu

Parameter sharing is a widely used technique in Multi-Agent Reinforcement Learning (MARL) that enhances sample efficiency by equipping agents with a unified policy. While effective in homogeneous settings, it often struggles in heterogeneous environments where agents possess diverse capabilities. Conversely, learning customized policies for agents can resolve knowledge conflicts but significantly hinders knowledge transfer, thereby reducing learning efficiency. Existing approaches attempt to balance this trade-off using clustering or agent-specific masks, but they typically rely on strong environment-specific priors and struggle in settings where the team exhibits multi-modal policies. To address these limitations, we propose Dspic, an efficient shared-policy algorithm grounded in the maximum entropy framework. Specifically, Dspic employs self-supervised learning to extract discriminative role embeddings for each agent. These embeddings guide a complete division of the observation space, providing a theoretical guarantee for the optimality of parameter sharing. Furthermore, to handle the increased observation complexity and diversity resulting from this division, Dspic incorporates a diffusion policy, enhancing the capacity to model complex action distributions while enabling efficient learning. Extensive experiments on MaMuJoCo, SMAC, SMACv2, and LBF demonstrate that Dspic achieves superior sample efficiency while maintaining asymptotic optimality.

Optimization · Large Scale, Parallel and Distributed

Andrej Jovanović, Alex Iacob, Mher Safaryan, Ionut-Vlad Modoranu, Lorenzo Sani, Shen, Xinchi Qiu, Dan Alistarh, Nicholas Lane

Distributed training of foundation models via $\texttt{DDP}$ is limited by interconnect bandwidth. While infrequent communication strategies reduce synchronization frequency, they remain bottlenecked by the memory and communication requirements of optimizer states. Low-rank optimizers can alleviate these constraints; however, in the local-update regime, workers lack access to the full-batch gradients required to compute low-rank projections, which degrades performance. We propose $\texttt{LoRDO}$, a principled framework unifying low-rank optimization with infrequent synchronization. We first demonstrate that, while global projections based on pseudo-gradients are theoretically superior, they permanently restrict the optimization trajectory to a low-rank subspace. To restore subspace exploration, we introduce a full-rank quasi-hyperbolic update. $\texttt{LoRDO}$ achieves near-parity with low-rank $\texttt{DDP}$ in language modeling and downstream tasks at model scales of $125$M--$720$M, while reducing communication by $\approx10\times$. Finally, we show that $\texttt{LoRDO}$ improves performance even more in very low-memory settings with small rank/batch size.

Theory · Game Theory

Philip Jordan, Maryam Kamgarpour

We study the existence and computation of Nash equilibria in concave games where the players' admissible strategies are subject to shared coupling constraints. Under playerwise concavity of constraints, we prove existence of Nash equilibria. Our proof leverages topological fixed point theory and novel structural insights into the contractibility of feasible sets, and relaxes strong assumptions for existence in prior work. Having established existence, we address the question of whether in the presence of coupling constraints, playerwise independent learning dynamics have convergence guarantees. We address this positively for the class of potential games by designing a convergent algorithm. To account for the possibly nonconvex feasible region, we employ a log barrier regularized gradient ascent with adaptive stepsizes. Starting from an initial feasible strategy profile and under exact gradient feedback, the proposed method converges to an $\epsilon$-approximate constrained Nash equilibrium within $\mathcal{O}(\epsilon^{-3})$ iterations.

Social Aspects · Security

Xiaozuo Shen, Yifei Cai, RUI NING, Chunsheng Xin, Hongyi "Michael" Wu

The widespread adoption of Vision Transformers (ViTs) elevates supply-chain risk on third-party model hubs, where an adversary can implant backdoors into released checkpoints. Existing ViT backdoor attacks largely rely on poisoned-data training, while prior data-free attempts typically require synthetic-data fine-tuning or extra model components. This paper introduces Data-Free Logic-Gated Backdoor Attacks (DF-LoGiT), a truly data-free backdoor attack on ViTs via direct weight editing. DF-LoGiT exploits ViT’s native multi-head architecture to realize a logic-gated compositional trigger, enabling a stealthy and effective backdoor. We validate its effectiveness through theoretical analysis and extensive experiments, showing that DF-LoGiT achieves near-100% attack success with negligible degradation in benign accuracy and remains robust against representative classical and ViT-specific defenses.

Ionut-Vlad Modoranu, Philip Zmushko, Erik Schultheis, Mher Safaryan, Dan Alistarh

Shampoo is one of the leading approximate second-order optimizers: a variant of it has won the MLCommons AlgoPerf competition, and it has been shown to produce models with lower activation outliers that are easier to compress. Yet, applying Shampoo currently comes at the cost of significant computational slowdown, due to its expensive internal operations. In this paper, we take a significant step to address this shortcoming by proposing \method (for Distributed Accelerated SHampoo), a faster implementation of Distributed Shampoo based on two main new techniques: First, we show that preconditioner blocks can be stacked into 3D tensors to significantly improve GPU utilization; second, we introduce the Newton-DB iteration and the Chebyshev polynomial approximations as novel and faster approaches for computing the inverse matrix roots required by Shampoo. Along with these algorithmic contributions, we provide a first in-depth analysis of how matrix scaling critically affects Shampoo convergence. On the practical side, our GPU-aware implementation achieves up to $4.83\times$ faster optimizer steps compared to the well-optimized Distributed Shampoo, while Newton-DB attains the lowest validation perplexity per iteration among all tested methods.

Reinforcement Learning · Deep RL

Mahsa Bastankhah, Sophie Broderick, Benjamin Eysenbach

In many practical reinforcement learning (RL) environments, observations are far higher-dimensional than the variables that matter for control. In this work, we ask: can we learn representations that capture only control-relevant features of the environment? We study this question through the \emph{empowerment} objective, which maximizes an agent’s influence over the environment and is widely used for unsupervised skill learning. We show that empowerment agents induce two distinct representations --- forward and backward --- that capture complementary aspects of the state, and both of which are invariant to control-irrelevant features. Thus, empowerment maximization leads agents to learn an implicit, \emph{control-centric} model of the world. Our analysis highlights the importance of learning representations through interaction rather than from passive datasets: interaction aimed at maximizing control is essential for learning useful invariance properties, a perspective that aligns closely with the causal learning literature.

Deep Learning · Large Language Models

Parth Asawa, Alan Zhu, Abigail O'Neill, Matei Zaharia, Alex Dimakis, Joseph E Gonzalez

Frontier language models are deployed as black-box services, where model weights cannot be modified and customization is limited to prompting. We introduce Advisor Models, a method to train small open-weight models to generate dynamic, per-instance natural language advice that improves the capabilities of black-box frontier models. Advisor Models improve GPT-5's performance on RuleArena (Taxes) by 71\%, reduce Gemini 3 Pro's steps taken in SWE agent tasks by 24.6\%, and outperform static prompt optimizers in personalizing GPT-5 to user preferences (85-100\% vs. 40-60\%). We also find that advisors are transferable: an advisor trained with a low-cost student model still transfers improvements to a frontier model. Moreover, Advisor Models are robust: we observe no degradation on other benchmarks than the pipeline is trained on. Our method shows how to perform parametric optimization for black-box frontier models in a practical and cost-effective way.

Deep Learning · Large Language Models

Yang Yue, Xuancheng Zhu, YuYang Ma, Guoshun Nan, Zihan Dou, JingRu Shan, Congyu Guo, Ji Zhang, Hua Wang, Jingfeng Zhang

The automated design of agentic systems offers a promising pathway for scaling large language models (LLMs) beyond single-agent reasoning. While prior work has advanced task performance through handcrafted or automatically generated multi-agent workflows, robustness is often treated as an afterthought, leaving systems vulnerable to external adversaries and internal failures. We propose AutoRAS, a framework for the Automated design of Robust Agentic Systems. AutoRAS formulates system design as generating a sequence of symbolic primitives that jointly encode structural connectivity and behavioral actions, and learns to optimize this sequence using execution-derived safety signals and flow-based sequence-level objectives. Extensive experiments show that AutoRAS achieves the best performance in both vanilla and adversarial settings, with the smallest performance degradation under attacks. Further analyses demonstrate strong transferability, stable optimization behavior, stability across primitive sets, and favorable cost trade-offs. Our code is available at [this link](https://anonymous.4open.science/r/AutoRAS-56C8/).

Applications · Computer Vision

Chengyu Zheng, Songlin Yang, Jin Huang, Honghua Chen, Weiming Wang, Haoran Xie, Fu Lee Wang, Mingqiang Wei

Point cloud registration can be categorized into rigid and non-rigid settings depending on the motion characteristics of the underlying objects. Rigid alignment assumes a single global transformation under which corresponding points remain geometrically consistent across scales, whereas non-rigid alignment involves spatially varying deformations, where geometric similarity holds only locally and semantic correspondence dominates at larger scales. This multi-scale discrepancy creates an optimization gap that has made unified registration particularly challenging. To this end, we propose RGGT, a Generative-Prior-Guided Transformer that unifies rigid and non-rigid registration within a shared optimization space. Through coordinated design at the representation, architecture, and supervision levels, RGGT jointly captures local geometric details and global structural semantics: generative priors enrich point features with unified geometric–semantic cues; a Global–Self–Cross Attention module models long-range structure, local interaction, and bidirectional cross-shape reasoning; and a dual correspondence–reconstruction objective provides consistent supervision for both deformation types. Extensive experiments on rigid (ModelNet40) and non-rigid (4DMatch) benchmarks demonstrate that RGGT achieves state-of-the-art accuracy across both rigid and non-rigid settings within a single unified framework.

Deep Learning · Generative Models and Autoencoders

Marta Aparicio Rodriguez, Anastasia Borovykh, Grigorios A Pavliotis, Daniel Korchinski

Generative models have a persistent limitation: their tendency to memorize training data can create legal liabilities and erode creative diversity. Understanding which samples are memorized in whole or in part, and under what conditions, therefore remains an important open problem. Here we answer the question "Are atypical or rare samples memorized first?" in the negative. We train diffusion models on strings generated according to the production rules of the Random Hierarchy Model (RHM), and find that samples composed of *common substrings* are preferentially memorized. This holds true even if the training data consists of entirely unique samples, indicating that deduplication at the data point level does not provide a meaningful privacy guarantee. Correspondingly we predict, then observe, delayed memorization for fat-tailed datasets (i.e., those with more atypical samples). This effect is amplified when fat-tails are introduced into high-level production rules. These together suggest that *dataset diversity*, particularly at higher levels of abstraction, plays an important role in staving off memorization. Finally, we identify an intermediate regime of partial memorization in which common substrings are learned first and subsequently overproduced during generation. If training is stopped in this regime, models will exhibit the reversion-to-the-mean blandness often derided as "slop".

Deep Learning · Large Language Models

Xiandong Zou, Jianshu Li, Jing Huang, Pan Zhou

Speculative decoding accelerates inference for (M)LLMs, yet a training-decoding discrepancy persists: while existing methods optimize single greedy trajectories, decoding involves verifying and ranking multiple sampled draft paths. We propose *Variational Speculative Decoding* (VSD), formulating draft training as variational inference over latent proposals (draft paths). VSD maximizes the marginal probability of target-model acceptance, yielding an ELBO that promotes high-quality latent proposals while minimizing divergence from the target distribution. To enhance quality and reduce variance, we incorporate a path-level utility and optimize via an Expectation-Maximization procedure. The E-step draws MCMC samples from an oracle-filtered posterior, while the M-step maximizes weighted likelihood using Adaptive Rejection Weighting (ARW) and Confidence-Aware Regularization (CAR). Theoretical analysis confirms that VSD increases expected acceptance length and speedup. Extensive experiments across LLMs and MLLMs show that VSD achieves up to a 9.58\% speedup over EAGLE-3 and 8.80\% over ViSpec, significantly improving decoding efficiency.

Javier Porras-Valenzuela, Samar Hadou, Alejandro Ribeiro

We introduce a constrained optimization framework for training transformers that behave like optimization descent algorithms. Specifically, we enforce layerwise descent constraints on the objective function and replace standard empirical risk minimization (ERM) with a primal-dual training scheme. This approach yields models whose intermediate representations decrease the loss monotonically in expectation across layers. We apply our method to both unrolled transformer architectures and conventional pretrained transformers on tasks of video denoising and text classification. Across these settings, we observe that constrained transformers achieve stronger robustness to perturbations and maintain higher out-of-distribution generalization, while preserving competitive in-distribution performance.

Reinforcement Learning · Deep RL

Jiafei Lyu, Zichuan Lin, Scott Fujimoto, Kai Yang, Yangkun Chen, Saiyong Yang, Zongqing Lu, Deheng Ye

Model-based representations recently stand out as a promising framework that embeds latent dynamics information into the representations for downstream off-policy actor-critic learning. It implicitly combines the advantages of both model-free and model-based approaches while avoiding the training costs associated with model-based methods. Nevertheless, existing model-based representation methods can fail to capture sufficient information about relevant variables and can overfit to early experiences in the replay buffer. These incur biases in representation and actor-critic learning, leading to inferior performance. To address this, we propose Debiased model-based Representations for Q-learning, tagged DR.Q algorithm. DR.Q explicitly maximizes the mutual information between the representations of the current state-action pair and the next state besides minimizing their deviations, and samples transitions with faded prioritized experience replay. We evaluate DR.Q on numerous continuous control benchmarks with a single set of hyperparameters, and the results demonstrate that DR.Q can match or surpass recent strong baselines, sometimes outperforming them by a large margin.