Strong Coresets for k-Median and Subspace Approximation: Goodbye Dimension

Introduction

Often in these problems one seeks a strong coreset, which means that with high probability, the data structure $D$ should work simultaneously for all queries $Q$. That is, one may use random choices in the construction of $D$, but after forming $D$ it should be the case that $D$ can be used to provide a $(1+\epsilon)$-relative error approximation for every possible query simultaneously. An advantage of such a coreset is that for any objective function for which a table of $(1+\epsilon)$-approximate values to all possible queries can be used to provide a $(1+O(\epsilon))$-approximation to the objective function, one can throw away the original set of points and instead just retain the data structure $D$. For example, note that the above coreset for subspace approximation contains enough information to approximately solve principal component analysis (PCA), since if one finds the query $k$-dimensional subspace with minimum approximate value, this provides a $k$-dimensional subspace providing a $(1+\epsilon)$-approximation to the space spanned by the top $k$ principal components. However, the above coreset for subspace approximation can also be used to solve the $k$-means problem, since the latter can be rewritten as a constrained low rank approximation problem . Thus, given that a strong coreset approximately preserves the cost of any query, it can be used in place of the original point set in any application which depends only on the answers to the queries. Note that if the coreset were instead to only approximately preserve the cost of any fixed query with high probability, then it might not be possible to solve the problem using the coreset since one may need to adaptively query the data structure, and outputs to successive queries may no longer be correct since the inputs depend on outputs to previous queries.

Another advantage of a coreset is if it small, then it leads to considerable efficiency gains. For example, in distributed settings, each machine which has a subset of input points can compress its input points to a coreset, and then communicate the coreset to a central coordinator. The central coordinator, who often has more resources available, can then combine the coresets and use them to optimize the desired function. As communication is a bottleneck, a small coreset gives rise to more efficient protocols. Similarly, when processing a data stream, a common technique is the merge-and-reduce framework, in which one partitions the stream into chunks, computes a coreset on each chunk, and merges the coresets in a binary tree like structure as one processes successive chunks of the data stream. A small coreset thus leads to small space streaming algorithms.

A major open question was if one could obtain strong coresets independent of $d$ (and $n$) for $k$-median and the subspace approximation problem with sum of distances $\sum_{i=1}^{n}\|p_{i}-p_{i}P_{V}\|_{2}$, as opposed to the sum of squares of distances. Unlike the $k$-means and sum of squares objective for subspace approximation, the $k$-median and sum of distances measures are much less amenable to algebraic manipulation; indeed there is no singular value decomposition (SVD) which was the driving force behind previous results. Notably, this version of the subspace problem is NP-hard , unlike minimizing the sum of squares.

Now consider the cost of an arbitrary point $q$ at distance $1$ from the origin. The expected distance of an input point to this point is roughly $\sqrt{2}$ and so the sum of distances will approach $\sqrt{2}n$ as $n\rightarrow\infty$. Now recall that the length of the projection of the input points goes to $0$. Thus their distance to $q$ will be roughly $1$. Thus, the sum of distances of the projected points is roughly $n$ plus the projection cost, which is roughly $n$, and thus will give an estimate of $2n$, which is not a $(1+\epsilon)$-approximation. Hence, we cannot simply work with a single additive weight as in the case of squared distances.

Next, since we can “move” each of the rows of $AP_{V\cup S}$ to the corresponding rows in $AP_{S}$ by paying a total sum of distances cost of $\epsilon\cdot\text{opt}$, it follows by the triangle inequality that for any set $C$ of points that is contained in a $k$-dimensional subspace $V$, the sum of distances from the rows of $AP_{S}$ to their corresponding closest points in $C$ is within $\epsilon\cdot\text{opt}$ of the sum of distances from the rows of $AP_{V\cup S}$ to their corresponding closest points in $C$.

Now we want to replace our original points (the rows of $A$) with their projections onto $S$, namely, replace $A$ with $AP_{S}$. Although this step by itself does not reduce the number $n$ of points, each of the $n$ points after projection lives in a much lower $k/\epsilon^{2}$ dimensional subspace (rather than the initial space which has dimension $d$), and we will then be able to apply coreset construction techniques which depend on this much smaller dimension. For any set $C$ of points contained in a $k$-dimensional subspace $V$, by the Pythagorean theorem we can write the distance of a row $p$ of $A$ to $C$ as $\sqrt{a^{2}+b^{2}}$, where $a$ is the distance of $p$ to $V\cup S$, and $b$ is the distance of the projection of $p$ onto $V\cup S$, to $C$. We instead try to approximate $\sqrt{a^{2}+b^{2}}$ by $\sqrt{f^{2}+g^{2}}$, where $f$ is the distance of $p$ to $S$ and $g$ is the distance of the projection of $p$ onto $S$, to $C$. We observe in Lemma 4 that $|\sqrt{a^{2}+b^{2}}-\sqrt{f^{2}+g^{2}}|\leq|a-f|+|b-g|$, and we know that the average values (over the $n$ points) of $|a-f|$ and $|b-g|$ are small by Lemma 6 combined with the triangle inequality.

