论文检索

Theory · Game Theory

Shuang Cui, He Huang, Yu-e Sun, Chen Xue

Budget-feasible procurement auctions play a pivotal role in various AI-driven marketplaces, such as data acquisition and crowdsourcing, where a buyer with a limited budget seeks to procure services from strategic sellers with private costs. While numerous budget-feasible mechanisms have been proposed for the classic objective of maximizing the buyer's valuation, the more challenging and economically significant objective of social welfare maximization has only recently been studied, and existing approaches still sacrifice budget feasibility, thereby limiting their practical applicability. In this paper, we bridge this gap by proposing BFM-SWM, the first budget-feasible mechanism with provable approximation guarantees for submodular welfare maximization in procurement auctions. Our mechanism satisfies standard economic properties, including truthfulness, individual rationality, and non-negative auctioneer surplus. As a by-product, we develop BFM-VM, a variant tailored for valuation maximization, which achieves a deterministic approximation ratio of $1/(12+4\sqrt{3})$ for general submodular functions, substantially improving upon the best-known deterministic ratio of $1/64$ established by [Balkanski et al., SODA 2022], while reducing the running time from $\mathcal{O}(n^2\log n)$ to $\mathcal{O}(n\log n)$. Extensive experiments demonstrate the efficiency and effectiveness of our mechanisms.

Social Aspects · Accountability, Transparency, and Interpretability

Min Xue, Artur Andrzejak

Mechanistic interpretability of Transformer models commonly relies on training auxiliary proxy models, such as Sparse Autoencoders or Cross-Layer Transcoders. While effective, these post-hoc approaches introduce approximation bias and incur substantial computational overhead. We propose an alternative, training-free interpretability framework that directly exploits the Singular Value Decomposition (SVD) of weight matrices in Transformer MLP sublayers. By operating natively on model parameters, our method improves scalability while preserving fidelity to the original weights. We show that the projection matrices of MLP sublayers admit a natural decomposition into orthogonal, interpretable rank-1 subspaces, which we term **Detector-Effector Units** (DEUs). Within each unit, a singular vector functions as a detector of input patterns and modulates a coupled effector vector that encodes output semantics. Building on this structure, we introduce **Subspace Contribution Analysis** (SCA), a diagnostic method that quantifies the direct causal contribution of individual native subspaces to model predictions. Experiments across the GPT-2 family demonstrate that our framework, **Native Network Anatomy** (NaNA), identifies dominant functional pathways with orders-of-magnitude efficiency gains over training-based interpretability baselines, while maintaining weight fidelity. Our results suggest that SVD-based analyses provide a scalable and faithful alternative to learned proxy approaches for mechanistic interpretability.

Theory · Deep Learning

Sejun Park, Yeachan Park, Geonho Hwang

Research on the expressive power of neural networks has identified the minimum depth and width of neural networks that enable universal approximation and memorization. However, existing results are derived under exact arithmetic and cannot be directly applied to real implementations on computers, which can only use a finite set of numbers and inexact machine operations with round-off errors. In this work, we study floating-point ReLU networks that have floating-point parameters and use floating-point operations. Specifically, we investigate their minimum depth and width to represent all functions from the set of floating-point vectors $\mathbb F^d$ to the set of floating-point numbers $\mathbb F$. We first show that the minimum depth for representing all functions from $\mathbb F^d$ to $\mathbb F$ is exactly three, where two layers can be sufficient if we consider a smaller domain and/or codomain. We further show that the minimum width for representing all functions from $\mathbb F^d$ to $\mathbb F$ lies between $2d$ and $2d+4$. In addition, if we restrict the domain to non-negative floats, it lies between $d$ and $d+4$, where it can be smaller for a smaller domain, even beyond $d$. Our results show that the existing results analyzed under exact arithmetic do not extend to the floating-point setup.

Yana Wei, Hongbo Peng, Yanlin Lai, Liang Zhao, Kangheng Lin, En Yu, Keyu Lv, Han Zhou, Yin Tang, Haodong Li 等

