Large language models (LLMs) have demonstrated remarkable performance in diverse tasks using zero-shot and few-shot prompting.Even though their capabilities of data synthesis have been studied well in recent years, the generated data suffers from a lack of diversity, less adherence to the prompt, and potential biases that creep into the data from the generator model.In this work, we tackle the challenge of generating datasets with high diversity, upon which a student model is trained for downstream tasks.Taking the route of decoding-time guidancebased approaches, we propose CORRSYNTH, which generates data that is more diverse and faithful to the input prompt using a correlated sampling strategy.Further, our method overcomes the complexity drawbacks of some other guidance-based techniques like classifier-based guidance.With extensive experiments, we show the effectiveness of our approach and substantiate our claims.In particular, we perform intrinsic evaluation to show the improvements in diversity.Our experiments show that CORRSYNTH improves both student metrics and intrinsic metrics upon competitive baselines across four datasets, showing the innate advantage of our method.

We consider collaborative multi-user reinforcement learning, where multiple users have the same state-action space and transition probabilities but different rewards. Under the assumption that the reward matrix of the $N$ users has a low-rank structure – a standard and practically successful assumption in the collaborative filtering setting – we design algorithms with significantly lower sample complexity compared to the ones that learn the MDP individually for each user. Our main contribution is an algorithm which explores rewards collaboratively with $N$ user-specific MDPs and can learn rewards efficiently in two key settings: tabular MDPs and linear MDPs. When $N$ is large and the rank is constant, the sample complexity per MDP depends logarithmically over the size of the state-space, which represents an exponential reduction (in the state-space size) when compared to the standard “non-collaborative” algorithms. Our main technical contribution is a method to construct policies which obtain data such that low rank matrix completion is possible (without a generative model). This goes beyond the regular RL framework and is closely related to mean field limits of multi-agent RL.

Many-user MAC is an important model for understanding energy efficiency of massive random access in 5G and beyond. Introduced in Polyanskiy’2017 for the AWGN channel, subsequent works have provided improved bounds on the asymptotic minimum energy-per-bit required to achieve a target per-user error at a given user density and payload, going beyond the AWGN setting. The best known rigorous bounds use spatially coupled codes along with the optimal AMP algorithm. But these bounds are infeasible to compute beyond a few (around 10) bits of payload. In this paper, we provide new achievability bounds for the many-user AWGN and quasi-static Rayleigh fading MACs using the spatially coupled codebook design along with a scalar AMP algorithm. The obtained bounds are computable even up to 100 bits and outperform the previous ones at this payload.

We consider the problem of estimating a linear time-invariant (LTI) dynamical system from a single trajectory via streaming algorithms, which is encountered in several applications including reinforcement learning (RL) and time-series analysis. While the LTI system estimation problem is well-studied in the {\em offline} setting, the practically important streaming/online setting has received little attention. Standard streaming methods like stochastic gradient descent (SGD) are unlikely to work since streaming points can be highly correlated. In this work, we propose a novel streaming algorithm, SGD with Reverse Experience Replay (SGD-RER), that is inspired by the experience replay (ER) technique popular in the RL literature. SGD-RER divides data into small buffers and runs SGD backwards on the data stored in the individual buffers. We show that this algorithm exactly deconstructs the dependency structure and obtains information theoretically optimal guarantees for both parameter error and prediction error. Thus, we provide the first -- to the best of our knowledge -- optimal SGD-style algorithm for the classical problem of linear system identification with a first order oracle. Furthermore, SGD-RER can be applied to more general settings like sparse LTI identification with known sparsity pattern, and non-linear dynamical systems. Our work demonstrates that the knowledge of data dependency structure can aid us in designing statistically and computationally efficient algorithms which can ``decorrelate'' streaming samples.

We consider the setting of vector valued non-linear dynamical systems $X_{t+1} = \phi(A^{*} X_t) + \eta_t$, where $\eta_t$ is unbiased noise and $\phi : \mathbb{R} \to \mathbb{R}$ is a known link function that satisfies certain {\em expansivity property}. The goal is to learn $A^{*}$ from a single trajectory $X_1,\cdots , X_T$ of {\em dependent or correlated} samples.While the problem is well-studied in the linear case, where $\phi$ is identity, with optimal error rates even for non-mixing systems, existing results in the non-linear case hold only for mixing systems. In this work, we improve existing results for learning nonlinear systems in a number of ways: a) we provide the first offline algorithm that can learn non-linear dynamical systems without the mixing assumption, b) we significantly improve upon the sample complexity of existing results for mixing systems, c) in the much harder one-pass, streaming setting we study a SGD with Reverse Experience Replay (SGD-RER) method, and demonstrate that for mixing systems, it achieves the same sample complexity as our offline algorithm, d) we justify the expansivity assumption by showing that for the popular ReLU link function --- a non-expansive but easy to learn link function with i.i.d. samples --- any method would require exponentially many samples (with respect to dimension of $X_t$) from the dynamical system. We validate our results via. simulations and demonstrate that a naive application of SGD can be highly sub-optimal. Indeed, our work demonstrates that for correlated data, specialized methods designed for the dependency structure in data can significantly outperform standard SGD based methods.

