Schedule for: 24w5280 - Algorithmic Structures for Uncoordinated Communications and Statistical Inference in Exceedingly Large Spaces

A buffet dinner is served daily between 5:30pm and 7:30pm in Vistas Dining Room, top floor of the Sally Borden Building.

Meet and Greet at BIRS Lounge (PDC 2nd Floor)

Breakfast is served daily between 7 and 9am in the Vistas Dining Room, the top floor of the Sally Borden Building.

A brief introduction to BIRS with important logistical information, technology instruction, and opportunity for participants to ask questions.

It is common knowledge that a time-domain pulse is well adapted to pure delay channels, and that a frequency domain pulse is well adapted to pure Doppler channels. In this talk we will explain why the Zak-OTFS waveform, a pulse in the delay-Doppler domain, is well adapted to the doubly spread channels that arise in wireless communication. We will describe how to design the Zak-OTFS waveform so that the input-output (IO) relation is predictable and non-fading, and we will explain how it is possible to learn the IO relation without needing to estimate the underlying channel. We will explore the possibility of a model-free mode of operation, which is especially useful when a traditional model-dependent mode of operation (reliant on channel estimation) is out of reach. We will also describe how the Zak-OTFS waveform supports combined communication and sensing by enabling unambiguous delay-Doppler estimation.

Nonlinear random matrices have significant applications in machine learning, statistics, and signal processing. Recent results in the field have pointed to an intriguing equivalence principle for these matrices. This principle shows that their asymptotic properties, including but not limited to their spectral characteristics, are asymptotically equivalent to those of simpler, noisy linear equivalent models. In my presentation, I will discuss these recent findings, shedding light on their implications and applications in characterizing the performance of random feature regression and kernel ridge regression in high-dimensional settings.

In this talk, we investigate the distributed parameter estimation problems where the distributed nodes are allowed to communicate features of their data with given dimensionality constraints. The goal of the distributed nodes is to design the feature functions and send the corresponding statistics to the decision node to minimize the parameter estimation mean-squared error (MSE). To illustrate the insight of feature extractions in the distributed system, we first quantify the performance loss of the parameter estimation for suboptimal estimators by a local information geometric approach. Then, the proposed approach is applied to the distributed parameter estimation problems. We show that the designs of informative features for distributed nodes can be interpreted as projecting the score function of the parametrized model onto functional subspaces of distributed nodes. From that, distributed feature extraction problem can be reduced to a quadratic optimization problem, and the optimal features can be learned from training data. Finally, the operational meaning of the singular value decomposition of the Fisher information is provided in terms of informative feature extractions.

Lunch is served daily between 11:30am and 1:30pm in the Vistas Dining Room, the top floor of the Sally Borden Building.

With Release 16 of the 3GPP 5G New Radio standard, a new grant-free random access procedure has been included. The protocol, commonly referred to as two-step random access, supports the transmission of data units without negotiation of radio resources. In this presentation, we review the 3GPP two-step random access protocol from an unsourced multiple access (UMAC) perspective, analyzing its limitations. Directions on the upgrade of two-step random access in future releases of the 3GPP standard are then discussed. Taking advantage of the connection between random multiple access channels and compressed sensing (CS), we outline practical modifications of two-step random access that build on a divide-and-conquer strategy. The strategy relies on a CS phase on a set of preambles, while simultaneously sparsifying collisions in a second phase. The analysis of the proposed improvements is provided for both the Gaussian multiple access channel and for the quasi-static fading channel cases, showing how simple modifications of two-step random access may enable the support of large terminal populations, approaching the performance limits of the UMAC setting.

Meet in foyer of TCPL to participate in the BIRS group photo. The photograph will be taken outdoors, so dress appropriately for the weather. Please don't be late, or you might not be in the official group photo!

