Learning with Semi-Definite Programming: new statistical bounds based on fixed point analysis and excess risk curvature

Many statistical learning problems have recently been shown to be amenable to Semi-Definite Programming (SDP), with community detection and clustering in Gaussian mixture models as the most striking instances where SDP performs significantly better than other current approaches [60]. SDP is a class of convex optimisation problems generalising linear programming to linear problems over semi-definite matrices [94], [107], [21], and which proved an important tool in the computational approach to difficult challenges in automatic control, combinatorial optimisation, polynomial optimisation, data mining, high dimensional statistics and the numerical solution to partial differential equations. The goal of the present paper is to introduce a new fixed point approach to the statistical analysis of SDP-based estimators and illustrate our method on four current problems of interest, namely MAX-CUT, community detection, signed clustering, angular group synchronization. The rest of this section gives some historical background and presents the mathematical definition of SDP based estimators.

From a statistical point of view, the task remains to estimate in the most efficient way the oracle $Z^{*}$, and to that end $\hat{Z}$ is our candidate estimator. The point of view we will use to evaluate how far $\hat{Z}$ is from $Z^{*}$ is coming from the learning theory literature. We therefore see $\hat{Z}$ as an empirical risk minimization (ERM) procedure built on a single observation $A$, where the loss function is the linear one $Z\in{\cal C}\to\ell_{Z}(A)=-\bigl{<}A,Z\bigr{>}$, and the oracle $Z^{*}$ is indeed the one minimizing the risk function $Z\in{\cal C}\to\mathbb{E}\ell_{Z}(A)$ over ${\cal C}$. Having this setup in mind, we can use all the machinery developed in learning theory (see for instance [99, 63, 76, 97]) to obtain rates of convergence for the ERM (here $\hat{Z}$) toward the oracle (here $Z^{*}$).

There is one key quantity driving the rate of convergence of the ERM: a fixed point complexity parameter. This type of parameter carries all the statistical complexity of the problem, and even though it is usually easy to set up, its computation can be tedious since it requires to control, with large probability, the supremum of empirical processes indexed by “localized classes”. We now define this complexity fixed point related to the problem we are considering here.

Fixed point complexity parameters have been extensively used in learning theory since the introduction of the localization argument [76, 64, 97, 13]. When they can be computed, they are preferred to the (global) analysis developed by Chervonenkis and Vapnik [99] to study ERM, since the latter analysis always yields slower rates given that the Vapnik-Chervonenkis bound is a high probability bound on the non-localized empirical process $\sup_{Z\in{\cal C}}\bigl{<}A-\mathbb{E}A,Z-Z^{*}\bigr{>}$, which is an upper bound for $r^{*}(\Delta)$ since $\{Z\in{\cal C}:\bigl{<}{\mathbb{E}}A,Z^{*}-Z\bigr{>}\leq r\}\subset{\cal C}$. The gap between the two global and local analysis can be important since fast rates cannot be obtained using the VC approach, whereas the localization argument resulting in fixed points such as the one in Definition 1 may yield fast rates of convergence or even exact recovery results.

An example of a Vapnik-Chervonenkis’s type of analysis of SDP estimators can be found in [54] for the community detection problem. An improvement of the latter approach has been obtained in [41] thanks to a localization argument – even though it is not stated in these words (we elaborate more on the two approaches from [54, 41] in Section 3). Somehow, a fixed point such as (2.1) is a sharp way to measure the statistical performances of ERM estimators and in particular for the SDP estimators that we are considering here. They can even be proved to be optimal (in a minimax sense) when the noise $A-\mathbb{E}A$ is Gaussian [69] and under mild conditions on the structure of ${\cal C}$.

Before stating our general result, we first recall a definition of a minimal structural assumption on the constraint ${\cal C}$.

This is a pretty mild assumption satisfied, for instance, when ${\cal C}$ is convex, which is the setup we will always encounter in practical applications, given that SDP estimators are usually introduced after a “convex relaxation” argument. Our main general statistical bound on SDP estimators is as follows.

