pwc-archive/papers-with-abstracts huggingface dataset:
Information-Theoretic Guarantees for Recovering Low-Rank Tensors from Symmetric Rank-One Measurements
Authors: Eren C. Kızıldağ
Date: 2025-02-07 00:00:00

In this paper, we investigate the sample complexity of recovering tensors with low symmetric rank from symmetric rank-one measurements. This setting is particularly motivated by the study of higher-order interactions and the analysis of two-layer neural networks with polynomial activations (polynomial networks). Using a covering numbers argument, we analyze the performance of the symmetric rank minimization program and establish near-optimal sample complexity bounds when the underlying distribution is log-concave. Our measurement model involves random symmetric rank-one tensors, which lead to involved probability calculations. To address these challenges, we employ the Carbery-Wright inequality, a powerful tool for studying anti-concentration properties of random polynomials, and leverage orthogonal polynomials. Additionally, we provide a sample complexity lower bound based on Fano's inequality, and discuss broader implications of our results for two-layer polynomial networks.
UAV-Based Cell-Free Massive MIMO: Joint Placement and Power Optimization under Fronthaul Capacity Limitations
Authors: Neetu R. R, Ozan Alp Topal, Özlem Tuğfe Demir, Emil Björnson, Cicek Cavdar, Gourab Ghatak, Vivek Ashok Bohara
Date: 2025-02-07 00:00:00

We consider a cell-free massive multiple-input multiple-output (mMIMO) network, where unmanned aerial vehicles (UAVs) equipped with multiple antennas serve as distributed UAV-access points (UAV-APs). These UAV-APs provide seamless coverage by jointly serving user equipments (UEs) with out predefined cell boundaries. However, high-capacity wireless networks face significant challenges due to fronthaul limitations in UAV-assisted architectures. This letter proposes a novel UAV-based cell-free mMIMO framework that leverages distributed UAV-APs to serve UEs while addressing the capacity constraints of wireless fronthaul links. We evaluate functional split Options 7.2 and 8 for the fronthaul links, aiming to maximize the minimum signal-to-interference-plus-noise ratio (SINR) among the UEs and minimize the power consumption by optimizing the transmit powers of UAV-APs and selectively activating them. Our analysis compares sub-6 GHz and millimeter wave (mmWave) bands for the fronthaul, showing that mmWave achieves superior SINR with lower power consumption, particularly under Option 8. Additionally, we determine the minimum fronthaul bandwidth required to activate a single UAV-AP under different split options.
Dark Brain Energy: Toward an Integrative Model of Spontaneous Slow Oscillations
Authors: ZhuQing Gong, XiNian Zuo
Date: 2025-02-06 00:00:00
Tasks: Anatomy, Specificity

Neural oscillations facilitate the functioning of the human brain in spatial and temporal dimensions at various frequencies. These oscillations feature a universal frequency architecture that is governed by brain anatomy, ensuring frequency specificity remains invariant across different measurement techniques. Initial magnetic resonance imaging (MRI) methodology constrained functional MRI (fMRI) investigations to a singular frequency range, thereby neglecting the frequency characteristics inherent in blood oxygen level-dependent oscillations. With advancements in MRI technology, it has become feasible to decode intricate brain activities via multi-band frequency analysis (MBFA). During the past decade, the utilization of MBFA in fMRI studies has surged, unveiling frequency-dependent characteristics of spontaneous slow oscillations (SSOs) believed to base dark energy in the brain. There remains a dearth of conclusive insights and hypotheses pertaining to the properties and functionalities of SSOs in distinct bands. We surveyed the SSO MBFA studies during the past 15 years to delineate the attributes of SSOs and enlighten their correlated functions. We further proposed a model to elucidate the hierarchical organization of multi-band SSOs by integrating their function, aimed at bridging theoretical gaps and guiding future MBFA research endeavors.
Speeding up Speculative Decoding via Sequential Approximate Verification
Authors: Meiyu Zhong, Noel Teku, Ravi Tandon
Date: 2025-02-06 00:00:00