We consider tensorial modulation for unsourced random access based on Binary Subspace Chirps (BSSCs). Binary subspace chirps constitute a Grassmannian line codebook in N complex dimensions with an algebraically defined decoder of complexity $N (\log N)^3$, which is intimately connected with the Clifford groups pertinent for quantum computation. BSSCs can be understood as codebooks of on-off -patterns, combined with quadriphase Binary Chirp (BC) sequences in the “on” locations. This structure renders them suitable for controlling user activity in a coded slotted ALOHA sense. We apply order-2 tensor transmissions for random access, where a BSSC is used as an outer code to determine slotting in S dimensions, while transmissions in active slots come from the other tensorial direction represented by BCs in $M$ dimensions. This makes it possible to apply serial interference cancelation in multiuser detection, which combined with low-complexity BC decoding leads to an unsourced random access scheme with low-complexity decoder. Fixing the number of on-positions in the BSSC to be $R$, decoding of $U$ users requires complexity of order $U R M (\log M)^2$.

This work considers an asynchronous 𝖪a-active-user unsourced multiple access channel (AUMAC) with the worst-case asynchronicity. The transmitted messages must be decoded within n channel uses, while some codewords are not completely received due to asynchronicities. We consider a constraint of the largest allowed delay of the transmission. The AUMAC lacks the permutation-invariant property of the synchronous UMAC since different permutations of the same codewords with a fixed asynchronicity are distinguishable. Hence, the analyses require calculating all 2𝖪a−1 combinations of erroneously decoded messages. Moreover, transmitters cannot adapt the corresponding codebooks according to asynchronicity due to a lack of information on asynchronicities. To overcome this challenge, a uniform bound of the per-user probability of error (PUPE) is derived by investigating the worst-case of the asynchronous patterns with the delay constraint. Numerical results show the trade-off between the energy-per-bit and the number of active users for different delay constraints. In addition, although the asynchronous transmission reduces interference, the required energy-per-bit increases as the receiver decodes with incompletely received codewords, compared to the synchronous case.

In this talk I present non-asymptotic achievability bounds for the A-channel with random insertions. In this multiple-access channel, users transmit q-ary codewords picked from a common codebook. The receiver observes the set of transmitted symbols but without order or multiplicity. In addition, the transmitted set may be corrupted by wrongfully included symbols. The reconstruction of the transmitted codewords presents a challenging combinatorial problem that has applications in unsourced coding and group testing.

We explore the fundamental limits of spectral efficiency (in bits/s/Hz/unit area) in Low Earth Orbit (LEO) satellite constellations. Unlike terrestrial cellular networks, increasing link density in LEO constellations doesn't guarantee unlimited spectral efficiency gains. We investigate this trade-off, focusing on a practical scenario where single-user codebooks are used and interference is treated as noise. The abstract analyzes a regular constellation configuration and proposes methods for satellite-ground station association and spectrum allocation. This includes an algorithm to prevent nearby links from interfering by targeting the same area.

In this talk, the novel concept of simultaneously transmitting and reflecting surfaces (STARS) will be introduced. First, the STAR basics will be introduced. In particular, the fundamental signal modelling, performance limit characterization, practical operating protocols, and joint beamforming design will be discussed. Then, the coupled phase-shift STAR model, AI enabled STARS, and channel estimation methods will be focused. Furthermore, several promising case studies of employing STARS will be put forward, including STAR-NOMA, spatial analysis for STARS, federated learning with STARS, and STARS enabled integrated sensing and communications (ISAC). Finally, research opportunities and problem as well as commercial progress of STARS.

We consider the problem of computing a function of $n$ variables using noisy queries, where each query is incorrect with some fixed and known probability $p \in (0,1/2)$. Specifically, we consider the computation of the $\mathsf{OR}$ function of $n$ bits (where queries correspond to noisy readings of the bits) and the $\mathsf{MAX}$ function of $n$ real numbers (where queries correspond to noisy pairwise comparisons). We show that an expected number of queries of $(1 \pm o(1)) \frac{n\log \frac{1}{\delta}}{D_{\mathsf{KL}}(p \| 1-p)}$ is both sufficient and necessary to compute both functions with a vanishing error probability $\delta = o(1)$, where $D_{\mathsf{KL}}(p \| 1-p)$ denotes the Kullback-Leibler divergence between $\mathsf{Bern}(p)$ and $\mathsf{Bern}(1-p)$ distributions. Compared to previous work, our results tighten the dependence on $p$ in both the upper and lower bounds for the two functions.