Theorem 1 applies to any type of setup where an oracle $Z^{*}$ is estimated by an estimator $\hat{Z}$ such as in (1.3). Its result shows that $\hat{Z}$ is almost a maximizer of the true objective function $Z\to\bigl{<}{\mathbb{E}}A,Z\bigr{>}$ over ${\cal C}$ up to $r^{*}(\Delta)$. In particular, when $r^{*}(\Delta)=0$, $\hat{Z}$ is exactly a maximizer such as $Z^{*}$ and, in that case, we can work with $\hat{Z}$ as if we were working with $Z^{*}$ without any loss.

Theorem 1 may be applied in many different settings; in the following, we study four such instances. We will apply Theorem 1 (or one of its corollary stated below) to some popular problems in the networks and graph signal processing literatures, namely, community detection [43] (we will mostly revisit the results in [54] and [41] from our perspective), signed clustering [32], group synchronization [90] and MAX-CUT.

The proof of Theorem 1 is straightforward (mostly because the loss function is linear). Its importance stems from the fact that it puts forward two important concepts originally introduced in Learning Theory, namely that the complexity of the problem comes from the one of the local subset ${\cal C}\cap\{Z:\bigl{<}\mathbb{E}A,Z^{*}-Z\bigr{>}\leq r^{*}(\Delta)\}$ and that the “radius” $r^{*}(\Delta)$ of the localization is solution of a fixed point equation. For a setup given by a random matrix $A$ and a constraint ${\cal C}$, we should try to understand how these two ideas apply to obtain estimation properties of SDP estimators such as $\hat{Z}$. That is to understand the shape of the local subsets ${\cal C}\cap\{Z:\bigl{<}\mathbb{E}A,Z^{*}-Z\bigr{>}\leq r\},r>0$ and the maximal oscillations of the empirical process $Z\to\bigl{<}A-\mathbb{E}A,Z-Z^{*}\bigr{>}$ indexed by these local subsets. We will consider this task in three distinct problem instances. We now provide a proof for Theorem 1.

Proof of Theorem 1. Denote $r^{*}=r^{*}(\Delta)$. Assume first that $r^{*}>0$ (the case $r^{*}=0$ is analyzed later). Let $\Omega^{*}$ be the event onto which for all $Z\in{\cal C}$ if $\bigl{<}\mathbb{E}A,Z^{*}-Z\bigr{>}\leq r^{*}$ then $\bigl{<}A-\mathbb{E}A,Z-Z^{*}\bigr{>}\leq(1/2)r^{*}$. By Definition of $r^{*}$, we have ${\mathbb{P}}[\Omega^{*}]\geq 1-\Delta$.

Let $Z\in{\cal C}$ be such that $\bigl{<}\mathbb{E}A,Z^{*}-Z\bigr{>}>r^{*}$ and define $Z^{\prime}$ such that $Z^{\prime}-Z^{*}=\left(r^{*}/\bigl{<}\mathbb{E}A,Z^{*}-Z\bigr{>}\right)(Z-Z^{*})$. We have $\bigl{<}\mathbb{E}A,Z^{*}-Z^{\prime}\bigr{>}=r^{*}$ and $Z^{\prime}\in{\cal C}$ because ${\cal C}$ is star-shaped in $Z^{*}$. Therefore, on the event $\Omega^{*}$, $\bigl{<}A-\mathbb{E}A,Z^{\prime}-Z^{*}\bigr{>}\leq(1/2)r^{*}$ and so $\bigl{<}A-\mathbb{E}A,Z-Z^{*}\bigr{>}\leq(1/2)\bigl{<}\mathbb{E}A,Z^{*}-Z\bigr{>}$. It therefore follows that on the event $\Omega^{*}$, if $Z\in{\cal C}$ is such that $\bigl{<}\mathbb{E}A,Z^{*}-Z\bigr{>}>r^{*}$ then

