Coresets for $1$-Center in ${\mathrm{\ell }}_1$ Metrics

We point our attention to a more relaxed notion, called weak coreset, which only approximates the cost of certain centers, namely, centers that may be found by solving the coreset instance. Trivially, every strong $ϵ$-coreset is also a weak $ϵ$-coreset.

Weak coresets were introduced in [8] specifically for $1$-center in Euclidean space. It is well-known that in Euclidean space, there is a unique optimal solution,²²2The uniqueness follows from the fact that ${\mathrm{\ell }}_2$ is strictly convex, whereas ${\mathrm{\ell }}_1$ is convex but not strictly convex. which is why previous work often refers to $c^Q$ as the optimal center. The challenge then becomes how to extend this definition to other metric spaces, like ${\mathrm{\ell }}_1$ norm, that might have multiple optimal solutions. The typical use of a coreset $Q$ is to apply an algorithm on $Q$ and take the resulting center $c^Q$ as an approximated solution for the original instance $P$. Since a generic algorithm might pick any of the multiple optimal centers for $Q$, it is essential to have a guarantee that applies to every possible optimal solution $c^Q$ for $Q$, hence the universal quantifier (“for all”) in (2).

Remarkably, in Euclidean space, every instance $P$ admits a weak $ϵ$-coreset of size $\lceil 1/ϵ\rceil$, which is independent of the input size $n=|P|$ and of the Euclidean dimension $d$, and is in fact tight [7]. This result improved an earlier $O(1/{ϵ}^2)$ bound from [8], which was also dimension independent. Can similar bounds be proved for ${\mathrm{\ell }}_1$ metrics?

We demonstrate that, in sharp contrast to the ${\mathrm{\ell }}_2$ setting, weak coresets in ${\mathrm{\ell }}_1$ are dimension dependent and moreover grow exponentially with $d$, even for a fixed $ϵ>0$. At the same time, we show how to construct a strong $0$-coreset of size $2^d$, which again contrasts with the ${\mathrm{\ell }}_2$ setting (and doubling metric spaces), where coresets grow with $1/ϵ$ and are thus not applicable for $ϵ=0$. It is well-known that a strong coreset is composable, i.e., the union of coresets is itself a coreset for the union of the original datasets, which is very useful for designing algorithms in the streaming and dynamic settings. Thus, our coreset construction can be used in these settings, particularly in low dimension.

We prove this theorem in Section 2. The upper bound leverages the unique geometry of ${\mathrm{\ell }}_1$, where only $2^d$ directions are in effect important. The lower bound builds a hard instance and employs classical techniques from coding theory, particularly the Hamming bound. We remark that an unpublished result from [30, Theorem 5], for a related problem about a convex shape in ${\mathrm{\ell }}_2$ metric, seems to imply a weak $ϵ$-coreset of size $\mathrm{poly}(d/ϵ)$ for our problem of $1$-center in ${\mathrm{\ell }}_1$ metrics. This would contradict our lower bound in Theorem 1.3, indicating that its statement is inaccurate or its proof is flawed; see also a similar discussion in [6].

Due to the exponential dependency on $d$ in the general case, it is important to identify cases with a smaller coreset size, say $\mathrm{poly}(d)$ or even dimension independent. Additionally, one may suspect that the huge disparity between ${\mathrm{\ell }}_1$ and Euclidean space, which does admit a dimension-independent weak coreset [7, 8], is the fact that in ${\mathrm{\ell }}_1$ the optimal center need not be unique. We thus study the special case of ${\mathrm{\ell }}_1$ where the optimal center is unique, which may occur naturally in certain contexts, or be “enforced” by adding at most two points to the input dataset. We provide bounds that are exponentially smaller than in the general case, but still depend on $d$, which establishes that ${\mathrm{\ell }}_1$ is inherently more complex than ${\mathrm{\ell }}_2$.