A buffet dinner is served daily between 5:30pm and 7:30pm in Vistas Dining Room, top floor of the Sally Borden Building.

Breakfast is served daily between 7 and 9am in the Vistas Dining Room, the top floor of the Sally Borden Building.

Massive random access for machine-type communications is one of the key use cases for future 5G/6G cellular communication networks. In this talk, I will describe the system model, problem formulation, algorithmic development, and performance analysis for the massive connectivity scenarios in which a large number of potential devices communicate with a base-station but with sporadic traffic. First, we show that the problem of detecting the device activity patterns together with estimating the channels can be formulated as a compressed sensing problem, which can be solved using an approximate message passing (AMP) algorithm. Alternatively, if we do not need to estimate the channels, it is possible to take advantage of channel hardening in the massive MIMO regime and to use a covariance-based approach to detect the device activities with much fewer pilots. Finally, we compare with the classic carrier-sensing multiple access and illustrate how feedback can significantly improve the design of the overall massive random access scheme.

In this talk, we focus on the activity detection problem in a multi-cell massive multiple-input multiple-output (MIMO) system, where active devices transmit their signature sequences to multiple base stations (BSs), and the BSs cooperatively detect the active devices based on the received signals. We shall present some recent results of the covariance-based approach for activity detection in cooperative multi-cell massive MIMO systems. In particular, we shall present some scaling law results and efficient coordinate descent (CD) algorithms for the problem.

In this talk, we discuss the problem of user activity detection in the context of a specific protocol for grant-free massive random access, namely, irregular repetition slotted ALOHA. Issues that need to be accounted for in this context include the choice of pilot sequences, their length, assignment of pilot sequences to users, the IRSA repetition distribution, path loss, fading, and the use of a massive number of antennas at the base station. We present a modified version of the sparse Bayesian learning algorithm that can be used to detect active users. Through simulations, we illustrate the performance of the protocol in terms of the probability of active user detection and false alarm, as a function of the aforementioned parameters. We conclude with interesting directions for future work.

We consider design of massive machine-type uplink communications systems with multiantenna base station receiver. We assume that the wireless channels are spatially correlated, and grant-free access is applied. We firstly consider joint activity detection and channel estimation (JADCE) with correlated user or transmitter device activity patterns. The problem is a sparse recovery and estimation problem, which we solve in a Bayesian framework when the spatial channel correlation is unknown. Then we discuss the possibility of allocating pilot sequences to the user devices assuming that the channel correlation is known or estimated. Channel charting framework is utilized in the pilot allocation.

Lunch is served daily between 11:30am and 1:30pm in the Vistas Dining Room, the top floor of the Sally Borden Building.

Current communication systems are designed following the Shannon paradigm. Here, the maximum number of possible messages that can be transmitted scales exponentially with the blocklength of the codewords. For future communication systems, we advocate a paradigm change towards Post-Shannon communication that allows the encoding of messages whose maximum number scales double-exponentially with the blocklength! In addition, secrecy comes "for free" in the sense that it can be incorporated without penalizing the transmission rate! This paradigm shift is the study of semantic communication instead of message only transmission. It involves a shift from the traditional design of message transmission to a new Post-Shannon design that takes the semantics of the communication into account going beyond the transmission of pure message bits. This paradigm change can bring not only marginal but also exponential gains in the efficiency of communication. Further key enabler for future communication systems are molecular communication with the identification capacity as an alternative metric and also joint communication and sensing that enables a tight integration of communication (and identification, respectively) and sensing. Accordingly, within the Post-Shannon framework, we will explores identification codes, molecular communication, and the concept of joint identification, and sensing.

