GenAI4ELab/papercli-papers huggingface dataset:
Individual Regret in Cooperative Stochastic Multi-Armed Bandits
Authors: Idan Barnea; Tal Lancewicki; Yishay Mansour
Venue: NeurIPS 2025 (NeurIPS 2025 poster)

Abstract: We study the regret in stochastic Multi-Armed Bandits (MAB) with multiple agents that communicate over an arbitrary connected communication graph.
We analyzed a variant of Cooperative Successive Elimination algorithm, $\texttt{Coop-SE}$, and show an individual regret bound of ${O}(\mathcal{R} / m + A^2   + A \sqrt{\log T})$ and a nearly matching lower bound.
Here $A$ is the number of actions, $T$ the time horizon, $m$ the number of agents, and $\mathcal{R} = \sum_{\Delta_i > 0}\log(T)/\Delta_i$ is the optimal single agent regret, where $\Delta_i$ is the sub-optimality gap of action $i$.
Our work is the first to show an individual regret bound in cooperative stochastic MAB that is independent of the graph's diameter.

When considering communication networks there are additional considerations beyond regret, such as message size and number of communication rounds.
First, we show that our regret bound holds even if we restrict the messages to be of logarithmic size.
Second, for logarithmic number of
communication rounds, we obtain a regret bound of ${O}(\mathcal{R} / m+A \log T)$.
Low-degree evidence for computational transition of recovery rate in stochastic block model
Authors: Jingqiu Ding; Yiding Hua; Lucas Slot; David Steurer
Venue: NeurIPS 2025 (NeurIPS 2025 spotlight)

Abstract: We investigate implications of the (extended) low-degree conjecture (recently formalized in [moitra et al2023]) in the context of the symmetric stochastic block model. Assuming the conjecture holds, we establish that no polynomial-time algorithm can weakly recover community labels below the Kesten-Stigum (KS) threshold. In particular, we rule out polynomial-time estimators that, with constant probability, achieve $n^{-0.49}$ correlation with the true communities. 
Whereas, above the KS threshold, polynomial-time algorithms are known to achieve constant correlation with the true communities with high probability  [massoulie et al 2014,abbe et al 2015]. 

To our knowledge, we provide the first rigorous evidence for such sharp transition in recovery rate for polynomial-time algorithms at the KS threshold. 
Notably, under a stronger version of the low-degree conjecture, our lower bound remains valid even when the number of blocks diverges. 
Furthermore, our results provide evidence of a computational-to-statistical gap in learning the parameters of stochastic block models.

In contrast, prior work either (i) rules out polynomial-time algorithms with $1 - o(1)$ success probability [Hopkins 18, bandeira et al 2021] under the low-degree conjecture, or (ii) degree-$\text{poly}(k)$ polynomials for learning the stochastic block model [Luo et al 2023].

For this, we design a hypothesis test which succeeeds with constant probability under symmetric stochastic block model, and $1-o(1)$ probability under the distribution of \Erdos \Renyi random graphs.
Our proof combines low-degree lower bounds from [Hopkins 18, bandeira et al 2021]  with graph splitting and cross-validation techniques. 
In order to rule out general recovery algorithms, we employ the correlation preserving projection method developed in [Hopkins et al 17].
The Cost of Compression: Tight Quadratic Black-Box Attacks on Sketches for $\ell_2$ Norm Estimation
Authors: Sara Ahmadian; Edith Cohen; Uri Stemmer
Venue: NeurIPS 2025 (NeurIPS 2025 poster)

Abstract: Dimensionality reduction via linear sketching is a powerful and widely used technique, but it is known to be vulnerable to adversarial inputs. We study the \emph{black-box adversarial setting}, where a fixed, hidden sketching matrix $A \in \mathbb{R}^{k \times n}$ maps high-dimensional vectors $\boldsymbol{v} \in \mathbb{R}^n$ to lower-dimensional sketches $A\boldsymbol{v} \in \mathbb{R}^k$, and an adversary can query the system to obtain approximate $\ell_2$-norm estimates that are computed from the sketch.

We present a \emph{universal, nonadaptive attack} that, using $\tilde{O}(k^2)$ queries, either causes a failure in norm estimation or constructs an adversarial input on which the optimal estimator for the query distribution (used by the attack) fails. The attack is completely agnostic to the sketching matrix and to the estimator—it applies to \emph{any} linear sketch and \emph{any} query responder, including those that are randomized, adaptive, or tailored to the query distribution.