Note that the value $f$, which is different for each of the $n$ rows of $A$, does not depend on $V$ or $C$, whereas the value $g$ is exactly the distance of the row of $AP_{S}$ to $C$. If we were simply to define $B=AP_{S}$, then $\|B-B_{C}\|_{1,2}$, where the i-$th$ row of $B_{C}$ contains the closest point (of the closure) of $C$ to the corresponding row of $B$, would fail to capture the distances of the $n$ rows of $A$ to $S$. Further, unlike for the $\|\cdot\|_{2,2}$ norm, we cannot add a single number $\|A(I-P_{S})\|_{2,2}$ to account for this, which is a technique used in ; this is precisely the difficulty of the $\|\cdot\|_{1,2}$ norm that we must deal with. Instead, a crucial idea is to append one additional coordinate to each row of $B$, where in the $i$-th row we append $\|A_{i*}(I-P_{S})\|_{2}$, where $P_{S}$ is the orthogonal projection onto $S$. Then, to compute the distance to a $k$-dimensional subspace $V$, instead of approximating $\|A-A_{C}\|_{1,2}$ by $\|B-B_{C}\|_{1,2}$, where the $i$-th rows of $A_{C}$ and $B_{C}$ contain the closest points (of the closure) of $C$ to the corresponding row of $A$ and the first $d$ coordinates of the corresponding row of $B$, respectively, we approximate $\|A-AP_{V}\|_{1,2}$ by $\|B-B_{C}I^{T}\|_{1,2}$, where $B_{C}I^{T}$ is the matrix which appends an all $0$ column to $B_{C}$. Thus, the norm of the $i$-th row of $B-B_{C}I^{T}$ is $\sqrt{f^{2}+g^{2}}$, where $f$ is the distance of $A_{i}$ to $S$, captured by the $(d+1)$-st coordinate of $B$, and $g$ is the distance of $A_{i}P_{S}$ to $C$. Thus, we have “encoded” the distances of the rows of $A$ to $AP_{S}$ in the coreset this way. Note that this appended additional coordinate cannot be taken out of each row and combined into a single number, as in , because for each row, its square is added to the squared distance of a point to its projection onto $S$, and then a square root is taken, so it occurs “under the square root” in the distance computations.

1.2 Coreset Construction for Subspace Approximation

1.3 Coreset Construction for kk-Median

To obtain a coreset for $k$-median, we first apply our dimensionality reduction to get a matrix $B$ such that for every set of $k$-centers $C$ we have $\big|\|A-A_{C}\|_{1,2}-\|B-B_{C}I^{T}\|_{1,2}\big|\leq\epsilon\cdot\|A-A_{C}\|_{1,2}$, where $A_{C}$ and $B_{C}$ denote the matrices that contain in the $i$-th row the closest center of $C$ to the $i$-th row of $A$ and $B$, respectively. We note that $B$ can be viewed as a point set in $O(k/\epsilon^{2})$ dimensions. We can then use an arbitrary coreset construction for this low dimensional point set where we append $k$ arbitrary dimensions to the space. Thus, the effect of the construction will be to replace the $d$ in a coreset construction by $O(k/\epsilon^{2})$. We claim that a coreset for this enlarged space is also a coreset for the $d$-dimensional space. The reason is that any set of $k$-centers in the $d$-dimensional space is either in the span of $B$ (in which case the coreset guarantee holds) or there is an orthogonal transformation that does not change $B$ and maps the remaining centers to the $k$ added dimensions. This implies that the coreset property holds for the full space. Thus, the cost of the coreset approximates the cost of $B$ upto a factor of $1\pm\epsilon$. Combining this with the error bound of $\big|\|A-A_{C}\|_{1,2}-\|B-B_{C}\|_{1,2}\big|\leq\epsilon\cdot\|A-A_{C}\|_{1,2}$ gives that the resulting set will be a $1+O(\epsilon)$ coreset and the result follows by rescaling $\epsilon$ by a constant. Notice that the guarantee the coreset provides is slightly stronger than what we need as our centers will always have the last (special) coordinate equal to $0$.