This presentation will look into the problem of designing a common acknowledgment message for the massive random access scenario, where we wish to acknowledge a small subset of a very large user population. We will define information theoretic bounds and compare them to a number of practical schemes. Finally, we will see how the schemes can be used to implement ARQ in the massive access scenario.

In this talk, I will describe the problem of multiple support recovery, where we are given access to linear measurements of multiple sparse samples in $\mathbb{R}^d$. These samples can be partitioned into $\ell$ groups, with samples having the same support belonging to the same group. For a given budget of $m$ measurements per sample, the goal is to recover the $\ell$ underlying supports, in the absence of the knowledge of group labels. We will study this problem with a focus on the measurement-constrained regime where $m$ is smaller than the support size $k$ of each sample. I will describe a two-step procedure that first estimates the union of the underlying supports, and then uses a spectral algorithm to estimate the individual supports. This estimator can recover the supports with $m (Online)

In this talk, we investigate the training paradigm of next-token prediction (NTP) in language models, which involves predicting the next token in a sequence. Departing from traditional one-hot classification, in NTP, multiple tokens with varying frequencies follow each given context. We frame NTP training as cross-entropy minimization over distinct contexts, each associated with a sparse empirical probability vector across a finite vocabulary. The talk then explores the behavior of gradient descent as the NTP training loss over linear models approaches its lower bound (entropy). We illustrate conditions under which gradient descent can reach the entropy lower bound and characterize the structure of the model learned at convergence. Our work parallels prior research on the implicit bias of one-hot classification, opening exciting avenues for future research that can lead to better understanding the optimization and generalization principles of models trained with NTP.

A buffet dinner is served daily between 5:30pm and 7:30pm in Vistas Dining Room, top floor of the Sally Borden Building.

Breakfast is served daily between 7 and 9am in the Vistas Dining Room, the top floor of the Sally Borden Building.

This talk will present recent work on non-asymptotic Gaussian approximations for approximate message passing (AMP) algorithms. I will begin with a self-contained review of the existing theory for AMP with Gaussian matrices and generic full-memory denoisers. I will then describe a new approach for analyzing these algorithms that constructs an explicit coupling between the AMP iterates and a zero-mean Gaussian process whose covariance is defined recursively via (non-asymptotic) state evolution update equations. Under mild regularity conditions, this coupling argument provides simple and interpretable guarantees on the finite sample behavior of AMP algorithms.

In a generalized linear model (GLM), the goal is to estimate a d-dimensional signal x from an n-dimensional observation of the form f(Ax, w), where A is a design matrix and w is a noise vector. Well-known examples of GLMs include linear regression, phase retrieval, 1-bit compressed sensing, and logistic regression. We focus on the high-dimensional setting in which both the number of measurements n and the signal dimension d diverge, with their ratio tending to a fixed constant. Spectral methods provide a popular solution to obtain an initial estimate, and they are also commonly used as a ‘warm start’ for other algorithms. In particular, the spectral estimator is the principal eigenvector of a data-dependent matrix, whose spectrum exhibits a phase transition. In the talk, I will start by (i) discussing the emergence of this phase transition for an i.i.d. Gaussian design A, and (ii) combining spectral methods with Approximate Message Passing (AMP) algorithms, thus solving a key problem related to their initialization. I will then focus on two instances of GLMs that capture the heterogeneous and structured nature of practical data models: (i) a mixed GLM with multiple signals to recover, and (ii) a GLM with a correlated design matrix. To study spectral estimators in these challenging settings, the plan is to go back to Approximate Message Passing: I will demonstrate that the AMP framework not only gives Bayes-optimal algorithms, but it also unveils phase transitions in the spectrum of random matrices, thus leading to a precise asymptotic characterization of spectral estimators. (Based on a series of joint works with Hong Chang Ji, Andrea Montanari, Ramji Venkataramanan, and Yihan Zhang.)