which implies that $\bigl{<}A,Z-Z^{*}\bigr{>}<0$ and therefore $Z$ does not maximize $Z\to\bigl{<}A,Z\bigr{>}$ over ${\cal C}$. As a consequence, we necessarily have $\bigl{<}\mathbb{E}A,Z^{*}-\hat{Z}\bigr{>}\leq r^{*}$ on the event $\Omega^{*}$ (which holds with probability at least $1-\Delta$).

Let us now assume that $r^{*}=0$. There exists a decreasing sequence $(r_{n})_{n}$ of positive real numbers tending to $r^{*}=0$ such that for all $n\geq 0$, ${\mathbb{P}}[\Omega_{n}]\geq 1-\Delta$ where $\Omega_{n}$ is the event $\Omega_{n}=\left\{\psi(r_{n})\leq\theta/2\right\}$ where for all $r>0$,

Since ${\cal C}$ is star-shapped in $Z^{*}$, $\psi$ is a non-increasing function and so $(\Omega_{n})_{n}$ is a decreasing sequence (i.e. $\Omega_{n+1}\subset\Omega_{n}$ for all $n\geq 0$). It follows that ${\mathbb{P}}[\cap_{n}\Omega_{n}]=\lim_{n}{\mathbb{P}}[\Omega_{n}]\geq 1-\Delta$. Let us now place ourselves on the event $\cap_{n}\Omega_{n}$. For all $n$, since $\Omega_{n}$ holds and $r_{n}>0$, we can use the same argument as in first case to conclude that $\bigl{<}\mathbb{E}A,Z^{*}-\hat{Z}\bigr{>}\leq r_{n}$. Since the latter inequality is true for all $n$ (on the event $\cap_{n}\Omega_{n}$) and $(r_{n})_{n}$ tends to zero, we conclude that $\bigl{<}\mathbb{E}A,Z^{*}-\hat{Z}\bigr{>}\leq 0=r^{*}$.  

The main conclusion of Theorem 1 is that all the information for the problem of estimating $Z^{*}$ via $\hat{Z}$ is contained in the fixed point $r^{*}(\Delta)$. We therefore have to compute or upper bound such a fixed point. This might be difficult in great generality but there are some tools that can help to find upper bounds on $r^{*}(\Delta)$.

A first approach is to understand the shape of the local sets ${\cal C}\cap\{Z:\bigl{<}\mathbb{E}A,Z^{*}-Z\bigr{>}\leq r\},r>0$ and to that end it is helpful to characterize the curvature of the excess risk $Z\to\bigl{<}\mathbb{E}A,Z^{*}-Z\bigr{>}$ around its maximizer $Z^{*}$. This type of local characterization of the excess risk is also a tool used in Learning theory that goes back to classical conditions such as the Margin assumption [96, 75] or the Bernstein condition [11]. The latter condition was initially introduced as an upper bound of the variance term by its expectation: for all $Z\in{\cal C},\;\mathbb{E}(\ell_{A}(Z)-\ell_{A}(Z^{*}))^{2}\leq c_{0}\mathbb{E}(\ell_{A}(Z)-\ell_{A}(Z^{*}))$ for some absolute constant $c_{0}$, but it has now been better understood as a way to discriminate the oracle from the other points in the model ${\cal C}$. These assumptions were global assumption in the sense that they concern all $Z$ in ${\cal C}$. It has been recently shown [26] that only the local curvature of the excess risk needs to be understood. We now introduce this tool in our setup.

We characterize the local curvature of the excess risk by some function $G:{\mathbb{R}}^{n\times n}\to{\mathbb{R}}$. Most of the time the $G$ function is a norm like the $\ell_{1}$-norm or a power of a norm such as the $\ell_{2}$ norm to the square. The radius defining the local subset onto which we need to understand the curvature of the excess risk is also solution of a fixed point equation:

The difference between the two fixed points $r^{*}(\Delta)$ and $r^{*}_{G}(\Delta)$ is that the local subsets are not defined using the same proximity function to the oracle $Z^{*}$; the first one uses the excess risk as a proximity function while the second one uses the $G$ function as a proximity function. The $G$ function should play the role of a simple description of the curvature of the excess risk function locally around $Z^{*}$; that is formalized in the next assumption.

Typical examples of curvature function $G$ will have the form $G(Z^{*}-Z)=\theta\left\|Z^{*}-Z\right\|^{\kappa}$ for some $\kappa\geq 1$, $\theta>0$ and some norm $\left\|\cdot\right\|$. In that case, the parameter $\kappa$ was initially called the margin parameter [95, 75]. Even though the relation given in Assumption 1 has been typically referred to as a margin condition or Bernstein condition in the learning theory literature, we will rather call it a local curvature assumption, following [54] and [26], since this type of relation describes the behavior of the risk function locally around its oracle. The main advantage for finding a local curvature function $G$ is that $r^{*}_{G}(\Delta)$ should be easier to compute than $r^{*}(\Delta)$ and $r^{*}(\Delta)\leq r^{*}_{G}(\Delta)$ because of the definition of $r_{G}^{*}(\Delta)$ and $\{Z\in{\cal C}:\bigl{<}\mathbb{E}A,Z^{*}-Z\bigr{>}\leq r_{G}^{*}(\Delta)\}\subset\{Z\in{\cal C}:G(Z^{*}-Z)\leq r_{G}^{*}(\Delta)\}$ (thanks to Assumption 1). We can therefore state the following corollary.

When it is possible to describe the local curvature of the excess risk around its oracle by some $G$ function and when some estimate of $r^{*}_{G}(\Delta)$ can be obtained, Corollary 1 applies and estimation results of $Z^{*}$ by $\hat{Z}$ (w.r.t. to both the ”excess risk” metric $\bigl{<}\mathbb{E}A,Z^{*}-\hat{Z}\bigr{>}$ and the $G$ metric) follow. If not, either because understanding the local curvature of the excess risk or the computation of $r^{*}_{G}(\Delta)$ is difficult, it is still possible to apply Theorem 1 with the global VC approach which boils down to simply upper bound the fixed point $r^{*}(\Delta)$ used in Theorem 1 by a global parameter that is a complexity measure of the entire set ${\cal C}$:

Interestingly, if the latter last resort approach is used then, following the approach form [54], Grothendieck’s inequality [51, 85] appears to be a powerful tool to upper bound the right-hand side of (2.3) in the case of the community detection problem such as in [53] as well as in the MAX-CUT problem. Of course, when it is possible to avoid this ultimate global approach one has to do it because the local approach will always provide better results.

Finally, proving a “local curvature” property such as in Assumption 1 may be difficult because it requires to understand the shape of the local subsets ${\cal C}\cap\{Z:\bigl{<}\mathbb{E}A,Z^{*}-Z\bigr{>}\leq r\},r>0$. It is however possible to simplify this assumption if getting estimation results of $Z^{*}$ only w.r.t. the $G$ function (and not necessarily an upper bound on the excess risk $\bigl{<}\mathbb{E}A,Z^{*}-\hat{Z}\bigr{>}$) is enough. In that case, Assumption 1 may be replaced by the following one.

Assumption 2 assumes a curvature of the excess risk function in a $G$ neighborhood of $Z^{*}$ unlike Assumption 1 which grants this curvature in an “ excess risk neighborhood”. The shape of a neighborhood defined by the $G$ function may be easier to understand (for instance when $G$ is a norm, a neighborhood defined by $G$ is the ball of a norm centered at $Z^{*}$ with radius $r_{G}^{*}(\Delta)$). In general, the latter assumption and Assumption 1 do not compare. If Assumption 2 holds then $\hat{Z}$ can estimate $Z^{*}$ w.r.t. the $G$ function.