Plugging in the $k$-median coresets of or , which are both of size $O(\frac{dk\log k}{\epsilon^{2}})$ (the first one has negative weights, which may be undesirable in some situations), we obtain a coreset of size $O(\frac{k^{2}\log k}{\epsilon^{4}})$.

1.4 Outline

In Section 2, we give preliminaries. In Section 3, we provide our main dimensionality reduction technique. In Section 4, we obtain our coresets for subspace approximation. Finally, in Section 5, we obtain our coreset for $k$-median.

Preliminaries

We start with a few claims that will be useful to deal with norms and powers of norms. These are elementary properties about numbers and we defer the proofs to the Appendix.

Let $a,b,c\geq 0$ such that $a^{2}=b^{2}-c^{2}$. For $p\geq 2$ we have $a^{p}\leq b^{p}-c^{p}$.

Let $a,b,c\geq 0$ such that $a^{2}=b^{2}-c^{2}$, $a^{p}\geq\epsilon b^{p}$ and $b^{p}\geq c^{p}$. Let $1\leq p\leq 2$ and $1\geq\epsilon>0$. Then $a^{p}\leq 10\cdot\epsilon^{\frac{p-2}{p}}\cdot(b^{p}-c^{p})$.

Let $a,b\geq 0$ and $1\geq\epsilon>0$ and $p\geq 1$. Then

Dimensionality Reduction

Our first result is a dimensionality reduction lemma for clustering problems where the cluster centers are contained in a low-dimensional subspace such as, for example, $k$-median clustering.

Proof: We know from the algorithm that $\|A-AP\|_{p,2}^{p}-\|A-AP^{*}\|_{p,2}^{p}\leq\epsilon^{\max\{\frac{2}{p},1\}}\text{opt}/80$. Furthermore, we have $\|A-AP\|_{p,2}^{p}\leq(1+\epsilon)\cdot\text{opt}$ by the way $S$ is computed. We first consider the case when $p=2$. Since $A_{i*}-A_{i*}P^{*}$ is orthogonal to $A_{i*}P^{*}-A_{i*}P$ we know that in this case

Applying the above equality row wise we obtain

Next we consider $p>2$. We define $a=\|A_{i*}P-A_{i*}P^{*}\|_{2}$, $b=\|A_{i*}-A_{i*}P\|_{2}$ and $c=\|A_{i*}-A_{i*}P^{*}\|_{2}$. We observe that $a^{2}=b^{2}-c^{2}$ and so by Claim 1 we obtain that

Again we can apply the inequality row-wise and obtain

Now we consider the final case of $1\leq p<2$. Here we will make a case distinction. The first case is that $\|A_{i*}P^{*}-A_{i*}P\|_{2}^{p}\leq\frac{\epsilon}{4}\|A_{i*}-A_{i*}P\|_{2}^{p}$. Let $J$ be the set of indices for which this inequality is satisfied. It follows by summing up over all rows in $J$ that

For the remaining case we will use Claim 2 with $a=\|A_{i*}P-A_{i*}P^{*}\|_{2}$, $b=\|A_{i*}-A_{i*}P\|_{2}$ and $c=\|A_{i*}-A_{i*}P^{*}\|_{2}$. We observe that $a^{2}=b^{2}-c^{2}$ and that $a^{p}\geq\frac{\epsilon}{4}b^{p}$ since we are in the second case. Furthermore, $b^{p}\geq c^{p}$ by the choices of $P$ and $P^{*}$. Therefore, Claim 2 implies

Applying the above inequality row wise we obtain

Summing up the two cases yields the lemma. $\Box$

We observe that in the proof we only used two properties of $S$. The first one is that $\|A-AP\|_{p,2}^{p}\leq(1+\epsilon)\cdot\text{opt}$ and the second one is that $\|A-AP\|_{p,2}^{p}-\|A-AP^{*}\|_{p,2}^{p}\leq\epsilon^{\max\{\frac{2}{p},1\}}\text{opt}/80$. Thus, any subspace that satisfies these two properties will also satisfy the above lemma. We will use this later on when we discuss optimizing the running time of our algorithm.

We first consider the case of minimizing sum of distances. This case is technically less tedious and illustrates the underlying ideas.

where opt is the cost of an optimal solution to the $k$-subspace problem with sum of distances. By orthogonality, we can write