Approximate Message Passing (AMP) type algorithms are widely used to the signal recovery in high-dimensional noisy linear systems. Recently, we developed a framework called Memory AMP (MAMP). Within this framework, the gradient-descent MAMP (GD-MAMP) algorithm inherits the strengths of AMP and OAMP/VAMP algorithms. This talk provides an overview of MAMP and GD-MAMP. Then it looks at recent results on implementation aspects of GD-MAMP. An overflow-avoiding GD-MAMP (OA-GD-MAMP) addresses an overflow problem that arises from some intermediate variables exceeds the range of floating point numbers. Second, we develop a complexity-reduced GD-MAMP (CR-GD-MAMP) that reduces the number of matrix-vector products per iteration by $1/3$ (from $3$ to $2$) without significantly reducing convergence speed.

We study a version of approximate message passing (AMP) in which the data matrix is only available after passing through some linear operator. To avoid information loss, we allow our algorithm to include memory terms for the past iterations. We leverage results from the theory of Gaussian AMP with non-separable denoisers to derive a state evolution and convergence result for our setting. As a motivating application, we consider a version of the power method where the data matrix is broken in sub-blocks and distributed to several servers, some of which fail to respond by the deadline (i.e, stragglers). Our framework provides a single-letter characterization for the limiting performance as well as the appropriate AMP correction term that guarantees the existence of a coupled Gaussian process that is close to the iterations with high probability. An interesting by-product of our analysis is that carefully-scheduled, partial applications of the data matrix can converge more efficiently, in terms of total multiplications, than the standard method of applying the full data matrix at each iteration. The theory is validated via numerical simulations. Joint work with Riccardo Rossetti and Galen Reeves.

We present a new algorithmic solution to the problem of massive unsourced random access (mURA) using massive MIMO. The proposed uncoupled compressed sensing (UCS)-based scheme combines the steps of activity detection, channel estimation, and data decoding into a unified mURA framework. Owing to the inherent bilinear structure of the underlying joint channel estimation and data decoding problem, the proposed framework capitalizes on recent advances in the bilinear vector approximate message passing (Bi-VAMP) paradigm, tailored to fit the inherent constraints of mURA. We do so by recasting the mURA problem into recovering a set of assignment matrices, one for each slot, and a common channel matrix across all slots. The novel formulation of the mURA problem does not require any additional processing for collision resolution and all collisions are resolved automatically once assignment matrices are determined. The sparker will first give an overview of the underlying general-purpose Bi-VAMP algorithm, then show how to customize it to efficiently solve the mURA problem.

Lunch is served daily between 11:30am and 1:30pm in the Vistas Dining Room, the top floor of the Sally Borden Building.

A buffet dinner is served daily between 5:30pm and 7:30pm in Vistas Dining Room, top floor of the Sally Borden Building.

Breakfast is served daily between 7 and 9am in the Vistas Dining Room, the top floor of the Sally Borden Building.

The problem of binary hypothesis testing occurs in communication (demodulation) and in natural sciences (finding Higgs boson). Classically the problem was solved by fully specifying the probability distributions for each of the hypotheses and applying Neyman-Pearson likelihood ratio test. In this talk I will discuss a more modern approach in which the likelihood function is not available but instead a number of iid samples from each hypothesis are given for the purpose of training the detector/tester. These samples are obtained by capturing background interference in the communication setting and by running expensive simulation code in natural sciences. I will describe recent progress on the theoretical understanding of this task (COLT’2023, NeurIPS’2023) and also on practical machine-learning based algorithms (RF Challenge at ICASSP’2024).