Proof of Theorem 2. Let $r^{*}=r^{*}_{G}(\Delta)$. First assume that $r^{*}>0$. Let $Z\in{\cal C}$ be such that $G(Z^{*}-Z)>r^{*}$. Let $f:\lambda\in[0,1]\to G(\lambda(Z^{*}-Z))$. We have $f(0)=G(0)=0$, $f(1)=G(Z^{*}-Z)>r^{*}$ and $f$ is continuous. Therefore, there exists $\lambda_{0}\in(0,1)$ such that $f(\lambda_{0})=r^{*}$. We let $Z^{\prime}$ be such that $Z^{\prime}-Z^{*}=\lambda_{0}(Z-Z^{*})$. Since ${\cal C}$ is star-shapped in $Z^{*}$ and $\lambda_{0}\in[0,1]$ we have $Z^{\prime}\in{\cal C}$. Moreover, $G(Z^{*}-Z^{\prime})=r^{*}$. As a consequence, on the event $\Omega^{*}$ such that for all $Z\in{\cal C}$ if $G(Z^{*}-Z)\leq r^{*}$ then $\bigl{<}A-{\mathbb{E}}A,Z-Z^{*}\bigr{>}\leq(1/2)r^{*}$, we have $\bigl{<}A-{\mathbb{E}}A,Z^{\prime}-Z^{*}\bigr{>}\leq(1/2)r^{*}$. The latter and Assumption 2 imply that, on $\Omega^{*}$,

and so $\bigl{<}A,Z^{\prime}-Z^{*}\bigr{>}\leq-r^{*}/2$. Finally, using the definition of $Z^{\prime}$, we obtain

In particular, $Z$ cannot be a maximizer of $Z\to\bigl{<}A,Z\bigr{>}$ over ${\cal C}$ and so necessarily, on the event $\Omega^{*}$, $G(Z^{*}-\hat{Z})\leq r^{*}$.

Let us now consider the case where $r^{*}=0$. Using the same approach as in the proof of Theorem 1, we only have to check that the function

is non-increasing. Let $0<r_{1}<r_{2}$. W.l.o.g. we may assume that there exists some $Z_{2}\in{\cal C}$ such that $G(Z^{*}-Z_{2})\leq r_{2}$ and $\psi(r_{2})=\bigl{<}A-\mathbb{E}A,Z_{2}-Z^{*}\bigr{>}/r_{2}$. If $G(Z^{*}-Z_{2})\leq r_{1}$ then $\psi(r_{2})\leq(r_{1}/r_{2})\psi(r_{1})\leq\psi(r_{1})$. If $G(Z^{*}-Z_{2})>r_{1}$ then there exists $\lambda_{0}\in(0,1)$ such that for $Z_{1}=Z^{*}+\lambda_{0}(Z_{2}-Z^{*})$ we have $G(Z^{*}-Z_{1})=r_{1}$ and $Z_{1}\in{\cal C}$. Moreover, $r_{1}=G(\lambda_{0}(Z^{*}-Z_{2}))\leq\lambda_{0}G(Z^{*}-Z_{2})\leq\lambda_{0}r_{2}$ and so $\lambda_{0}\geq r_{1}/r_{2}$. It follows that

where we used that $\psi(r)>0$ for all $r>0$ because $Z^{*}\in\{Z\in{\cal C}:G(Z^{*}-Z)\leq r\}$ for all $r>0$.  