Using Lemma 4 with $a=\|A_{i*}-A_{i*}P^{*}\|_{2}$, $b=\|A_{i*}P^{*}-A^{\prime}_{i*}\|_{2}$, $e=\|A_{i*}-A_{i*}P\|_{2}$ and $f=\|A_{i*}P-B^{\prime}_{i*}\|_{2}$ we obtain that

Using the triangle inequality and the fact that $A^{\prime}_{i*},B^{\prime}_{i*}$ is the closest point in the closure of $C$ to $A_{i*}P^{*}$ and $A_{i*}P$, respectively, we obtain

Summing up over all rows and using $\|AP-AP^{*}\|_{1,2}\leq\frac{\epsilon}{2}\cdot\text{opt}$ together with the fact that the sum of distances to $C$ is at least opt we obtain the result. $\Box$

If $C$ is a $k$-dimensional linear subspace we can slightly simplify the statement of the above theorem.

2 Dimensionality reduction for powers of Euclidean distances

In order to obtain a dimensionality reduction for powers of Euclidean distances we follow the same approach as before. The main challenge is that some calculations become more difficult as the triangle inequality is replaced by a relaxed triangle inequality.

where opt is the cost of an optimal solution to the $k$-subspace problem with sum of powers of distances. By orthogonality, we can write

Now let us assume that $\|A_{i*}-A^{\prime}_{i*}\|_{2}\leq\|B_{i*}-B^{\prime}_{i*}I^{T}\|_{2}$ (the other case is analogous). By the triangle inequality and the definition of $A^{\prime}$ and $B^{\prime}$ we have

where the last inequality follows from Claim 5 with $\lambda^{2}$ replacing the $\epsilon$ there. We can write

Thus, using $\lambda=\epsilon^{1/2+1/p}/(21p)$ we obtain

The final result follows by summing up over all rows, replacing $(\sqrt{x})^{p}$ by $\|A_{i*}-A_{i*}^{\prime}\|_{2}^{p}$, and plugging in the bound for $\|AP-AP^{*}\|_{p,2}^{p}$.

Now let us assume that $\|A_{i*}-A^{\prime}_{i*}\|_{2}>\|B_{i*}-B^{\prime}_{i*}I^{T}\|_{2}$. By the triangle inequality and the definition of $A^{\prime}$ and $B^{\prime}$ we have

where the last inequality follows from Claim 5 with $\lambda^{2}$ replacing the $\epsilon$ there. We can write

Thus, using $\lambda=\epsilon^{1/2+1/p}/(21p)$ we obtain

The final result follows by summing up over all rows, replacing $(\sqrt{x})^{p}$ by $\|A_{i*}-A_{i*}^{\prime}\|_{2}^{p}$, and plugging in the bound for $\|AP-AP^{*}\|_{p,2}^{p}$.

3 Optimizing the Running Time

We first give an alternative algorithm to our DimensionalityReduction algorithm. This algorithm can be implemented using a black box call to an algorithm for finding low dimensional subspaces approximately minimizing the $\|\cdot\|_{p,2}^{p}$ norm.

There are $10/\tau$ summands in the telescoping sum, and they sum up to at most opt, so a $9/10$-fraction of them must be at most $\tau\text{opt}$. Let $i^{*}$ be the index sampled by the algorithm. Then with probability at least $9/10$, we have $\|A(I-P_{V^{i^{*}}})\|_{p,2}^{p}-\|A(I-P_{V^{i^{+}1}})\|_{p,2}^{p}\leq\tau\text{opt}$, and let us condition on this event.

where we used that $\|A(I-P_{V^{i^{*}}})\|_{1,2}-\|A(I-P_{V^{i^{*}+1}})\|_{1,2}\leq\tau\text{opt}$ for our choice of $i^{*}$, and also that $\|A(I-P_{V^{i^{*}}})\|_{p,2}^{p}\leq\text{opt}$.

Note that the overall success probability is at least $1-1/10-1/10$ in the first case and $1-1/10-1/20-1/20=4/5$ in the second, and the claimed running time follows from , and . $\Box$

We also need the following lemma stating that the approximations returned by Lemma 12 suffice.

Suppose we replace the last column $v$ of $B$ with a vector $v^{\prime}$ for which $v_{i}=(1\pm\epsilon)v^{\prime}_{i}$ for all $i\in[n]$. Then (1) continues to hold with $\epsilon$ replaced with $O(\epsilon)$.