We introduce the Perception Rubric Benchmark (PRB), a rubric-based evaluation framework for Multimodal Large Language Models (MLLMs) that addresses the growing gap between benchmark scores and human-perceived quality. While standard perception metrics approach saturation, they produce compressed rankings that obscure meaningful performance differences, largely due to their linear and lenient reward designs. PRB reframes evaluation from holistic scoring to rubric-based verification. It is built through a scalable hybrid automation pipeline over a stratified collection of complex, multi-domain visual inputs. Using pair-wise contrastive generation, PRB distills over 15,000 diagnostic rubric criteria that function as explicit unit tests for perception and are evaluated via a ternary protocol distinguishing benign approximations from perceptually critical errors. Experiments show that PRB decouples compressed leaderboard rankings, reveals perceptual blind spots in top-performing models, and aligns more closely with human preference than conventional metrics. Beyond evaluation, generated rubrics can be reused as inference-time verifiers, yielding consistent gains on multiple perception benchmarks. PRB provides a principled foundation for reliable and discriminative multimodal evaluation.

Theory · Reinforcement Learning and Planning

Yifan Jiang, Jiasheng Pan, Mengtian Li, Li Jin

We study decentralized multi-agent reinforcement learning (MARL) for networked service systems with affinity in the presence of Byzantine nodes. The way that a server processes a job depends on an affinity state that captures the correlation between the job and the server. Each node learns a local control policy via an actor-critic algorithm with linear function approximation over inherently unbounded space of traffic states, while exchanging parameter information with neighbors through a communication graph. A set of Byzantine agents can exploit the unbounded state space and the resulting stochastic variance to compromise the consensus mechanism, destabilizing both learning and queuing processes. To address this vulnerability, we propose a resilient consensus-based MARL algorithm with momentum-based smoothing, which mitigates adversarial parameter manipulation and guarantees traffic stability under mild assumptions. We prove that the cooperative agents’ policies converge almost surely to a bounded neighborhood of a stationary solution of the global objective. We demonstrate the effectiveness and generality of the proposed framework in several representative service systems, including semantic routing for large language model serving, distributed polling in cloud computing, and smart manufacturing logistics.

Deep Learning · Generative Models and Autoencoders

Ning Lin, Luxi Chen, Huaguan Chen, Jiacheng Cen, Chongxuan Li, Wenbing Huang, Hao Sun

Generating objects with specific symmetries is essential in various real-world scenarios, with the creation of patterns exhibiting planar group symmetries being a representative task. However, adapting existing 2D continuous representations to enforce symmetry remains a significant challenge, as the transformation of non-reflective group elements may disrupt continuity. To overcome this limitation, we propose a novel symmetric continuous representation framework for arbitrary planar groups. Our method transforms any underlying 2D continuous representation into a symmetric one while strictly preserving continuity. We provide the mathematical formulation of this representation, demonstrate its universal approximation capability for symmetric functions, and detail the construction methodology. We validate our approach through three distinct generation tasks: general symmetric pattern design, connectivity-preserving paper-cutting design, and mechanically-constrained geometric stylized patterns. Experimental results confirm that our representation enables precise and effective symmetry control in pattern generation.

Deep Learning · Theory

Min ZHOU, Enming Liang, Minghua Chen

Learning permutation-invariant functions over sets of $N$ elements is fundamental to many deep learning applications. While sum-decomposable architectures like DeepSets theoretically offer universal approximation capabilities for such functions, existing constructive bounds suggest that the latent dimension must grow linearly with the set size, i.e., $\mathcal{O}(N)$. This linear scaling poses a significant bottleneck for scalability. In this paper, we break this theoretical barrier by proving that a latent dimension of $\mathcal{O}(\log N)$ suffices for the universal approximation of Wasserstein-stable permutation-invariant functions. We establish this by first showing that the covering number of the Wasserstein space scales linearly with $N$. Then, we show that random embeddings, specifically Random Fourier Features, with a logarithmic latent dimension to the covering number can preserve the geometry with high probability, thereby guaranteeing the existence of deterministic embeddings of the same width. This result advances the understanding of the expressivity of set-based neural network architectures.

Applications · Robotics

Tao Sun, Utkarsh Mishra, Jiaxin Lu, Danfei Xu, Iro Armeni

Compositional diffusion planners enable robotic decision-making beyond the horizon of training trajectories. Yet, current approaches often rely on the heuristic stitching of local predictions. We demonstrate that this induces a non-conservative vector field that does not mathematically correspond to any valid global trajectory log-density function. We propose Energy-based Compositional Diffuser (ECD), a framework that formulates the global trajectory as the minimizer of the sum of local bridge potentials. This energy-based perspective guarantees a conservative update field by construction and reveals a critical endpoint reaction term that is missing in heuristic stitching methods. To enable efficient inference, we further introduce a Markov-based score approximation that computes the reaction term though a single block-tridiagonal solve, maintaining time complexity linear in the planning horizon. Empirically, ECD achieves state-of-the-art success rates on a range of OGBench stitching tasks, while nearly matching the inference speed of heuristic stitching methods.