Our lower bound construction tightly matches the known upper bounds of $\tilde{\Omega}(k^2)$, achieved by specialized estimators for Johnson–Lindenstrauss transforms and AMS sketches. Beyond sketching, our results uncover structural parallels to adversarial attacks in image classification, highlighting fundamental vulnerabilities of compressed representations.
SnapMoGen: Human Motion Generation from Expressive Texts
Authors: chuan guo; Inwoo Hwang; Jian Wang; Bing Zhou
Venue: NeurIPS 2025 (NeurIPS 2025 poster)

Abstract: Text-to-motion generation has experienced remarkable progress in recent years. However, current approaches remain limited to synthesizing motion from short or general text prompts, primarily due to dataset constraints. This limitation undermines fine-grained controllability and generalization to unseen prompts. In this paper, we introduce SnapMoGen, a new text-motion dataset featuring high-quality motion capture data paired with accurate, \textit{expressive} textual annotations. The dataset comprises 20K motion clips totaling 44 hours, accompanied by 122 detailed textual descriptions averaging 48 words per description (vs. 12 words of HumanML3D). Importantly, these motion clips preserve original temporal continuity as they were in long sequences, facilitating research in long-term motion generation and blending. We also improve upon previous generative masked modeling approaches. Our model, MoMask++, transforms motion into \textbf{multi-scale} token sequences that better exploit the token capacity, and learns to generate all tokens using a single generative masked transformer. MoMask++ achieves state-of-the-art performance on both HumanML3D and OmniMotion benchmarks. Additionally, we demonstrate the ability to process casual user prompts by employing an LLM to reformat inputs to align with the expressivity and narration style of SnapMoGen.
Robust Integrated Learning and Pauli Noise Mitigation for Parametrized Quantum Circuits
Authors: Md Mobasshir Arshed Naved; Wenbo Xie; Wojciech Szpankowski; Ananth Grama
Venue: NeurIPS 2025 (NeurIPS 2025 poster)

Abstract: We propose a novel gradient-based framework for learning parameterized quantum circuits (PQCs) in the presence of Pauli noise in gate operation. The key innovation in our framework is the simultaneous optimization of model parameters and learning of an inverse noise channel, specifically designed to mitigate Pauli noise. Our parametrized inverse noise model utilizes the Pauli-Lindblad equation and relies on the principle underlying the Probabilistic Error Cancellation (PEC) protocol to learn an effective and scalable mechanism for noise mitigation. In contrast to conventional approaches that apply predetermined inverse noise models during execution, our method systematically mitigates Pauli noise by dynamically updating the inverse noise parameters in conjunction with the model parameters, facilitating task-specific noise adaptation throughout the learning process. We employ proximal stochastic gradient descent (proximal SGD) to ensure that updates are bounded within a feasible range to ensure stability. This approach allows the model to converge efficiently to a stationary point, balancing the trade-off between noise mitigation and computational overhead, resulting in a highly adaptable quantum model that performs robustly in noisy quantum environments. Our framework is well-suited to near-term quantum devices in the noisy intermediate-scale quantum (NISQ) era, where noise is a significant challenge.
Embeddings as Probabilistic Equivalence in Logic Programs
Authors: Jaron Maene; Efthymia Tsamoura
Venue: NeurIPS 2025 (NeurIPS 2025 poster)

Abstract: The integration of logic programs with embedding models resulted in a class of neurosymbolic frameworks that jointly learn symbolic rules and representations for the symbols in the logic (constant or predicate). The key idea that enabled this integration was the differentiable relaxation of unification, the algorithm for variable instantiation during inference in logic programs. Unlike unification, its relaxed counterpart exploits the similarity between symbols in the embedding space to decide when two symbols are semantically equivalent. We show that this similarity between symbols violates the transitive law of equivalence, leading to undesirable side effects in learning and inference. To alleviate those side effects, we are the first to revamp the well-known possible world semantics of probabilistic logic programs into new semantics called equivalence semantics. In our semantics, a probabilistic logic program induces a probability distribution over all possible equivalence relations between symbols, instead of a probability distribution over all possible subsets of probabilistic facts. We propose a factorization of the equivalence distribution using latent random variables and characterize its expressivity. Additionally, we propose both exact and approximate techniques for reasoning in our semantics. Experiments on well-known benchmarks show that the equivalence semantics leads to neurosymbolic models with up to 42% higher results than state-of-the-art baselines.
Understanding Representation Dynamics of Diffusion Models via Low-Dimensional Modeling
Authors: Xiao Li; Zekai Zhang; Xiang Li; Siyi Chen; Zhihui Zhu; Peng Wang; Qing Qu
Venue: NeurIPS 2025 (NeurIPS 2025 poster)