We prove this theorem in Section 3. We further conjecture that the lower bound can be improved to $\mathrm{\Omega }(d)$, and prove it in the special case $ϵ=0$ using Hadamard code. The upper bound in our theorem employs tools from convex geometry, specifically the Steinitz Theorem, which is relatively obscure, to prove the existence non-constructively (i.e., without an efficient algorithm). For the lower bound, we consider the instance $P={\{\pm 1\}}^d$, which has a unique optimal center at the origin, and show that a coreset $Q$ that is too small, must have an optimal center $c^Q$ in which most coordinates are $\pm 1$, and this center is clearly a poor solution for $P$.

To further reduce the coreset size, we consider an even less restrictive variant that preserves solely the objective function $\mathrm{opt}(P)$, without imposing any conditions on the optimal centers of the coreset. This concept, which we shall refer to as a value-preserving coreset, has been studied previously under the general term “coreset” [6, 14, 33], and it is most useful in applications that focus on measuring the similarity among points in the cluster, rather than identifying a center. It is easy to verify that every weak coreset is also a value-preserving coreset.

We show that there exist value-preserving $ϵ$-coresets of size $\tilde{O}(1/{ϵ}^2)$, which is dimension independent, in contrast with Theorems 1.3 and 1.4. We thus establish a sharp separation between preserving an optimal solution (center point) or only preserving its value. This result is stated in the next theorem and proved in Section 4. It also answers a question posed in [6], which studies a generalization of $1$-center, called the Minimum Enclosing Polytope problem, and asks for polytopes that admit a dimension-independent value-preserving coreset.³³3Prior to our result showing that the ${\mathrm{\ell }}_1$ ball (also known as the cross-polytope) admits dimension-independent value-preserving coreset, the only known example was the parallelotope, which trivially has a value-preserving $0$-coreset with only $2$ points.

We prove this theorem in Section 4. Our algorithm is based on random sampling, a technique that was rarely used (if at all) for $1$-center coresets, but widely used for $k$-median and $k$-means coresets [15, 18, 22]. This is very natural because sampling is an excellent fit for objectives like $k$-median that that are formed by summation, but not for objectives like $k$-center that are formed by maximization, which are sensitive to missing even one term. It is thus not surprising that our sampling is conducted not on the $1$-center problem but rather on its dual. More precisely, we formulate $1$-center as a linear programming (LP) problem and write its dual problem, then solve this dual problem to obtain sampling probabilities for the input points. Crucially, the dual objective is formed by summation, and is thus conducive to sampling. Compared with the primal-dual framework, our algorithm is dual-only and it solves the dual LP explicitly, which is then related in the analysis to the primal via strong duality. Our sampling is similar to the randomized rounding commonly used in approximation algorithms, however its purpose here is to generate a coreset instead of a solution, and also the analysis is somewhat different.

We demonstrate that our results for weak coresets in ${\mathrm{\ell }}_1$ (in Sections 2 and 3) apply also to other discrete metric spaces. Specifically, we provide in Section 5 examples that use Kendall’s tau and Jaccard metrics, drawing inspiration from the results obtained in the ${\mathrm{\ell }}_1$ setting.

Let $\mathrm{\Sigma }={\{-1,1\}}^d$ denote the set of all sign vectors in ${ℝ}^d$. For each sign vector $\sigma \in \mathrm{\Sigma }$, let $p_{\sigma }$ be a point in $P$ such that the inner product $p_{\sigma }\cdot \sigma$ is maximized. Define $Q_{\mathrm{\Sigma }}=\{p_{\sigma }:\sigma \in \mathrm{\Sigma }\}$, clearly $\left|Q_{\mathrm{\Sigma }}\right|\le \left|\mathrm{\Sigma }\right|=2^d$.

Let $c\in {ℝ}^d$. Since $Q_{\mathrm{\Sigma }}$ is a subset of $P$, we have that $\mathrm{cost}(c,Q_{\mathrm{\Sigma }})\le \mathrm{cost}(c,P)$. Let $p$ be some point in $P$, then there exists a sign vector $\sigma \in \mathrm{\Sigma }$ for which we can write the distance between $p$ and $c$ as:

