where the last inequality follows from the fact that Uij 1. Also, for any i [n ] and j [k], we have xi bµj

To prove Lemma 2 we start by proving a few inequalities. Since Ais an ( 1, 2,Q)-solver, using Definition 4 and Taylor's expansion, we get for any i [n] and j [k], In this section we present and prove a few auxiliary results which will be used in the proofs our main results. We start with the following standard concentration inequalities. R2, (32) if n clog(1/δ)2, where c > 0 is some absolute constant. The following locality lemma states that the fuzzy k-means function is strictly increasing. Lemma 5. Let (X,P?) be a clustering instance, where P? refers to the optimal solution for the fuzzy k-mean problem (namely, minimizes the objective in (2)). Output: bµj 1: Initialize S φ. 2: for s= 1,2,...,mdo 3: Sample iuniformly at random from [n] and update S S {i}. Next, we analyze the performance of Algorithm 6, which estimates the center of a given cluster using a set of randomly sampled elements. Note that this algorithm is used as a sub-routine in Algorithm 1. Lemma 6 (Estimate of mean using uniform sampling). Let (X,P) be a consistent center-based clustering instance, and let δ (0,1).