As a consequence, Theorem 1, Corollary 1 and Theorem 2 are the three tools at our disposal to study the performance of SDP estimators depending on the deepness of understanding we have on the problem. The best approach is given by Theorem 1 when it is possible to compute efficiently the complexity fixed point $r^{*}(\Delta)$. If the latter approach is too complicated (likely because understanding the geometry of the local subset ${\cal C}\cap\{Z:\bigl{<}{\mathbb{E}}A,Z^{*}-Z\bigr{>}\leq r\},r>0$ may be difficult) then one may resort to find a curvature function $G$ of the excess risk locally around $Z^{*}$. In that case, both Corollary 1 and Theorem 2 may apply depending on the hardness to find a local curvature function $G$ on an “excess risk neighborhood” (see Assumption 1) or a “$G$-neighborhood” (see Assumption 2). Finally, if no local approach can be handled (likely because describing the curvature of the excess risk in any neighborhood of $Z^{*}$ or controlling the maximal oscillations of the empirical process $Z\to\bigl{<}{\mathbb{E}}A-A,Z^{*}-Z\bigr{>}$ locally are too difficult) then one may resort ultimately to a global approach which follows from Theorem 1 as explained in (2.3). In the following, we will use these tools for various problems.

Results like Theorem 1, Corollary 1 and Theorem 2 appeared in many papers on ERM in learning theory such as in [64, 11, 76, 69]. In all these results, typical loss functions such as the quadratic or logistic loss functions were not linear one such as the one we are using here. From that point of view our problem is easier and this can be seen by the simplicity to prove our three general results from this section. What is much more complicated here than in other more classical problems in Learning Theory is the computation of the fixed point because 1) the stochastic processes $Z\to\bigl{<}A-{\mathbb{E}}A,Z-Z^{*}\bigr{>}$ may be far from being a Gaussian process if the noise matrix $A-{\mathbb{E}}A$ is complicated and 2) the local sets $\{Z\in{\cal C}:\bigl{<}\mathbb{E}A,Z^{*}-Z\bigr{>}\leq r\}$ or $\{Z\in{\cal C}:G(Z^{*}-Z)\leq r\}$ for $r>0$ maybe very hard to describe in a simple way. Fortunately, we will rely on several previous papers such as [41] to solve such problems.

The rapid growth of social networks on the Internet has lead many statisticians and computer scientists to focus their research on data coming from graphs. One important topic that has attracted particular interest during the last decades is that of community detection [43, 86], where the goal is to recover mesoscopic structures in a network, the so-called called communities. A community consists of group of nodes that are relatively densely connected to each other, but sparsely connected to other dense groups present within the network. The motivation for this line of work stems not only from the fact that finding communities in a network is an interesting and challenging problem of its own as it leads to understanding structural properties of networks, but community detection is also used as a data pre-processing step for other statistical inference tasks on large graphs, as it facilitates parallelization and allows one to distribute time consuming processes on several smaller subgraphs (i.e., the extracted communities).

One challenging aspect of the community detection problem arises in the setting of sparse graphs. Many of the existing algorithms, which enjoy theoretical guarantees, do so in the relatively dense regime for the edge sampling probability, where the expected average degree is of the order $\Theta(\log n)$. The problem becomes challenging in very sparse graphs with bounded average degree. To this end, Guédon and Vershynin proposed a semidefinite relaxation for a discrete optimization problem [54], an instance of which encompasses the community detection problem, and showed that it can recover a solution with any given relative accuracy even in the setting of very sparse graphs with average degree of order $O(1)$.

A subset of the existing literature for community detection and clustering relies on spectral methods, which consider the adjacency matrix associated to a graph, and employ its eigenvalues, and especially eigenvectors, in the analysis process or to propose efficient algorithms to solve the task at hand. Along these lines, Can et al. [68] proposed a general framework for optimizing a general function of the graph adjacency matrix over discrete label assignments by projecting onto a low-dimensional subspace spanned by vectors that approximate the top eigenvectors of the expected adjacency matrix. The authors consider the problem of community detection with $k=2$ communities, which they frame as an instance of their proposed framework, combined with a regularization step that shifts each entry in the adjacency matrix by a small constant $\tau$, which renders their methodology applicable in the sparse regime as well.