Abstract: Diffusion models, though originally designed for generative tasks, have demonstrated impressive self-supervised representation learning capabilities. A particularly intriguing phenomenon in these models is the emergence of unimodal representation dynamics, where the quality of learned features peaks at an intermediate noise level. In this work, we conduct a comprehensive theoretical and empirical investigation of this phenomenon. Leveraging the inherent low-dimensionality structure of image data, we theoretically demonstrate that the unimodal dynamic emerges when the diffusion model successfully captures the underlying data distribution. The unimodality arises from an interplay between denoising strength and class confidence across noise scales. Empirically, we further show that, in classification tasks, the presence of unimodal dynamics reliably reflects the diffusion model’s generalization: it emerges when the model generate novel images and gradually transitions to a monotonically decreasing curve as the model begins to memorize the training data.
Gompertz Linear Units: Leveraging Asymmetry for Enhanced Learning Dynamics
Authors: Indrashis Das; Mahmoud Safari; Steven Adriaensen; Frank Hutter
Venue: NeurIPS 2025 (NeurIPS 2025 poster)

Abstract: Activation functions are fundamental elements of deep learning architectures as they significantly influence training dynamics. ReLU, while widely used, is prone to the dying neuron problem, which has been mitigated by variants such as LeakyReLU, PReLU, and ELU that better handle negative neuron outputs. Recently, self-gated activations like GELU and Swish have emerged as state-of-the-art alternatives, leveraging their smoothness to ensure stable gradient flow and prevent neuron inactivity. In this work, we introduce the Gompertz Linear Unit (GoLU), a novel self-gated activation function defined as $\mathrm{GoLU}(x) = x \\, \mathrm{Gompertz}(x)$, where $\mathrm{Gompertz}(x) = e^{-e^{-x}}$. The GoLU activation leverages the right-skewed asymmetry in the Gompertz function to reduce variance in the latent space more effectively compared to GELU and Swish, while preserving robust gradient flow. Extensive experiments across diverse tasks, including Image Classification, Language Modeling, Semantic Segmentation, Object Detection, Instance Segmentation, and Diffusion, highlight GoLU's superior performance relative to state-of-the-art activation functions, establishing GoLU as a robust alternative to existing activation functions.
Nonlinear Laplacians: Tunable principal component analysis under directional prior information
Authors: Yuxin Ma; Dmitriy Kunisky
Venue: NeurIPS 2025 (NeurIPS 2025 spotlight)

Abstract: We introduce a new family of algorithms for detecting and estimating a rank-one signal from a noisy observation under prior information about that signal's direction, focusing on examples where the signal is known to have entries biased to be positive. Given a matrix observation $\mathbf{Y}$, our algorithms construct a *nonlinear Laplacian*, another matrix of the form $\mathbf{Y} + \mathrm{diag}(\sigma(\mathbf{Y1}))$ for a nonlinear $\sigma: \mathbb{R} \to \mathbb{R}$, and examine the top eigenvalue and eigenvector of this matrix. When $\mathbf{Y}$ is the (suitably normalized) adjacency matrix of a graph, our approach gives a class of algorithms that search for unusually dense subgraphs by computing a spectrum of the graph "deformed" by the degree profile $\mathbf{Y1}$. We study the performance of such algorithms compared to direct spectral algorithms (the case $\sigma = 0$) on models of sparse principal component analysis with biased signals, including the Gaussian planted submatrix problem. For such models, we rigorously characterize the strength of rank-one signal, as a function of the nonlinearity $\sigma$, required for an outlier eigenvalue to appear in the spectrum of a nonlinear Laplacian matrix. While identifying the $\sigma$ that minimizes the required signal strength in closed form seems intractable, we explore three approaches to design $\sigma$ numerically: exhaustively searching over simple classes of $\sigma$, learning $\sigma$ from datasets of problem instances, and tuning $\sigma$ using black-box optimization of the critical signal strength. We find both theoretically and empirically that, if $\sigma$ is chosen appropriately, then nonlinear Laplacian spectral algorithms substantially outperform direct spectral algorithms, while retaining the conceptual simplicity of spectral methods compared to broader classes of computations like approximate message passing or general first order methods.
Restricted Spectral Gap Decomposition for Simulated  Tempering Targeting Mixture Distributions
Authors: Jhanvi Garg; Krishna Balasubramanian; Quan Zhou
Venue: NeurIPS 2025 (NeurIPS 2025 poster)