Speculative Decoding (SD) is a recently proposed technique for faster inference using Large Language Models (LLMs). SD operates by using a smaller draft LLM for autoregressively generating a sequence of tokens and a larger target LLM for parallel verification to ensure statistical consistency. However, periodic parallel calls to the target LLM for verification prevent SD from achieving even lower latencies. We propose SPRINTER, which utilizes a low-complexity verifier trained to predict if tokens generated from a draft LLM would be accepted by the target LLM. By performing sequential approximate verification, SPRINTER does not require verification by the target LLM and is only invoked when a token is deemed unacceptable. This reduces the number of calls to the larger LLM, achieving further speedups and lower computation cost. We present a theoretical analysis of SPRINTER, examining the statistical properties of the generated tokens, as well as the expected reduction in latency as a function of the verifier. We evaluate SPRINTER on several datasets and model pairs, demonstrating that approximate verification can still maintain high quality generation while further reducing latency.
Ensuring Reliability via Hyperparameter Selection: Review and Advances
Authors: Amirmohammad Farzaneh, Osvaldo Simeone
Date: 2025-02-06 00:00:00

Hyperparameter selection is a critical step in the deployment of artificial intelligence (AI) models, particularly in the current era of foundational, pre-trained, models. By framing hyperparameter selection as a multiple hypothesis testing problem, recent research has shown that it is possible to provide statistical guarantees on population risk measures attained by the selected hyperparameter. This paper reviews the Learn-Then-Test (LTT) framework, which formalizes this approach, and explores several extensions tailored to engineering-relevant scenarios. These extensions encompass different risk measures and statistical guarantees, multi-objective optimization, the incorporation of prior knowledge and dependency structures into the hyperparameter selection process, as well as adaptivity. The paper also includes illustrative applications for communication systems.
Variations on the Expectation due to Changes in the Probability Measure
Authors: Samir M. Perlaza, Gaetan Bisson
Date: 2025-02-05 00:00:00
Tasks: Form

In this paper, closed-form expressions are presented for the variation of the expectation of a given function due to changes in the probability measure used for the expectation. They unveil interesting connections with Gibbs probability measures, mutual information, and lautum information.
Theoretical Guarantees for Low-Rank Compression of Deep Neural Networks
Authors: Shihao Zhang, Rayan Saab
Date: 2025-02-04 00:00:00
Tasks: Low-rank compression, Model Compression

Deep neural networks have achieved state-of-the-art performance across numerous applications, but their high memory and computational demands present significant challenges, particularly in resource-constrained environments. Model compression techniques, such as low-rank approximation, offer a promising solution by reducing the size and complexity of these networks while only minimally sacrificing accuracy. In this paper, we develop an analytical framework for data-driven post-training low-rank compression. We prove three recovery theorems under progressively weaker assumptions about the approximate low-rank structure of activations, modeling deviations via noise. Our results represent a step toward explaining why data-driven low-rank compression methods outperform data-agnostic approaches and towards theoretically grounded compression algorithms that reduce inference costs while maintaining performance.
Three-dimensional signal processing: a new approach in dynamical sampling via tensor products
Authors: Yisen Wang, HanQin Cai, Longxiu Huang
Date: 2025-02-04 00:00:00

The dynamical sampling problem is centered around reconstructing signals that evolve over time according to a dynamical process, from spatial-temporal samples that may be noisy. This topic has been thoroughly explored for one-dimensional signals. Multidimensional signal recovery has also been studied, but primarily in scenarios where the driving operator is a convolution operator. In this work, we shift our focus to the dynamical sampling problem in the context of three-dimensional signal recovery, where the evolution system can be characterized by tensor products. Specifically, we provide a necessary condition for the sampling set that ensures successful recovery of the three-dimensional signal. Furthermore, we reformulate the reconstruction problem as an optimization task, which can be solved efficiently. To demonstrate the effectiveness of our approach, we include some straightforward numerical simulations that showcase the reconstruction performance.
Analysis of Diffusion Models for Manifold Data
Authors: Anand Jerry George, Rodrigo Veiga, Nicolas Macris
Date: 2025-02-01 00:00:00