Reinforcement Learning · Online

Arsalan Sharifnassab, Mohamed Elsayed, Kris De Asis, Rupam Mahmood, Rich Sutton

In gradient-based learning, a step size chosen in parameter units does not produce a predictable per-step change in the function output. This may lead to instability in the streaming setting (i.e., batch size=1), where stochasticity is not averaged out and update magnitudes can momentarily become arbitrarily big or small. Instead, we propose \emph{intentional updates}: first specify the \emph{intended outcome} of an update and then solve for the step size that approximately achieves it. This strategy has precedent in online supervised linear regression via normalized LMS, which selects a step size to yield a specified change in the function output proportional to the current error. We extend this principle to streaming reinforcement learning by defining appropriate intended outcomes: \emph{Intentional TD} aims for a fixed fractional reduction of the current TD error relative to the momentary bootstrap target, and \emph{Intentional Policy Gradient} aims for a bounded per-step change in the policy, limiting local KL divergence. We develop practical implementations integrating eligibility traces and diagonal scaling; our experiments show that these methods yield state-of-the-art streaming performance often comparable to batch and replay-buffer learning.

Applications · Chemistry, Physics, and Earth Sciences

Dongzhe Zheng, Tao Zhong, Christine Allen-Blanchette

In this paper, we study solution operators of physical field equations on geometric meshes from a function-space perspective. We reveal that Hodge orthogonality fundamentally resolves spectral interference by isolating unlearnable topological degrees of freedom from learnable geometric dynamics, enabling an additive approximation confined to structure-preserving subspaces. Building on Hodge theory and operator splitting, we derive a principled operator-level decomposition. The result is a Hybrid Eulerian-Lagrangian architecture with an algebraic-level inductive bias we call Hodge Spectral Duality (HSD). In our framework, we use discrete differential forms to capture topology-dominated components and an orthogonal auxiliary ambient space to represent complex local dynamics. Our method achieves superior accuracy and efficiency on geometric graphs with enhanced fidelity to physical invariants.

General Machine Learning · Causality

Qing Chen, Peng Zhang

We study experimental designs that balance nonlinear functions of covariates, extending classical methods that primarily target linear balance. Building on the Gram-Schmidt Walk (GSW) framework of Harshaw et al (2024) for linear covariate balancing, we introduce a design that directly controls imbalance in nonlinear structure, including polynomial and more general smooth function classes. Like GSW, the proposed design retains sufficient robustness against model misspecification. Our implementation operates directly on a Gram matrix, avoiding the expensive step of explicitly constructing the nonlinear covariate expansions. We further accelerate the nonlinear design via a low-rank approximation of the Gram matrix, achieving runtimes comparable to the GSW of Harshaw et al (2024) while preserving nonlinear covariate balance and robustness.

Theory · Probabilistic Methods

William He, Nicholas Kocurek, William Gay, Ryan O'Donnell

We study the problems of approximate sampling from and distribution testing of \emph{mixture models}, where the modes satisfy a functional inequality called \textit{approximate tensorization of entropy} (ATE). While it is known that ATE makes these tasks more efficient in the unimodal setting, mixtures of few distributions satisfying ATE do not necessarily satisfy ATE overall, leading to a lack of theoretical guarantees for multimodal distributions, which are a key challenging case of modern generative models. We show this gap can be overcome by establishing the following pair of results for mixtures of ATE distributions: 1) We show fast mixing of Glauber dynamics from a \textit{data-based initialization}, with \textit{optimal} sample complexity, for mixtures of distributions satisfying modified log-Sobolev inequalities, building on similar results in \cite{KoehlerV24, HuangMRW24} for mixtures satisfying the weaker Poincaré inequality. 2) Answering an open question from \cite{blanca2023complexity}, we give efficient identity-testers for mixtures of ATE distributions in the coordinate-conditional sampling access model.

Applications · Neuroscience, Cognitive Science

Wu S. Zihan, Ariane Delrocq, Wulfram Gerstner, Guillaume Bellec

While end-to-end self-supervised learning with backpropagation (global BP-SSL) has become central for training modern AI systems, theories of local self-supervised learning (local-SSL) have struggled to build functional representations in deep neural networks. To establish a link between global and local rules, we first develop a theory for deep linear networks: We identify conditions for local-SSL algorithms (like Forward-forward or CLAPP) to implement exactly the same weight update as a global BP-SSL. Starting from the theoretical insights, we then develop novel variants of local-SSL algorithms to approximate global BP-SSL in deep non-linear convolutional neural networks. Variants that improve the similarity between updates of local-SSL with those of global BP-SSL also show better performance on image datasets (CIFAR-10, STL-10, and Tiny ImageNet). The best local-SSL rule with the CLAPP loss function matches the performance of a comparable global BP-SSL with InfoNCE or CPC-like loss functions, and improves upon state-of-the-art for layer-wise SSL on these benchmarks.