Abstract: Simulated tempering is a widely used strategy for sampling from multimodal distributions. In this paper, we consider simulated tempering combined with an arbitrary local Markov chain Monte Carlo sampler and present a new decomposition theorem that provides a lower bound on the restricted spectral gap of the algorithm for sampling from mixture distributions.  By working with the restricted spectral gap, the applicability of our results is extended to broader settings such as when the usual spectral gap is difficult to bound or becomes degenerate. We demonstrate the application of our theoretical results by analyzing simulated tempering combined with random walk Metropolis--Hastings for sampling from mixtures of Gaussian distributions. Our complexity bound scales polynomially with the separation between modes, logarithmically with $1/\varepsilon$, where $\varepsilon$ denotes the target accuracy in total variation distance, and exponentially with the dimension $d$.
FreeControl: Efficient, Training-Free Structural Control via One-Step Attention Extraction
Authors: Jiang Lin; Xinyu Chen; Song Wu; Zhiqiu Zhang; Jizhi Zhang; Ye Wang; Qiang Tang; qian Wang; Jian Yang; Zili Yi
Venue: NeurIPS 2025 (NeurIPS 2025 poster)

Abstract: Controlling the spatial and semantic structure of diffusion-generated images remains a challenge. Existing methods like ControlNet rely on handcrafted condition maps and retraining, limiting flexibility and generalization. Inversion-based approaches offer stronger alignment but incur high inference cost due to dual-path denoising.
We present \textbf{FreeControl}, a training-free framework for semantic structural control in diffusion models. Unlike prior methods that extract attention across multiple timesteps, FreeControl performs \textit{one-step attention extraction} from a single, optimally chosen timestep and reuses it throughout denoising.  This enables efficient structural guidance without inversion or retraining.
To further improve quality and stability, we introduce \textit{Latent-Condition Decoupling (LCD)}: a principled separation of the timestep condition and the noised latent used in attention extraction. LCD provides finer control over attention quality and eliminates structural artifacts. FreeControl also supports compositional control via reference images assembled from multiple sources, enabling intuitive scene layout design and stronger prompt alignment. FreeControl introduces a new paradigm for test-time control—enabling structurally and semantically aligned, visually coherent generation directly from raw images, with the flexibility for intuitive compositional design and compatibility with modern diffusion models at ~5\% additional cost.
Finite Sample Analysis of Linear Temporal Difference Learning with Arbitrary Features
Authors: Zixuan Xie; Xinyu Liu; Rohan Chandra; Shangtong Zhang
Venue: NeurIPS 2025 (NeurIPS 2025 poster)

Abstract: Linear TD($\lambda$) is one of the most fundamental reinforcement learning algorithms for policy evaluation. Previously, convergence rates are typically established under the assumption of linearly independent features, which does not hold in many practical scenarios. This paper instead establishes the first $L^2$ convergence rates for linear TD($\lambda$) operating under arbitrary features, without making any algorithmic modification or additional assumptions. Our results apply to both the discounted and average-reward settings. To address the potential non-uniqueness of solutions resulting from arbitrary features, we develop a novel stochastic approximation result featuring convergence rates to the solution set instead of a single point.
Chain-of-Zoom: Extreme Super-Resolution via Scale Autoregression and Preference Alignment
Authors: Bryan Sangwoo Kim; Jeongsol Kim; Jong Chul Ye
Venue: NeurIPS 2025 (NeurIPS 2025 spotlight)