Community detection involves identifying clusters of nodes with denser connections within them than between them. Despite numerous algorithms addressing this problem, two main challenges persist. First, computational complexity is a significant hurdle; even clustering algorithms with polynomial complexity are limited to small graphs. Second, smaller clusters are often overlooked when cluster sizes are disproportionate. In this study, we introduce sketch-based approaches for graphs from the stochastic block model, which effectively tackle both limitations. Regarding computational complexity, our approach applies the clustering step exclusively to a small graph sketch. Results are then extrapolated to the entire graph using a low-complexity retrieval step, resulting in polylogarithmic complexity in graph size. Moreover, our proposed framework exhibits improved phase transitions, enabling the detection of smaller cluster sizes. We extend the framework to dynamic graphs, capturing community events like growth, shrinkage, merging, splitting, birth, and death. We present a standardized benchmark, modeling node addition/deletion, as well as community birth/death. Our sketch-based techniques track the evolutionary graph processes in real-time, showcasing advantages in both runtime and handling of small clusters.

The logistic regression model is one of the most popular data generation model in noisy binary classification problems. In this work, we study the sample complexity of estimating the parameters of the logistic regression model up to a given ℓ2 error, in terms of the dimension and the inverse temperature, with standard normal covariates. The inverse temperature controls the signal-to-noise ratio of the data generation process. While both generalization bounds and asymptotic performance of the maximum-likelihood estimator for logistic regression are well-studied, the non-asymptotic sample complexity that shows the dependence on error and the inverse temperature for parameter estimation is absent from previous analyses. We show that the sample complexity curve has two change-points in terms of the inverse temperature, clearly separating the low, moderate, and high temperature regimes.

Error correction is a fundamental tool for protecting data from noise. In this talk, I'll focus on distributed settings, and ask: What happens when we want to compute on data that is already protected with error correction? It turns out that, in some cases, we can take advantage of error correction in order to speed up or reduce the communication costs of that computation. I'll mention a few places where this comes up -- including distributed storage, distributed computation and homomorphic secret sharing -- and I'll discuss some recent theoretical results.

Novel sparse regression LDPC (SR-LDPC) codes exhibit excellent performance over additive white Gaussian noise (AWGN) channels in part due to their natural provision of shaping gains. Though SR-LDPC-like codes have been considered within the context of single-user error correction and massive (unsourced) random access, they have yet to be examined as candidates for coordinated multi-user communication scenarios. This talk explores this gap in the literature and demonstrates that SR-LDPC codes, when combined with coded demixing techniques, offer a new framework for efficient non-orthogonal multiple access (NOMA). The ensuing communication scheme, referred to as MU-SR-LDPC coding, is shown to achieve a target bit error rate (BER) at a higher sum rate than orthogonal multiple access (OMA) techniques such as time division multiple access (TDMA) and frequency division multiple access (FDMA). Furthermore, empirical evidence suggests that MU-SR-LDPC codes are amenable to decoding that is somewhat robust to timing asynchrony. Finally, MU-SR-LDPC codes are shown to enable a pragmatic solution path for user-centric cell-free communication systems with (local) joint decoding.

Lunch is served daily between 11:30am and 1:30pm in the Vistas Dining Room, the top floor of the Sally Borden Building.

We consider the graph alignment problem, where the goal is to identify the vertex/user correspondence between two correlated graphs. Existing work mostly recovers the correspondence by exploiting the user-user connections. However, in many real-world applications, additional information about the users, such as affiliation or educational background, might be publicly available. In this talk, we introduce the attributed graph alignment problem, where additional user information, referred to as attributes, is incorporated to assist graph alignment. We derive information-theoretic limits, which demonstrate the benefit of attribute information. When specialized to seeded graph alignment and bipartite graph alignment, the region we derive improves the existing region. For the vanilla graph alignment problem (without attribute information), it is conjectured that constant edge correlation is required for any polynomial-time algorithms to achieve exact recovery. We demonstrate that with a vanishing amount of additional attribute information, it is possible to design polynomial-time algorithms that achieve exact recovery with vanishing edge correlation.

