Learning a Latent Simplex in Input Sparsity Time
Authors: Ainesh Bakshi
Chiranjib Bhattacharyya
Ravi Kannan
David Woodruff
Samson Zhou
Venue: ICLR 2021 Spotlight (2021)
Keywords: Latent Simplex
numerical linear algebra
low-rank approximation

Abstract: We consider the problem of learning a latent $k$-vertex simplex $K\in\mathbb{R}^d$, given $\mathbf{A}\in\mathbb{R}^{d\times n}$, which can be viewed as $n$ data points that are formed by randomly perturbing some latent points in $K$, possibly beyond $K$. A large class of latent variable models, such as adversarial clustering, mixed membership stochastic block models, and topic models can be cast in this view of learning a latent simplex. Bhattacharyya and Kannan (SODA 2020) give an algorithm for learning such a $k$-vertex latent simplex in time roughly $O(k\cdot\text{nnz}(\mathbf{A}))$, where $\text{nnz}(\mathbf{A})$ is the number of non-zeros in $\mathbf{A}$. We show that the dependence on $k$ in the running time is unnecessary given a natural assumption about the mass of the top $k$ singular values of $\mathbf{A}$, which holds in many of these applications. Further, we show this assumption is necessary, as otherwise an algorithm for learning a latent simplex would imply a better low rank approximation algorithm than what is known. 

We obtain a spectral low-rank approximation to $\mathbf{A}$ in input-sparsity time and show that the column space thus obtained has small $\sin\Theta$ (angular) distance to the right top-$k$ singular space of $\mathbf{A}$. Our algorithm then selects $k$ points in the low-rank  subspace with the largest inner product (in absolute value) with $k$ carefully chosen random vectors. By working in the low-rank subspace, we avoid reading the entire matrix in each iteration and thus circumvent the $\Theta(k\cdot\text{nnz}(\mathbf{A}))$ running time.

Published as a conference paper at ICLR 2021
LEARNING A LATENT SIMPLEX IN INPUT-SPARSITY TIME
Ainesh Bakshi
Chiranjib Bhattacharyya
Ravi Kannan
Carnegie Mellon University abakshi @ @ww@@ccccmmmm.... cmu.edu
Indian Institute of Science chiru @ iisccaccin
Microsoft Research India kannan @ microsoft.com
David Woodruff Carnegie Mellon University dwoodruf cmu.edu
Samson Zhou Carnegie Mellon University samsonzhou @ @gmail.com
ABSTRACT
We consider the problem of learning a latent k-vertex simplex C. R given access A E Rdxxn which can be viewed data matrix with points that are obtained by randomly perturbing latent points in the simplex K. (potentially beyond K.). A large class of latent variable models, such as adversarial clustering, mixed membership stochastic block models, and topic models can be cast as learning a latent simplex. Bhattacharyya and Kannan (SODA, 2020) give an algorithm for learning such a latent simplex in time roughly O(k (A)), where nnz(A) is the number of non-7eros in A. We show that the dependence on k in the running time is unnecessary given natural assumption about the mass of the top l singular values of A, which holds in many of these applications. Further, we show this assumption is necessary, otherwise an algorithm for learning a latent simplex would imply an algorithmic breakthrough for spectral low rank approximation.
At a high level, Bhattacharyya and Kannan provide an adaptive algorithm that makes k matrix-vector product queries to A and each query is function of all queries preceding it. Since each matrix-vectis product requires nnz(A) time, their overall running time appears unavoidable. Instead, approximation to A in input-sparsity time and show that the column space thus obtained has small sin @ (angular) distance to the right top-k singular space of A. Our algorithm then selects k points in the low-rank subspace with the largest inner product (in absolute value) with k carefully chosen random vectors. By working in the low-rank subspace, we avoid reading the entire matrix in each iteration and thus circumvent the (): nnz(A)) running time.
obtain low-rank
INTRODUCTION
We study the problem of learning & vertices M.,....,,NM Mc,k of a latent k-dimensional simplex AC in Rd using data points generated from IC and then possibly perturbed by stochastic, deterministic, or adversarial source before given the algorithm. In particular, the resulting points observed input data could be heavily perturbed so that the initial points may no longer be discernible or they could be outside the simplex K. Recent work BBhattacharyya & Kannan (2020) unifies several stochastic models for unsupervised learning problems, including k-means clustering, topic models (Bleil 2012). and mixed membership stochastic block models (Airoldi et al., (014)) under the problem of learning latent simplex. In general, identifying the latent simplex can be computationally intractable. However many special applications do not require the full generality. For example, in a mixture model like Gaussian mixtures, the data is assumed to be generated from convex combination of density functions. Thus, it may be possible to efficiently approximately learn the latent simplex given certain distributional properties in these models.
Indeed, [Bhattacharyya & Kannan (2020) showed that given certain reasonable geometric assumptions that are typically satisfied for real- world instances of Latent Dirichlet Allocation, Stochastic Block

---

Published as a conference paper at ICLR 2021
Models and Clustering, there exists Ö(k: (A)) time algorithm for recovering the vertices of the underlying simplex. We show that, given an additional natural assumption, we can remove the dependency & and obtain a true imput sparsity time algorithm. We begin by defining the model along with our new assumption:
Definition 1.1 (Latent Simplex Model), Let
M. E R denote the vertices of ... P=, Id be n points in the convex hull K. Given a > observe points A, 1: A. ... A.,, Rd such that ||A pll2 oyn. Further, make the following assumptions on the data generation process:
k-simplex, K. Let ,,,,, P.,
Well-Separateness. For all [k], M..e has non-trivial mass in the orthogonal complement of the span of the remaining vectors, i.e., for all E [k), [Proj(M,, Null(M \ M..e))] >
a max, M,, where Proj(2r, U' denotes the orthogonal projection of x to the subspace U.
Proximate Latent Points. For all & E [k)] there exists a set St C [n] such that |St] 2 8n and for all j E Se, | Px,fl22 222 - 40/8.
3. Spectrally Bounded Perturbation. The spectrum of A P is bounded, i.e., for sufficiently large constant c, o/vō S a² mine rlaa///k
4. Significant Singular Values. Let A = Eie(d) dinee be the singular value decomposition and let 0 < Φ < nnz(A)/(r) poly(k)). We assume that for all i E [k], > Φ ok+1 and |A A S o A Ax
These assumptions natural across many interesting applications: Section 2 for more details.
Bhattacharyya & Kannan 2020) introduced the Well-Separatennss (T.. Proximate Latent Points (2) and Spectrally Bounded Perturbation (3) assumptions. We include additional Significant Singular Values assumption (4). which is crucial for obtaining a faster running time; we discuss this in more detail below. Our main algorithmic result can then be stated follows:
Theorem 1.2 (Learning a Latent Simplex in Input-Sparsity Time). Given k 2 2 and A E Rdxx from the Latent Simplex Model (Definition 1.1g. there exists an algorithm that runs in Ô (nnz(A) + (n + d)poly(k/o)) ()) time to output subsets AR....., ARe such that upon permut- ing the columns of M, with probability at least 1 - 1/9(vK), for all e E [k]], we have ||RR, -M.ell2 I 300k*a/(av/5
Our result implies faster algorithms for various stochastic models that can formulated as special cases of the Latent Simplex Model, including Latent Dirichlet Allocation for Topic Modeling, Mixed Membership Stochastic Block Models and Adversarial Clustering. We summarize the connections to these applications below. We describe algorithm and provide an outline to analysis; we defer all formal proofs to the supplementary material.
CONNECTION TO STOCHASTIC MODELS
We first formalize the connection between the Latent Simplex Model and numerous stochastic models. In particular, we show that topic models like Latent Dirichlet Allocation (LDA) and Stochastic Block Models can be viewed as special cases of the Latent Simplex Model; we defer discussion on Adversarial Clustering the supplementary material.
2.1 TOPIC MODELS
Probabilistic Topic Models attempt to identify abstract topics in a collection of documents by discovering latent semantic structure (Blei & Jordan 2003 Blei & Lafferty 2006 Hoffman et al. 2010
Zhu Zhu et al., 2012) Blei 2012). Each document in the corpus is represented by bag-of-words vectorization with the corresponding word frequencies. The standard statistical assumption is that the generative process for the corpus is joint probability distribution over both the observed and hidden random variables. The hidden random variables can be interpreted as representative documents for each topic. The goal is to then design algorithms that can learn the underlying topics. The topics can
TThroughout the paper we the notation Ô to suppress poly-logarithmic factors.
2