Theory · Online Learning and Bandits

Lorenzo Croissant

Linear bandits have long been a central topic in online learning, with applications ranging from recommendation systems to adaptive clinical trials. Their general learnability has been established when the objective is to minimise the inner product between a cost parameter and the decision variable. While this is highly general, this reliance on an inner product structure belies the name of \emph{linear} bandits, and fails to account for problems such as Optimal Transport. Using the Kantorovich formulation of Optimal Transport as an example, this article shows that an inner product structure is \emph{not} necessary to achieve efficient learning in linear bandits. We propose a refinement of the classical OFUL algorithm that operates by embedding the action set into a Hilbertian subspace, where confidence sets can be built via least-squares estimation. Actions are then constrained to this subspace by penalising optimism. The analysis is completed by leveraging convergence results from penalised (entropic) transport to the Kantorovich problem. Up to this approximation term, the resulting algorithm achieves the same trajectorial regret upper bounds as the OFUL algorithm, which we turn into worst-case regret using functional regression techniques. Its regret interpolates between $\tilde{\mathcal O}(\sqrt{T})$ and ${\mathcal O}(T)$, depending on the regularity of the cost function, and recovers the parametric rate $\tilde{\mathcal O}(\sqrt{dT})$ in finite-dimensional settings.

Reinforcement Learning · Planning

Yunxiang LI, Mark Schmidt, Reza Babanezhad, Sharan Vaswani

Temporal difference (TD) learning is a fundamental algorithm for estimating value functions in reinforcement learning. Recent finite-time analyses of TD with linear function approximation quantify its theoretical convergence rate. However, they often require setting the algorithm parameters using problem-dependent quantities that are difficult to estimate in practice --- such as the minimum eigenvalue of the feature covariance ($\omega$) or the mixing time of the underlying Markov chain ($\tau_\text{mix}$). In addition, some analyses rely on nonstandard and impractical modifications, exacerbating the gap between theory and practice. To address these limitations, we use an exponential step-size schedule with the standard TD(0) algorithm. We analyze the resulting method under two sampling regimes: independent and identically distributed (i.i.d.) sampling from the stationary distribution, and the more practical Markovian sampling along a single trajectory. In the i.i.d. setting, the proposed algorithm does not require the knowledge of problem-dependent quantities such as $\omega$, and attains the optimal bias-variance trade-off for the last iterate. In the Markovian setting, we propose a regularized TD(0) algorithm with an exponential step-size schedule. The resulting algorithm achieves a comparable convergence rate to prior works, without requiring projections, iterate averaging, or knowledge of $\tau_\text{mix}$ or $\omega$.

Probabilistic Methods · Gaussian Processes

Marcus Noack, Mark Risser, HENGRUI LUO, Vardaan Tekriwal, Ronald Pandolfi

Despite a large corpus of recent work on scaling up Gaussian processes, a stubborn trade-off between computational speed, prediction and uncertainty quantification accuracy, and customizability persists. This is because the vast majority of existing methodologies exploit various levels of approximations that lower accuracy and limit the flexibility of kernel and noise-model designs --- an unacceptable drawback at a time when expressive non-stationary kernels are on the rise in many fields. Here, we propose a methodology we term \emph{gp2Scale} that scales exact Gaussian processes to more than 10 million data points without relying on inducing points, kernel interpolation, or neighborhood-based approximations, and instead leveraging the existing capabilities of a GP: its kernel design. Highly flexible, compactly supported, and non-stationary kernels lead to the identification of naturally occurring sparse structure in the covariance matrix, which is then exploited for the calculations of the linear system solution and the log-determinant for training. We demonstrate our method's functionality on several real-world datasets and compare it with state-of-the-art approximation algorithms. Although we show superior approximation performance in many cases, the method's real power lies in its agnosticism toward arbitrary GP customizations --- core kernel design, noise, and mean functions --- and the type of input space, making it optimally suited for modern Gaussian process applications.

Reinforcement Learning · Everything Else

Xiyue Peng, Lingkai Zu, Ziyu Shao, Xin Liu