By definition of $Q_{\mathrm{\Sigma }}$, there exists a point $p_{\sigma }\in Q_{\mathrm{\Sigma }}$ satisfying $\sigma \cdot p\le \sigma \cdot p_{\sigma }$. Thus,

That is,

$◀$

We may assume without loss of generality that $d$ is even, as otherwise we can take the construction for $d-1$ and append $0$ to all the points (vectors).

Denote by $\overrightarrow{1}$ the vector $(1,1,\mathrm{\dots },1)$, and let $B\subseteq {\{\pm 1\}}^d$ be the set of points that are balanced, in the sense that they have an equal number of $1$ and $-1$ coordinates, i.e., $B=\{b\in {\{\pm 1\}}^d:{\sum }_{i=1}^d{b}_i=0\}$. Fix , and let $P=\{-\overrightarrow{1},\overrightarrow{1}\}\bigcup (1-\delta )B$, where $(1-\delta )B$ denotes the set of points in $B$ scaled by factor $1-\delta$. Thus, $|P|=2+\left(\genfrac{}{}{0pt}{}{d}{d/2}\right)=\mathrm{\Theta }(2^d/\sqrt{d})$. One can verify that the origin $\overrightarrow{0}\in {ℝ}^d$ is an optimal center, with value $d$. However it is not unique; to see this, observe that the antipodal pair $\{-\overrightarrow{1},\overrightarrow{1}\}$ establishes the optimal value $\mathrm{opt}(P)=d$, thus an optimal center must have the same distance $d$ to each of them, which holds for points $x\in {[-1,1]}^d$ that lie on the hyperplane ${\sum }_{i=1}^d{x}_i=0$. The set $(1-\delta )B$ restricts the optimal solutions (inside that hyperplane) in a delicate manner, as we shall see.

We first show that $P$ is the only weak $0$-coreset of $P$. Let $Q\subseteq P$ be a weak $0$-coreset, and notice that $\mathrm{opt}(Q)=\mathrm{opt}(P)=d$, implying that $Q$ must contain the antipodal pair $-\overrightarrow{1}$ and $\overrightarrow{1}$. Assume towards contradiction that $Q$ is a proper subset of $P$. Then there exists $(1-\delta )\tilde{b}\in P\setminus Q$ for some $\tilde{b}\in B$. Let $\eta =\frac{1}{d}$ and consider $c^{\ast }=-(1+\eta )\delta \tilde{b}$; it cannot be an optimal center of $P$, because

We next show that this point $c^{\ast }=-(1+\eta )\delta \tilde{b}$ is an optimal center of $Q$. Indeed, observe that $\delta \le \frac{1}{3}$ implies $(1+\eta )\delta \le 1-\delta$, and thus the sign of $1-\delta$ will not change if we add/subtract to it $(1+\eta )\delta$. Let $\mathrm{sgn}(x)\in \{-1,0,1\}$ denote the sign function. Now consider $a\in Q$; its distance to $-(1+\eta )\delta \tilde{b}$ is:

In the case $a\in \{-\overrightarrow{1},\overrightarrow{1}\}$, the above equals $d$. In the remaining case $a\in Q\setminus \{-\overrightarrow{1},\overrightarrow{1}\}$, the choice of $\tilde{b}$ implies that ${\sum }_{i=1}^d\mathrm{sgn}(a_i){\tilde{b}}_i\le d-2$, and thus

We have thus confirmed that $-(1+\eta )\delta \tilde{b}$ is an optimal center of $Q$, but not for $P$. This contradicts our assumption that $Q$ is a weak 0-coreset, and completes the proof of the first item.

To prove the second item, let $P\subset {ℝ}^d$ be as before but now for $\delta =\frac{1}{3}$, and consider a weak $ϵ$-coreset $Q$ of $P$, for some . Notice that $Q$ must contain both $-\overrightarrow{1}$ and $\overrightarrow{1}$, as otherwise, if $-\overrightarrow{1},\overrightarrow{1}\notin Q$, consider the origin $\overrightarrow{0}\in {ℝ}^d$ as a center. If $Q$ contains just one of $\{-\overrightarrow{1},\overrightarrow{1}\}$ say $\overrightarrow{1}$, consider $\delta \overrightarrow{1}$ as a center. In both cases, we obtain that , in contradiction to the weak $ϵ$-coreset.