A key challenge in wireless networking is the management of interference between transmissions. Motivated by work in the CS systems community on how passively to deduce the interference environment in a WLAN, we formulate the question as a graph learning problem. Nodes represent transmitters and edges represent the presence of interference between pairs of transmitters. We passively observe network traffic transmission patterns and collect information on transmission successes and failures. We establish bounds on the number of observations (each a snapshot of a network traffic pattern) required to identify the interference graph correctly with high probability. Our main results are scaling laws that tell us that to identify the graph, it is necessary and sufficient that the observation period grows like d2 log n where n is the number of transmitters and d is the maximum number of interfering transmitters per node.

One of the most fundamental problems in machine learning is finding interpretable representations of the functions we learn. The Mobius transform is a useful tool for this because its coefficients correspond to unique importance scores on sets of input variables. The Mobius Transform is strongly related (and in some cases equivalent) to the concept of Shapley value, which is a widely used game-theoretic notion of importance. This work focuses on the (typical) regime where the fraction of non-zero Mobius coefficients (and thus interactions between inputs) is small compared to the set of all 2n possible interactions between n inputs. When there are $K=O(2^n\delta)$ with $\delta≤1/3$ non-zero coefficients chosen uniformly at random, our algorithm exactly recovers the Mobius transform in $O(Kn)$ samples and O(Kn^2) time with vanishing error as $K \rightarrow \infty$, the first non-adaptive algorithm to do so. We also uncover a surprising connection between group testing and the Mobius transform. In the case where all interactions are between at most $t=\Omega(n^{\alpha})$ inputs, for $\alpha<0.409$, we are able to leverage results from group testing to provide the first algorithm that computes the Mobius transform in $O(Kt \log n)$ sample complexity and $O(K \mathrm{poly}(n))$ time with vanishing error as $K \rightarrow \infty$. Finally, we present a robust version of this algorithm that achieves the same sample and time complexity under some assumptions, but with a factor depending on noise variance. Our work is deeply interdisciplinary, drawing from tools spanning across signal processing, algebra, information theory, learning theory and group testing to address this important problem at the forefront of machine learning.

Local differential privacy is a powerful method for privacy-preserving data collection. In this talk, we will develop a framework for training Generative Adversarial Networks on differentially privatized data. We will show that entropic regularization of the Wasserstein distance -- a popular regularization method in the literature that has been often leveraged for its computational benefits -- can be used to denoise the data distribution when data is privatized by common additive noise mechanisms, such as Laplace and Gaussian. This combination enables the mitigation of both the regularization bias and the effects of privatization noise, thereby enhancing the overall efficacy of the model. We will analyze the proposed method, provide sample complexity results and experimental evidence to support its efficacy.

Federated Learning (FL) has emerged as a powerful approach to training large models on distributed datasets, offering advantages in terms of data locality, scalability, and privacy. However, practical implementation of FL faces significant challenges, primarily due to the communication constraints between remote learners and the Parameter Server (PS). In this talk, we will provide a comprehensive survey of the current state of communication-efficient federated learning, exploring the various techniques and methodologies that have been proposed to address these challenges. We will first discuss the practical issues arising from distributed training, focusing on the communication bottleneck between remote learners and the PS. Next, we will delve into the two main classes of gradient compression algorithms: gradient sparsification and gradient quantization. Furthermore, we will explore the role of dimensionality reduction algorithms and error feedback mechanisms in improving training performance. Our contribution, the M22 algorithm, will be presented in the context of these broader developments. M22, a rate-distortion inspired approach to gradient compression, leverages an M-magnitude weighted L2 distortion measure and 2 degrees of freedom distribution fitting to achieve efficient compression in FL scenarios.

A buffet dinner is served daily between 5:30pm and 7:30pm in Vistas Dining Room, top floor of the Sally Borden Building.

Breakfast is served daily between 7 and 9am in the Vistas Dining Room, the top floor of the Sally Borden Building.

