We consider the problem of localizing change points in a generalized linear model (GLM), a model that covers many widely studied problems in statistical learning including linear, logistic, and rectified linear regression. We propose a novel and computationally efficient approximate message passing (AMP) algorithm for estimating both the signals and the change point locations, and rigorously characterize its performance in the high-dimensional limit where the number of parameters $p$ is proportional to the number of samples $n$. This characterization is in terms of a state evolution recursion, which allows us to precisely compute performance measures such as the asymptotic Hausdorff error of our change point estimates, and allows us to tailor the algorithm to take advantage of any prior structural information of the signals and change points. Moreover, we show how our AMP iterates can be used to efficiently compute a Bayesian posterior distribution over the change point locations in the high-dimensional limit. We validate our theory via numerical experiments, and demonstrate the favorable performance of our estimators on both synthetic and real data in the settings of linear, logistic, and rectified linear regression.

Consider the Hitting Set problem where, for a given universe 𝒳 = {1, ..., n} and a collection of subsets 𝒮₁, ..., 𝒮_m, one seeks to identify the smallest subset of 𝒳 which has a nonempty intersection with every element in the collection. We study a probabilistic formulation of this problem, where the underlying subsets are formed by including each element of the universe independently with probability p. We rigorously analyze integrality gaps between linear programming and integer programming solutions to the problem. In particular, we prove the absence of an integrality gap in the sparse regime mp ≲ log(n) and the presence of a non-vanishing integrality gap in the dense regime mp ≫ log{n}. Moreover, for large enough values of n, we look at the performance of Lovász’s celebrated Greedy algorithm [Lovász, 1975] with respect to the chosen input distribution, and prove that it finds optimal solutions up to multiplicative constants. This highlights separation of Greedy performance between average-case and worst-case settings.

We consider the problem of localizing change points in high-dimensional linear regression. We propose an Approximate Message Passing (AMP) algorithm for estimating both the signals and the change point locations. Assuming Gaussian covariates, we give an exact asymptotic characterization of its estimation performance in the limit where the number of samples grows proportionally to the signal dimension. Our algorithm can be tailored to exploit any prior information on the signal, noise, and change points. It also enables uncertainty quantification in the form of an efficiently computable approximate posterior distribution, whose asymptotic form we characterize exactly. We validate our theory via numerical experiments, and demonstrate the favorable performance of our estimators on both synthetic data and images.

We consider the problem of mixed sparse linear regression with two components, where two k-sparse signals β_1, β_2 ∈ R^p are to be recovered from n unlabelled noisy linear measurements. The sparsity is allowed to be sublinear in the dimension (k = o(p)), and the additive noise is assumed to be independent Gaussian with variance σ^2. Prior work has shown that the problem suffers from a k/SNR^2 -to- k^2/SNR^2 statistical-to-computational gap, resembling other computationally challenging high- dimensional inference problems such as Sparse PCA and Robust Sparse Mean Estimation (Brennan and Bresler, 2020b); here SNR := ∥β1∥^2/σ^2 = ∥β2∥^2/σ^2 is the signal-to-noise ratio. We establish the existence of a more extensive k/SNR^2 -to- k^2 (SNR+1)^2/SNR^2 computational barrier for this problem through the method of low-degree polynomials, but show that the problem is computationally hard only in a very narrow symmetric parameter regime. We identify a smooth information-computation tradeoff between the sample complexity n and runtime exp( Θ(k^2(SNR + 1)^2/(nSNR^2))) for any randomized algorithm in this hard regime. Via a simple reduction, this provides novel rigorous evidence for the existence of a computational barrier to solving exact support recovery in sparse phase retrieval with sample complexity n = o(k^2). Our second contribution is to analyze a simple thresholding algorithm which, outside of the narrow regime where the problem is hard, solves the associated mixed regression detection problem in O(np) time and matches the sample complexity required for (non-mixed) sparse linear regression of k(SNR+1)/SNR log p; this allows the recovery problem to be subsequently solved by state-of-the-art techniques from the dense case. As a special case of our results, we show that this simple algorithm is order-optimal among a large family of algorithms in solving exact signed support recovery in sparse linear regression. To the best of our knowledge, this is the first thorough study of the interplay between mixture symmetry, signal sparsity, and their joint impact on the computational hardness of mixed sparse linear regression.

Non-adaptive group testing refers to the problem of inferring a sparse set of defectives from a larger population using the minimum number of simultaneous pooled tests. Recent positive results for noiseless group testing have motivated the study of practical noise models, a prominent one being dilution noise. Under the dilution noise model, items in a test pool have a fixed probability of being independently diluted, meaning their contribution to a test does not take effect. In this setting, we investigate the number of tests required to achieve vanishing error probability with respect to existing algorithms and provide an algorithm-independent converse bound. In contrast to other noise models, we also encounter the interesting phenomenon that dilution noise on the resulting test outcomes can be offset by choosing a suitable noise-level-dependent Bernoulli test design, resulting in matching achievability and converse bounds up to order in the high noise regime.

Robotic swarms are decentralized multi-robot systems whose members use local information from proximal neighbors to execute simple reactive control laws that result in emergent collective behaviors. In contrast, members of a general multi-robot system may have access to global information, all-to-all communication or sophisticated deliberative collaboration. Some algorithms in the literature are applicable to robotic swarms. Others require the extra complexity of general multi-robot systems. Given an application domain, a system designer or supervisory operator must choose an appropriate system or algorithm respectively that will enable them to achieve their goals while satisfying mission constraints (e.g, bandwidth, energy, time limits). In this paper, we compare representative swarm and general multi-robot algorithms in two application domains - navigation and dynamic area coverage - with respect to several metrics (e.g, completion time, distance travelled). Our objective is to characterize each class of algorithms to inform offline system design decisions by engineers or online algorithm selection decisions by supervisory operators. Our contributions are (a) an empirical performance comparison of representative swarm and general multi-robot algorithms in two application domains, (b) a comparative analysis of the algorithms based on the theory of information invariants, which provides a theoretical characterization supported by our emnirical results.