Denote by $\psi (Q)$ the minimum Hamming distance between any point in $B$ and its furthest point in $Q$, that is, $\psi (Q)={\min }_{b\in B}{\max }_{a\in Q}\mathrm{Hamm}(a,b)$. The next proposition follows by a standard counting-bound.

Denote by $C_{\frac{3d}{4}}(a)$ the set of all points in ${\{\pm 1\}}^d$ whose Hamming distance from $a\in {\{\pm 1\}}^d$ is at least $\frac{3d}{4}$. Then

where the last inequality is the known entropy bound for binomial coefficients and $H(p)=-p\log p-(1-p)\log (1-p)$, hence $H(\frac{1}{4})\approx 0.811$. Taking a union over all $a\in Q$,

where in the last inequality we used the known bound $\frac{1}{\sqrt{2d}}{2}^d\le \left(\genfrac{}{}{0pt}{}{d}{d/2}\right)$. Hence, there exists some point in $B$ for which the maximum Hamming distance to points in $Q$ is smaller than $\frac{3d}{4}$. $◀$

Assume towards contradiction that $\left|Q\right|\le \frac{1}{\sqrt{2d}}{2}^{0.18d}$. Then by Proposition 2.3, there is a point $\tilde{b}\in B$ for which the maximum Hamming distance to points in $Q$ is smaller than $\frac{3d}{4}$. We next show that the point $2\delta \tilde{b}$ is an optimal center for $Q$. Similarly to Equation (4), since $2\delta \le 1-\delta$, for every $a\in Q$ we can write:

where:

and thus:

In the case $a\in \{-\overrightarrow{1},\overrightarrow{1}\}$, since $\tilde{b}\in B$ then we have ${\Vert a-2\delta \tilde{b}\Vert }_1={\Vert a\Vert }_1=d$. Otherwise $a\in (1-\delta )B$, and . In both cases, the distance from $a\in Q$ to $2\delta \tilde{b}$ is at most $d=\mathrm{opt}(Q)$, with equality for some $a\in Q$. Thus, $2\delta \tilde{b}$ is an optimal center for $Q$. However, $\mathrm{cost}(2\delta \tilde{b},P)\ge {\Vert 2\delta \tilde{b}+(1-\delta )\tilde{b}\Vert }_1=(1+\delta )d>(1+ϵ)\mathrm{opt}(P)$. This contradicts that $Q$ is a weak $ϵ$-coreset of $P$, and completes the proof of Theorem 2.2. $◀$

It is easy to note that the origin $\overrightarrow{0}\in {ℝ}^d$ is a unique optimal center with value $d$ as the input contains a point from every face of the ${\mathrm{\ell }}_1$ ball centered at $\overrightarrow{0}$. Consider a weak $ϵ$-coreset $Q\subset P$ of size $|Q|\le \frac{1}{2}\log d$. Every point $p\in Q$ induces a partition ${\mathrm{\Pi }}_p$ of $[d]$ into at most two parts, by splitting the coordinates of $p$ into the positive and negative ones. Let $\mathrm{\Pi }$ be the common refinement of all these partitions (i.e. placing $i,j\in [d]$ in the same part of $\mathrm{\Pi }$ if and only if for every $p\in P$ they are in the same part of ${\mathrm{\Pi }}_p$). Since each ${\mathrm{\Pi }}_p$ has at most two parts, $\mathrm{\Pi }$ has at most $2^{|Q|}\le \sqrt{d}$ parts. Observe that for every point $p\in Q$, coordinates in the same part of $\mathrm{\Pi }$ have the same sign.