We analyze the time reversed dynamics of generative diffusion models. If the exact empirical score function is used in a regime of large dimension and exponentially large number of samples, these models are known to undergo transitions between distinct dynamical regimes. We extend this analysis and compute the transitions for an analytically tractable manifold model where the statistical model for the data is a mixture of lower dimensional Gaussians embedded in higher dimensional space. We compute the so-called speciation and collapse transition times, as a function of the ratio of manifold-to-ambient space dimensions, and other characteristics of the data model. An important tool used in our analysis is the exact formula for the mutual information (or free energy) of Generalized Linear Models.
ProofWala: Multilingual Proof Data Synthesis and Theorem-Proving
Authors: Amitayush Thakur, George Tsoukalas, Greg Durrett, Swarat Chaudhuri
Date: 2025-02-07 00:00:00
Tasks: Automated Theorem Proving

Neural networks have shown substantial promise at automatic theorem-proving in interactive proof assistants (ITPs) like Lean and Coq. However, most neural theorem-proving models are restricted to specific ITPs, leaving out opportunities for cross-lingual $\textit{transfer}$ between ITPs. We address this weakness with a multilingual proof framework, ${\rm P{\small ROOF}W{\small ALA}}$, that allows a standardized form of interaction between neural theorem-provers and two established ITPs (Coq and Lean). It enables the collection of multilingual proof step data -- data recording the result of proof actions on ITP states -- for training neural provers. ${\rm P{\small ROOF}W{\small ALA}}$ allows the systematic evaluation of a model's performance across different ITPs and problem domains via efficient parallel proof search algorithms. We show that multilingual training enabled by ${\rm P{\small ROOF}W{\small ALA}}$ can lead to successful transfer across ITPs. Specifically, a model trained on a mix of ${\rm P{\small ROOF}W{\small ALA}}$-generated Coq and Lean data outperforms Lean-only and Coq-only models on the standard prove-at-$k$ metric. We open source all code including code for the ${\rm P{\small ROOF}W{\small ALA}}$ Framework (https://github.com/trishullab/proof-wala), and the Multilingual ITP interaction framework (https://github.com/trishullab/itp-interface).
Solvability of Approximate Reach-Avoid Games
Authors: Mario Gleirscher
Date: 2025-02-06 00:00:00

Objective: In a companion paper, we propose a parametric hybrid automaton model and an algorithm for the online synthesis of robustly correct and near-optimal controllers for cyber-physical system with reach-avoid guarantees. A key part of this synthesis problem is based on a weighted discretised game and solved via scope-adaptive discrete dynamic programming. Approach: This work examines proofs of key properties of the discussed algorithm. Evaluation: The main proof is by induction over the stages of a discrete Hamilton-Jacobi-Bellman system of equations. Contribution: The results include a game solvability theorem and identify necessary and sufficient conditions for its applicability.
Strong Equivalence in Answer Set Programming with Constraints
Authors: Pedro Cabalar, Jorge Fandinno, Torsten Schaub, Philipp Wanko
Date: 2025-02-06 00:00:00
Tasks: Translation

We investigate the concept of strong equivalence within the extended framework of Answer Set Programming with constraints. Two groups of rules are considered strongly equivalent if, informally speaking, they have the same meaning in any context. We demonstrate that, under certain assumptions, strong equivalence between rule sets in this extended setting can be precisely characterized by their equivalence in the logic of Here-and-There with constraints. Furthermore, we present a translation from the language of several clingo-based answer set solvers that handle constraints into the language of Here-and-There with constraints. This translation enables us to leverage the logic of Here-and-There to reason about strong equivalence within the context of these solvers. We also explore the computational complexity of determining strong equivalence in this context.
Explain Yourself, Briefly! Self-Explaining Neural Networks with Concise Sufficient Reasons
Authors: Shahaf Bassan, Ron Eliav, Shlomit Gur
Date: 2025-02-05 00:00:00