Consider a (multiple-access) wireless communication system where users are connected to a unique base station over a shared-spectrum radio links. Each user has a fixed number k of bits to send to the base station, and his signal gets attenuated by a random channel gain (quasi-static fading). In this paper we consider the many-user asymptotics of Chen-Chen-Guo'2017, where the number of users grows linearly with the blocklength. Differently, though, we adopt a per-user probability of error (PUPE) criterion (as opposed to classical joint-error probability criterion). Under PUPE the finite energy-per-bit communication is possible, and we are able to derive bounds on the tradeoff between energy and spectral efficiencies. We reconfirm the curious behaviour (previously observed for non-fading MAC) of the possibility of almost perfect multi-user interference (MUI) cancellation for user densities below a critical threshold. Further, we demonstrate the suboptimality of standard solutions such as orthogonalization (i.e. TDMA/FDMA) and treating interference as noise (i.e. pseudo-random CDMA without multi-user detection). Notably, the problem treated here can be seen as a variant of support recovery in compressed sensing for the unusual definition of sparsity with one non-zero entry per each contiguous section of 2kcoordinates. This identifies our problem with that of the sparse regression codes (SPARCs) and hence our results can be equivalently understood in the context of SPARCs with sections of length 2100. Finally, we discuss the relation of the almost perfect MUI cancellation property and the replica-method predictions.

We discuss the problem of designing channel access architectures for enabling fast, low-latency, grant-free, and uncoordinated uplink for densely packed wireless nodes. Specifically, we study random-access codes, previously introduced for the AWGN MAC, in the practically more relevant case of Rayleigh fading, when channel gains are unknown to the decoder. We propose a random coding achievability bound, which we analyze both non-asymptotically and asymptotically. As a candidate practical solution, we propose an explicit iterative coding scheme. The performance of such a solution is surprisingly close to the finite blocklength bounds. Our main findings are twofold. First, just like in the AWGN MAC, we see that jointly decoding a large number of users leads to a surprising phase transition effect, where, at spectral efficiencies below a critical threshold, a perfect multi-user interference cancellation is possible. Second, while the presence of Rayleigh fading significantly increases the minimal required energy-per-bit, the inherent randomization introduced by the channel makes it much easier to attain the optimal performance via iterative schemes. We hope that a principled definition of the random-access model, together with their information-theoretic analysis, will open the road towards unified benchmarking and performance comparison of various random-access solutions for the 5G/6G.

We discuss the problem of designing channel access architectures for enabling fast, low-latency, grant-free and uncoordinated uplink for densely packed wireless nodes. Specifically, we extend the concept of random-access code introduced at ISIT'2017 by one of the authors to the practically more relevant case of the AWGN multiple-access channel (MAC) subject to Rayleigh fading, unknown to the decoder. We derive bounds on the fundamental limits of random-access coding and propose an alternating belief-propagation scheme as a candidate practical solution. The latter's performance was found to be surprisingly close to the information-theoretic bounds. It is curious, thus, that while fading significantly increases the minimal required energy-per-bit Eb/N0(from about 0-2 dB to about 8-11 dB), it appears that it is much easier to attain the optimal performance over the fading channel with a practical scheme by leveraging the inherent randomization introduced by the channel. Finally, we mention that while a number of candidate solutions (MUSA, SCMA, RSMA, etc.) are being discussed for the 5G, the information-theoretic analysis and benchmarking has not been attempted before (in part due to lack of common random-access model). Our work may be seen as a step towards unifying performance comparisons of these methods.

Consider a (multiple-access) wireless communication system where users are connected to a unique base station over a shared-spectrum radio links. Each user has a fixed number k of bits to send to the base station, and his signal gets attenuated by a random channel gain (quasi-static fading). In this paper we consider the many-user asymptotics of Chen-Chen-Guo'2017, where the number of users grows linearly with the blocklength. In addition, we adopt a per-user probability of error criterion of Polyanskiy'2017 (as opposed to classical joint-error probability criterion). Under these two settings we derive bounds on the optimal required energy-per-bit for reliable multi-access communication. We confirm the curious behaviour (previously observed for non-fading MAC) of the possibility of perfect multi-user interference cancellation for user densities below a critical threshold. Further we demonstrate the suboptimality of standard solutions such as orthogonalization (i.e., TDMA/FDMA) and treating interference as noise (i.e. pseudo-random CDMA without multi-user detection).

We investigate the problem of uncoordinated massive random access in the quasi-static asynchronous Rayleigh fading channel. In the previous work [1], the authors assumed a completely synchronous scenario which is impossible in any practical implementation. This paper extends the previous work to the asynchronous case. As energy efficiency is of critical importance for massive machine-type communication (mMTC), our main goal is to minimize the energy-per-bit required to achieve the target probability of error. Another issue required for mMTC is a transmitter simplicity. As in the synchronous case, we focus on grant-free transmission and do not use preambles and other synchronization sequences. We propose a practical implementation of a transmission scheme based on synchronization error estimation and cancellation in the frequency domain. The simulation shows that the proposed transmission scheme's performance is very close to the synchronous case. The only source of E_b/N_0 loss is the need for an additional cyclic prefix that helps to solve the synchronization error cancellation problem in the frequency domain.