Group testing is the problem of identifying a small subset of defectives from a large set using as few binary tests as possible. In most current literature on group testing the binary test outcome is $1$ if the pool contains at least one defective, and $0$ otherwise. In this work we initiate the study of a generalized model of group testing that accommodates the physical effects of dilution of infected samples in large pools. In this model the binary test outcome is $1$ with probability $f(\rho)$, where $\rho$ is the density of the defectives in the test, and $f:[0,1]\rightarrow [0,1]$ is a given "test function" that models this dilution process. For a large class of test functions our results establish near-optimal sample complexity bounds, by providing information-theoretic lower bounds on the number of tests necessary to recover the set of defective items, and providing computationally efficient algorithms with sample complexities that match these lower bounds up to constant or logarithmic factors. Furthermore, using tools from real analysis, we extend our results to any "sufficiently well-behaved function" $f:[0,1]\rightarrow [0,1]$.

1-bit compressed sensing (1bCS) is a quantized signal acquisition technique to compress high-dimensional sparse signals. The goal is to design sensing matrices A ∈ ℝm×nwith the fewest possible rows that enable efficient and accurate recovery of sparse signals x ∈ ℝnfrom 1-bit measurements of the form sign(Ax). This work focuses on recovering the support of sparse signals from noisy 1-bit measurements, specifically in presence of adversarial noise. Existing methods handle random noise, or small number of adversarial sign flips. We demonstrate that exact support recovery is impossible when a constant fraction of measurements are affected by adversarial noise. Hence, we design sensing matrices that can reliably recover support in presence of (b, c)-burst noise, tolerating a constant fraction of errors concentrated in O(log m) blocks.

Pretraining large language models (LLMs) on vast and heterogeneous datasets is crucial for achieving state-of-the-art performance across diverse downstream tasks. However, current training paradigms treat all samples equally, overlooking the importance or relevance of individual samples throughout the training process. Existing reweighting strategies, which primarily focus on group-level data importance, fail to leverage fine-grained instance-level information and do not adapt dynamically to individual sample importance as training progresses. In this paper, we introduce novel algorithms for dynamic, instance-level data reweighting aimed at improving both the efficiency and effectiveness of LLM pretraining. Our methods adjust the weight of each training sample based on its loss value in an online fashion, allowing the model to dynamically focus on more informative or important samples at the current training stage. In particular, our framework allows us to systematically devise reweighting strategies deprioritizing redundant or uninformative data, which we find tend to work best. Furthermore, we develop a new theoretical framework for analyzing the impact of loss-based reweighting on the convergence of gradient-based optimization, providing the first formal characterization of how these strategies affect convergence bounds. We empirically validate our approach across a spectrum of tasks, from pretraining 7B and 1.4B parameter LLMs to smaller-scale language models and linear regression problems, demonstrating that our loss-based reweighting approach can lead to faster convergence and significantly improved performance.

In this work, we present distributed clustering algorithms that can handle large-scale data across multiple machines in the presence of faulty machines. These faulty machines can either be straggling machines that fail to respond within a stipulated time or Byzantines that send arbitrary responses. We propose redundant data assignment schemes that enable us to obtain clustering solutions based on the entire dataset, even when some machines are stragglers or adversarial in nature. Our proposed robust clustering algorithms generate a constant factor approximate solution in the presence of stragglers or Byzantines. We also provide various constructions of the data assignment scheme that provide resilience against a large fraction of faulty machines. Simulation results show that the distributed algorithms based on the proposed assignment scheme provide good-quality solutions for a variety of clustering problems.

1-bit compressed sensing (1bCS) is a quantized signal acquisition technique to compress high-dimensional sparse signals. The goal in 1bCS is to design sensing matrices A ∈ ℝm×nwith the fewest possible rows that enable efficient and accurate recovery of sparse signals x ∈ ℝnfrom 1-bit measurements of the form sign(Ax). In this work, we leverage the locality in sparsity patterns observed in many real-world datasets to recover the support of signals exhibiting this sparsity pattern. Our results improve the existing bounds on the number of measurements sufficient for support recovery when the non-zero entries of a signal occur within small local neighborhoods.

We consider a set of data samples such that a fraction of the samples are arbitrary outliers, and the rest are the output samples of a single-layer neural network with rectified linear unit (ReLU) activation. Our goal is to estimate the parameters (weight matrix and bias vector) of the neural network, assuming the bias vector to be non-negative. We estimate the network parameters using the gradient descent algorithm combined with either the median- or trimmed mean-based filters to mitigate the effect of the arbitrary outliers. We then prove that $\tilde{O}\left( \frac{1}{p^2}+\frac{1}{\epsilon^2p}\right)$ samples and $\tilde{O}\left( \frac{d^2}{p^2}+ \frac{d^2}{\epsilon^2p}\right)$ time are sufficient for our algorithm to estimate the neural network parameters within an error of $\epsilon$ when the outlier probability is $1-p$, where $2/3 DOI 10.52202/068431-0796

In this paper, we present robust variants of distributed clustering algorithms for large datasets distributed across multiple machines in the presence of Byzantines. We propose a redundant data assignment scheme that enables us to obtain global information about the entire dataset for clustering purposes even when some machines are adversarial in nature. Simulation results show that the distributed algorithms based on the proposed assignment scheme provide good-quality solutions for a variety of clustering problems.

We consider the distributed stochastic optimization problem of minimizing a nonconvex function f in an adversarial setting. All the w worker nodes in the network are expected to send their stochastic gradient vectors to the fusion center (or server). However, some (at most α-fraction) of the nodes may be Byzantines, which may send arbitrary vectors instead. Vanilla implementation of distributed stochastic gradient descent (SGD) cannot handle such misbehavior from the nodes. We propose a robust variant of distributed SGD which is resilient to the presence of Byzantines. The fusion center employs a novel filtering rule that identifies and removes the Byzantine nodes. We show that T = Õ (1/wϵ2+ α2/ϵ2) iterations are needed to achieve an ϵ-approximate stationary point (x such that ∥∇f(x)∥2≤ ϵ) for the nonconvex learning problem. Unlike other existing approaches, the proposed algorithm is independent of the problem dimension.

Device-to-device (D2D) communication enables simultaneous data transmissions by cellular users (CU) and D2D user pairs, but at the expense of additional interference between them. The literature on resource allocation in D2D systems often assumes that the base station (BS) has complete channel state information (CSI) about all the links between all the users in a cell. However, acquiring the CSI of cross links between the CUs and the D2D receivers is a critical bottleneck because the number of cross links is the product of the number of CUs and D2D pairs. We study a novel partial CSI model in which the overhead of feeding back the CSI of the cross links is much lower. For a cell with one D2D pair and multiple CUs, we propose a novel throughput-optimal joint mode selection, user scheduling, and rate adaptation policy that exploits information about the statistics of the cross links and incorporates inter-cell interference. We derive closed-form expressions for the feedback-conditioned goodput for the underlay mode, which drives this optimal policy. We also present extensions that incorporate user fairness, quantized CSI, and multiple D2D pairs and multiple subchannels.