*Minimal sufficient reasons* represent a prevalent form of explanation - the smallest subset of input features which, when held constant at their corresponding values, ensure that the prediction remains unchanged. Previous *post-hoc* methods attempt to obtain such explanations but face two main limitations: (1) Obtaining these subsets poses a computational challenge, leading most scalable methods to converge towards suboptimal, less meaningful subsets; (2) These methods heavily rely on sampling out-of-distribution input assignments, potentially resulting in counterintuitive behaviors. To tackle these limitations, we propose in this work a self-supervised training approach, which we term *sufficient subset training* (SST). Using SST, we train models to generate concise sufficient reasons for their predictions as an integral part of their output. Our results indicate that our framework produces succinct and faithful subsets substantially more efficiently than competing post-hoc methods, while maintaining comparable predictive performance.
Token Assorted: Mixing Latent and Text Tokens for Improved Language Model Reasoning
Authors: DiJia Su, Hanlin Zhu, Yingchen Xu, Jiantao Jiao, Yuandong Tian, Qinqing Zheng
Date: 2025-02-05 00:00:00
Tasks: Language Modeling, Language Modelling, Mathematical Reasoning

Large Language Models (LLMs) excel at reasoning and planning when trained on chainof-thought (CoT) data, where the step-by-step thought process is explicitly outlined by text tokens. However, this results in lengthy inputs where many words support textual coherence rather than core reasoning information, and processing these inputs consumes substantial computation resources. In this work, we propose a hybrid representation of the reasoning process, where we partially abstract away the initial reasoning steps using latent discrete tokens generated by VQ-VAE, significantly reducing the length of reasoning traces. We explore the use of latent trace abstractions in two scenarios: 1) training the model from scratch for the Keys-Finding Maze problem, 2) fine-tuning LLMs on this hybrid data with an extended vocabulary including unseen latent tokens, for both logical and mathematical reasoning problems. To facilitate effective learning, we introduce a simple training procedure that randomly mixes latent and text tokens, which enables fast adaptation to new latent tokens. Our approach consistently outperforms the baselines methods in various benchmarks.
Near-Optimal Online Learning for Multi-Agent Submodular Coordination: Tight Approximation and Communication Efficiency
Authors: Qixin Zhang, Zongqi Wan, Yu Yang, Li Shen, DaCheng Tao
Date: 2025-02-07 00:00:00

Coordinating multiple agents to collaboratively maximize submodular functions in unpredictable environments is a critical task with numerous applications in machine learning, robot planning and control. The existing approaches, such as the OSG algorithm, are often hindered by their poor approximation guarantees and the rigid requirement for a fully connected communication graph. To address these challenges, we firstly present a $\textbf{MA-OSMA}$ algorithm, which employs the multi-linear extension to transfer the discrete submodular maximization problem into a continuous optimization, thereby allowing us to reduce the strict dependence on a complete graph through consensus techniques. Moreover, $\textbf{MA-OSMA}$ leverages a novel surrogate gradient to avoid sub-optimal stationary points. To eliminate the computationally intensive projection operations in $\textbf{MA-OSMA}$, we also introduce a projection-free $\textbf{MA-OSEA}$ algorithm, which effectively utilizes the KL divergence by mixing a uniform distribution. Theoretically, we confirm that both algorithms achieve a regret bound of $\widetilde{O}(\sqrt{\frac{C_{T}T}{1-\beta}})$ against a $(\frac{1-e^{-c}}{c})$-approximation to the best comparator in hindsight, where $C_{T}$ is the deviation of maximizer sequence, $\beta$ is the spectral gap of the network and $c$ is the joint curvature of submodular objectives. This result significantly improves the $(\frac{1}{1+c})$-approximation provided by the state-of-the-art OSG algorithm. Finally, we demonstrate the effectiveness of our proposed algorithms through simulation-based multi-target tracking.
$TAR^2$: Temporal-Agent Reward Redistribution for Optimal Policy Preservation in Multi-Agent Reinforcement Learning
Authors: Aditya Kapoor, Kale-ab Tessera, Mayank Baranwal, Harshad Khadilkar, Stefano Albrecht, Mingfei Sun
Date: 2025-02-07 00:00:00
Tasks: Multi-agent Reinforcement Learning, TAR