Random graph models with community structure have been studied extensively in the literature. For both the problems of detecting and recovering community structure, an interesting landscape of statistical and computational phase transitions has emerged. A natural unanswered question is: might it be possible to infer properties of the community structure (for instance, the number and sizes of communities) even in situations where actually finding those communities is believed to be computationally hard? We show the answer is no. In particular, we consider certain hypothesis testing problems between models with different community structures, and we show (in the low-degree polynomial framework) that testing between two options is as hard as finding the communities. In addition, our methods give the first computational lower bounds for testing between two different “planted” distributions, whereas previous results have considered testing between a planted distribution and an i.i.d. “null” distribution. This is joint work with Fiona Skerman, Alexander S. Wein, and Dana Yang.

This talk will present recent results concerning the Bayesian estimation of low-rank matrices corrupted by structured noise, namely noise matrices with generic spectrum, and thus dependencies among its entries. We show that the Approximate Message Passing (AMP) algorithm currently proposed in the literature for Bayesian estimation is sub-optimal. We explain the reason for this sub-optimality and as a consequence we deduce an optimal Bayesian AMP algorithm with a rigorous state evolution matching our prediction for the minimum mean-square error. Based on a joint work with Francesco Camilli, Marco Mondelli and Manuel Saenz: https://www.pnas.org/doi/abs/10.1073/pnas.2302028120?doi=10.1073/pnas.2302028120

We consider communication over the Gaussian multiple-access channel in the asymptotic regime where the number of users grows linearly with the code length. Recent works have studied the tradeoff between energy-per-bit and achievable user density, and proposed efficient coding schemes based on random linear models and Approximate Message Passing (AMP) decoding. In this talk we generalize these CDMA-type schemes in two ways. First we discuss a coded CDMA scheme where each user’s information is encoded with a linear code, and propose an AMP decoder that can be tailored to the structure of the code. We then consider random user activity, and propose a spatially-coupled CDMA scheme with AMP decoding, which improves on finite-length achievability bounds obtained using random Gaussian codebooks. This is joint work with Xiaoqi Liu, Kuan Hsieh, and Pablo Pascual Cobo.

5-day workshop participants are welcome to use BIRS facilities (TCPL ) until 3 pm on Friday, although participants are still required to checkout of the guest rooms by 11AM.

We develop a unified framework for upper bounding the minimax risk in high-dimensional parameter estimation problems. To this end, we study a quantized maximum likelihood estimator, where the estimator computes the likelihood for all points within a discrete cover, and outputs the candidate with the maximal likelihood. While this concept is straightforward, our analysis is quite delicate. It splits the competing candidates in the cover to small shells, and controls the number of candidates in each shell, as well as the probability that a candidate in the shell outscores a candidate which is close to the true parameter. We demonstrate the utility of our bounds by applying them to different Gaussian problems, and showing that they recover the optimal minimax rate for the Gaussian location model and the spiked Wigner Model. For the multi-reference alignment problem we obtain a novel minimax upper bound, which essentially places no assumptions on the signal of interest.

In this talk we focus on the fundamental limits of unsourced random access (URA). By fundamental limits, we mean the minimal energy per bit required to achieve the target per-user probability of error. All the results in the talk are obtained with the use of Fano’s method, which is based on the choice of the so-called “good” region. We start with the Gaussian channel, consider the cases of Gaussian and binary codebooks and obtain two achievability bounds. The first bound is very close to Polyanskiy’s bound (2017) but does not lead to any improvement. At the same time, the numerical results show that the bound for the binary case practically coincides with the bound for the Gaussian codebook. Thus, we conclude that energy-efficient schemes using binary modulation do exist. Finally we shift to the MIMO channel, perform a projection-based decoder analysis and derive energy efficiency achievability bounds when channel state information is unknown at transmitters and the receiver (no-CSI scenario). A comparison to the maximum-likelihood (ML) achievability bounds by Gao et al. (2023) is performed. We show that there is a range of parameters where the new bound outperforms the ML bound. The key improvement reason is a new good region induced by the projection decoding rule. Moreover, the transition to projection decoding rule allows for significant dimensionality reduction, which greatly reduces the bound computation time.