We study episodic constrained Markov decision processes (CMDPs) with linear function approximation, where the goal is to achieve strong regret and constraint violation guarantees without allowing error cancellations. Unlike the existing work, which focuses on either tabular CMDP or model-based reinforcement learning methods. We propose a model-free policy APMPO that achieves near-optimal $\widetilde{O}(\sqrt{K})$ strong regret and strong constraint violation with Slater's condition (or strict feasibility assumption), where $K$ is the total number of episodes. It matches the best-known rates without requiring any prior knowledge of the feasibility gap reported in prior model-based work for tabular CMDPs. Besides, APMPO achieves $\widetilde{O}(K^{\frac{3}{4}})$ strong regret and $\widetilde{O}(K^\frac{3}{4})$ strong constraint violation without Slater's condition. To the best of our knowledge, this is the first sublinear result of CMDP w.r.t. the strong metrics without Slater's condition. APMPO achieves these results by a novel and adaptive design of a violation-aware penalty and learning rates to balance the strong regret and constraint violation, which is quite different from the (regularized) primal-dual methods imposing constraints via dual penalty in the literature. The experiments show APMPO significantly outperforms the strong baselines, which justify our design and theoretical performance.

Theory · Everything Else

Chansophea Wathanak In, Yi Li, Wai Ming Tai, Xuan Wu

This paper studies active regression for single-index models under general $\ell_p$-loss with an unknown $1$-Lipschitz link function $f$, formulated as $\min_{f,x} \Vert f(Ax)-b\Vert_p^p$ with full access to $A$ but coordinate-query access to $b$. Prior work established upper bounds for known link functions for all $p\geq 1$ and for unknown link functions only in the $p=2$ case, together with lower bounds for $p\leq 2$. This work addresses the more challenging setting of unknown link functions and general $p \geq 1$. A non-adaptive sampling algorithm is presented that achieves a $(1+\epsilon)$-approximation using $O(d^{p/2\vee 1}/\epsilon^{p\vee 2}\text{poly}\log(n/\epsilon))$ queries. Nearly tight lower bounds are also established for non-adaptive queries when $p>2$. These results close much of the remaining gap in active $\ell_p$ regression for single-index models.

Optimization · Non-Convex

Luxuan Li, Xiao Wang, Chunfeng Cui

In this paper, we study a general class of nonconvex constrained stochastic problems with difference-of-convex (DC) regularization, where the feasible set is possibly nonconvex, and the concave part of the DC regularizer is allowed to be nonsmooth. The fundamental challenge lies in maintaining feasibility for nonconvex constraints while achieving favorable oracle complexity. Although single-loop algorithms are efficient in solving unconstrained DC optimization problems, their potential for constrained optimization with DC structure remains largely unexplored. To address this gap, we develop **MoSSP**, a **Mo**mentum-based **S**ingle-loop **S**tochastic **P**enalty method for such problems with provable complexity guarantee. The key idea is to perform a single stochastic proximal-gradient update that approximates the gradient of the Moreau envelope of the composite term, which consists of the penalty function and the convex component of the DC regularizer. Simultaneously, the proximal mapping of its concave component is computed in parallel. We derive two algorithm variants: a Polyak-momentum version with $\mathcal{O}(\varepsilon^{-4})$ oracle complexity for finding stochastic $\varepsilon$-KKT points, and an improved $\mathcal{O}(\varepsilon^{-3})$ version incorporating recursive momentum. Experiment results demonstrate the effectiveness of our proposed algorithms.

Theory · Domain Adaptation and Transfer Learning

Subash Timilsina, Hoang-Son Nguyen, Sagar Shrestha, Xiao Fu

Generative analysis often models multi-domain observations as nonlinear mixtures of domain-invariant content variables and domain-specific style variables. Identifying both factors from unpaired domains enables tasks such as domain transfer and counterfactual data generation. Prior work establishes identifiability under (block-wise) statistical independence between content and style, or via sparse Jacobian assumptions on the nonlinear mixing function, but such conditions can be restrictive and may not hold in practice. In this work, we introduce differential independence, a weaker structural condition requiring that infinitesimal variations in content and style induce orthogonal directions on the data manifold, thereby enabling identifiability even when content and style are dependent and the Jacobian is dense. We operationalize this condition through a blockwise orthogonality constraint on the Jacobian subspaces associated with content and style. To support high-dimensional generative models, we design a stochastic regularizer based on numerical Jacobian approximation, enabling scalable training in settings such as high-resolution image generation. Experiments across multiple datasets corroborate the identifiability analysis and demonstrate practical benefits on counterfactual generation and domain translation tasks.