In cooperative multi-agent reinforcement learning (MARL), learning effective policies is challenging when global rewards are sparse and delayed. This difficulty arises from the need to assign credit across both agents and time steps, a problem that existing methods often fail to address in episodic, long-horizon tasks. We propose Temporal-Agent Reward Redistribution $TAR^2$, a novel approach that decomposes sparse global rewards into agent-specific, time-step-specific components, thereby providing more frequent and accurate feedback for policy learning. Theoretically, we show that $TAR^2$ (i) aligns with potential-based reward shaping, preserving the same optimal policies as the original environment, and (ii) maintains policy gradient update directions identical to those under the original sparse reward, ensuring unbiased credit signals. Empirical results on two challenging benchmarks, SMACLite and Google Research Football, demonstrate that $TAR^2$ significantly stabilizes and accelerates convergence, outperforming strong baselines like AREL and STAS in both learning speed and final performance. These findings establish $TAR^2$ as a principled and practical solution for agent-temporal credit assignment in sparse-reward multi-agent systems.
Free Energy Risk Metrics for Systemically Safe AI: Gatekeeping Multi-Agent Study
Authors: Michael Walters, Rafael Kaufmann, Justice Sefas, Thomas Kopinski
Date: 2025-02-06 00:00:00
Tasks: Decision Making

We investigate the Free Energy Principle as a foundation for measuring risk in agentic and multi-agent systems. From these principles we introduce a Cumulative Risk Exposure metric that is flexible to differing contexts and needs. We contrast this to other popular theories for safe AI that hinge on massive amounts of data or describing arbitrarily complex world models. In our framework, stakeholders need only specify their preferences over system outcomes, providing straightforward and transparent decision rules for risk governance and mitigation. This framework naturally accounts for uncertainty in both world model and preference model, allowing for decision-making that is epistemically and axiologically humble, parsimonious, and future-proof. We demonstrate this novel approach in a simplified autonomous vehicle environment with multi-agent vehicles whose driving policies are mediated by gatekeepers that evaluate, in an online fashion, the risk to the collective safety in their neighborhood, and intervene through each vehicle's policy when appropriate. We show that the introduction of gatekeepers in an AV fleet, even at low penetration, can generate significant positive externalities in terms of increased system safety.
Fairness Aware Reinforcement Learning via Proximal Policy Optimization
Authors: Gabriele La Malfa, Jie M. Zhang, Michael Luck, Elizabeth Black
Date: 2025-02-06 00:00:00
Tasks: Attribute, counterfactual, Decision Making, Fairness, reinforcement-learning, Reinforcement Learning

Fairness in multi-agent systems (MAS) focuses on equitable reward distribution among agents in scenarios involving sensitive attributes such as race, gender, or socioeconomic status. This paper introduces fairness in Proximal Policy Optimization (PPO) with a penalty term derived from demographic parity, counterfactual fairness, and conditional statistical parity. The proposed method balances reward maximisation with fairness by integrating two penalty components: a retrospective component that minimises disparities in past outcomes and a prospective component that ensures fairness in future decision-making. We evaluate our approach in the Allelopathic Harvest game, a cooperative and competitive MAS focused on resource collection, where some agents possess a sensitive attribute. Experiments demonstrate that fair-PPO achieves fairer policies across all fairness metrics than classic PPO. Fairness comes at the cost of reduced rewards, namely the Price of Fairness, although agents with and without the sensitive attribute renounce comparable amounts of rewards. Additionally, the retrospective and prospective penalties effectively change the agents' behaviour and improve fairness. These findings underscore the potential of fair-PPO to address fairness challenges in MAS.
Enhancing Online Learning Efficiency Through Heterogeneous Resource Integration with a Multi-Agent RAG System
Authors: Devansh Srivastav, Hasan Md Tusfiqur Alam, Afsaneh Asaei, Mahmoud Fazeli, Tanisha Sharma, Daniel Sonntag
Date: 2025-02-06 00:00:00
Tasks: RAG, Retrieval, Retrieval-augmented Generation

Efficient online learning requires seamless access to diverse resources such as videos, code repositories, documentation, and general web content. This poster paper introduces early-stage work on a Multi-Agent Retrieval-Augmented Generation (RAG) System designed to enhance learning efficiency by integrating these heterogeneous resources. Using specialized agents tailored for specific resource types (e.g., YouTube tutorials, GitHub repositories, documentation websites, and search engines), the system automates the retrieval and synthesis of relevant information. By streamlining the process of finding and combining knowledge, this approach reduces manual effort and enhances the learning experience. A preliminary user study confirmed the system's strong usability and moderate-high utility, demonstrating its potential to improve the efficiency of knowledge acquisition.