In the remainder of this section, we focus on the community detection problem on random graphs under the general stochastic block model. We will mostly revisit the work in [54] and [41] from the perspective given by Theorem 1, which simplifies the proof in [41] since the peeling argument is no longer required, and neither is the upper bound from [54] unlike [41], thanks to the homogeneity argument hidden in Theorem 1 (which underlies the localization argument).

We first recall the definition of the generalized stochastic block model (SBM). We consider a set of vertices $V=\{1,\cdots,n\}$, and assume it is partitioned into $K$ communities ${\cal C}_{1},\cdots,{\cal C}_{K}$ of arbitrary sizes $|{\cal C}_{1}|=l_{1},\cdots,|{\cal C}_{K}|=l_{K}$.

For each pair $(i,j)$ of nodes from $V$, we draw an edge between $i$ and $j$ with a fixed probability $p_{ij}$ independently from the other edges. We assume that there exist numbers $p$ and $q$ satisfying $0<q<p<1$, such that

We denote by $A=(A_{i,j})_{1\leq i,j,\leq n}$ the observed symmetric adjacency matrix, such that, for all $1\leq i\leq j\leq n$, $A_{ij}$ is distributed according to a Bernoulli of parameter $p_{ij}$. The community structure of such a graph is captured by the membership matrix $\bar{Z}\in\mathbb{R}^{n\times n}$, defined by $\bar{Z}_{ij}=1$ if $i\sim j$, and $\bar{Z}_{ij}=0$ otherwise. The main goal in community detection is to reconstruct $\bar{Z}$ from the observation $A$.

Spectral methods for community detection are very popular in the literature [54, 41, 100, 15, 29]. There are many ways to introduce such methods, one of which being via convex relaxations of certain graph cut problems aiming to minimize a modularity function such as the RatioCut [80]. Such relaxations often lead to SDP estimators, such as those introduced in Section 1.

Considering a random graph distributed according to the generalized stochastic block model, and its associated adjacency matrix $A$ (i.e. $A=A^{\top}$ and $A_{ij}\sim{\rm Bern}(p_{ij})$ for $1\leq i\leq j\leq n$ and $p_{ij}$ as defined in (3.1)), we will estimate its membership matrix $\bar{Z}$ via the following SDP estimator

where $\mathcal{C}=\{Z\in\mathbb{R}^{n\times n},Z\succeq 0,Z\geq 0,{\rm diag}(Z)\preceq I_{n},\sum_{i,j=1}^{n}Z_{ij}\leq\lambda\}$ and $\lambda=\sum_{i,j=1}^{n}\bar{Z}_{ij}=\sum_{k=1}^{K}|\mathcal{C}_{k}|^{2}$ denotes the number of nonzero elements in the membership matrix $\bar{Z}$. The motivation for this approach stems from the fact that the membership matrix $\bar{Z}$ is actually the oracle, i.e., $Z^{*}=\bar{Z}$ (see Lemma 7.1 in [54] or Lemma 1 below), where

Following the strategy from Theorem 1 and from our point of view, the upper bound on $r^{*}(\Delta)$ from [54] is the one that is based on the global approach – that is, without localization. Indeed, [54] uses the observation that, for all $r>0$, it holds true that