---

Published as a conference paper at ICLR 2021
be viewed geometrically as k latent vectors M.,1. M..,....... M. E R where d is the size of the dictionary and M,, is the expected frequency of word in topic E. Since each vector M,, represents probability distribution, >; M = 1. Let M be the corresponding d x k matrix. One important stochastic model is Latent Dirichlet Allocation (LDA) (Blei et al. 2003). where each document consists of words is generated as follows:
For all & E [k). we pick topic weights W Dir(1/k), where (k) is the Dirichlet distribu- tion over the unit simplex. The topic distribution of document j decided by the topic weights, Wje and given by P-,- Eee[k] W j.e" M.,,, where P.. are latent points.
We then generate the j-th document with m words by taking i.i.d. samples from Mult(P-.j). the multinomial distribution with Px,y as the probability vector. The resulting document observed
is denoted by the vector A.g. where for all i E [d] A.,, = 1
m Σ X "s such that x
(g.), where x = if the i-th word was chosen in the t-th draw while generating the j-th document, and 0 otherwise.
The data generation process of LDA can be viewed as a special case of the Latent Simplex Model, where the j-th document is the data point A., generated from the stochastic vector P. p..j. j. a point in the simplex KC. The vertices of the simplex are the k topic vectors M.,,,... M.,x; the goal is then to recover the vertices of K.. We formally justify our assumptions below.
Lemma 2.1 (LDA as Latent Simplex). Given A, P. following the LDA model as described above, such that for all & E [k)] ||M,2 = 22(1), m, = [(poly(k/aa) and 5 ca / Vk, assumptions and (4) from Definition 1.1 are satisfied with high probability.
2.2 MIXED MEMBERSHIP STOCHASTIC BLOCK MODELS
The Stochastic Block Model (Airoldi et al. 2008: Miller al. 2009 Xing et al. 2010 Fu et al. 2009; Li et al. 2016: Fan et al. 2016) is a well-studied stochastic model for generating random graphs, where the vertices partitioned into k communities and edges within each community more likely to occur than edges across communities. Given communities C1, Cz.... Ck. there exists & symmetrie latent matrix B, where, B ,&2 the probability that there exists an edge between vertices in C₁, and Ct. The MMBM can be formalized as the following stochastic process:
For j E [n]. vertex j picks a probability vector Wa.j E IR* representing community membership probabilities that sum to i... Wij Dir(1/k) for all i i [k].
For all pairs (j1,12) E [n], vertex ji picks a community & proportional to Mult W ..jh and ja picks a community & proportional to Mult (i e.jz). The edge (ji,jz) included in the graph with probability .2 Since Σe, W Ji f2 Wigh/2 represents the edge probability of the edge (J1,f2), the latent variable matrix of edge probabilities can be represented as W BWT.
However, our reduction is not straightforward since now P depends quadratically on W and the only polynomial time algorithms for B directly rely on semidefinite programming. Further, they require non-degeneracy assumptions in order to compute a tensor decomposition provably in polynomial time (Anandkumar et al. 2014: Hopkins & Stcurer 2017). However, we can pose the problem of recovery of the underlying communities differently and first pick at random a subset V C [n] of vertices and represent the f-th community by d-dimensional vector that represents the probabilities of vertices in [n] \ Vi belonging to community E and having an edge with each of the vertices in V1. We now define W (1) to be k x d matrix representing the fractional membership of weights of vertices in Vi and W (2) to be the analogous k x n matrix for vertices in [n] V.. Observe that the probability matrix P can now be represented as WT BW(2). (2)-
The reduction to the Latent Simplex Model can now be stated as follows: given data matrix A which is the adjacency matrix of the community graph, and the latent variable matrix P. recover the simplex M WT. B. Further, (Airoldi et al. 2008) assumes that each column of W is picked from the Dirichlet distribution with parameter 7k. Combined with tools from random matrix theory (Vershynin 2010), (Bhattacharyya & Kannan 2020) (Lemma 7.2) shows that the Proximate Latent Points and Spectrally Bounded assumptions hold for Stochastic Block Models. As for the Significant Singular Values assumption, it is satisfied when is a small enough polynomial in k.
3

---

Published as a conference paper at ICLR 2021
Justifying Significant Singular Values. We give the following further justification for assump- tion (4) in the supplementary material: a faster algorithm using the assumptions from (Bhattacharyya & Kannan 2020) would imply algorithmic breakthrough for spectral low-rank approximation and partially resolve the first open question of (Woodrufi) 2014).
Theorem 2.2 (Spectral LRA and Learning Simplex (informal)). There exists a distribution over instances such that learning latent simplex in o o(nnz(A) k) time with good probability implies constant factor spectral low-rank approximation algorithm in the same running time.
ALGORITHM AND ANALYSIS
Preliminaries. We use n, d, and & to denote the number of data points, the number of dimensions of the space and the number of vertices of K respectively. We use the notation A.,j to denote the j-th column of matrix A. For A E Rd with rank r, its singular value decomposition, denoted by (V) = UEV", guarantees that is a d x r matrix with orthonormal columns, V is an X matrix with orthonormal rows and Σ is an X diagonal matrix. The diagonal entries of E are the singular values of A, denoted by 01 2 d2 2 2 or- Given an integer k S r, we define the truncated singular value decomposition of A that
out all but the top singular values of A, i.c., A = UΣg V where Σn has only k non-zero entries along the diagonal. It is well- that the truncated SVD computes the best rank-k approximation to A under the Frobenius norm, i.e. A = min X s ||A - X Given an orthonormal basis U for subspace, we use Pu UU to denote the projection matrix corresponding the subspace. We consider the following notion of subspace distance:
Definition 3.1 (sin θ Distance). For any two subspaces R, S of Rd, the sin θ distance between R and S is defined sin O(R, S) max min sin (u, v) max minl u|]-
R DES
m NER. nER.|uj=10E3
We use the notion of spectral low-rank approximation to obtain compact representation of the input and compute matrix- vector products efficiently. We also require the notion of mixed spectral- Frobenius low-rank approximation. This guarantee is weaker than spectral-low rank approximation but admits faster algorithms.
Definition 3.2 (Spectral Low-rank Approximation, Spectral-Frobenine Low-rank Approximation). Given matrix A, an integer & and >> 0, rank-k matrix B satisfies relative-error spectral low-rank approximation guarantee if AAA B < (1 +
A - Ax B satisfies a mixed spectral-Frobes Frobbenuus A 2 + &l l.
low-rank approximation guarantee if
A
B
[1 +1++c]ee A
3.1 OVERVIEW
In this section, we provide an overview of our algorithmic techniques and discuss the main challenges we overcome obtain an input-sparsity time algorithm.
Our Techniques. The starting point in Bhattacharyya & Kannan 2020) is that the smoothened polytope, obtained by averaging points in the data matrix is itself close to the latent points in the convex hull of IC in operator norm. This fact is captured by the following lemma:
Lemma 3.3 (Subset Smoothing). For any S C. [n], let As be a vector obtained by averaging the columns of indexed by S and define Pss similarly. Then for ||A Pll2 I ovnn, we have
||As - Psll2 & ////SS
Our main insight is that we can approximately optimize a linear function on the smoothed polytope by working with rank-k spectral approximation to A instead. Geometrically, this implies that while the smoothed polytope is perhaps d-dimensional, projecting onto the k-dimensional space spanned by the top-k singular values of the data matrix A suffices to recover the latent k-simplex, A. This is surprising since the data matrix can contain points significantly far from the latent polytope. Further, this approach presents several challenges: we do not have access to the left singular space of and even if we are provided this subspace exactly, is unclear why it spans a set of points that approximate vertices of K. Finally, the points obtained by smoothing the projected polytope have no immediate relation to points in the smoothed high-dimensional polytope considered by (Bhattacharyya & Kannan 2020).
4