Consider an optimal center $c^{\ast }$ for $Q$. The idea is to modify it iteratively, without increasing its cost for $Q$, so as to have more coordinates take values in $\{-1,1\}$. Each iteration takes two indices $i,j$ in the same part of $\mathrm{\Pi }$, whose coordinates in $c^{\ast }$ are both not in $\{-1,1\}$, say, . The iterations stop when no such indices exist. Now add $\delta$ to $c_i^{\ast }$ and $-\delta$ to $c_j^{\ast }$, where $\delta >0$ is as large as possible while keeping both new values in the range $[-1,1]$, that is, $\delta =\min \{1-c_j^{\ast },c_i^{\ast }-1\}$. It is easy to see that after this modification, at least one of $c_i^{\ast }$ and $c_j^{\ast }$ will be in $\{\pm 1\}$, and at the same time the distance to every $p\in Q$ does not change. The iteration stop at a center ${\overline{c}}^{\ast }$, where in each part of $\mathrm{\Pi }$ at most one coordinate is not in $\{\pm 1\}$, and in total at most $|\mathrm{\Pi }|\le 2^{|Q|}\le \sqrt{d}$ coordinates are not in $\{\pm 1\}$.

Finally, we show that $\overline{c^{\ast }}$, which is an optimal center for $Q$, has a too large cost for $P$. Consider the point in $P$ that is closest to $-\overline{c^{\ast }}$, i.e., where each coordinate of $-\overline{c^{\ast }}$ is rounded to the nearest value among $\{\pm 1\}$. This point disagrees with $-\overline{c^{\ast }}$ (i.e., rounding was “needed”) on at most $|\mathrm{\Pi }|$ coordinates, hence its distance from ${\overline{c}}^{\ast }$ is at least $2d-|\mathrm{\Pi }|$, hence $\mathrm{cost}({\overline{c}}^{\ast },P)\ge 2d-|\mathrm{\Pi }|\ge 2d-\sqrt{d}>(1+ϵ)\mathrm{opt}(P)$. $◀$

We remark that the proof works also for the discrete space ${\{-1,0,+1\}}^d$ (endowed with ${\mathrm{\ell }}_1$ norm), which has more limited choices for the center point, e.g., for $c^{\ast }$ above. Moreover, note that the distance of the modified optimal center ${\overline{c}}^{\ast }$ from $\overrightarrow{0}$ is at least $d-2^{|Q|}$.

$(\Rightarrow ):$ Write $\overrightarrow{0}$ as a convex combination, $\overrightarrow{0}={\sum }_i{\lambda }_i{s}_i$ where ${\lambda }_i\ge 0$ and ${\sum }_i{\lambda }_i=1$. Then,

If for all $s_i$, $v\cdot s_i\le 0$, then it must hold that for all $s_i$, $v\cdot s_i=0$, but then $\overrightarrow{0}$ is not in the interior of $\mathrm{conv}(S)$.

$(\Leftarrow ):$ If $\overrightarrow{0}\notin \mathrm{int}(\mathrm{conv}(S))$ then there exists a hyperplane $\mathscr{H}$ containing $\overrightarrow{0}$ such that $S\subseteq {\mathscr{H}}^{+}$. Since $\overrightarrow{0}$ is a point in the hyperplane we can write the hyperplane equation as $vx=0$ for some $v\in {ℝ}^d\setminus \{\overrightarrow{0}\}$. It follows that $v\cdot s\le 0$ for every $s\in S$, hence $S$ is not complete. $◀$

This leads to the following alternative statement of Steinitz’s theorem.