Proof: Notice that this operation changes $\|B-BIPI^{T}\|_{p,2}^{p}$ by at most a $(1+O(\epsilon))$ factor for constant $p$, since each row changes by at most this factor. Letting $B^{\prime}$ denote the new matrix, we have

and rescaling $\epsilon$ by a constant factor gives the desired guarantee. $\Box$

where the first equality uses the definition of $B$, the second equality uses (3), the third equality just expands the square, the fourth equality uses (4) and that $\text{dist}(A_{i},A_{i}P)=\text{dist}(A_{i},S)$, the penultimate equality absorbs the previous equality in the asymptotic notation $O(\epsilon)$, and the final equality uses that $\|B_{i}-(B^{\prime}I)_{i}\|_{2}^{2}=\text{dist}(A_{i}P,C)^{2}+\text{dist}(A_{i},S)^{2}$.

Now, for a given $i$, $\|B_{i}-(B^{\prime}I)_{i}\|_{2}^{2}=\text{dist}(A_{i}P,C)^{2}+\text{dist}(A_{i},S)^{2}$. Notice that $\text{dist}(A_{i}P,C)\leq\text{dist}(A_{i},C)+\text{dist}(A_{i}P,A_{i})=\text{dist}(A_{i},C)+\text{dist}(S,A_{i})$, and consequently $\|B_{i}-(B^{\prime}I)_{i}\|_{2}^{2}=O(\text{dist}(A_{i},C)^{2}+\text{dist}(A_{i},S)^{2})$, and plugging into (5),

where the first equality follows by plugging into (5), the second equality follows from $(\text{dist}(A_{i},C)^{2}+\text{dist}(A_{i},S)^{2})^{p/2}\leq(2\max(\text{dist}(A_{i},C)^{2},\text{dist}(A_{i},S)^{2}))^{p/2}\leq 2^{p/2}\max(\text{dist}(A_{i},C)^{p},\text{dist}(A_{i},S)^{p})\leq 2^{p/2}(\text{dist}(A_{i},C)^{p}+\text{dist}(A_{i},S)^{p})$, the third equality follows from $\sum_{i}\text{dist}(A_{i},S)^{p}\leq(1+\epsilon)\sum_{i}\text{dist}(A_{i},C)^{p}$ by definition of $S$ and the fact that $C$ is contained in a $k$-dimensional subspace, and the final equality just uses the definition of $\|A-A^{\prime}\|_{p,2}^{p}$. $\Box$

Coresets for Subspace Approximation

Plugging in the guarantee of Lemma 11 into Remark 7 shows how to obtain an $n\times(d+1)$ matrix $B$ for which

for all rank-$k$ orthogonal projection matrices $P$. Lemma 11 shows how to efficiently find the $S$ for which $B=AP_{S}$, and Lemma 12 shows how to efficiently find an approximate vector $v$ of $(d+1)$-st coordinates of $B$. Further, after scaling $\epsilon$ by a constant factor, Lemma 13 shows that (6) continues to hold with the approximate vector $v$ of $(d+1)$-st coordinates of $B$ furnished by Lemma 12.

Before showing how to find a sampling and rescaling matrix $T$, we first need the following theorem due to Dvoretsky.

Proof: Let $t$ be as in Fact 15, and fix the $d\times t$ matrix $G$ of that fact. Applying the guarantee of Fact 15 to each row of $B-BIPI^{T}$,

where for a matrix $C$, $\|C\|_{p,p}^{p}$ denotes the sum of $p$-th powers of absolute values of its entries.

since each column of $BG$ is in the column span of $AU$. Again applying the guarantee of Fact 15 to each row of $TBG-TBIPI^{T}G$, we have

and the guarantee of the lemma follows by rescaling $\epsilon$ by a constant factor. $\Box$

Proof: We start by proving the structural part of the theorem, and then address the running time.

Let $B$ be the output of DimensionalityReduction, which has property (6). As described above, we can assume DimensionalityReduction produces $B=[AP_{S},v]$, where $P_{S}$ and $v$ are described above. Further, we can assume $AP_{S}$ is given in factored form $(AU)U^{T}$ for $P_{S}=UU^{T}$.

By Lemma 16, we can find a sampling and rescaling matrix $T$ for which for all rank-$k$ orthogonal projection matrices $P$, $\|TB-TBIPI^{T}\|_{p,2}^{p}=(1\pm\epsilon)\|B-BIPI^{T}\|_{p,2}^{p}$, so

