While supervised federated learning approaches have enjoyed significant success, the domain of unsupervised federated learning remains relatively underexplored. Several federated EM algorithms have gained popularity in practice, however, their theoretical foundations are often lacking. In this paper, we first introduce a federated gradient EM algorithm (FedGrEM) designed for the unsupervised learning of mixture models, which supplements the existing federated EM algorithms by considering task heterogeneity and potential adversarial attacks. We present a comprehensive finite-sample theory that holds for general mixture models, then apply this general theory on specific statistical models to characterize the explicit estimation error of model parameters and mixture proportions. Our theory elucidates when and how FedGrEM outperforms local single-task learning with insights extending to existing federated EM algorithms. This bridges the gap between their practical success and theoretical understanding. Our numerical results validate our theory, and demonstrate FedGrEM's superiority over existing unsupervised federated learning benchmarks.

Since its development, the minimax framework has been one of the corner stones of theoretical statistics, and has contributed to the popularity of many well-known estimators, such as the regularized M-estimators for high-dimensional problems. In this paper, we will first show through the example of sparse Gaussian sequence model, that the theoretical results under the classical minimax framework are insufficient for explaining empirical observations. In particular, both hard and soft thresholding estimators are (asymptotically) minimax, however, in practice they often exhibit sub-optimal performances at various signal-to-noise ratio (SNR) levels. The first contribution of this paper is to demonstrate that this issue can be resolved if the signal-to-noise ratio is taken into account in the construction of the parameter space. We call the resulting minimax framework the signal-to-noise ratio aware minimaxity. The second contribution of this paper is to showcase how one can use higher-order asymptotics to obtain accurate approximations of the SNR-aware minimax risk and discover minimax estimators. The theoretical findings obtained from this refined minimax framework provide new insights and practical guidance for the estimation of sparse signals.

In many application areas ranging from bioinformatics to imaging, we are faced with the following question: can we recover a sparse vector xo∈ ℝNfrom its undersampled set of noisy observations y ∈ ℝn, y = Axo+w. The last decade has witnessed a surge of algorithms and theoretical results to address this question. One of the most popular schemes is the ℓp-regularized least squares given by the following formulation:x̂(y, p) ∈ arg minx(1/2)∥y - Ax∥22+ γ∥x∥pp, where p ∈ [0, 1]. Among these optimization problems, the case p = 1, also known as LASSO, is the best accepted in practice, for the following two reasons. First, thanks to the extensive studies performed in the fields of high-dimensional statistics and compressed sensing, we have a clear picture of LASSO's performance. Second, it is convex and efficient algorithms exist for finding its global minima. Unfortunately, neither of the above two properties hold for 0 ≤ pothan x̂(γ, 1). Second, if we employ iterative methods that aim to converge to a local minima of arg minx(1/2)∥y - Ax∥22+ γ∥x∥pp, then under good initialization, these algorithms converge to a solution that is still closer to xothan x̂(γ, 1). In spite of the existence of plenty of empirical results that support these folklore theorems, the theoretical progress to establish them has been very limited. This paper aims to study the above-mentioned folklore theorems and establish their scope of validity. Starting with approximate message passing (AMP) algorithm as a heuristic method for solving ℓp-regularized least squares, we study the following questions. First, what is the impact of initialization on the performance of the algorithm? Second, when does the algorithm recover the sparse signal xounder a “good” initialization? Third, when does the algorithm converge to the sparse signal regardless of the initialization? Studying these questions will not only shed light on the second folklore theorem, but also lead us to the answer the first one, i.e., the performance of the global optima x̂(γ, p). For that purpose, we employ the replica analysis1to show the connection between the solution of AMP and x̂(γ, p) in the asymptotic settings. This enables us to compare the accuracy of x̂(γ, p) and x̂(γ, 1). In particular, we will present an accurate characterization of the phase transition and noise sensitivity of ℓp-regularized least squares for every 0 ≤ pp-regularized least squares (if γ is tuned optimally) exhibits the same phase transition for every 0 ≤ pp-regularized least squares with different values of p. For instance, we will show that for very small and very large measurement noises, p = 0 and p = 1 outperform the other values of p, respectively.

Recovering a sparse vector x0∈ ℝNfrom its noisy linear observations, y ∈ ℝnwith y = Ax0+ w, has been the central problem of compressed sensing. One of the classes of recovery algorithms that has attracted attention is the class of ℓp-regularized least squares (LPLS) that seeks the minimum of 1/2 ∥y - Ax∥22+ λ∥x∥ppfor p ∈ [0, 1]. In this paper we employ the Replica method1from statistical physics to analyze the global minima of LPLS. Our paper reveals several surprising asymptotic properties of LPLS: (i) The phase transition curve of LPLS is the same for every 0 ≤ p0. (iii) Despite the equality of the phase transition curves, different values of p show different performances once a small amount of measurement noise, w, is added.