W.l.o.g., assume that $\overrightarrow{0}$ is the unique solution of $P$ and let $\mathrm{opt}(P)=\mathrm{cost}(\overrightarrow{0},P)=r$. Since $\overrightarrow{0}$ is unique, we can further assume that ${\Vert \overrightarrow{0}-p\Vert }_1=r$ for every $p\in P$; otherwise, any points that do not satisfy this can be removed without affecting the optimal solution or its cost. Given a pair $a=(\sigma ,p)\in {\{-1,1\}}^d\times P$, we denote by ${\mathscr{H}}_a$ the hyperplane $\sigma \cdot (x-p)=r$ and by ${\mathscr{H}}_a^{+}$ the halfspace $\sigma \cdot (x-p)\le r$. In general, $x\in {ℝ}^d$ is a feasible 1-center of $P$ if for every $p\in P$, ${\Vert x-p\Vert }_1\le r$. Assuming $r$ is known, we can write the LP formulation of the 1-center problem with $d$ variables $x=(x_1,\mathrm{\dots },x_d)$ and the $2^d|P|$ constraints $\sigma \cdot (x-p)\le r$ for every $\sigma \in {\{-1,1\}}^d$ and $p\in P$. That is, every constraint defines a hyperplane ${\mathscr{H}}_{(\sigma ,p)}$. We further remove from the set of constraints ${\{-1,1\}}^d\times P$, pairs $(\sigma ,p)$ for which $\overrightarrow{0}\notin {\mathscr{H}}_{(\sigma ,p)}$ and denote the updated set of constraint by $A=S\times P$. Note that no points from $P$ are removed in this process, as each has distance $r$ from $\overrightarrow{0}$. Since $\overrightarrow{0}$ is the unique optimal solution of $P$, this also does not change the set of feasible solutions, and $\overrightarrow{0}$ is the unique intersection point of all hyperplanes in $A$.

$(\Rightarrow ):$ Let $v\in {ℝ}^d\setminus \{\overrightarrow{0}\}$, then there exists $a\in A$ such that $v\notin {\mathscr{H}}_a^{+}$. That is, $\sigma \cdot (v-p)>r$ and since $\overrightarrow{0}\in {\mathscr{H}}_a$, $\sigma \cdot (\overrightarrow{0}-p)=r$, and it follows $\sigma \cdot v>0$.

$(\Leftarrow ):$ $A$ is non-empty so clearly $\overrightarrow{0}\in {\bigcap }_{a\in A}{\mathscr{H}}_a^{+}$. Let $v\ne \overrightarrow{0}$, then there exists $(\sigma ,p)\in A$ such that $\sigma \cdot v>0$. Since $\overrightarrow{0}\in {\mathscr{H}}_a$ we have $\sigma (\overrightarrow{0}-p)=r$, it follows that $\sigma (v-p)>r$, that is, $v\notin {\mathscr{H}}_a^{+}$. $◀$

We are now ready to prove our main Theorem:

By Proposition 3.6 the set $S$ is complete and by Corollary 3.5 there exists $R\subseteq S$ such that $R$ is complete and of size at most $2d$. For each $\sigma \in R$ we select a single point $p\in P$ such that the pair $(\sigma ,p)$ is a constraint in $A$. That is we obtain a set of at most $2d$ different points from $P$ we denote by $Q$ and denote by $A^{\prime }$ this refined set of constraints. Since $R$ is complete, using the second direction of Proposition 3.6 we have that ${\bigcap }_{a\in A^{\prime }}{\mathscr{H}}_a^{+}=\{\overrightarrow{0}\}$, meaning that $Q$ is a weak 0-coreset of size at most $2d$. $◀$

We conclude this section by providing an example of a set $P$ of size $2d$, where $P$ is the sole weak 0-coreset of itself, demonstrating that the upper bound of $2d$ cannot be further improved. The set $P$ is composed of the row vectors of the Hadamard matrix and their negations. The proof is provided in Appendix A.1.

Recall that Algorithm 1 shifts $P$ so that ${\sum }_{p\in P}p=\overrightarrow{0}$. This does not change the optimal value, hence our analysis simply assumes that the input $P$ already satisfies ${\sum }_{p\in P}p=\overrightarrow{0}$, avoiding cumbersome notations for before and after the shift. This property of $P$ yields the following immediate lower bound on $\mathrm{opt}(P)$.

For every point $p\in P$,

$◀$