and rescaling $\epsilon$ by a constant factor gives the desired guarantee. We note that By Lemma 16, $T$ will have $O(k(\log k)/\epsilon^{4})$ rows for $p=1$ if we run DimensionalityReduction.

Coresets for kk-Median

We can combine our dimensionality reduction with coreset computations. We first compute the matrix $B$ using our dimensionality reduction. Recall that this matrix has rank $O(k/\epsilon^{2})$. We can therefore compute an orthogonal basis for the span of $B$ and add $k$ arbitrary dimensions. Then we apply an arbitrary coreset construction in the resulting space. We will only be interested in the space spanned by the first $d$ dimensions of $B$ (recall that the last dimension is only needed to “adjust” the distances). Since the Euclidean distance does not change under orthogonal transformations we can rotate any set of centers to our subspace without changing the distances. Therefore, the coreset will be a coreset for the whole input space.

Here $A^{C}$ contains for each row of $A$ the nearest center of $C$, $T^{C}$ contains for each row of $T$ the nearest center of $C$ with respect to $TI^{T}$.

We get the following guarantees. Theorem 8 implies

Rescaling $\epsilon$ gives the result. $\Box$

Acknowledgment

Christian Sohler acknowledges the support of the German Science Foundation (DFG) Collaborative Research Center SFB 876 ”Providing Information by Resource-Constrained Analysis”, project A2. David Woodruff acknowledges support in part by an Office of Naval Research (ONR) grant N00014-18-1-2562.

We thank Lingxiao Huang for pointing out an error in the proof of Lemma 14 in an earlier version of this paper.

References

Appendix A Appendix

Proof: ( of Claim 1) By our assumptions we have

Subtracting $c^{p}$ yields the claim. $\Box$

Proof: ( of Claim 2) We observe that for $c=0$ the result is trivial, so we may assume $c\not=0$. We know that $a^{2}+c^{2}=b^{2}$ and so $(a^{2}+c^{2})^{p/2}=b^{p}$. We write $a=\delta c$ for some $\delta>0$ (the case $\delta=0$ implies $a=b=c=0$ and the result follows immediately). For the case $\delta<1$ we obtain

where the second inequality follows from $(1+\delta^{2}/3)^{2}\leq 1+\delta^{2}$. The last inequality follows from from $\delta^{p}c^{p}=a^{p}\geq\epsilon b^{p}\geq\epsilon c^{p}$ (since c¿0) and hence $\delta^{p}\geq\epsilon$.

Plugging this into $(a^{2}+c^{2})^{p/2}=b^{p}$ gives

which implies the claim for $\delta<1$ by subtracting $c^{p}$ and multiplying with $3\epsilon^{\frac{p-2}{p}}$.

Plugging this into $(a^{2}+c^{2})^{p/2}=b^{p}$ gives

which implies the claim since $\epsilon^{\frac{p-2}{p}}\geq 1$.

and the claim follows analogous to the above.

Proof: ( of Claim 3) We can assume wlog. $a\geq b$ and then this is equivalent to showing $(a+x)^{p}-a^{p}\leq(b+x)^{p}-b^{p}$. When $x=0$ both sides are $0$. The derivative, as a function of $t$, of $f_{c}(t):=(c+t)^{p}-c^{p}$, for a fixed $c$, is $p/(c+t)^{1-p},$ so the derivative $df_{a}(t)/dt$ is less than or equal to $df_{b}(t)/dt$ for every $t\geq 0$, and by the fundamental theorem of calculus,

Proof: ( of Claim 5) Observe that $(1+\epsilon/(2p))^{p}\leq 1+\epsilon$ follows from the monotonicity of the logarithm and $\ln((1+\epsilon/(2p))^{p})\leq p\cdot\epsilon/(2p)\leq\epsilon-\epsilon^{2}/2\leq\ln(1+\epsilon)$ by the Taylor expansion of $\ln(1+x)$ for $0<\epsilon<1$ (for $\epsilon=1$ the Claim follows immediately). If $b\leq\frac{\epsilon}{2p}\cdot a$ then $(a+b)^{p}\leq(1+\frac{\epsilon}{2p})^{p}\cdot a^{p}\leq(1+\epsilon)a^{p}$. Otherwise, $b>\frac{\epsilon}{2p}\cdot a$. In this case $(a+b)^{p}\leq(1+\frac{2p}{\epsilon})^{p}b^{p}$. $\Box$

Proof: ( of Lemma 4) We have by the triangle inequality and $2$-norm to $1$-norm relationship,