---

Published as a conference paper at ICLR 2021
We would like begin by computing a spectral low-rank approximation (Definition 3.2) for A. Since a low-rank approximation to A can be represented factored form YZ", where is d x & and z" is k x n, any matrix-vecter product of the form YZ" only requires (n + d)k time. Thus optimizing a linear function k times over a smoothed low-rank polytope requires only (n + d)k² time, circumventing the previous bound of k nnz( A). However, the best known algorithm for spectral low-rank approximation (Theorem and thus provides no improvement. A natural direction to pursue is then to compute Frobenius low-rank approximation (which requires nnz time) for A and use this as our proxy. However, a Frobenius low-rank approximation is too coarse obtain subspace that is close to the top-k singular vectors of A.
(Mucco Musco 2015)) requires ((nzz() k/vE) time
Algorithm
I:
Learning Latent k-Simplex in Input Sparsity Time
Input: A matrix A E Rdxa, integer k; and
0.
1. Using the algorithm from Lemma 3.4, compute rank-k matrices Y, Z such that Yz" spectral low-rank approximation A, i... ||A YZ S (1 + c) A
2. Let S
{0}. For each E [k],
(a) Let U, be an orthonormal basis for the vectors in S.
(b) Compute the projection matrix P. U.U. that projects onto the row span of S.
(c) Let 9 ~~~~~ Ix) and let u, = Y P,) be a random vector R". Compute R2 C. [n], subset of ón indices corresponding to the largest coordinates of u, absolute value.
(d) Let AR, be the average of the columns of A indexed by R4- Update S = S.-
Output: The set of vectors AR, AR...... AR, as our approximation to the vertices of the latent k-simplex K.
Instead we compute mixed spectral-Frobente low-rank approximation (see Definition 3.2 that runs in (nnz(A) + dk.2) time, but the resulting eттоr guarantee is weaker. In particular, incurs an additive <| A / term. Here, we use the assumption we introduced (the Significant Singular Value assumption) to show that the low-rank matrix obtained from this algorithm also satisfies relative-error spectral low-rank approximation guarantee. The next challenge is that the aforementioned guarantee only bounds the spectral norm of A - YZ" in terms of the (A: + 1)-st singular value of A. This guarantee does not relate how close the subspaces spanned by the columns and rows of the low-rank approximation are to the top-k k singular space of A.
A key technical contribution of our work is thus to prove that the subspaces obtained via spectral low-rank approximation are close to the true left and right top-k singular space in angular (sin θ) distance. We note that such guarantee is crucial approximately optimize linear function over A. Further, this result provides an intriguing connection between spectral low-rank approximation and power iteration. is well known that power iteration suffices to obtain a subspace that is close to the top-k subspace of a matrix in sin θ distance, which at first glance appears much stronger than spectral low-rank approximation. However, our work implies that it suffices to compute spectral low-rank approximation, which provides a succinct representation of the data matrix and can be computed faster than power iteration in several natural settings.
In the context of learning the latent simplex, given a spectral low low-rank approximation, YZT we first restrict the column span of Y, which w.l.o.g. has orthonormal columns, and iteratively generate I vectors in this subspace. In the first iteration, we generate a random vector g Y and compute g Y' We then consider the largest ôn indices of g Yz""". While the resulting vector does not have strong provable guarantees, we show that averaging the columns of A corresponding to these indices results in a vector, AR,, which intuitively corresponds to efficiently optimizing a linear function over low-rank approximation to the smoothened polytope, where the smoothened polytope obtained by averaging over all subsets of on data points. Our next contribution is to show that AR. obtained by the aforementioned algorithmic process is indeed close a vertex of K.
5

---

Published as a conference paper at ICLR 2021
To obtain approximation to the remaining vertices of K., consider the following iterative process: in the t-th iteration, consider the subspace ('(I-P,) Pt), where (I- Pt) is the projection onto the orthogonal complement of the span of AR. AR. R.-.. Then generate random vector g Y Pt), and compute the largest ón coordinates of g (1- -I)
P.) Average the corresponding columns of A to obtain RR, and output this vector. We prove that after iterating ls times, the vectors AR, AR.,. AR, approximate all the vertices of the latent simplex K. within the desired accuracy and running time.
In contrast, prior work of (Bhattacharyya Kannan, 2020 uses power iteration approximate the left top-k singular space U₂ of using a subspace V that is poly(a/k) /k) close in sin θ distance. Each step of the power iteration uses ((nnz(A) dk2) time and is repeated log(d) times. Next, they pick random vector ij in the subspace spanned V and compute AR, s/) [4 As). using the resulting vector an approximation to some vertex M.,1-
They then repeat the above algorithm & times and in the i-th iteration, they pick u, to be a uniformly random direction in the k k dimensional subspace constructed as follows: let V be an orthonormal basis for AR, A AR.... Intuitively, this corresponds to sampling a random vector from the subspace orthogonal to the set of vertex approximations picked thus far. The resulting l vectors AR....., AR, are the approximation to the vertices of the latent simplex. Since they directly optimize over the smoothened polytope, the correctness analysis is more straightforward.
However, each iteration of the algorithm requires optimizing linear function over the smoothened polytope and in particular requires computing u, A, and thus, the overall running time is dominated by k (nz) Since the latent simplex satisfies the Well-Separateness condition, the inner product with random direction is maximized by unique vertex. Intuitively, it appears necessary project away from the set of vectors obtained up to the i-th iteration in order to learn new vertices of XC. The inherently iterative nature of the algorithm combined with matrix-vector product lower bounds indicates that the new algorithmic ideas we introduce are in fact necessary.
3.2 TECUNICAL DISCUSSION
In this section, we provide an outline of our proof. We defer the full proofs to the supplementary material. We start with spectral low-rank approximation for A. We then use the right factor as an approximation to Σn V and the left factor as an approximation to Uk.
Lemma 3.4. Haput-Sparsinn Spectral LRA (Cohen et al. 2015 2017).) Given a matrix E Rdxn 6 > O and k N, there exists an algorithm that outputs matrices Y, Z, such that with probability at least 1, 5, IA YZTI2 S (1 + e) Aul + & - A&ll in time
Ö Ö(nnz(A) A) (n + d)poly(k/eo)).
Under the Significant Singular Values condition setting c = o in Lemma 3.4 implies A& 2 I of
poly(k) with probability 99/100, 1 Σn Ei of (oly(k)
A
A
and thus A YZ S 2||A Axl Further, such matrix YZT can be computed in δ (nnz(A) + (n + d))ooy(k/o) time. Next, we show that if YZ" is a good rank k spectral approximation to A, then the subspace spanned by the columns of Y must be close to the column span of UR, the top-k left singular vectors of A. We begin by recalling Wedin's sin @ theorem that relates norms of projectors to angular distance:
Theorem 3.5 (sin theorem (Wedin 1972)). Let R. E dR and < m < l be integers. Let Rm, and So denote the subspaces spanned by the top singular vectors of R and top E singular vectors of S, respectively. Suppose 7 = a. (R) ( Then, sin ((R,,, Sat) R
We use the above theorem to bound the spectral norm of the projectors onto the relevant subspaces. Lemma 3.6 (Proximity of Subspace Projections). Let be defined as in Algorithm be the subspace spanned by the top k left singular vectors of A. Let Py and Pu. be the d x d projection matrices onto the row span of Y and Ug. Then P - -Puzl12 1000
2 Land let Uk
Proof Sketch. Suppose by way of contradiction that |PY - PUll2 TO This implies
|UUUT Y is large and thus | TT is bounded by k [1000k Intuitively,

---

Published as a conference paper at ICLR 2021
show that if the inner product term is small, lows: an upper bound on ||U, I suffices to obtain an upper bound on the the k-th singular value of Uu Y via averaging. This, in turn lower bounds || - Py 12 = |U YY"U" by (10008 oR (A), contradicting the Significant Singular Value assumption.
obtain lower bound ||A Py P 2|,, as fol-
Our analysis proceeds via induction on the number of iterations performed by the algorithm. Suppose our algorithm has selected points from our approximation of the top & subspace and these points are reasonably close to points of the k-simplex. In the (1 + 1)-st iteration, we again bound the sin θ distance between Y (I Pt). which corresponds to our approximation of the top subspace projected away from the selected vectors, and the actual k-simplex projected away from the corresponding points closest to our selected vectors. This argues that we can continue selecting random vectors in the subspace spanned by Y P.) as close approximation to random vectors in ((IM P,). We first bound the k-th singular values of the simplex vertices (M) and latent variables (P):
Lemma 3.7. (Bhattacharyya & Kannan 2020 If the underlying points M follow the Well-
Separateness and Spectrally Bounded Perturbations assumptions, then a (M) 2 1000 and
48
995k Vn 0.
O (P)
Next, we prove our lemma relating angular distance the subspace obtained in the i-th iteration of the algorithm (Y(I P.)) to the optimal subspace (M(I P.)).
Lemma 3.8 (Angular Distance between Subspaces.). For some E [k]. let M = M., M.,e, be the matrix with r columns corresponding vertices of the latent k-simplex M closest to the first T points selected by Algorithm ! AR.....,,Ag respectively. Sup- 300k
pose ||AR, -M.,,,l S
a V8 for each
[r]. Let P, be the projection matrix or-
thogonal AR...... AR. Then sin ① (Y PP),, (M) n Null(M)) S a/100k* and sin θ Span (M) O Nu))(M)) (I, - -P,) S a/100k*.
Proof Sketch. Let E (I. PITd-PAy PP) be a unit vector. It can be shown that using the sin O theorem and the hypothesis that there exists x Span (M) with ||x ylla S 500k3.3. Let z = MM be the component of x Null We can then bound ||x - z/|2 S ||x y11a + || (MMMM) -M 12) where A is the set of vectors selected thus far and A y = O. Combining the aforementioned observations, can bound ||x 2/12 by a² /5500/..5) k-1.ag / (avv /0r. (M)). We then observe that y E (L, - Pr) and z E Span (M) n (M), and appeal to Lemma 10.1 in Bhattacharyya & Kannan 2020 to yield sin θ (Y P.). Span (M) n Null(M) S a/100k4.
a²
To prove the second half of the claim, it suffices show that the dimension of is.) since Span (M) n (ull(M) has dimension k - and the sin θ distance symmetric between two subspaces of the same dimension. By construction Y has dimension A so that YL PP)) has dimension at least - r. Therefore, there exist vectors uI....; Ug-r+1 E Y - P,) and vectors Vi,..., Vk V E Span (M) n Null(M) such that |lu, valla < a/100k4, We can then upper and lower bound V. vol for all a of to conclude that VI....; Vk-r+1 are orthogonal, contradicting that Span (M) n Null(M) spans l dimensional space and the claim follows.
Now we need to show that our algorithm is (1) well-defined and (2) preserves the invariant that the (i + 1)-st point sampled from Y (I- will also be reasonably close some different point of the k-sipleex. We show the selected procedure is well-defined in Lemma 3.9 by arguing that there exists a unique solution to the maximization problem.
Lemma 3.9 (Optimization is Well-Defined), Let Rdd be a random unit vector in the space of (I- P,), where P, is the orthogonal projection to AR....., AR,- Then there exists a constant c > 0 so that with probability least c/k--
0.097 1. For all distinct a, b & (l1.-.., (.). then ju (Ma,a Mo,a)l >
kT max; |M,,ell
7

---

Published as a conference paper at ICLR 2021
2. For all & {fi....,ff) Cr). then Iu M.,ao
0.0989 |M,,ell-
max; k4
We then show that the algorithm preserves the aforementioned invariant by showing that the unique solution AR, cannot correspond one of the vertices of the k-simplex that have been found in the first i rounds, thus proving that we find solution AR. that corresponds to a new vertex of M. We then show AR, close to the new vertex of M. preserving the inductive hypothesis.
Lemma 3.10 (Recovery Guarantees). Let l--1 argmax, M.,e if u AR.+1 2 0 and be argming u M., otherwise. Then, ||AR,11 - MM,,, lla S 3000
Proof Sketch. We consider the case AR,+1 2 as the analysis for the case AR... 0 is symmetric. Let lx+1
argmax, M.,-- It can be shown that fx+1 & (f1...., 4, Thus applying Lemma 3.9 u M,,,+1 2 0.0989a max; ||M.,ell el/k. By the Proximate Latent Points assumption, there exists a set 1 of size on so that [Pa. - M.,t. ll2 S 4a for all j E tt,
v
so that |P 0,0e,11 -Ma,f .112 S y8 Then by Lemma 3.1 (Bhattacharyya & Kannan 2020
u As,o1,4: 2 u M,,,+ - 5 /8. Similarly, we can show u AR,., 2 u M.,.,,, - 80/V6.
Further, using Lemma 3.9 and the Spectrally Bounded Perturbation assumption, we obtain u M.,. S u M.-M 0.097a max; /l/////k This enables us to upper bound AR,,1 by u M.,f,+1 - 0.097a max, | 1 We, )/h:² + 40/v5. Combining the upper and lower bounds, straightforward computations yield the claim.
L
In contrast to (Bhattacharyya & Kannan 2020), we only need input sparsity time to compute the low-rank approximation to A. The subsequent & iterations of selecting points from Y (I P,) are computed in the low-dimensional space and use lower-order runtime. Hence, the dominating term in the final runtime is just the input sparsity time used to compute (I(I-P;))
4 EMPIRICAL EVALUATION
In this section, we describe a series of experiments that demonstrate the advantage of our algorithm. performed in Python 3.6.9 on an Intel Core 17-8700K 3.70 GHz CPU with 12 cores and 64GB DDR4 memory, using an Nvidia Geforce GTX 1080 Ti 1IGB GPU, on both synthetic and real-world data. Whereas previous work requires computing the top k subspace as a pre-processing step, our main improvement is that we only require a crude approximation. Thus we compared the running times for finding the top k subspace required by (Bhattacharyya & Kannan 2020) to finding mixed approximation using an input sparsity algorithm, as required by our algorithm. For the svds method from the sparse scipy linalg package optimized by LAPACK.
the former, For the latter, (Cohen et al. 2015: 2017) show that using a sparse CountSketch matrix (Clarkson & Woodruff 2013 Meng Mahoney| 2013 Nelson & Nguyen 2013). i.e., matrix with O(K2) columns and a single nonzero entry in each row that is in a random location and is a random sign, suffices obtain a mixed
guarantee; we evaluate such matrix with exactly k2 columns. Across all parameters and datasets, the input sparsity procedure used by our algorithm significantly outperforms the optimized power iteration methods required by (Bhattacharyya & Kannan 2020).
Synthetic Data. Since our theoretical results are most interesting when k < < n, we set 50000, d = 1000, A E {20, 50, 100} and generate random d matrix A that consists of independent entries that are each with probability p E { 500 2000 5006 1 1- p. Figure we report the average running time of both algorithms, among 5 independent runs for each choice of and k:
1 1 and 0 with probability
Social Networks. We also evaluate the algorithms on the ema 1 1-Eu-core network dataset of interactions across email data between individuals from large European research institution (Yin) ct al., 2017: Leskovec et al., 2007) and the com- Youtub: ube dataset of friendships on the Youtube social network (Yang & Leskovec 2015), both accessed through the Stanford Network Analysis Project (SNAP). In the former, there are n = d = 1005 nodes in the adjacency matrix over 25571 total edges, forming from which we extract a d x n matrix with n = 100000, d = 1000 to represent a bipartite graph, as described in both Section 2.2 and (Bhattacharyya & Kannan 2020). In Figure 4.2] we report the
42 communities. In the latter, there 1134890 nodes with 8385 communities,
8

---

Published as a conference paper at ICLR 2021
Mean Runtime Algorithms across Parameters
p 1/500
1/2000
p 1/5000
Top l Subspace, & 20
35.056s
29.725s
16.45s
Input Sparsity Approximation,
20
0.595s
0.329s
0.83s
Top & Subspace,
50
56. 1466
54.613s
53.213s
Input Sparsity Approximation,
50
0.658s
0.657s
0.434s
Top k Subspace, At = 100
78,420s
79,410s
71.424s
Input Sparsity Approximation,
100
0,501s
0.387s
0.440s
Figure 4.1: Mean runtime comparison of algorithms across parameters on synthetic data.
running time of both algorithms across each dataset among choices of & {20, 50, 1000. We observe that the resulting matrix has sparsity roughly 1000, which is consistent with p = and is much less than the sparsity parameters tested in our synthetic data.
emai Amail-Eu-core network
com-Youtube
Top Subspace, & = 20
0.387s
5.713s
Input Sparsity Approximation, h 20
0.005s
0.379s
Top Subspace, k 50
0.556s
16.711s
Input Sparsity Approximation. k = 50
0.003s
0.373s
Top l Subspace, k 100
1.281s
41,788s
Input Sparsity Approximation, 100
0.003s
0.366s
Figure 4.2: Mean runtime comparison of algorithms across parameters on real-world data.
Finally, consider a full end-to-end implementation comparing the runtime and least squares loss of the top subspace algorithm and our input sparsity approximation algorithm over various ranges of the parameter k and smoothening parameter ôn the com Youtube dataset, from which randomly extract an n x matrix, with n 20000 and d = 1000 to represent bipartite graph. Our results in Figure 4.3 show that our algorithm not only significantly outperforms the top & subspace algorithm in runtime, but also produces solutions with lower least squared loss.
Nandeal
Sianc
Namdow
Figure 4.3: Comparison of least squares loss by power iteration algorithm (in blue triangles) and by our algorithm (in red circles), over various ranges of the parameter with smoothening parameter ön = 10, and over various ranges of ōn with h = 20, on the com com-Youtube dataset. Also runtime comparison over range of k. with ön 10.
ACKNOWLEDGMENTSS
A.B., and D. W. were supported by the Office of Naval Research (ONR) grant 800014-18-1-2555 and the National Science Foundation (NSF) Grant No. CCF-1815840. D.W and S.Z were supported by National Institute of Health (NIH) grant 5RO1 HG 10798-2 and Simons Investigator Award.
REFERENCES
Edoardo M. Airoldi, David M. Blei, Stephen F. Fienberg, and Eric P. Xing. Mixed membership stochastic blockmodels. Mach. Learn. Res.,
June 2008. ISSN 1532-4435.
Edoardo M. Airoldi, David M. Blei, Elena A. Erosheva, and Stephen E, Fienberg, Introduction to mixed membership models and methods, 2014.

---

Published as a conference paper at ICLR 2021
Animashree Anandkumar, Rong Ge, Daniel J. Hsu, and Sham M. Kakade. A tensor approach to learning mixed membership community models. Journal of Machine Learning Research, 15(1): 2239-2312 2014.
Pranjal Awasthi. 598: Theoretical machine learning lecture notes, 2017. https: /wwp Cs
Futgers. edu/ (ttp://..ddddpp33/mm.m.mm (tt5:/mmmtt1111e111111111 pdf
Pranjal Awasthi and Or Sheffet. Improved specetralnccee bounds for clustering, CoRR, abs/1206.3204,
2012. UtL.ftttp:/arxx...crr////////
3204
Chiranjib Bhattacharyya and Ravindran Kannan. Finding a latent k-siple in O* (k nnz(data)) time via subset smoothing. In Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, pp. 122-140. SIAM, 2020.
David Blei, Andrew Ng, and Michael Jordan. Latent Dirichlet allocation. Journal of Machine Learning Research, 3:993-1022, 2003.
David M. Blei. Probabilistic topic models. Commun. ACM, 55(4):77-84, 2012.
David Blei and Michael Jordan. Modeling annotated data. In Proceedings of the 26th annual international ACM SIGIR conference on Research and development in informaion retrieval, pp. 127-134, 2003.
David M Blei and John D Lafferty. Dynamic topic models. In Proceedings of the 23rd international conference on Machine learning, pp. 113-120, 2006.
Moses Charikar, Jacob Steinhardt, and Gregory Valiant. Learning from untrusted data. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pp. 47-60, 2017.
Kenneth I. Clarkson and David Woodruff. Low rank approximation and regression in input sparsity time. In Proceedings of the forty-fifth annual ACM symposium on Theory of computing, pp. 81-90. ACM, 2013.
Michael B Cohen, Sam Elder, Cameron Musco, Christopher Musco, and Madalina Persu. Dimen- sionality reduction for k-means clustering and low rank approximation. In Proceedings of the forty-seventh annual ACM symposium on Theory of computing, pp. 163-172. ACM, 2015.
Michael B. Cohen, Cameron Musco, and Christopher Musco. Input sparsity time low-rank approxi- mation via ridge leverage score sampling. In Proceedings of the Twenty- Eiigtt-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira. Jamuary 16-19, pp. 1758-1777, 2017.
Ilias Diakonikolas, Daniel M Kane, and Alistair Stewart. List-decodable robust mean estimation and learning mixtures of spherical gaussians. In Proceedings of the 50th Annual ACM SIGACT Symposium Theory of Computing, pp. 1047-1060, 2018.
Xuhui Fan, Richard Yi Da Xu, and Longbing Cao. Copula mexee-mmmbershipp stochastic block model. In IJCAI International Joint Conference on Artificial Intelligence, 2016.
Wenjie Fu, Le Song, and Eric P Xing. Dynamic mixed membership blockmodel for evolving networks. In Proceedings of the 26th annual international conference on machine learning, pp. 329-336, 2009.
Matthew Hoffman, Francis R Bach, and David M Blei. Online learning for latent dirichlet allocation. In advances in neural information processing systems, pp. 856-864, 2010.
Samuel B. Hopkins and David Steurer. Efficient bayesian estimation from few samples: Community detection and related problems. In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pp. 379-390, 2017.
Amit Kumar and Ravindran Kannan. Clustering with spectral norm and the k-means algorithm. FOCS, 2010. URL hattp:://axxvvoor///aea
Jure Leskovec, Jon M. Kleinberg, and Christos Faloutsos. Graph evolution: Densification and shrinking diameters. ACM Trans. Knowl. Discov. Data 1(1):2, 2007.
10

---

Published as a conference paper at ICLR 2021
Wenzhe Li, Sungjin Ahn, and Max Welling. Scalable meme for mixed membership stochastic
blockmodels. In Artificial Intelligence and Statistics, pp. 723-731, 2016.
Allen Liu and Ankur Moitra. Efficiently learning mixtures of mallows models. In 2018 IEEE 59th Annual Symposium Foundations of Computer Science (FOCS), pp. 627-638. IEEE, 2018.
Tyler Lu and Craig Boutilier. Learning mallows models with pairwise preferences, 2011.
Xiangrui Meng and Michael Mahoney. Low-distortion subspace embeddings in input-sparsity time and applications to robust linear regression. In Proceedings of the forty-fifth annual ACM symposium on Theory of computing, pp. 91-100. ACM, 2013.
Kurt Miller, Michael Jordan, and Thomas L Griffiths. Nonparametric latent feature models for link prediction. In Advances neural information processing systems, pp. 1276-1284 2009.
Cameron Musco and Christopher Musco. Randomized block krylov methods for stronger and faster approximate singular value decomposition. In Advances in Neural Information Processing Systems, pp. 1396-1404, 2015.
Jelani Nelson and Huy L. Nguyen. OSNAP: faster numerical linear algebra algorithms via sparser subspace embeddings. In 54th Anmual IEEE Symposium Foundations of Computer Science, FOCS, pp. 117-126. IEEE Computer Society, 2013.
Arora Sanjeev and Ravi Kannan. Learning mixtures of arbitrary gaussians. In Proceedings of the thirty-third annual ACM symposium Theory of computing, pp. 247-257, 2001.
Santosh Vempala and Grant Wang. A spectral algorithm for learning mixture models. Journal of Computer and System Sciences, (8(4))841-860 2004.
Roman Vershynin. Introduction to the non-asymptotic analysis of random matrices. arXiv preprint arXiv:1011.3027, 2010.
Per-Ake Wedin. Perturbation bounds in connection with singular value decomposition. BIT Numerical Mathematics, 12(1):99-111, 1972.
David Woodruff. Sketching as tool for numerical linear algebra. Foundations and Trends in Theoretical Computer Science, (01-2))1-157, 2014.
Eric P Xing, Wenjie Fu, Le Song, et al. A state-space mixed membership blockmodel for dynamic network tomography. The Annals of Applied Statistics, 4(2))535-566, 2010.
Jaewon Yang and Jure Leskovec. Defining and evaluating network communities based on ground-truth. Knowl. Inf. Syst., 42(1):181-21) 2015.
Hao Yin, Austin R. Benson, Jure Leskovec, and David F. Gleich. Local higher- graph clustering. In Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 555-564 ACM, 2017.
Jun Zhu, Amr Ahmed, and Eric P Xing. Medlda: maximum margin supervised topic models. Journal of Machine Learning Research, 13(Aug):2237-2278, 2012.


Reviews:
[{"review_id": "sEHV6pX0kV3", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper considers the problem of learning a latent k-vertex simplex K, given a collection A of n points that are obtained by randomly perturbing latent points in the simplex. It improves the prior work [Bhattacharyya and Kannan, SODA 2020] by removing the multiplicative k factor in the running time given an (necessary) assumption about the mass of the top k singular values of A. Empirically, their algorithm is faster than the prior algorithm on both the synthetic and the real-world datasets. \n\nOverall, I vote for accepting. The work is tough and technically novel.\n\nPros:\n    1. The paper provides a detailed discussion on the application of their latent simplex model, which I really appreciate. These discussions make their additional assumption reasonable.\n    2. The paper provides a detailed discussion of the technical novelty. Specifically, the idea of obtaining a low-rank approximation to A introduces a small angular distance is interesting and accelerates the running time.\n\nCons:\n    1. The experimental results that your algorithm not only outperforms on the running time but also produces solutions with lower least squared loss are interesting. Could you give some explanation of this phenomenon?", "extra_scores": {}, "extra_text": {}}, {"review_id": "m4fKGR_TJix", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper considers the problem of learning/finding a simplex with k vertices in R^d from a set of points \"close\" to the simplex. That is, given a set of points A, and integer k, the goal is to find subsets R_1, ... , R_k of A such that the mean of R_i is close to the ith vertex of the underlying simplex. \n\nThis problem is considered by Bhattacharyya and Kannan (SODA 2020) and they gave an O(k nnz(A)) algorithm assuming that the data follows certain assumptions: 1) well-separateness, 2) proximate latent points, and 3) spectrally bounded perturbations.\n\nThe current paper adds an additional assumption of significant singular values and presents an O(nnz(A)) algorithm for this case. The paper argues that in some important machine learning applications (e.g., LDA), the newly introduced assumption holds. Moreover, they show that only considering the three assumptions of Bhattacharyya and Kannan, there does not exist an asymptotically faster algorithm than of Bhattacharyya and Kannan (unless there exists a constant factor spectral low-rank approximation algorithm in the same running time). Finally, the paper presents empirical evaluations on synthetic and real-world datasets and shows that the proposed method achieves a better running time and least square error compared to the prior method.\n\nThe paper is very well-written. It is very interesting that LDA and stochastic block models satisfy this assumption. Moreover, the analysis of the algorithm is novel and interesting. I am wondering if this method can be used for learning a general V-polytope. How could we change the assumptions so the algorithm would work for a V-polytope? and what would be the running time?\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "bpi8cR-_Buh", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 9, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This is a paper in theoretical computer science which considers what \nmany would consider a very hard problem -- learning a latent simplex lurking 'underneath' a cloud of data.\nIt is extremely well organized and tightly put together. \n\nIt patiently shows that this problem is lurking behind many different \nhigh-dimensional data analysis challenges, and then carefully lays the groundwork\nfor discussing a proposed algorithm and  its performance characteristics.\n\nWhat really surprised me about the paper was that the assumptions\ngoing to make up the 'math result' seemed to be quite stylized to me,\nin such a way that many datasets could never really satisfying them\n(although perhaps some could). Nevertheless, the authors present results on\nreal data which seem to suggest that the algorithm really can be used\nin empirical representation learning. This really surprises me,\nwhile putting forward positive results based on the authors' own\ninvented assumptions impresses me not so much.  So it would be interesting\nto hear from the authors, for example in a talk or in an eventual journal paper,\nto what extent the data actually obey the stated assumptions. If they\ndon'y obey the stated assumptions of this paper, then some less restrictive\nassumptions would be the 'sharp conditions'. In that case, what are the true \nconditions needed for the algorithm to work? \n\nObviously the significance this work will have in the eyes of potential users \ndepends a lot on the just-discussed  Q and A.\n\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: 
This paper considers the problem of learning a k-dimensional latent simplices given perturbations of data points in the simplex: this problem is of wide relevance in machine learning as it encompasses many latent variable models including Latent Dirichlet Allocation and Stochastic Block Models. It presents a modification of the recent algorithm of Bhattacharya & Kannan (SODA, 2020) which takes time O(k * nnz(A)), where A is the matrix of perturbed data points. The modified algorithm works with a low-dimensional sketch of the matrix A instead of A, and thereby avoids the dependence on k in the running time of the original algorithm, which used k passes over the data set. The main result of the paper is thus that the latent simplex problem can be solved in O(nnz(A)) time for instances of the problem that satisfy the "Spectrally Bounded Perturbation" property introduced by the authors.

The main questions of the reviewers concerned the question of whether the assumptions needed for the analysis of the novel algorithm to apply hold on real data sets. The authors point out that the assumptions may be stronger than are needed in practice, and suggest that the assumptions could be weakened to assuming that a spectrally-accurate sketch could be used--- this would increase the run-time dependence from just nnz(A), but weakens the assumptions needed. It was also observed that, in addition to a faster runtime, the method outperforms the benchmark method.

This paper should be accepted, due to its theoretical and practical contributions to the problem of latent simplex recovery: it presents an algorithm that provably runs in true input sparsity time given an amenable instance, and practically this algorithms performs well relative to the baseline, verifying the theoretical claims.
Decision: Accept (Spotlight)