We now wish to use $\widehat{W}$ from Algorithm 1 to construct a solution for the dual LP. Informally, the idea is to construct a solution $u^{\widehat{W}}$ (can also think of it as a vector with $2^{d}n$ coordinates), that is the average of $m$ sparse solutions, namely, each has a single non-zero variable, whose value is $1$ and it is drawn at random from the probability distribution defined by $u^{\ast }$ (think of $u^{\ast }$ as a vector with $2^{d}n$ coordinates that sum to $1$), using precisely the random draws made in Algorithm 1. Next, we formalize this construction in a slightly more general form.

Given a multiset $Z\subseteq {\{\pm 1\}}^d\times P$ of size $m$, such as $\widehat{W}$, we define the dual solution induced by $Z$, denoted $u^Z$, as follows. Take each pair $(\sigma ,p)\in Z$ and build a dual solution $u$, where the variable corresponding to this pair is set as $u_{\sigma ,p}=1$, and the other $2^{d}n-1$ variables are set to zero, and then we average all these $m$ solutions. Formally, $u^Z$ is given by

The following fact rewrites certain linear forms over $u^Z$, that appear in (DLP), in terms of pairs $(\sigma ,p)\in Z$.

Before building a feasible dual solution for (DLP) on $S$, we first consider an initial dual solution $\widehat{u}:=u^{\widehat{W}}$, which is just the solution induced by $\widehat{W}$ from Algorithm 1. We shall see below that $\widehat{u}$ is feasible in an expected sense, and that turning the expectation into a high-probability guarantee introduces an additive error in the constraints (and in the objective). Nonetheless, this is still useful as we will later “fix” this solution into one that does satisfy the constraints (without additive error).

Let us examine this initial random solution $\widehat{u}$. It always satisfies the second constraint of (DLP) by construction (recall that $\widehat{u}$ is the average of $m$ sparse solutions), i.e.,

By linearity of expectation, $\widehat{u}$ satisfies the first constraint in expectation (the middle term uses 4.4 to provide an alternate formulation),

And again by linearity of expectation, the expected objective of $\widehat{u}$ is the same as the optimal solution $u^{\ast }$, because:

We bound the deviation of $\widehat{u}$ from satisfying the first constraint, as follows. Consider $i\in [d]$ and let ${ℱ}_i$ be the event that $|{\sum }_{\sigma \in {\{\pm 1\}}^d}{\sum }_{p\in S}{\sigma }_i{\widehat{u}}_{\sigma ,p}|>ϵ$, which by 4.4 can be also written as $|\frac{1}{m}{\sum }_{(\sigma ,p)\in \widehat{W}}{\sigma }_i|>ϵ$. Informally, we want to bound the probability of this event, because when it does not occur, the constraint is “almost satisfied”. By applying Hoeffding’s inequality, where we use (5) for the expectation and the fact that $|{\sigma }_i|\le 1$, we get (by our choice of $m$),

We next use $\widehat{W}$ to construct a new multiset $W$ whose induced dual $u^W$ is feasible, and in particular satisfies the first constraint. We will then take our final dual solution to be $u:=u^W$, and it will remain to bound its objective value. At a high level, $W$ is obtained by “flipping” some of the signs appearing in $\widehat{W}$. More precisely, given $\widehat{W}=(({\widehat{\sigma }}^1,p^1),\mathrm{\dots },({\widehat{\sigma }}^m,p^m))$, we shall define new sign vectors ${\sigma }^1,\mathrm{\dots },{\sigma }^m$ but keep the exact same points $p^1,\mathrm{\dots },p^m\in P$, and construct $W=(({\sigma }^1,p^1),\mathrm{\dots },({\sigma }^m,p^m))$. It will be convenient to arrange the sign vectors ${\widehat{\sigma }}^1,\mathrm{\dots },{\widehat{\sigma }}^m$ as the rows of a matrix $\widehat{M}\in {\{\pm 1\}}^{m\times d}$, and use this $\widehat{M}$ to define a new matrix $M$, whose rows define the new sign vectors ${\sigma }^1,\mathrm{\dots },{\sigma }^m$.