Abstract: Modern single-image super-resolution (SISR) models deliver photo-realistic results at the scale factors on which they are trained, but collapse when asked to magnify far beyond that regime. We address this scalability bottleneck with Chain-of-Zoom (CoZ), a model-agnostic framework that factorizes SISR into an autoregressive chain of intermediate scale-states with multi-scale-aware prompts. CoZ repeatedly re-uses a backbone SR model, decomposing the conditional probability into tractable sub-problems to achieve extreme resolutions without additional training. Because visual cues diminish at high magnifications, we augment each zoom step with multi-scale-aware text prompts generated by a vision-language model (VLM). The prompt extractor itself is fine-tuned using  Generalized Reward Policy Optimization (GRPO) with a critic VLM, aligning text guidance towards human preference. Experiments show that a standard $4\times$ diffusion SR model wrapped in CoZ attains beyond $256\times$ enlargement with high perceptual quality and fidelity.
ImageNet-trained CNNs are not biased towards texture: Revisiting feature reliance through controlled suppression
Authors: Tom Burgert; Oliver Stoll; Paolo Rota; Begüm Demir
Venue: NeurIPS 2025 (NeurIPS 2025 oral)

Abstract: The hypothesis that Convolutional Neural Networks (CNNs) are inherently texture-biased has shaped much of the discourse on feature use in deep learning. We revisit this hypothesis by examining limitations in the cue-conflict experiment by Geirhos et al. To address these limitations, we propose a domain-agnostic framework that quantifies feature reliance through systematic suppression of shape, texture, and color cues, avoiding the confounds of forced-choice conflicts. By evaluating humans and neural networks under controlled suppression conditions, we find that CNNs are not inherently texture-biased but predominantly rely on local shape features. Nonetheless, this reliance can be substantially mitigated through modern training strategies or architectures (ConvNeXt, ViTs). We further extend the analysis across computer vision, medical imaging, and remote sensing, revealing that reliance patterns differ systematically: computer vision models prioritize shape, medical imaging models emphasize color, and remote sensing models exhibit a stronger reliance on texture. Code is available at https://github.com/tomburgert/feature-reliance.
DataRater: Meta-Learned Dataset Curation
Authors: Dan A. Calian; Gregory Farquhar; Iurii Kemaev; Luisa Zintgraf; Matteo Hessel; Jeremy Shar; Junhyuk Oh; András György; Tom Schaul; Jeff Dean; Hado van Hasselt; David Silver
Venue: NeurIPS 2025 (NeurIPS 2025 poster)

Abstract: The quality of foundation models depends heavily on their training data.
Consequently, great efforts have been put into dataset curation.
Yet most approaches rely on manual tuning of coarse-grained mixtures of large buckets of data, or filtering by hand-crafted heuristics.
An approach that is ultimately more scalable (let alone more satisfying) is to \emph{learn} which data is actually valuable for training.
This type of meta-learning could allow more sophisticated, fine-grained, and effective curation.
Our proposed \emph{DataRater} is an instance of this idea. It estimates the value of training on any particular data point. This is done by meta-learning using `meta-gradients', with the objective of improving training efficiency on held out data.
In extensive experiments across a range of model scales and datasets, we find that using our DataRater to filter data is highly effective, resulting in significantly improved compute efficiency.
Optimistic Query Routing in Clustering-based Approximate Maximum Inner Product Search
Authors: Sebastian Bruch; Aditya Krishnan; Franco Maria Nardini
Venue: NeurIPS 2025 (NeurIPS 2025 poster)

Abstract: Clustering-based nearest neighbor search algorithms partition points into shards to form an index, and search only a subset of shards to process a query. Even though search efficacy is heavily influenced by the algorithm that identifies the shards to probe, it has received little attention in the literature. We study routing in clustering-based maximum inner product search, which includes cosine similarity search. We unpack existing routers and notice the surprising role of optimism. We then take a page from the sequential decision making literature and formalize that insight following the principle of ``optimism in the face of uncertainty.'' In particular, we present a framework that incorporates the moments of the distribution of inner products within each shard to estimate the maximum inner product. We then develop a practical instance of our algorithm that uses only the first two moments to reach the same accuracy as state-of-the-art routers by probing up to $50\%$ fewer points on benchmark datasets without compromising efficiency. Our algorithm is also space-efficient: we design a sketch of the second moment whose size is independent of the number of points and requires $\mathcal{O}(1)$ vectors per shard.