## 4 \(k\)-Means++ for \(\rho\)-Metric
\), and the randomness is over the \(t\) sampled points in \(Y\setminus X\)._  
**Proof. ** The proof is by the following induction on \(t\geq 0\): (i) the base case \(t=0\) (and any \(u\geq 0\)), and (ii) the inductive step \(t\geq 1\) (and any \(u\geq 0\)). **(i) Base Case : \(t=0\). ** We then have  
\[ \begin{split} E[f(P,Y)]&=E[f(P,X)]=f(P,X)=f(P \setminus U,X)+f(U,X)=f(P\setminus U,X)+\frac{u-t}{u}\cdot f(U,X)\\ &\leq\big{(}f(P\setminus U,X)+4\rho^{2}f^{*}(U,u)\big{)}H_{t}+ \frac{u-t}{u}\cdot f(U,X),\end{split} \]  
where the first two equalities hold since \(Y=X\) is not random, and the inequality holds since \(t=0\), \(H_{0}=1\) and \(f^{*}(U,u)\geq 0\). Hence, the lemma holds for \(t=0\) and any \(u\geq 0\). **(ii) Inductive step: \(t\geq 1\). ** Let \(y\in P\) denote the first sampled point that was inserted to \(Y\setminus X\) during the execution of Line 5 in Algorithm 1. Let \(X^{\prime}=X\cup\{y\}\). Let \(j\in[k]\) such that \(y\in P_{j}\), and \(U^{\prime}=U\setminus P_{j}\) denote the remaining \"uncovered\" \(u^{\prime}=|\left\{P_{1},\cdots,P_{u}\right\}\setminus P_{j}|\) clusters, i.e, \(u^{\prime}\in\{u,u-1\}\). The distribution of \(Y\) conditioned on the known sample \(y\) is the same as the output of a call to KMeans++(\(P,w,f,X^{\prime},t^{\prime}\)) where \(t^{\prime}=t-1\). Hence, we need to bound  
\[E[f(P,Y)]=\Pr(y\in P\setminus U)E[f(P,Y)\mid y\in P\setminus U]+\Pr(y\in U)E[ f(P,Y)\mid y\in U]. \tag{24}\]  
We will bound each of the last two terms by expressions that are independent of \(X^{\prime}\) or \(U^{\prime}\). Bound on \(E[f(P,Y)\mid y\in P\setminus U]\). Here \(u^{\prime}=u\in[k]\), \(U^{\prime}=U\) (independent of \(j\)), and by the inductive assumption that the lemma holds after replacing \(t\) with \(t^{\prime}=t-1\), we obtain  
\[ \begin{split} E[f(P,Y)\mid y\in P\setminus U]&\leq \big{(}f(P\setminus U^{\prime},X^{\prime})+4\rho^{2}f^{*}(U^{\prime},u^{\prime} )\big{)}H_{t^{\prime}}+\frac{u^{\prime}-t^{\prime}}{u^{\prime}}\cdot f(U^{ \prime},X^{\prime})\\ &=\big{(}f(P\setminus U,X^{\prime})+4\rho^{2}f^{*}(U,u)\big{)}H_ {t-1}+\frac{u-t+1}{u}\cdot f(U,X^{\prime})\\ &\leq\big{(}f(P\setminus U,X)+4\rho^{2}f^{*}(U,u)\big{)}H_{t-1}+ \frac{u-t+1}{u}\cdot f(U,X).\end{split}  \tag{25}\]  
Bound on \(E[f(P,Y)\mid y\in U]\). In this case, \(U^{\prime}=U\setminus P_{j}\) and \(u^{\prime}=u-1\in\{0,\cdots,k-1\}\). Hence,  
\[ \begin{split} E[f(P,Y)\mid y\in U]&=\sum_{m=1}^{u} \Pr(j=m)E[f(P,Y)\mid j=m]\\ &=\sum_{m=1}^{u}\Pr(j=m)\sum_{x\in P_{m}}\Pr(y=x)E[f(P,Y)\mid x =y].\end{split}  \tag{26}\]  
Multiplying by \(u\) yields  
\[\sum_{m=1}^{u}f^{2}(P_{m},X)\geq\frac{f^{2}(U,X)}{u}.\]  
Plugging this in (29) gives the desired bound on the term \(f(U^{\prime},X)\),  
\[\sum_{m=1}^{u}\Pr(j=m)f(U\setminus P_{m},X)\leq\left(1-\frac{1}{u}\right)\frac{ f^{2}(U,X)}{f(P,X)}=\frac{u^{\prime}}{u}\frac{f^{2}(U,X)}{f(P,X)}\leq\frac{ \max\left\{u^{\prime},1\right\}}{u}f(U,X),\]  
where the last inequality holds since \(f(U,X)\leq f(P,X)\). Plugging the last inequality in (28) bounds \(E[f(P,Y)\mid y\in U]\) by  
\[E[f(P,Y)\mid y\in U]\leq\big{(}f(P\setminus U,X)+4\rho^{2}f^{*}(U,u)\big{)}H_{ t-1}+\frac{u-t}{u}f(U,X). \tag{30}\]  
Bound on \(E[f(P,Y)]\). Plugging (30) and (25) in (24) yields  
\[E[f(P,Y)] \leq\big{(}f(P\setminus U,X)+4\rho^{2}f^{*}(U,u)\big{)}H_{t-1}\] \[\quad+f(U,X)\left(\Pr(y\in P\setminus U)\cdot\frac{u-t+1}{u}+ \Pr(y\in U)\cdot\frac{u-t}{u}\right). \tag{31}\]  
Firstly, we have  
\[\Pr(y\in P\setminus U)\cdot\frac{u-t+1}{u}+\Pr(y\in U)\cdot\frac{u-t}{u}= \frac{u-t}{u}+\Pr(y\in P\setminus U)\cdot\frac{1}{u}\leq\frac{u-t}{u}+\Pr(y \in P\setminus U)\cdot\frac{1}{t},\]  
where the last inequality holds as \(u\geq t\).