where $\left\|\cdot\right\|_{{\rm cut}}$ is the cut-norm¹¹1The cut-norm $\left\|\cdot\right\|_{{\rm cut}}$ of a real matrix $A=(a_{ij})_{i\in R,j\in C}$ with a set of rows indexed by $R$ and a set of columns indexed by $C$, is the maximum, over all $I\subset R$ and $J\subset C$, of the quantity $|\sum_{i\in I,j\in J}a_{ij}|$. It is also the operator norm of $A$ from $\ell_{\infty}$ to $\ell_{1}$ and the “injective norm” in the orginal Grothendieck “résumé” [52, 85] and $K_{G}$ is the Grothendieck constant (Grothendieck’s inequality is used in (b), see [85, 100]). Therefore, the localization around the oracle $Z^{*}$ by the excess risk “band” $B^{*}_{r}:=\{Z:\bigl{<}\mathbb{E}A,Z^{*}-Z\bigr{>}\leq r\}$ is simply removed in inequality (a). As a consequence, the resulting statistical bound is based on the complexity of the entire class ${\cal C}$ whereas, in a localized approach, only the complexity of ${\cal C}\cap B^{*}_{r}$ matters. Next step in the proof of [54] is a high probability upper bound on $\left\|A-{\mathbb{E}}A\right\|_{\mathrm{cut}}$ which follows from Bernstein’s inequality and a union bound since one has $\left\|A-{\mathbb{E}}A\right\|_{\mathrm{cut}}=\max_{x,y\in\{-1,1\}^{n}}\bigl{<}A-{\mathbb{E}}A,xy^{\top}\bigr{>}$, then for all $t>0$, $\left\|A-\mathbb{E}A\right\|_{\mathrm{cut}}\leq tn(n-1)/2$ with probability at least $1-\exp\left(2n\log 2-(n(n-1)t^{2})/(16\bar{p}+8t/3)\right)$ where $\bar{p}\overset{def}{=}2/[n(n-1)]\sum_{i<j}p_{ij}(1-p_{ij})$. The resulting upper bound on the fixed point obtained in [54] is,

Finally, under the assumption of Theorem 1 in [54] (i.e., for some some $\epsilon\in(0,1)$, $n\geq 5.10^{4}/\epsilon^{2}$, $\max(p(1-p),q(1-q))\geq 20/n$, $p=a/n>b/n=q$ and $(a-b)^{2}\geq 2.10^{4}\epsilon^{-2}(a+b)$), for $\Delta=e^{3}5^{-n}$ we obtain (using the general result in Theorem 1) with probability at least $1-\Delta$, the bound $\bigl{<}\mathbb{E}A,Z^{*}-\hat{Z}\bigr{>}\leq r^{*}(\Delta)\leq\epsilon n^{2}=\epsilon\left\|Z^{*}\right\|_{2}^{2}$, which is the result from Theorem 1 in [54]. Finally, [54] uses a (global) curvature property of the excess risk in its Lemma 7.2:

Therefore, a (global– that is for all $Z\in{\cal C}$) curvature assumption holds for a $G$ function which is here the $\ell_{1}^{n\times n}$ norm, a margin parameter $\kappa=1$ and $\theta=(p-q)/2$ for the community detection problem. However this curvature property is not use to compute a “better” fixed point parameter but only to have a $\ell_{1}^{n\times n}$ estimation bound since

The latter bound together with the sin-Theta theorem allow the authors from [54] to obtain estimation bound for the community membership vector $x^{*}$.

The approach from [41] improves upon the one in [54] because it uses a localization argument: the curvature property of the excess risk function from Lemma 1 is used to improve the upper bound in (3.3) obtained following a global approach. Indeed, the authors from [41] obtain high probability upper bound on the quantity

depending on $r$. This yields to exact reconstruction result in the “dense” case and exponentially decaying rates of convergence in the “sparse” case. This is a typical example where the localization argument shows its advantage upon the global approach. The price to pay is usually a more technical proof for the local approach compare with the global one. However, the argument from [41] also uses an unnecessary peeling argument together with an unnecessary a priori upper bound on $\left\|\hat{Z}-Z^{*}\right\|_{1}$ (which is actually the one from [54]). It appears that this peeling argument and this a priori upper bound on $\left\|\hat{Z}-Z^{*}\right\|_{1}$ can be avoided thanks to our approach from Theorem 1. This improves the probability estimate and simplifies the proofs (since the result from [54] is not required anymore neither is the peeling argument). For the sign clustering problem we consider below as an application of our main results, we will mostly adapt the probabilistic tools from [41] (in the “dense” case) to the methodology associated with Theorem 1 (without this two unnecessary arguments).