Contrastive Moments: Unsupervised Halfspace Learning in Polynomial Time
Authors: Xinyuan Cao
Santosh Vempala
Venue: NeurIPS 2023 poster (2023)
Keywords: Unsupervised Learning
Learning Halfspaces
Non-Gaussian Component analysis
TL;DR: Learning margin Halfspaces without labels!

Abstract: We give a polynomial-time algorithm for learning high-dimensional halfspaces with margins in $d$-dimensional space to within desired Total Variation (TV) distance when the ambient distribution is an unknown affine transformation of the $d$-fold product of an (unknown) symmetric one-dimensional logconcave distribution, and the halfspace is introduced by deleting at least an $\epsilon$ fraction of the data in one of the component distributions. Notably, our algorithm does not need labels and establishes the unique (and efficient) identifiability of the hidden halfspace under this distributional assumption.  The sample and time complexity of the algorithm are polynomial in the dimension and $1/\epsilon$. The algorithm uses only the first two moments of *suitable re-weightings* of the empirical distribution, which we call *contrastive moments*; its analysis uses classical facts about generalized Dirichlet polynomials and relies crucially on a new monotonicity property of the moment ratio of truncations of logconcave distributions. Such algorithms, based only on first and second moments were suggested in earlier work, but hitherto eluded rigorous guarantees.

Prior work addressed the special case when the underlying distribution is Gaussian via Non-Gaussian Component Analysis. We improve on this by providing polytime guarantees based on TV distance, in place of existing moment-bound guarantees that can be super-polynomial. Our work is also the first to go beyond Gaussians in this setting.

Contrastive Moments: Unsupervised Halfspace Learning in Polynomial Time
Xinyuan Cao Georgia Tech xcao780gatech.co edu
Santosh S. Vempala Georgia Tech vempala@gatech. edu
Abstract
We give polynomial-tmne algorithm for learning high-dimensional halfspaces with margins in d-dimensional space to within desired Total Variation (TV) distance when the ambient distribution is an unknown affine transformation of the d-fold product of an (unknown) symmetric one-dimensional logconcave distribution, and the halfspace is introduced by deleting at least an fraction of the data in one the component distributions. Notably, our algorithm does not need labels and establishes the unique (and efficient) identifiability of the hidden halfspace under this distributional assumption. The sample and time complexity of the algorithm are polynomial in the dimension and l/c. The algorithm uses only the first two moments suitable re-weightings of the empirical distribution, which we call contrastive moments; its analysis uses classical facts about generalized Dirichlet polynomials and relies crucially on a new monotonicity property of the moment ratio of truncations of logconcave distributions. Such algorithms, based only on first and second moments were suggested in earlier work, but hitherto eluded rigorous guarantees.
Prior work addressed the special case when the underlying distribution is Gaussian via Gaussian Component Analysis. We improve on this by providing polytime guarantees based on TV distance, in place of existing moment-bound guarantees that can be super-polynomial. Our work is also the first to go beyond Gaussians in this setting.
Introduction
Suppose points in Rd are labeled according to linear threshold function (a halfspace). Learning threshold function from labeled examples is the archetypal well-solved problem learning theory, in both the PAC and mistake-bound models; its study has led to efficient algorithms, range of powerful techniques and many interesting learning paradigms. While the sample complexity in general grows with the dimension, when the halfspace has margin, the complexity can instead be bounded in terms of the reciprocal the squared margin width (PCST99, SBS +00, AV06, LS11J. The problem is also very interesting for special classes of distributions, e.g., when the underlying distribution is logconcave, agnostic learning is possible [KKMS08], and active learning needs fewer samples compared to the general case [BBL06].
The main motivation for our work learning a halfspace with margin with no labels, i.e., unsupervised learning of halfspaces. This is, of course, impossible in general - there could be multiple halfspaces with margins consistent with the data - raising the question: Can there be natural distributional assumptions that allow the unsupervised learning of halfspaces? For example, suppose data drawn from a Gaussian in &d with points in an unknown band removed, i.c., we assume there exists unit vector E IR and interval [a, bj that the input distribution is the Gaussian restricted to the set {z E Rd (u, z) < or (u, x)) 2 b). Can the vector be efficiently essentially unique,
learned? Such a distributional assumption ensures that the band normal leaving open the question of whether it can be efficiently learned.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Such models have been considered in the literature, notably for Non- -on-Gausiian Component Analysis (NGCA) [BKS 06, TV TV18]. learning relevant subspaces [Blu94, VX11] and low-dimensional convex concepts [Vem 10] where data comes from product distribution with all components being Gaussian except for one (or a small number). It is assumed that the non-Gaussian component differs from Gaussian in some low moment and the goal is to identify this component. Another related model Independent Component Analysis (ICA) where the input consists of samples from an affine transformation of product distribution and the goal is to identify the transformation itself [Com94, Car98, GVX14, JK3 For this problem to be well-defined, it is important that at most one component of the product distribution is Gaussian. No such assumption is needed for NGCA the more general problem we consider here.
Formally. we consider the following model and problem, illustrated in Figure 1.1.
Definition 1 (Affine Product Distribution with e-Margin). Let q be a symmetric one-dimensional
isotropic logconcave density function. Let be the d-fold product distribution obtained from q. Let be the isotropized density obtained after restricting q to R Ra, bj where u((-o0, al) 2 e, (, b)) 2 and ([b, x)) 2 Let P be the product of one copy of q and d - 1 copies of q. Let P be obtained by full-rank affine transformation of P: we refer P as Affine Product Distribution with e-Margin. Let be the unit vector normal to the margin before transformation.
p(x)
p(x)
Affine Transformation
u x
uxx
(a) Symmetric and asymmetric margin aa b). We use contrastive covariance and mean respectively.
(b) Definition with uniform P is full-rank affine transformation of from P. The goal is learn the normal vector
(c) Unlabeled data is drawn
the product distribution P.
Figure 1.1: Affine Product Distribution with Margin.
With this model in hand, we have the following algorithmic problem.
Problem. Given input parameters c, 5 > O and access to iid samples from Р. an affine product distribution with e-margin, the learning problem is compute unit vector à that approximates to within TV distance 6. That is, the TV distance between the corresponding P and P is at most 8, where P is the distribution with margin normal to
In this formulation of the problem with a TV distance guarantee, each side of the halfspace receives a different label, then the probability that the output halfspace of the data disagrees with the true label (up to swapping the labels) is at most 8.
natural approach to identifying the halfspace is maximum margin clustering [XNLS04]: find a partition of the data into two subsets s.t. the distance between the two subsets along some direction is maximized. Unfortunately, this optimization problem is NP-hard, even to approximate.
There at least two major difficulties we have to address. The first is the unknown affine transformation, which we cannot hope to completely identify in general. The second is that, even reversed the transformation, the halfspace normal is in an arbitrary direction in R and would be undetectable almost all low oin-eineniional projections, i.e., we have a needle in a haystack problem.
1.1 Results and Techniques
We give an efficient algorithm for the unsupervised halfspace learning problem under any symmetric product logconeave distribution. It consists of the following three high-level steps.
(1) Make the data isotropic (mean zero and covariance matrix identity).
(2) Re-weight data and compute the re-weighted mean ias and the top eigenvector v of the re- weighted covariance.
(3) Project data along the vectors i., and output the vector with the largest margin.

---

Although the algorithm is simple and intuitive, its analysis has to overcome substantial challenges. Our main result the following. The formal version (Theorem 7) is in the Appendix.
Theorem 1 (Main). There is algorithm that learn any affine product distribution with c-margin to within TV distance 5 with time and sample complexity that are polynomial in d, 1/c and 1/6 with high probability.
To see the idea of the algorithm, we first consider the case when no affine transformation is applied. In this case. we detect the direction by calculating the empirical mean and top eigenvector of the empirical uncentered covariance matrix. If the margin (a, bj lies on one side of the origin, the mean along is nonzero while the mean in any other direction that is orthogonal to is zero. Thus the mean itself reveals the vector u. Otherwise, we can show that the second moment along is higher than along any other orthogonal direction. Thus, there is positive gap between the top two eigenvalues of the uncentered covariance matrix and the top eigenvector is u. In fact, the algorithm applies more generally, the product distribution created from one-dimensional bounded isoperimetric distributions. A one-dimensional distribution p is isoperimetric if there exists constant gi > 0 such that for any x E R. p(x) 2 Ab min(p([ x)), ((oo0, xi)) }. The theorem is stated as follows. The formal version (Theorem 6), algorithm and proofs are included in the Appendix.
Theorem 2 (Isotropic Isoperimetric Distribution). There is algorithm that can learn any isotropic isoperimetric bounded product distribution with e-margin to within TV distance â with time and sample complexity that are polynomial in d, 1/e, 1/8 with high probability.
In the general case, when an unknown affine transformation is applied, the algorithm first computes the empirical mean and covariance of the sample and makes the empirical distribution isotropic. Then we will consider two cases as illustrated in Figure 1. If the unknown band is not centered around the mean along u, can expect the empirical mean to differ from the mean of the underlying product distribution without the margin. Consequently, if we knew the latter, we can use the difference to estimate u. However, in general, exists a re-weighting of the sample so that re-weighted empirical mean compared to the unweighted empirical mean is good estimate of In other words. with appropriate re- weighting, the mean shifts along the normal direction to the unknown band. On the other hand, if the band is centered along u. the mean shift will be zero. In this scenario, we will show that the maximum eigenvector of a re-weighted covariance matrix is nearly parallel to u!
do not have this information. Instead, we demonstrate that there
Our algorithm only uses first and second order moments, can be implemented efficiently, and is in fact practical (see Section 5). The main challenges are (1) proving the existence of band-revealing re-weightings and (b) showing that a polynomial-sized sample (and polynomial time) suffice.
To prove the main theorem, we will show that either the re-weighted mean induces contrastive gap (Lemma 1), or the eigenvalues of the re-weighted covariance matrix induce a contrastive gap (Lemma 2). In the subsequent two lemmas, we adopt the notation from Definition 1. Here, P represents a product distribution with e-margin defined by the interval (a, b] (before transformation).
Lemma (Contrastive Mean). If la + bl > O, then for any two distinct nonzero 01, 02 E R. least one of the corresponding re- re-weighted means is nonzero, i.e.
1x
ealllil T~P
T x0) 0.
max
EE x
u
x
E
O. such that (1) there is a positive gap between the top two eigenvalues of the re-weighted uncentered covariance matrix = Ex- =|| (xxT) That is, >1 (E) > A²(E.) (2) The top eigenvector of Σ. is u.
Lemma 2 (Contrastive Covariance). If + O, then there exists
The proof of Lemma uses Descartes' rule of signs applied to a suitable potential function. To prove Lemma 2, we develop a new monotonicity property of the moment ratio (defined as the ratio of the variance of x and the squared mean of x²2) for truncations of logconcave distributions. The moment ratio is essentially the square the coefficient of variation X². An insight from the monotonicity of the moment ratio is that for logconcave distributions with positive support, when the distribution is restricted to an interval away from the origin, needs a smaller sample size to estimate its second moment accurately. We state the lemma as follows.
3

---

Lemma 3 (Monotonicity of Moment Ratio). Let q be logconcave distribution in one dimension with nonnegative support. For any 2 let qi be the distribution obtained by restricting q to [t. oo).
Then the moment ratio of 9, defined as mr,(() == vate, (X2)
is strictly decreasing with t.
(Egz x
To obtain polynomial guarantees, we will need quantitative estimates of the inequalities in the above two lemmas. Establishing such quantitative bounds is the bulk of the technical contribution of this paper. While our focus is on proving polynomial bounds, whose existence a priori is far from clear, we did not optimize the polynomial bounds themselves; our experimental results suggest that in fact the dependence on both and 1/c might be linear!
1.2 Related Work
Efficient algorithms for supervised halfspace learning [Ros58, MP69], combined with the kernel trick [CST*00, 00, HDO++8), serve as the foundation much learning theory. Halfspaces with margin are also well-studied, due to their motivation from the brain, attribute-effiiien learning [Va198, Blu90], random projection based learning [AV06], and turn out to have sample complexity that grows inverse polynomially with the margin, independent of the ambient dimension. When examples are drawn from a unit Euclidean ball in Rd and the halfspace has margin ", then the sample complexity grows O(1 //²) regardless of the dimension. This leads to the question of whether labels are necessary, or the halfspace can be identified from unlabeled samples efficiently - the focus of the present paper.
The model of unsupervised learning we study similar to other classical models in the literature, notably Independent Component Analysis where input data consists of iid samples from unknown affine transformation of a product distribution. There, the goal is to recover the affine transformation under minimal assumptions. Known polynomial-time algorithms rely on directional moments, and the assumption that component distributions differ from a Gaussian in some small moment. A related relevant problem, Non-Gaussian Component Analysis (NGCA), aims to extract hidden non-Gaussian direction in a high-ding high-dimensional distribution. Here too, the main idea is the fact that non-Gaussian component must have some finite moment different from that of a Gaussian. While finite moment difference implies a TV distance lower bound, to get c-TV distance, one might need ([log(1/e)) even for logconcave densities. As the dependence on
to use k'th moments for the moment number is exponential (even for the sample complexity), this approach does not yield polytime algorithms in terms of TV distance, the natural notion for classification.
The idea of applying Principal component analysis (PCA) to re-weighted samples was used in [B8 to unravel mixture of well-separated Gaussians. For a mixture of two general Gaussians that are mean separated, after making the mixture isotropic, it was shown that either the mean or top eigenvector of the covariance of a re- weighted sample reveals the vector of the mean differences. This high-level approach was used for solving general ICA by estimating re-weighted higher moments (tensors) [GVX14]. Higher moment re- weighhtinggs were also used by [VX11] give an algorithm for factoring a distribution and learning "subspace juntas", ,, functions of an unknown low-dimensional subspace, and by [TV18] to give a more efficient algorithm for the special case of NGCA. The question of whether expensive higher moment algorithms could be replaced by re-weighted second moments natural and one variant was specifically suggested by [TV18] for NGCA. Our work validates this intuition with rigorous polynomial-tie time algorithms.
Algorithm
Our algorithm first makes the data to be isotropic using the sample mean and sample covariance. Then we apply the weight w(y, ar) = ea livl to each isotropized sample y. and compute the re-weighted mean and the top eigenvector of the re-weighted covariance matrix. Then for each candidate normal vector, project the data to it, and scan to find the maximum gap. The algorithm outputs the vector with the maximal gap among all candidate vectors. We give the formal description in Algorithm I.
3 Analysis
We demonstrate that Algorithm operates within polynomial time and sample complexity. The details regarding sample complexity are presented in Theorem 1. The time complexity is justified by

---

Algorithm Unsupervised Halfspace Learning with Contrastive Moments
Input: Unlabeled data = {x(1), x
C Rd e, > 0.
(Isotropize) Compute the sample mean and covariance:
N Σ
(x0) -)) - -2)
i
N
Make the data isotropic: y (-1/2(2((1) (.).
(Re-weighted Moments) Set a1 - a2 -2 /d and ag -C3E2. Let w(y a:) glll" Compute the re-weighted sample means Pas Paz using ar, ar and the re-weighted sample covariance using ag as follows:
N
Pl. E w(y az)y((, for i {1,2) and Σ
1
(3)
N
Compute the top eigenvector of Σ.
(Max Margin) Calculate the max margin (i.e., maximum gap) of the one-dimensional projections of the data along the vectors Pay Pag v and let be the vector among these with the largest margin.
return à.
the algorithm's process: it calculates the re-weighted sample mean and the top eigenvector of the re-weighted sample covariance matrix, both of which require polynomial time.
In our algorithm, we consider two cases depending on whether the removed band [a, b] is origin- symmetric. If it is asymmetric, the correct direction by showing that the re- re-weighted mean along u has gap from zero while the re- re-weighted mean along all other orthogonal directions is zero. We state the positive gap quantitatively in Lemma 4. Otherwise, if the band symmetric, we will show a positive gap between the top two eigenvalues of the re-weighted covariance matrix, and the top eigenvector corresponds w. We quantify the gap between the top two eigenvalues in Lemma 5. In the algorithm, since we know neither the underlying distribution mean the location of the removed band, have compute both re- re-weighted means and re-weighted covariance, and then get the correct direction among all three candidate vectors by calculating the margin and finding the one with the largest margin.
will show that one of the re- reighteh means with two gives us
Lemma 4 (Quantitative Gap of Contrastive Mean). Suppose that la bl 2 é.. Then, for on -C16 // /d, 0:2 = - A2 /2//d. /d, the re-weighted mean of P, denoted as Pa, and Hag satisfies
159
max (Iu Mas I / (ozz)
forr some constant C O,
d²
Vvlu, u. Pay = Hag 0.
Lemma (Quantitative Spectral Gap of Contrastive Covariance). Suppose that |a + bl < è. Choose
03 -czé² for some constant e3 O. Then, for an absolute constant C, the top two eigenvalues
A 2 X2 of the corresponding re-weighted covariance of P satisfy
A - 2 Ce
4 Proofs
Recall that we are given data zz (1))
(N) drawn from the affine product distribution with
margin P. Algorithm I first makes the data isotropic. Denote (1),.... ,y(2), as the corresponding isotropicized data. Then each y is an independent and identically distributed variable drawn from
P = q 3 8 ... q. Since we compute the re- eeweeghteed moments on y() in the algorithm, we analyze the moments of P directly.
5

---

Recall in Definition 1 that is the symmetric one one-dimensional isotropic logconcave density function, and q is the density obtained by restricting q R2,aa, for some unknown
Denote μl, as the mean and variance of q. q is the density obtained after making / isotropic, with support R RRaaa, 1/, where a' -_ Ø1
الا We denote the standard basis of Id by {ei,-.. e.a) and assume wlog that e is the (unknown) normal vector the band. We write æi (I,ex) x's i-th coordinate. We assume in our proof that [b] > |a|- If this condition is not met, we can redefine our interval by setting a' 6 and b' a. The proof can then be applied considering the distribution is restricted to {æ E _ u S a' or 2 J. For vector E IR we use || to denote its la norm. For matrix A E mmxx we denote operator norm as Allopp
Contrastive Mean. We can write the contrastive mean as a linear combination of exponential functions of a. By Descartes' rule of signs, the number of zeros of this function is at most two. Since = is one root and corresponds to mean zero, there is at most one nonzero root. And thus we have that for any distinct nonzero a's, at least one of them achieves nonzero contrastive mean.
a'
a' 0
4(x)
400
20-3
1
-a'
6'
Coefficient of eas" in Fa)) In the proof of Lemma 1, by combining ea terms, we flip ((x) horizontally. For a' >> O, the coefficient is negative when (a', (a',b) and non-negative outside the interval. For a' & 0, it is negative when x E (-a',b) b') and positive when x > b.
Figure 4.1:
Theorem 3 (Descartes' Rule of Signs in the Integral Form). Let F(a) So a(z)ear dr. Then the number of roots of F(x)= 0 is at most the number of sign changes in a(x) for x O.
Proof of Lemma
(Contrastive Mean). [b] > |a| implies that μ41 < For any x 2 0, we have
019(101 + p1) ((x)
2 σ19( =001
20 + +111
1(-x).
1 1- Sa g(x) dx
- S ((x) dr
Since P is product distribution, we have
E
31
= E
e
asi
II
E e
ax?
ming
1=2
We denote
F(a)
E a
caz?
xQ(2)) dx
(4.1)
z~4
Then rearrange F(a) by combining an as in Figure 4.1. If a' < O, we rewrite F(a) as
/b'
zq( ()==)) dr + / x x(((x) - 9( (((=)))e dx
F(a) = F(a)=
We treat F(a:) as the integral of ax)) for x > -a' Since ((x) - ÿ( -(-x))= > 0 for x > b' we have a(x)) > 0 for x E [-a', --a'(/) I/) and a(x: < for x > V. In other words, for increasing x, the sign of a(z) only changes once. By Theorem 3, F(a) 0 has at most root.

---

If a > O, we arrange F(a) in the same way and get
F(a)= F(a)= =(((x) d( ((=r))e dx - [ xū(( (x)6 a0? dr / x(ğ(a) (( ((-x)))e dr
Similarly, we treat F(a) as the integral of a(z)e for x 2 O. For increasing the sign of a(x) changes twice. By Descartes' rule of signs, F(a) has most two roots. In addition, know F(O) E =1 = 0 by definition of P. which implies that a = 0 is one root of F(a)) So there is at
one nonzero root of F(o:). In other words, for any distinct nonzero on, 02, least of ((aa),F(as)) is nonzero. Consequently,
) 0. x1
max
E x>P
E zup
Proof Idea of Lemma 4 (Quantitative Gap of Contrastive Mean). To get quantitative bound on the contrastive mean, we follow the same idea of bounding the number roots of F(a)) as in Lemma 1. By taking the derivative of F(a). we can show that either F0()) # 0 or (0) * O. Then by Taylor expansion, we can choose two distinct a's (near zero) so that one of the corresponding contrastive means is bounded away from zero.
Moment Ratio and Contrastive Covariance. To prove Lemma 2, we develop a new monotonicity property of the moment ratio of logconcave distributions. Moment ratio is specifically defined as the ratio of the fourth moment to the square of the second moment of truncated versions of the distribution. This measurement essentially reflects the uncentered kurtosis of the distribution. We will prove the monotonicity of the moment ratio by reducing the case of general logconcave distributions to exponential distributions.
Proof of Lemma 3 (Moment Ratio). We show the monotonicity of moment ratio by showing its derivative with respect i is negative. Define Mt = Je (²)(x)) dr. By calculation, the derivative of moment ratio is proportional to (t), where (t) is defined follows:
(t) (2) Ma(t) 21 (a())
Let hxx) = BeB---e - be exponential function (B,y y 0) such that
Mo(1) No(1), M2(() N2((), where N&(1) 100 x x²1(x)) (1 E.
Then have
f. (h(a) (h(x)-((x)) dx dx= = =0, I. x -((()))(()))
q(x))
intersects with the graph of q at exactly two points u' < v, where O. Also we have h(x) < q(x) at the interval [u', v] and h(z) q(x) outside the interval. Let u = ma n'}. J. So for x 2 0, (x u)(x= -v) v) has the same sign as h(z) q(x). Since 2 0, we have
By the logconcavity of g, the graph
f.a( (a² 1 (h)()) -(x)) 20
20
Expanding the terms and we get
q(x))) 2 (u² + 02) f. 2h(x) ((x)) dx 1200 J.² (h(z) g(z)) -0
x (h(z))q(z))
(u²+
This shows that NN(t) > Mt).). To show that H() we consider two cases.
Firstly if M2(t) 21 2 0, we have
H (t) e' Mo()) + +M((0)(M2(( - 2t²) 0.
7

---

Secondly if M2(t) - 2t < O, by calculation of the exponential function's moments, we have
t N2 > - (N2(1)(22()) -2(²)
This implies that (!) e' ()))) + (M2 (()))))))))))))) 2 (M2(1) - (M) 2
The equality holds if and only if (4(() = N2(()) > 0. Then we have
H(t t
- 2t 0.
< 0, Vt 2 0, which implies that the moment ratio of is strictly Combining both cases, mr (t) (t) decreasing with respect to t.
Proof Idea of Lemma 2 (Constrastive Covariance). View the spectral gap of the re-weighted covariance, denoted as x (2) - (22) as a function S(a). By calculation, S(0) = 0 and (0) is proportional to mr, (b) - (r, which is negative by the monotonicity property of moment ratio. Then we can prove the spectral gap for the chosen using Taylor expansion.
Proof Idea of Lemma 5 (Quantitative Gap of Contrastive Covariance). We first prove the case when a = -b, and then extend the result to the eear-symmetric case when |a + bj < E by comparing the re- weigggtte second moments of two distributions created by restricting to R [a, b) and R [2)[[bb1 b, respectively.
The following theorem enables us bound the sample complexity estimate the covariance matrix. Lemma (Covariance Estimation [SV13]). Consider independent isotropic random vectors X in Rd s.f. for some C, for every orthogonal projection P in Rdd,
1- P(IIPXI|| t) S Ct Ct-1-1 for t 1> Crank(P):
Let c E 1). Then with the sample size N Odde (222/1)) we have
E | Slop S <<|>illop.
The following classical theorem will allow us to use the eigenvalue gap to identify the relevant vector. Lemma 7 (Davis-Katie Kahan [DK70]). Let S and I'' be symmetric matrices with the same dimensions. For a fixed i, assume that the largest eigenvalue of S is well separated from the second largest eigenvalue of S, i.3.6 > S. (1) A² > 8. Then for the top eigenvectors of S and T, we have
sin (() (S), (T)) 2 Tloop
8
Proof Sketch Main Theorem. We prove the theorem by considering whether the removed band Ja, b) is symmetric or not. If la bj 2 éτ, by Lemma 4, for the chosen two as, at least one of the contrastive means μı along u direction is bounded away from zero (by poly(1/d, (1/d,e)) e)) and the projection of the contrastive mean along any direction orthogonal to u is zero by symmetry. So by Chebyshev's Inequality, we will ensure that the angle between u and fı: less than 8 with high probability using (poly(d, 1/e, 1/8)) samples. On the other hand, if la bl < c., we rely the contrastive covariance. By Lemma 5, the top eigenvector v aligns with u while the top two eigenvalues A1 >> A satisfy Å A2 poly(e). By Lemma 7, we can upper bound the angle between u and v by the quotient of the operator norm of the difference of the contrastive covariance and sample contrastive covariance and the spectral gap \1 X2- The covariance matrix itself can be estimated to desired accuracy efficiently with (ppoyydd, 1/8)) samples by Lemma 6. This ensures the closeness of u and top eigenvector and hence TV-distance guarantee. The formal statement of the theorem and the proofs are included in the Appendix.
Experiments
While our primary goal is to establish polynomial bounds on the sample and time complexity, our algorithms are natural and easy to implement. We study the efficiency and performance of Algorithm I on data drawn from affine product distributions with margin. Here we consider three special cases of logconeave distribution: Gaussian, uniform in an interval and exponential. We include four experiments. In all results, we measure the performance of the algorithm using the sin of the angle between the true normal vector u and the predicted vector û, i.e., sin 0(u, u), which bounds the TV distance between the underlying distribution and the predicted one after isotropic transformation. Experimental results strongly suggest that the sample complexity a small polynomial, perhaps even just nearly linear in both the dimension and the separation parameter
8

---

Overall Performance. Here we conduct the experiments based on grid search of (a, b) pairs on three special cases of logconcave distribution: Gaussian, uniform in an interval and exponential. We measure the performance of (a, b) pairs, where for each pair of (a, b). we conduct five independent trials. For Gaussian and exponential distribution, we choose -3 S a b S and for uniform distribution, we choose 1.5 Σ a < b S 1.5. Here we set the dimension d = 10 and sample size N = 1000000. For the parameters, we choose 0i = 03 = 0.1, 02 = -0.2. See Figure 5.1 as the heatmap of sin (u, û) given different pairs of (a, b).
Although in Algorithm show that larger constant values also work empirically, leading to much smaller sample complexity. This coincides with our qualitative lemmas (Lemma Lemma 2).
use extremely small values the weight parameter a, our experiments
The algorithm performs well as seen in the results, except when a and are both close to the edge, and thus there is almost mass easiest to learn, while the exponential is the hardest among these three distributions. As shown in all three plots, the algorithm performs the best when and are near symmetric with origin. In other words, contrastive covariance has better sample complexity than contrastive mean when we fix other hyperparameters. This coincides with our sample complexity bounds in the proof of Theorem
side of the band. Also, the uniform distribution is the
227
3.33
0.30
3.5
0.75
005
43
0.15
006
0.3
0.45
09
15
155
1.05
0.07
2.
1.35
27
0.00
0.00
0.00
(a) Gaussian
(b) Uniform
(c) Exponential
Figure 5.1: The performance of Algorithm with varying (a, b).
Performance of Contrastive Mean and Covariance. In this experiment, fix negative the left endpoint of the removed band, and measure the performance of both contrastive mean and contrastive covariance with respect to different margin right endpoint b. As shown in Figure 5.2, contrastive mean performs well except when + is close to zero, while contrastive covariance performs well only when b is close the two cases. In addition, our algorithm chooses the best normal vector among candidates from both contrastive mean and covariance. So our algorithm achieves good performance (minimum of contrastive mean and covariance curves).
This coincides with algorithm and analysis for
Specifically, choose -2, b [.9. 4] for Gaussian and exponential cases, and -0.5, b [-0.4, 0.9] for uniform case. We choose the dimension = 10, the sample size = 2000000. We choose a 0:3 -0.1, 02 -0.2. We average the result with 50 independent trials.
2.0
0.2
3.0
3.0
(a) Gaussian,
22
(b) Uniform, -0.5.
(c) Expomential,
Figure 5.2: The performance of Algorithm for fixed a and varying b. The yellow lines show the result computed using the top eigenvector of the contrastive covariance. The blue dotted lines show the better of the two contrastive means.

---

Dimension Dependence. In this experiment, we show the relationship between the input dimension and the sample complexity. For fixed number size N 1000000, we measure the performance of our algorithm with different d. The result is averaged based on a grid search of (a, b) pairs, where for each pair of (a, b), we conduct five independent trials. For Gaussian and exponential distributions, we choose -3 v a < b < and for uniform distribution, we choose -0.8 S < S 0.8.
As shown Figure 5.3, the performance scales linearly with growing dimension d, suggesting linear relationship between the sample complexity and the input dimension.
37
15
44
3.
30
186
(a) Gaussian
(b) Uniform
(c) Exponential
Figure 5.3: The performance of Algorithm 1 for fixed sample size N and varying dimension d.
<-Dependence To further understand the dependence on the separation parameter c, we plot the performance versus 1/c in Figure 5.4. Here calculate 1/c as 1// b]). and the performance as the median sin 6 (u, ù) for specific mass g((a, bl). As we can see the performance drops near linearly with respect to 1/e, which indicates that the sample complexity is possibly linear in 1/c well.
0.04
0.0
3.04
0.00
2.00
0.2
0.53
1rmas
10
(a) Gaussian
(b) Uniform
(c) Exponential
Figure 5.4: The performance with respect to 1/e.
Discussion
We have proposed and analyzed an efficient algorithm learn the symmetric product logconcave distribution without labeled data. This is also connected to self-supervised learning. Specifically, contrastive learning without data augmentation is closely related the contrastive covariance part in our algorithm.
The algorithm delivers more than the theoretical analysis. While our analysis focuses on specific values of a, as demonstrated by the qualitative lemmas (Lemma I, Lemma 2), any distinct pair of nonzero values should work for contrastive mean, and any bounded small should work for contrastive covariance. This flexibility ensures the applicability of the algorithm in various real- world scenarios. Furthermore, our experimental results align with this claim.
The experiments reveals linear relationship with the input dimension d, raising an open question regarding the improvement of the sample complexity bound to be linear with respect to (as well as 1/c). Additionally, might be possible to extend the algorithm's is application to more general distributions.
Acknowledgements. This work was supported in part by NSF awards CCF-2007443 and CCF. 2 1134005 and an ARC fellowship.
10

---

References
[AV06] Rosa I Arriaga and Santosh Vempala. An algorithmic theory of learning: Robust concepts and random projection. Machine learning, 63:161-182, 2006.
[BBL06]
Maria-Florina Balcan, Alina Beygelzimer, and John Langford. Agnostic active learning. In Proceedings of the 23rd international conference on Machine learning, pages 65-72, 2006.
[BKS+06] Gilles Blanchard, Motoaki Kawanabe, Masashi Sugiyama, Vladimir Spokoiny, Klaus- Robert Müller, and Sam Roweis. In search of non-gaussian components of high- dimensional distribution. Journal of Machine Learning Research, 7(2). 2006.
[Blu90] Avrim Blum. Learning boolean functions in an infinite attribute space. In Proceedings of the twenty-second annual ACM symposium on Theory of computing, pages 64-72, 1990.
[Blu94] Avrim Blum. Relevant examples and relevant features: Thoughts from computational learning theory. In AAAI Fall Symposium on Relevance, volume 5, page 1, 1994.
[BVO8] Charles Brubaker and Santosh S Vempala. Isotropic pea and affine-invariant clustering. Building Bridges: Between Mathematics and Computer Science, pages 241-281, 2008
[Car98] J-F Cardoso. Multidimensional independent component analysis. In Proceedings of the 1998 IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP'98 (Cat. No. 98CH36181), volume 4, pages 1941-1944. IEEE, 1998.
[Com94] Pierre Comon. Independent component analysis, a new concept? Signal processing, 36(3):287-314, 1994.
[CST*00] Nello Cristianini, John Shawe-Taylor, et al. An introduction to support vector machines and other kernel-based learning methods. Cambridge university press, 2000.
[DK70] Chandler Davis and William Morton Kahan. The rotation of cigenvectors by perturbation. iii. SIAM Journal on Numerical Analysis, 7(1):1-46, 1970.
[GVX14] Navin Goyal, Santosh Vempala, and Ying Xiao. Fourier pea and robust tensor decomposition. In Proceedings of the forty-sixth annual ACM symposium on Theory of computing, pages 584-593, 2014.
[HDO IDDO+98] 98] Marti A. Hearst, Susan T Dumais, Edgar Osuna, John Platt, and Bernhard Scholkopf. Support vector machines. IEEE Intelligent Systems and their applications, 13(4):18-2, 1998.
[JV23] He Jia, Pravesh K Kothari, and Santosh Vempala. Beyond moments: Robustly learning affine transformations with asymptotically optimal error. arXiv preprint arXiv:2302. /2289, 2023.
[KKMS08] Adam Tauman Kalai, Adam R Klivans, Yishay Mansour, and Rocco A Servedio. Agnostically learning halfspaces. SIAM Journal on Computing, 37(6): 1777-1805, 2008
[LS11] Phil Long and Rocco Servedio. Algorithms and hardness results for parallel large margin learning. Advances in Neural Information Processing Systems, 24, 2011.
[LV07] László Lovász and Santosh Vempala. The geometry of logconcave functions and sampling algorithms. Random Structures & Algorithms, 30(3):307-358, 2007.
[MP69] Marvin Minsky and Seymour Papert. Perceptrons: An Introduction to Computational Geometry. MIT Press, Cambridge, MA, USA, 1969.
[PCST99] John Platt, Nello Cristianini, and John Shawe- Large margin dags for multiclass classification. Advances in neural information processing systems, 12, 1999.
[Ros58] Frank Rosenblatt. The perceptron: a probabilistic model for information storage and organization in the brain. Psychological review, 65(6):386, 1958.

---

[SBS 00] Alexander J Smola, Peter J Bartlett, Dale Schuurmans, Bernhard Schölkopf, et al. Advances large margin classifiers. MIT press, 2000.
[SV13] Nikhil Srivastava and Roman Vershynin. Covariance estimation for distributions with 2 + moments. The Annals of Probability, 41(5):3081-3111 2013.
[TV18] Yan Shuo Tan and Roman Vershynin. Polynomial time and sample complexity for non- gaussian component analysis: Spectral methods. In Conference On Learning Theory, pages 498-534, PMLR, 2018
[Va198] Leslie G Valiant. Projection learning. In Proceedings of the eleventh annual conference on Computational learning theory, pages 287-293, 1998.
[Vem10] Santosh S Vempala. Learning convex concepts from gaussian distributions with pca. In 2010 IEEE 5 Annual Symposium on Foundations of Computer Science, pages 124-130. IEEE, 2010.
[VXI1] Santosh S Vempala and Ying Xiao. Structure from local optima: Learning subspace juntas via higher order pea. arXiv preprint arXiv:1108.3329, 2011.
[XNLS04] Linli Xu, James Neufeld, Bryce Larson, and Dale Schuurmans. Maximum margin clustering. Advances neural information processing systems, 17, 2004.
12

---

Appendix
A Preliminaries
A.1 Logeoncave Distributions
Lemma 8 (Lemma 5.4, [LV07]). Let X be random point drawn from a one-dimensional logconcave distribution. Then
P(X 2 EX)
Lemma (Lemma 5.3,ILVO7D. Ler p + R+ be an isotropic logconcave density function. Then have
(a) For all x, g(z) - 1.
(b) g(0) 2 1/8.
Lemma 10 (Lemma 5.6,[LV0]J). Let X be random point drawn from logconcave density function p: R4. Then for every e 2 0,
P(p(X) Sc) max, p(z)
Lemma 11 (Lemma 5.7, [LV07]). Let X be a random variable drawn from a logconcave distribution in R. Assume that EX < L. Then for any 2 1, we have
P(X 2 t) S e
Corollary 1. Let X be random point drawn from an isotropic symmetric logconcave density function p R + R4. Then we have for 2 we have
P(X 2 t) < 8p(t)
Proof. Since p(x) is symmetric, know p(x) is monotonically decreasing for 0. Then apply Lemma 10 with = p(z), and get
p(t)
P(r S P()(X) S p(t) max, p(x)
On other hand, by Lemma 9, we have max, p(x) 2 p(0) 2 1/8. So we have
P(X 2 s 8p(t).
Lemma 12 (Theorem 5.22, [LV07]). For random point X drawn from logconcave distribution in Rd then
x k < (2k) (T((X)))*
Lemma 13. Let X be random point drawn from an isotropic symmetric logconcave fensityyuunctiin
function
p: R R4. Then for any 3, we have
p(t) p(0) 2-1/33
Proof. First we claim that p(3) < p(0)/2. Otherwise,
EX² / 2²p(x) dx ( 33
9
2 3
16
This leads to the contradiction. Then for any t 2 3, from the logconcavity of p.
p(3) > (0)) 1- - +())
This implies that
p(t) S p()) 2-3333
13

---

A.2 Descartes' Rule of Signs
Descartes' rule signs a well-known principle in algebra that offers way to estimate the maximum number of real roots for any polynomial. This classical theorem can be stated as follows:
Theorem 4 (Descartes' Rule of Signs). For the generalized Dirichlet polynomial
F(a)=
Σ j=1
P1
P2
Pnn Pn.
the number of roots of F(z) = 0 is at most the number of sign changes in the series {a1, 02. J.
In this section, we state and prove a variant of Descartes' rule of signs in the integral form, which we apply directly to prove Lemma 1. To begin with, say function has root of order i point
((x) [(.)
(x) = 0 and (x) # 0.
We denote Z(f) as the number of roots of f. counted with their orders. Then number roots of f is upper bounded by one plus the number of roots of f' in Lemma 14, We use Rolle's Theorem in the proof of the lemma.
show that the
Theorem 5 (Rolle's Theorem). Suppose that function is differentiable at all points of interval (a, b) and (a) = f(b). Then there is at least one point Do E (a, b) such that (((o =0. O.
Lemma 14. Z() Z(f)+ +1.
Proof. Suppose f has root of order hy as Zr, S n. Then f' has root of order 1 at Zr. These add up to
Σ (kr - - Z()) n
By Rolle's Theorem, fz) also has at least n roots the gaps between the points H,. Together, these two facts give
z("") 2 Z(f)
= z(f) - 1.
Theorem 3 (Descartes' Rule of Signs in the Integral Forn). Let F(a)= - So alx)e dr. Then the number roots of F(a) 0 is at most the number of sign changes in a(x) for 2 0.
Proof. We prove the theorem with induction on the number of sign changes of a(x). For the base case when the number of sign changes of a(x) zero, we assume wlog that a(x) 2 Then F(a) and thus (a)) has no root. Now we assume that the theorem holds when the number of sign changes & and we will show the t case.
Let one of the sign changes of a(x) occurs at xp. Define
Po(a) :- :0 { J. alz)e dr,
which has the same roots as F(a). By taking derivative, we get
(a = 1/ a(x)(2² al)) +z)) dx.
Let b(z:) (x) - xx6) be the sequence. Then b(x: has less sign changes than a(z). By induction hypothesis, the number of roots of (a: is upper bounded by the number of sign changes of b(x)). By Lemma 14, the number of roots of Fo is upper bounded by the number of sign changes of a(x)) thus leading to the induction step.
14

---

B Warm-up: Isotropic Isoperimetric Distribution with e-Margin
As a warm-up, we consider the isotropic product distributions with c-margin. Notably, without applying an unknown transformation on data, we can extend the logconcave distributions to isoperimetric distributions. In this section, we will demonstrate how retrieve the normal vector by calculating the empirical mean and top eigenvector of the empirical uncentered covariance matrix. This technique similar to Principal Component Analysis (PCA), instead computing covariance matrix, we use the uncentered covariance matrix.
Definition 2. A distribution with support R. is disspperietrticc if there exists vb 0 such that for any 2 R. have p(x) 2 a minnnp([2: o0)), po0 xl)]
Definition 3 (Isotropic Isoperimetric Distribution with e-Margin). Let ....... 9d be symmetric
one-dimensional isotropic -/-isoperimetric density functions bounded by r. Let Q ②1 8 ..... & qa-
Let q be the density obtained after restricting gi R RA,a, bj where qn ((-00, a] 2 e, (1 ([, b)) 2 and q1 ((b, x)) 2 6. Let be an arbitrary rotation of q @ 92 & ... 69 qd- We refer as an Isotropic Isoperimetric Distribution with e-Margin. Let u be the unit vector normal the margin.
Problem. Given input parameters e, > 0 and access to iid samples from P. an isotropic isoperimetric distribution with e-margin, the learning problem is compute unit vector that approximates within TV distance ö. That is, the TV distance between the corresponding P and P is at most 6, where P is the distribution with margin normal to
B.1 Algorithm
Given data drawn from P, we compute the sample mean and the top eigenvector of the uncentered covariance matrix. Then compare the margin along these two candidate normal vectors. This gives an efficient algorithm for the problem with no re-weighting. We state the algorithm formally in Algorithm 2.
Algorithm 2 Unsupervised Halfspace Learning from Isotropic Isoperimetric Data
Input: Unlabeled data (z/(1), (N)) C Rd 5 > O.
Compute the sample mean and uncentered covariance matrix:
(1) S
000
Compute Ess top eigenvector
Calculate the max margin (i.e., maximum gap) of the ane-dimensional projections of the data along the vectors A, Let û be the vector among these two with larger margin.
return the vector à.
B.2 Analysis
We demonstrate that Algorithm 2 operates within polynomial time and sample complexity. The details regarding sample complexity are presented in Theorem (formal statement of Theorem 6). The time complexity is justified by the algorithm's 's process: it calculates the sample mean and the top cigenvector the sample covariance matrix, both of which require polynomial time.
Theorem (Sample Complexity for Isotropic Isoperimetric Distribution). Algorithm 2 with 0 - samples learns the target isotropic isoperimetric distribution with e-margin to within TV distance 5 with probability 1 E.
The analytical approach straightforward. Given that the component distributions are isotropic the empirical mean will reveal the band if the removed band (a. b) stays one side of the origin. Otherwise, when [a, b) spans across origin, the variance along the component with the deleted band will increase. Consequently, this component emerges as the top principal component. Intriguing, this
15

---

property is "opposite" to the method used to identify low-dimensional convex concepts in [Vem OO] The latter relies on the Brascamp-Lieb inequality, where the variance of a restricted Gaussian less than that of the original Gaussian.
To prove Theorem 6, aim to quantify either the mean gap or the spectral gap (gap between the top two cigenvalues) of the uncentered covariance matrix. Specifically, Lemma 15 indicates that when 0 S a the mean along the direction u significantly deviates from zero. Meanwhile, Lemma 16 demonstrates that when a < 0 < 6, there's 's a gap between the first and second eigenvalues of the uncentered covariance matrix. Subsequently, we employ Lemma [SV [SV13] to determine the sample complexity, and utilize the Davis-Kahan Theorem [DK70] (Lemma 7) to leverage the eigenvalue gap in identifying the pertinent vector u. We leave the proof of the lemmas in Section B.3.
For any I E IR, we denote I2 as its i-th coordinate. We use ||>||| to denote its l2 norm. For a matrix A Rmxx, we denote its operator norm as || We denote the standard basis of IR by {eI,--- eaa, and assume wlog that e1 = is the (unknown) normal vector to the band. Denote = Er- rx as the uncentered covariance matrix of P, with eigenvalues \1 2 X2 2 2 Ad.
Lemma 15 (Mean Gap). For 0 S a < b and b a 2 ce for constant e > O, we have
I z~N
E
var S x 2
2
Lemma 16 (Spectral Gap of Covariance). If S O < b and b >> ce for constant >> O, then the first and second eigenvalues of the uncentered covariance matrix E. have the following gap
x1 >2 Ce for constant C 0.
Furthermore, the top eigenvector corresponds to u.
Now we are ready to prove Theorem 6.
Proof of Theorem 6. We proceed with the assumption that [6| > |a]. If this condition is not met, we can redefine our interval by setting
-b and b' -a. The proof can then be applied considering the distribution is restricted to {x E Rd
S a' or u 2 8}. We will prove the
theorem by considering two cases: 0 I a < and a S 0 <.
We first consider the case when 0 S < b. Given that q1 is bounded by it follows that b - a > E/T.
By Lemma 15, we know
D var x S amP
x>p
2-
2c
while for 2 2, we have
E T; 0, T; 1. r~P
x~P
Given data ........ (N,) let ft = $/2 -===1 x(1) be the sample mean. Then by Chebyshev's Inequality,
8
28
167
P(A
P(p
25isd
4-
7
4r2
No52
Let < <<< 1. So we know with sample size N1
16
2
36
alm
F(A
P(
5
4
2d
d'
472 2
Then we have
1
P(sin (p, 5) -PP(
1 1- 82)
Di=1 1
3
>P(11
47 f4:
25i50
472
21-
16

---

Secondly, we consider the case where - 0 < b. Given that b b-a > c/T and [6] > |a]. it results in b > e/ (2T). By Lemma 16, the top two eigenvalues of Σ, denoted X and A satisfies
22 2 Cca11 for some constant C > 0
By Lemma 6, with sample size N₂ Óde with probability at least
1 Eop S E ||
By Lemma 7, we know for the top eigenvector v of Σ satisfies
2 - -1ppp 2011 261 sin sin v)
Ce - Ce Cea
Choose 61 = C/28/2, and we will get sin ((n, I 8. The sample size we need is N2 = Oddc-68-2). So with sample size N = recover ej within TV distance ó with probability - g.
= Old 0( Algorithm 2 can
B.3 Proofs
Lemma 15 (Mean Gap). For 0 S a < b and b - a 2 CE for constant O, have
E z~a
<
var S
vaa 2c
Proof. Since qi is t io-pspprrrm,ercc, Vt E b). (t) 1b Se (2) dr 2 the. Then we have
L mq1 (x) dx > De { xd >
2
By the definition of expectation, we have
|Saeaa zq (x) dxl
1s x21(2)) dzl
ce
-|
JRyjo..) 91 (x) dx
Se 91 (x) dæ
zma
On the other hand, we can calculate the variance as follows.
SEyAa (x) (x) dr 1 (2) dx J0 (1(x) de
f x² x2 (x) dr
1
var x x 9
2e
2
Lemma (Second Moment). For a, satisfying a S < b,b cr for constant e: > 0, we have
E x² > 1 Ce2 CC2 for constant C >> 0.
Proof. By definition of q, we know its density on the support x E IK [a,
q (x)
( J= (x(x) dr So (x)
Then calculate its second moment as follows.
E x [ 2² (z)
(x) de + 1x x (z) dr
1 (x) de 1r 91 (x)) dr
Define :(=))==::)) := f (12 - (1) dl, x 2 0. Its derivative is g((x) = (1 xg))))))))))))))))) So we know
g(x) is monotonically increasing when x E (0. 1). and decreasing when 2 1. Since Pi is symmetric
and isotropic, we know f qı (x) dæ = - z²q1 (x) da 1/2. So we have g(0) = 0. This derives
that (xx) 2 0, Vz 2 0. In other words, 1 x q1 (z) do f (z) dx.
17

---

For any E (ee, MM. we have g(z) 2 min(g(ee), g Here we let M 0 such that Ja (()) dr = Then we can lower bound g(ce) as follows.
g(ce) g(0) / g((x) dr = S (1 (1-=2)g((z)dl (1-2))((z)) ce(1 - (e))) > vi (1- cce²)
M - 1, we know b1 < M < 1. Then we have g(b) 2 g(ce).
If M 2 1 1+
lower bound (MM) as
s(M (M² -1) / 91(x) dr > ((1 + +e)² - - 1)e = 2e²
Similarly will get g(b) min min((vec?( ( ) 2 + ). Finally if 1 < M + e, there exists
M' > 0 such that JM (2) dx c/2. Here M' - M > c/2. Then we have
/ M
g(M') (M - 11)
n (x) dr
1
In this case, we have g(b) ( can lower bound the second moment of & as follows.
( 22/2). Therefore, we
(x) dx + S (x) dr g(b)
E 2 gro
(1) dr Jo (1(x)) dæ
>1 min(wbe - 2 ( (1) do + S (x) 2 >1 + Ce² where C min (2//2.1/8)
>1 + min(vce (1- 2/8+
Lemma 16 (Spectral Gap of Covariance). Ifa S 0 < b and b > ce for constant e > 0, then the first and second eigenvalues of the uncentered covariance matrix Σ have the following gap
A x2 > Ce X1 for constant C > 0.
Furthermore, the top eigenvector corresponds to u.
Proof. We assume wlog that 61 u. Then the marginal distribution of Pin e1 q, while the marginal
distribution in e is for any 2 < < d. Since qs is isotropic, for any 2 s S d,
E
x²
= 1. By
Lemma 17, have
E of
C 3 for constant C' 0. Let ((v)
Then
x>P
z~P
have g(c)) > + C²e3, while g(c)) 1, 12 sis d. Then for any unit vector e Σi 8r0
satisfying Σd
i= 32 1, we have
((0) = Σ gig(e)) s g(e))
Then we know the top eigenvalue of E A > 1+ C.3. Furthermore, the top eigenvector corresponds
to ej. Similarly, the second eigenvalue of Σ is X2 max g(v) gle,) 1,2 i i d. This
implies that A A2 > Ce \ for constant C > 0.
18

---

C General Case: Affine Product Distribution with c-Margin
In this section, we first prove the main theorem in Section C.I using the quantitative lemmas, and then prove all the lemmas. We begin with proving the two qualitative lemmas (Lemma 1 and Lemma 2) in Section C.2, and then prove the quantitative lemmas (Lemma and Lemma 5) in the remaining section. For the quantitative part, we first consider the asymmetric case where |a + bj 2 cb. In this case, contrastive mean leads to recovering u, as elaborated in Section C.3. Secondly, we consider the symmetric case characterized by a a b- = 0, addressed in Section C.4. We show that we can recover u by calculating the top eigenvector of the re-weighted covariance matrix. Finally we extend the result to near-symmetric case where |a + b) < 6 in Section C.5.
Recall that we are given data x! ,('),... , (x\)) drawn from the affine product distribution with e- margin P. Algorithm 1 first makes the data isotropic. Denote y yy() as the corresponding isotropicized data. Then each yاو is an independent and identically distributed variable drawn from P = q @ @ ... q. Since we compute the re-weighted moments on y(T) in the algorithm, we analyze the moments of P directly.
Recall Definition that q is the symmetric one-dimensional isotropic logconcave density function, and is the density obtained by restricting g to IR', (R) bj for some unknown < b. Denote 111, of as the mean and variance of q. q is the density obtained after making ş isotropic, with support RV[aa,, 8).
where d' = a a-pi 6-H1 The density & on its support is
019(201 + 11)
((x) [ ((x) dx + Jo g(z)
We denote the standard basis of Idd by fei,... eed), and assume wlog that 61 u the (unknown) normal vector to the band. We write I2 := (z, e,) as I's i-th coordinate. We assume in our proof that [b| > Ja]. If this condition is not met,
redefine our interval by setting a' - and b' = aa The proof can then be applied considering the distribution is restricted to {z E Rd u Tx S a' or u x 2 8/. For vector I E Rd, we use ||æ||| to denote its la norm. For a matrix A E R we denote its operator norm as ||A
C.1 Proof of Theorem
Armed with two quantitative lemmas and the Davis-Kahan Theorem, we are now prepared to prove the main theorem. We state the formal version of Theorem follows.
Theorem 7 (Sample Complexity for Affine Product Distribution with e-Margin). Algorithm I with N = - -318--2g-1) samples learns the target affine product distribution with e-margin to within TV distance 8 with probubility 1 g.
Proof. Firstly we consider the case when la + bl > e.. Denote a" = argmax, (1aa)) (Mag)) l}. and Pa par By Lemma 4, [(Ha)1l 2 159 /d² Since for any negative for any S i < d.
var(ua); S E
20 livll y² S
E y² =1
y
yap
ea 11 y(0 satisfies
By Chebyshev's Inequality, the weighted sample mean
j1 = N
===
159
4d
C
P( <
P( 2
2 siidd d. N
2d
NC
2d VJ
Let the sample size N1
Cfeasaga = c -318 18188-26 ----11) and we have
1
C 159
P((
P( <
2sisd
2d
d'
2d Vd
d'
So we have
P(sin 0(ū, f1) ())55 5) =P(
2 21-82
1==1
19

---

C 159
C
2P([i11 2
siidd)
2d
2d 2d
21 -1-
This indicates that with probability 1 1 ç, the re-weighted mean can output the vector jú that within angle å to the vector é1.
Secondly, for the case when a and b sear-symmetric. Denote Σ as the re-weighted covariance matrix with eigenvalues A and Σ as the empirical ce-weigtted covariance matrix with eigenvector By Lemma 5, A1 X2 Cze A1. By Lemma 6, with sample size N2 O(de-88 probability 1 5.
-8--6 --)-) with
[ - Elpp S C2
By Lemma 7,
sin sin, S 2 -
-112- -llopp C2E" = C2e
C2c <
So given max(N1, e 25-1), the algorithm learns the distribution with probability 1 - 5.
C.2 Proofs of Qualitative Bounds
We present proofs of two qualitative lemmas: the contrastive mean (Lemma 1) and the contrastive covariance (Lemma 2). Their quantitative counterparts can be found in Section C.3 and Section C.5. To establish the contrastive mean, we invoke Descartes' Rule of Signs. For the proof concerning contrastive covariance, we introduce a novel monotonicity property on the moment ratio, as described in Lemma We include the complete proof within this section.
a' =
7
(00
1/
Figure C.I: Coefficients of F(a) ahead of eaz term Lemma I's proof. By combining ax terms, we flip ((x) horizontally, For a' > 0, the coefficient is negative when (a', D)) and non-negative outside the interval. For a' < 0, the it negative when (-a', 8') and positive when b'
Contrastive Mean. We can write the contrastive mean as linear combination of exponential functions of a. By Descartes' rule of signs, the number of zeros of this function is at most two. Since a = is one root and corresponds to mean zero, there is at most one nonzero root. And thus we have that for any two distinct nonzero a's s, at least one of them achieves nonzero contrastive mean.
Lemma (Contrastive Mean). [a one of the corresponding re- re-weighted means is nonzero, i.e.,
O, then for any distinct nonzero 01 02 R, least
eall=1 T 0.
max
E R~P
E TWP
Proof. bb] > |a| implies that μn < O. For any x 2 0. we have
σ1q(101 m1)
σ19( 20 M1) 9l xx).
@(x) 1 1.¹ g(x) dr
1 1 ((x) dx
20

---

Since P is product distribution, we have
all
e
E are p
21
E
31
E
1=2
2inig
We denote
F(a)
E e
enrizi
(C.1)
2m9
By calculation, we have
F(a) = Jaslaran oax x((x) dx
-
Then rearrange F(a:) by combining eos" as in Figure C.I. If a' S O, we rewrite F(a) as
F(a) - _ rqi ()( dr + { x(((x)) - 1( ((-=)))e dx
We treat F(a) the integral of a for -a'. Since q(x) - -(-x)> > 0 for x > b', we have a(x) > 0 for x E [=a', B/) and a(x) < for x: > V. In other words, for increasing 2, the sign of a(x) only changes once. By Theorem 3, ((a) 0 has at most root.
> a' we arrange F(x) the same way and get
10 r(((z) ((-x))eam dr dz-f. f( (G(-z)eart dr +
{ x(((x) 6( ((-x))e dæ
F(a) = F(a)=
Similarly, we treat F(a) as the integral of e for æ 2 0. For increasing the sign of a(x) changes twice. By Descartes' rule of signs, F(a) = has at most two roots. In addition, we know F(0) E. = 0 by definition of P. So a 0 is one root of F(a) = O. So there is at most one nonzero root of F(a) F(a1), is nonzero. This implies that
In other words, for any two distinct nonzero 0r, 0g2 least one of
)
22lll11 Ij
max
E P~P
E 2
Moment Ratio. To prove Lemma 2, we develop new monotonicity property of the moment ratio of logconcave distributions. Moment ratio is specifically defined as the ratio of the fourth moment to the square of the second moment of truncated versions of the distribution. This measurement essentially reflects the uncentered kurtosis of the distribution. The formal definition detailed in Definitinn 5.
Definition 4 (One-side t-restriction distribution). Let be distribution in one dimension with nonnegative support. For any 2 define q: as the one-side t-restriction distribution q obtained by restricting g to [t, oo).
Definition 5 (Moment Ratio). Let q distribution one dimension with nonnegative support. For any f 2 0, define q's moment ratio as function of t, given by
mr, (1) = varg, (X²)
where qe the one-side (-restriction distribution on g.
[E,, X2)2
We will prove the monotonicity of the moment ratio (Lemma 3) by reducing general logconcave distributions to exponential distributions. The monotonicity of the moment ratio for exponential distribution is detailed in Lemma 18.
Lemma 18 (Monotonicity of Moment Ratio of Exponential Distribution). Define h(x) Be-22 y2 0, 3, 7 > 0. Denote (t)t) fe x*h(x) da. Then for any 2 0, we have
e Noo())N2 + Ne(t)N, 2t (o( 0.
21

---

Proof. By calculation, we have
No(()= [.e BE- dx
B -
7
(1) 1.a 20 BIe 72 dx
B 1e- 71 + No((t)
1
=(++
1
B
en
_e e
N2(t)= = 1. 6 12 dr 2 ee
+ 2 (t)
1
- +
2
2 7/3
B 7t
?
(s(t)= I.a 3x0 dx = B tt + 3 (2)) =
6
B
1
(2
? e
en
?
2
33
100 Na(1)= = 1.a0 Ba'e dr L + - Ns(1) =
4 3
12
24
3 -7
x'+ +
+
? 6
7
g4
Then we can plug them and get
A (o(())N2(1) + (2(1)Na(1))
21
No(t)
32
280
81
2
+
2
t
2
+
2²
+
+
2
t +
1 +
12 2 +
24
t +
24 74 ))
72
?
72
72)
72
73
8,32
6t
12t
6
2rt
> 0
72
33
24
70
7
Next, we will prove the monotonicity of moment ratio for logconcave distributions.
Lemma 3 (Monotonicity of Moment Ratio). Let q be logconcave distribution in one dimension with nonnegative support. For any 2 O, let qi be the distribution obtained by restricting to [t, co).
Then the moment ratio of g, defined as (ty = varg,
is strictly decreasing with t.
(E., X2yz,
Proof. Denote (t(()= -0e0 x²q(x)) dr. By Definition 5,
I (a(a)( di
varg. (x2)
1 q(x) de
Mo(t)M((()) M2(1)²
(f,
-
(Ege X222
1: g(z)
Next we will show that mr 0, Vt 2 O. By taking the derivative,
mr (t) -9(1) (f)Mo())M)(t) + M.(t)
2t Mc(t)
M2(t)
21 (t Mt We will show that H > 0, V O. Clearly H()) (2(() > 0, So only consider & > 0 in the following proof.
Define H(I) = 1
Let l(xx)= = Be - be an exponential function (B,7 > 0) such that
Mo(t) = Not M2()) = N2(t), where Nx = 1.- x x²h(() (t,) N.
Then we have
J. (h(z) - q(x))) (()))-(=)))d dx d=zddd=-00 -0. 0, l. (2((()) -())) =0
By the logconcavity of g, the graph of intersects with the graph of q at exactly two points u' < v where v >> O. Also we have h(x) I q(x) at the interval Ju', v] and h(z) q(xx) outside the interval.
22

---

Let max(0, So for x 2 0, (x - u) - 2) has the same sign as h(z) g(x). Since 2 0, we have
[ (a²-2 2z)( (1(x)) ((x)) 20
Expanding and we get
((())) - 2 (u² + +00 J.a x² 2h(xx) - -x))) dx - u²r? J." (b(z)) g(x)) dr 0 J. x'
This shows that (t(1) 2 M4(t). To show that (t) > 0, we consider two cases.
Firstly if M2(t) 2t 2 0, we have
(t) + (2)( (M(()( - 21²) 0.
Secondly if M2(() 21 < 0, by calculation of the exponential function's 's moments (Lemma 18), we have
t No((t)N2()) > - -Na(t((N2(t) 2t²)
Then we have
(1)) = (0)) + (22()( 20
=t (t))) + (2())( -22)
2 - (a(0(N2(() - 2/²) + (M2() 26
(M2((t) (M4(() (N())
20
The equality holds if and only if (+(() = (t). This implies that
H(tt) e N2)) (a(() - -)))))))))>>>)) > 0.
Combining both cases, mr((1) < 0, 14 2 0, which implies that the moment ratio of is strictly decreasing with respect to L.
Contrastive Covariance. View the spectral gap the re-weighted covariance, denoted as x (1) )²(E), as a function of a. which we denote as S(a). By calculation, S()) = 0 and S' is proportional to mr(b) mr(0), which negative by the monotonicity property of moment ratio. Then we can prove Lemma using Taylor expansion.
Lemma 2 (Contrastive Covariance). bba O, then there exists an a < O, such that (1) there is positive gap between the top two eigenvalues of the re-weighted uncentered covariance matrix Σ = Eapp e!||=|? (xxx) T). That is, X1 {1) >²(E). (2) The top eigenvector of Σ is
Proof. Denote (t) fe x² (xq(()) dr. The variance of of restricted to R2|-b, is
S p()) M2(b)
of
S p(z) dx Ma(b)
Since ğ is isotropic, the density on the support R. RR[ b/oi) is
σ 01q(I01)
Pa(x))
2 q(x) dæ
Let
S(a)
ar
az2
E ax
x² E ax²
aaa
xmm
zmg
Since q and a are both isotropic,
S(0) = E
x
E
0. Then,
2nd
Ing
(abb)Mo() (O)O
5'
(b)
M2
23

---

The last step is because the distribution is isotropic. By Lemma 3, we know S'( mr (0) < 0. On the other hand, Yo S (a) can be bounded.
Mb(b)
Ma(6)
(a) M2 Mb(
< <pol([1/e)
By Taylor expansion, we know there exists a < such that
a S(a) =5()) - as)
// (a > O. where a' E [a,
Then we have for s S
E
e ||||||
E xmp
eallell 27 = -(aa)
E eax?) and
)
d-2
> 0
For any E Rd, define (bv) as
en||z]1? UJ xxxxx Tv
((v) == E
x-P
v viv
Substituting with ej and eg. 2 S d, we have
((E1)= = E
||||||
D(e))
2f
E
eallel? x3
p>p
amp
This implies that for 2 2 S d.
((e)) o(e,)
E
eallll
xj 29-
mnj > 0
xmp
Jup
For any vector == E/=1 7/C₁, we have
-== p,(((e)) n2;)²
Φbv) =
E
S ((e1)
Σ n
This shows that the top eigenvalue of Σ (E) max, d(u) Φ(e)). Similarly, A2(E) maxoweee (bv) = o(e,), j S Therefore, ( > {² and the top eigenvector is 61.
which is essentially
C.3 Quantitative Bounds for Contrastive Mean
We will prove Lemma 4 in this section. Here we consider the case when |a + b| c We compute the contrastive mean of P given a < as E
ea x using two different a' a's.
a
Definition 6. We define F(a)) as re-weighted mean for the one-dimensional distribution q.
F(a) =
E
e
eo
x =
/
ea2² =](xx) dx
(C.2)
J2v
B
Since P is isotropic, F(0)=
E x-4
O.
To prove Lemma 4, we need to show that for given 01 a2 the maximum of [a(a)), (F(2)) (F(2))) exceeds a certain positive threshold. We follow the same idea of bounding the number of roots of F(a) as in the qualitative lemma (Lemma 1). By taking the derivative of F(a), (O * 0 or (0) + O. Then by Taylor expansion, we can choose two distinct a's (near zero) so that one of the corresponding contrastive means is bounded away from zero
show that either
In the process of proving the quantitative bounds, similar to our approach with qualitative bounds, we must consider two distinct scenarios based on the sign of a', as illustrated in Figure 4.1.
In the case where a' is negative, lemma 20 asserts that the first derivative of F at zero, F'(O) is always positive.
24

---

Conversely, when a' is nonnegative, Lemma 23 reveals an essential characteristic of the function F(a): it's not possible for both (0) and F" (0) to be zero at the same time.
Lemma 24 provides upper bounds for the derivatives of F(a). These upper bounds crucial as they help in managing the extra terms that emerge during the Taylor expansion of F(a:).
The section concludes with the proof of Lemma 4, which is the quantitative lemma for the contrastive mean.
We start with Lemma 19 showing that [r is away from zero provided that la + 6| is also different from zero.
Lemma (Lower Bound of (. If a + ba 2 e* for & 2 2, then yn 2 62/2.
Proof. Firstly, let's consider the case when S 0. By Lemma 9, we know 7(x) is upper bounded by 1. Since la + b| 2 e* and q is logconcave, by Lemma 8, the mean of the density restricted q in [-a, b] satisfies p[-a,b] 2 1/e. Then
| = M[-a,b] l ((x) dx
S ((x) dr S ((x) dx + 2 22 q(x) de
2
1 la ((x) dr.
By Lemma 11,
q(b) 2 /0 q(z) dr
Since |a| < [6], we have
((x) dx 2 (b+ a)) 2 2(b +a) /
sc ((z) de
So we have
2(b + a) 6 2 + a) +2
2 e²
1 2
e
el c
2e
Secondly, when 0, since b a 6
|ia b (()) dæ
2
(a + - -
|nl
1 1 g(z) ) dx
Lemma 20 (Derivative of F(0) when a' < 0). If a + b1 2 e" for s 2 2 and a' < 0, then F'(0) > 3o43..5 /2.
Proof. We rearrange F(a) by combining terms with same eax² as in Figure 4.1, and get
xQ( (i)e-r))ax" dr f x(((x) 4( x)) dr F(a) = 1r
/b'
Define r(x) -q((-r)
x -d'
x (b', 20) Then have
(((I)= -(-xx
F(a) = 1 xr (x) dx
By calculating the derivative F(a), we have
Fa(a) 22 dx
r(a² 8/2 (r)r dx + 112 f xr(x) dr
25

---

alw² - r())
ax dx + + F(a)
Since r(x) is nonnegative for x 2 V' and negative otherwise, then for any x 2 -a', we have
x(x² --2-0% 1 )x()) 20
Since (()) = 0, we have
F'(O)= = I
x(2² - 8² )r(z) dx 2 I I(6²² - -x))(( dæ
By calculation,
b 111 ((--11)
2
(0 2 1 So ((x)) dx
- -x² 1201 + (1) dx
01
222
2
(x+ + M1) ((b - 11)² (xr + 11) )²) ((x)) de
o1 Sa ((x) de)
(x+ =1+ b)(6 2nd )g(x)) dx
of (1 Sa ((x) dr)
(b - a)21/111 / (o + Mi)g(z) (1)
dx
of 1a ((x) dr)
Choose to a-a, b) such that f ((x) dr 1 ((x) dr. Since ((x) is bounded by 1 by Lemma we have
to + a - ((x)(()))))) dz
On the other hand, similar to the proof of Lemma 19, we have
f ((x) de 2 2(b + a) (- ((t) dr 2 20
So we have
S (x (1)((1))())))) dr 2 f (x+a)q(zz)
2 1
dx 2 (to + a)
g(z) dx
to
(
pb
2
2
((x)
dx
2 20t2
4
By definition, we have
E x2 2m
of S SasjOLD z²((z)d dx
1- Sh g(x) dx
Sh ((x) dr
1- Sh ((()) dx
Applying Lemma 19, we know |A2| c² /2e.. Using these results to estimate F'(O), we get
F((0) 2(1 1'¹ ((x) dx)
6" 2042
3843.5
Lemma 21. a 2 pn S O, then we have 1 fa-2 xq(xx) do 2 1mil,5 ((x)) de.
Proof. Firstly we will show that -an-a (I (1) dr 2 O. For [M1, a), we have (2/11 xx² x² = =2=4p1 x) 2 O. Since q(x) is symmetric and uni-modal, we have q(2 - x) S 9(x), Vr E
[],
1 J (x- (--m))(x) du / - (o- (1)(())) de + f ( dr
m1)g(x)
n1
26

---

(Mi x)9(2(1 - -z) =x)xx dx [" -
ps )2(z)) dx
M1
(x - m))(((()) -0(211 x)) do.
20
And then, we have
I (000,2m -bjub- ((x) dx
(x H1)9(z) dr M1
11)022m---J1b20111 -1
2-211 ( ((x) dx
b22
Since 141 is the mean of the distribution q. We have
SANCO (5- (--m))((oddd- =0
Then we know
J (x - (1)((x) dr +
241 a
p-221 (0- (x (z21(gg()) dr s 2
00
g(x) dx
Then we have
211
b-2111
/ q(z) dx
0
(x- (e-Mi)g(I)de
(x (x- (2-(()g(z) dr 2/11
-p
b-2m
b-221
b-221
((x) dx + / 2-- zq(x) dr 11 f0 po-
x2(x) dx - 11
((x) dx
2-22p
202
2p11
((2) dx
b-211
b- 2p-
((x) dx ( p xq((x) dr l1 1. ((x)) de
xq(x) dx - 11
(xx)dx+
2-1
Ja-2pn
This derives that
1," Ja-2mn
((x) dr Mn / ((x) dr
xq(a)) dx 2 11 a-
2 Mz ((z) dx
Lemma 22 (Second Derivative of F(0) when d' 2 0). Ifa'
we define the following functions,
((x))
((-x:
x E [0, U [b,
00) 00)
.I((a) = /0²0 x(2² a'2) 8¹2 - (r))e() dx.
r(x)
1-1(--0 x E (a'
Then have
(a) = H(o) + (a + 8 F + 2 F(a).
Proof. We rearrange F(a) by combining terms with same aox in Figure 4.1, and get
F(a) = [ x(((x) ((-x)))ext dx - S" xQ( ()(- dx + I x(((x) á r)) dr
By the definition of r(x), naturally have
F(a) = ( 100 xx(x)) dx
27

---

Then we can calculate its first and second derivative as follows.
F((a) - / z'r(x)e dx, F* =
3 So xrr(z)e dx
By the definition of (()), we have
H(a)= H(a) = I ='r(z)e de - (a2 /--0 x2r(z)e de + 2200 /o ar(x)e de
=F) - (a22 (')
+ 2
Lemma 23 (First and Second Derivatives of F(0) when a' 2 0). 1f I 2 e for 8 2 2 and Cze 40.5 log (17c) or (0)
a' 2 then we have either (0)
2a (1/c]
for constants C2 Ca 0.
Proof. We prove the lemma by showing that H())
Cie c (1/e)
We calculate H(0) as follows.
xxx² -2 )²² - )r(x) dr
H(0)
x10² )62 x²)ā(=z)) dr
x0x² ) 2²2) 019(201 - p1) dx
1 Sa ((x)) dr
(x + 11) ((I + m1)² - (a m1 )² (lb- - (x +
+1 11) g(x) do
2p
of - S,¹ (xx) dx)
10-21 201 (x + M1)(z + a) + 2/11)( (b + 2b x 221) dx
4-22p
o J ( dx)
Denote p Sa-2p, 2p1 ((z) dr, by Lemma 21 and the bound of b, we know
l g(x) dx 2 1+ Im(/e) 6lm(1/e)
6/20. 2 c+1
p p=
e-201
Choose t < t2 such that l Ja-2 ((x) dr -¹²² q(x) dx = [ q(x) dr. Since g(x) is upper bounded by 1 by Lemma 9, we have
t - (112)))) 2 p b- 12 P
3
3
Using this, we can bound
(x +()( (4 + r)(b x - 22x1)g(x) do
6,4 (1/e)
| PPPPP
for some constant C₁ > 0
3333
We have shown that 01 S 1/v 1o g(x)) dr. Combining all results, we can compute (0)) as
5 log (1/e)
H(0)= > V ((x) da
log (1/e)
Given F(0) = 0, by Lemma 22,
(O) (0) + (a22 + +
28

---

Since the distribution is symmetric, we know
Jaa =q(x) dxl
[a|
E x²
amp
1
11
-a q(x)) dx
6
So know < d' b' b- 241 2.5/e, thus (a + 3 22)((22). Thus we have either
(0) log' (1/e) or (0) log' (1/e]
16.6 16.5
0..0.14.5 14.5
for constants C22 C3 > 0.
Lemma 24 (Upper Bound of F's derivatives). For S 0, the derivatives of F((:) are bounded as
[F'(a]] & Ca/c2, (F))))))((())) (a)) s Cs/e, (a) S Co/c² for constants C4, Cs, Co 0.
Proof.
Define M₂ z~y
By Cauchy-Schwerd Inequality, M1 S M2 By Lemma 12,
Ms - (2 - (2k)*
Also we have proved that 1 s 1/e. By definition of F(a), we calculate its first derivative as follows.
FF'(a)) <
(1)) le -m18 dr
(1x) -3112 + |x| mL) dx
M3 3p1 M₂ 3y4 - 1
<Ca/c² for some constant C4 > 0
Similarly, we calculate its second and third derivatives follows.
[a)( < (<)){ 11 dr
<M3 i M4 + 10p M3 10 + 5/ttM, 11d
<C3/e" for some constant C3 >
[a)) <
((>){> - 11l² dx
xc
= MM 7um M4 + 21 Ms 35 M4 35 -11 + +71M, - 14
<Cole" for some constant Cg > 0
Now ready to prove Lemma 4.
Lemma 4 (Quantitative Gap of Contrastive Mean). Suppose that Ja + b) 2 é. Then, for -o1e 82 /d,02 = 12 /d, the re-weighted mean of P, denoted as pa, and pagg satisfies
159
max (Iu T l. 1amll/e lu (az)) dc
for some constant > O,
Vulu,
JT Pas
=v Maz 0.
Proof of Lemma 4. For any 2 ks < d, for any a. by symmetry of q, the contrastive mean is
d-2
||| E
E c ax² x.
E
aa
z
200
avgg

---

Next we will consider
E edIlz|l? 2~P
21. For any x 2 0, we have
01q(201 + m4)
019( D01 + +111 4(-x)
((x) 1 - S g(z) dæ
Sa g(z) dx
Since P is product distribution, we have
e a-1
E a||=||
e
21
II
E ainig
e
F(a)
g-p
21-4
We will consider two cases depending on whether a' 2 0. See Figure 4.1.
Firstly, if a' O. We use 02 in this case. By Lemma 20, F'(0) 11.55/2 By Taylor expansion, there exists < no < 0 such that
F(az) = F(0) + a² + a (mo). 2
By Lemma 24, we know (T)) - C3/e9. Since F(O) = 0, we know for -c 2 /d,
a
F(a2) =a)F((0) +
F"(n))
2
C2
18.5
C26 42
C3
d
2d
e5
O7c
for some constant C7 > 0
Then we consider the case when a' >
0. By Lemma 23, we have either F'(0)
C2 log (1/e)
(0) > log (1/6)
34.3
Here we consider three cases with respect to (O)
Case 1: (0) <
C0. (1/e)
30.5
We use in this case. By Taylor expansion, there exists 771 such that
02 Th 0 and
a² 2 FM (m)
F(az) = F(O) + 02 F²
By Lemma 24, we know [F
Cs/e². By choosing a₂
Cze 42/d
a
F(a,)
F0) +
F")
2
C2 42
36.
O2e 42 Cs
d
(1/c)
2d
e
C 79
for some constant Cs > 0
Case 36.5 (1/e]
< " < F()
with some constant c, > 0. We use a2 in this case. By
d
Lemma 23, we know (0) > 34.5
3. / In (1/e). Then there exists 122 satisfying ag < 122 < and
a² p" (0) +
a pr (112).
F(oz) = F(0) 02 F' (0)
6
By Lemma 24, we know F (12) - Co/c². Thus by choosing 02 = - C2 12/dd
o FF(()
(0) + a FT)(1z)
F(o2) =02 F' +
2
6
42 (
77
22
24.
CZe Co
d
d
2d
In (1/e)
6d c7
119
for some constant Cg
d²
30

---

Case 3: (0 > se d
We use an in this case. Then there exists ya satisfying <m < 0 and
of (ma).
F(a:) F(0) + a, F ((
By Lemma 24, we know (1s) - C3/c². For a1 - // /d, we have
=a1 + af (ms)
2
c 82
C
ci 82 C3
d
d
2d
Ci0E
150
for some constant Co0 >
dc
Then we know for all cases, there exists a constant C" = min Cs, Co, C1o) such that
C59
max((((a))) 2
d
d-1
Finally we will lower bound
gan" kong
follows.
E
eazz
E amd
(1 + axz)) (1+)2²)
=1+
(1-
2 1/e
Let C' = /2/e, and we will get
159
max([u' Parb /u' pool)
d²
C.4 Quantitative Bounds for Contrastive Covariance: Symmetric Case
Before addressing Lemma 5 which is applicable in the scenario where |a + bl < cb, we first demonstrate that contrastive covariance works for the where the removed band [a, b] is symmetric around the origin. That is, a = -b. such cases, we aim to establish that there's a noticeable difference between the top two eigenvalues (Aı and A2) of the contrastive covariance matrix E, stated in Lemma 25. We will then extend the lemma the near-symmetric scenario in Section C.S.
Lemma 25 (Quantitative Spectral Gap of Contrastive Covariance Symmetric Case), Suppose + b O. Choose 0' = -c3e² for some constant 03 > Then, for an absolute constant C, the top two eigenvalues A1 2 d of the corresponding re-weighted covariance of P satisfy
A1 A2 2 Ce.
We recall the definition of moment ratio as Definition
(1, = var (X²)
Ma(t) - 1, where M²(1) = J. x= ((x) dx. (2
(Eg. X2)2
For simplicity, in the remaining section, we'll use mr(t) as a shorthand notation for this moment ratio. Just as in the proof of the qualitative bound in Section C.2, the difference between the first and second cigenvalues (the spectral gap) of the re-weighted covariance matrix, denoted as a Xg proportional to the difference in the moment ratio of the distribution y 0 and b, denoted as mr(0) mr(b). To prove the quantitative result Lemma 25, our proof strategy involves several steps.
Proving monotonicity of Moment Ratio mr(t). This property is stated in Lemma 3 and its proof is presented in Section C.2. The proof involves reducing the case of general logconcave distributions that of exponential distributions.
Establishing a positive spectral gap for small b. With Lemma 26, we focus on illustrating that for values of which are relatively small (less than a certain constant), there a guaranteed positive gap mr(0)- mr(b).
31

---

Generalizing to any b satisfying fa ((() dx 2 in Lemma 29. The lemma will directly imply the quantitative result lemma for the symmetric case (Lemma 25).
Having demonstrated the monotonicity of the moment ratio in Section C.2, we now begin by illustrating the positive gap, denoted mr(0) mr(b), for small 6 in Lemma 26. The proof relies on the properties of moments derived by the unimodality of the distribution (Lemma 27, Lemma 28).
Lemma 26 (Gap for small f), For & > 0 such that So ((x) da S 0.4, we have the following gap
mr(0) mr(() So ((x) dz
100
Proof. Denote So ((x) dx = So x² 22)(()) dr w. Then we have
mr(0) mr(t) (0 (o(t)Ma(t)
(0
M2(1)
l x d1(()) do 2(w + M2(1))
Ma(t)
G 12--) (a)
-2
(2
2 ( x x²((1)))))))))))(())) dx +
Mt(
1
1 + 22
(12
2
(1
w (2
Fix (()) and v, we apply Lemma 27 and have
M2(1)= v 2² 1 2 - -
-v
(t)t
Since q(r) is monotonically decreasing, for any S 1, (x)( (t). So we have the constraint that
f ((x) dr 2 t9(1)
Plug into the previous inequality and get
M2(1)= N 1
-w)
1 )-w))
[ v)
2 v
1 2
t
12
1
d())
v 12
1
v
v
2v
In addition, by fixing and we apply Lemma 28 and get
So know
2y²
3
M2(
v)
1
3 3 v)
24
By calculation, we will get
1 v) 2
2 (1 1) ( 3v + 202)² 2
1 1+ 2v
>
w (1 + Ma(2
( 3v + 222)²
2
4 4 1 2
v)
3
29
v
9
2 - v
- 2
3v + 2v²
2
(-8v² + +4 300 + 9)
9 2 1/
v
Let T(v) 38y3 + 24x² 30v + 9, then we know its derivative is
T'()) 2 + 48v
30
-24(v 1)2 6<0
32

---

So T(z) is monotonically decreasing. Since // < 0.4, we know
1 2
T(²) 2 T0.4) > 0.3,
0.1
Plugging in and we will get
1 + 2v 2 v. 0.1 0.3 0.01
9
M2
Finally by Cauchy-Schwand Inequality, we have Mo(1) 2 MZ(1).
mr(0) -mr(t) 2 2M2(t)
M1(t) 0.01v 2 (1)
V V
100
Lemma 27. Let 1 0,0 < 8 1. Define P (p(x) (0) [0, logconeave (a) S
0, Se p(x) dz ptt r.. Then we have
p(p( de 2 st? (1+ 8 rt
min PEP
Proof. For any E P, we denote M2(p) = Seee x²p(x) dx. Define
u(x) r sgje,t+a/rl
Clearly P. We will show that u(x) argminpep For any p E P, we have J. u(x) dr = Sr p(x) dæ, u(t) = p(t) and px( I O. So we know the graph of u and intersects at points and + s/r, where u(x) 2 p(x) in the interval [1, s/rl and u(x) p(x)
outside the interval. So we know
I. petelr
u(x) - p(x) dr = f p(x) u(x) dr
Jete/r
Since for any x E [t, + s/r], any y E [t s/r, oc), we have x S y. So we have
M2(u) - M2(p) = 1: plaar (u(x) p(=x))=² de - -
30
(p(x) - u(x))x² dr < 0
Lto/r
This shows that
min M2(p) = M2(u).
PEP
By calculating M2(u), we have
Mp(p) = M2(u)= = f PEP
f/-//r
rx² dr = r(t2" + 8²
3rd 2 st? (1+ 8
min
+
p2
rt
Lemma 28. Let t > 0,0 < 8 <
Define = (x(x) : [0,t] + [0. 1), logconcave, p'(x) s
0, S6 p(x) dx = s}. Then we have
[' x²p(x) dx st2
max pEP
Proof. For any p P, we denote M2(p) = So x²p(x) dr. Define u(x) = -r Clearly, P. Then for any p E P, because it is monotonically decreasing and f p(x) dx fe u(x) dr, the graphs of and intersect at point E [0,t], Also p(z) > u(x) for E [0, and p(z) u(x) for x E f.. Since for any x E [0, and any y E [1, t). we have x S y. So we know
M2(p) MM(()) = f <2(((x) - u(x)) do S <2(x()) - p(x)) So
33

---

By calculating M2(u), we have
M2(p) = =M2(u) {-² x dr t3
81
st?
max pEp
3
Using Lemma 3 and Lemma 26, will show the positive gap mr(0) mmr(b) for any b satisfying [_,g(x) ((x) dx 2 e as in Lemma 29.
Lemma 29 (Gap for Log-coneave Distribution). Ler 0 < c < 0.1, ler b > 0 satisfying So 2(x) de 2 e/2. Then we have for mr(0) mr(b) 2 e/200.
Proof. Let by such that S g(x) dx e/2. By Lemma 26, know
Jo ((x) da
mr(0) - mr(bb) 2
2
6
100
200
By Lemma 3, we know mr((t) - 0, v4 2 0. So for any b > 0 such that So (())dr 2 6/2,
mr(b) & mr(ag). Therefore,
mr(0) mr(b) 2 mr(0) mr(bo) 2 200
Before moving to the proof of the quantitative lemma, we will first present helper lemma that can be directly applied. Lemma 30. Define
S(a) = E and
é
aa
x
E azz
E x--q
az x
E
ax
(C.3)
xm
For a given a -C with and certain positive constant e, can be established that
S(a) Ce where C is positive constant.
Proof. We show the lower bound of S(a) using Taylor expansion. Firstly, since and q are both isotropic.
S(0)
= E x~
x²
E
Secondly, we will lower bound (S)) using the monotonicity of moment ratio. The variance of of restricted [-, is
of 1 x² 2²p(x) dr
M2(b)
S p(z) dx
Ma(b)
Since q is isotropic, the density on the support R R b/o b/bb// is σ1 (1q(Z0))
PP(x))
2 25 <(0) dx
By calculation, we have
2 2 eau² s'orp(oo) de S(a)
2 b/a ear aip(zo1) do
2 loe car? g(x) dx
2 lre cazz
cax2 22(22)(()) dx
2 g(z)dz
2 2 g(z) dx
2 l /o? o / dy
2 2 e /o? q(v) dy lo e end x²9(x) dx
fo ax q(2) dr
S (()) dx
Jo g(x) dr
34

---

oi Jo end l g So em q(x)) dx - -2000 c (o0l))((())))))))))))))))()))( dy So e~ x²q(x)) dz
S6 (()) do
Then we can compute (0) as
2
1
dy So q(x) dx + 1. saal)d So x²a(z) dæ
S'(0) o J (0)) de
01 ..
2
1
s dy I x²q(x) dx + 1 ((v) dy / 2'q(z) dr
Jh ((x) dx
0
2M (b) 2M
(2)
.M (o.b) M(00)Mo(0)
(b)
M2
mr mr
The last step is because the q is isotropic. By Lemma 29, mr(0) mm((b 2 c/200. This indicates that S'( - -c/200
Next, we can upper bound (a) for any a S as
11 of
1. eav" cas" g()) dy l0e caxe ((x))
(*(a)=
dx
Jo p(z) de
c coonloin (
dy IS e (() de
cas'
0 1c cax" eaxa Ag(a)) de
o
b
q(v) dy 10 eas' p q(()) dz
2
(22())MM(0)
Mo(b))M(()) M2(0)
Mo(b)
2
(M4(0) + Mc(0))((0))
Mo(b)
By Cauchy-Schwarz Inequllity (0) S / M2 = 1/2. By Lemma 12,
(x < (2M)
(2 (0))*/2 < (2h)*/2 /2
Since Mo(b)= 2 c, for some positive constant Csecs
(*) 2
Cssc
c
By Taylor expansion, we know for a3 CE" , c 1,00=1/1 there exists a' E [a, 0] such that for some constant C' > 0,
a S" (a') 2 0 "
c²e2 Cssc
S(a) =S(0) + +as -())=
e
> C+#11
2
200
2
e
Now we are ready to prove the contrastive covariance lemma (Lemma 25).
Proof of Lemma 25. Define
S(a) == E
e
au²
2
E. o00?
E
x² E
and xng
rwg
gnd
35

---

Then for s
eall
eallz!l
E
27
Dnj
xnp
d-2
E
e
e
11
E
E
e
a
x
E
aaai
E
gao?
21
22
22-4
E
ea||=
of
=S(a)
enai
2
E 3
21
m2m4g
Since 03 < 0, we have
S E oी =,
a
m
zin0g
m2
By Lemma 30, az = egt² implies that S(ar)) > Ce So we have
E
aall
E TmP
Ce
E a~p
aall
amp
Finally we will show that the first eigenvector corresponds to For any v E IR define @(v)
Tu
V xx
Φ(v) = E
V v
Then know for و d.
M())) - p(e,) > Ce3o(e))
For any vector v Ed
2i=1 7e4 we have
Φ(v)
2e
)
2
(e(()) al
Σ
> 1=
2
1=1
(
Σ
1/ ((e)) + Σ
w7s Ee Exers "i Ee (( 2s E Ee (zr,))) x3
Σ1= 7
1=1
in
2im1 (7((e))
nd
Di ??
<σ(e1)
This shows that the top eigenvalue of Σ is \ = max, d(u) = Φ(e1). In other word, the top eigenvector 61, which is essentially u. Similarly the second eigenvalue of E is X2 = max le ((v) o(e,), S < d. So get
A - C
C.5 Quantitative Bounds for Contrastive Covariance: Near-Symmetric Case
We have shown the result for symmetric case a- b 0 in Section C.4. Here we will show that we can extend the contrastive covariance lemma (Lemma 25) to the near-symmetric case, where |a + bl < cb. In this section, we will present proof of Lemma 5, which addresses the nearly symmetric case quantitatively. The proof idea is to approximate the re-weighted covariance of the distribution with margin la, b). by comparing to the same distribution truncated with the symmetric interval [-b, This enables us to generalize the result from the symmetric scenario to the near-symmetric scenario.
36

---

Recall that ğ is the distribution obtained by restricting to the set Ra b]. We denote F as the distribution that obtained by restricting q the set IR [- bj. and f as the isotropized distribution of r. Let o3 be the variance of P.
To approximate the characteristics of using those of i; we undertake the subsequent steps. Assessing the mean. We illustrate that the mean of q adequately small in Lemma 31.
Variance approximation. We approximate the variance of by using the variance of f, as elaborated Lemma 32.
Re-weighted second moment. We use the re-weighted second moment of to approximate the corresponding moment in q. The details are provided in Lemma 34.
Re-weighted zeroth moment. We use the re-weighted zero moment of f to approximate the corresponding moment in q. which is shown in Lemma 35.
Lemma 31. For an integer 8 2 1, if a + bj < ++1 then
(1) the mean of q. |uu| E" In(1/e);
(2) a < O.
Proof. We first consider the case when a < By Lemma 8, we have
Ja xg(xx) dr
b S ((x) de
b(b + a)
S
lnd ((()) de
S_ ((x) de + So ((x) dx
2c
By the tail bound of logconcave distributions (Lemmaa 11),
||| < 1 Il
Then have
|ull < (1 + In ))
E In(
2e
Next for a 2 0, we can bound by e+1 because |b| 2 |a]. This implies that - a < e0+1/2 /2, which leads contradiction that 1o ((x) dx Therefore, only be negative in this scenario.
Lemma 32. For |pr| S with 1/6, we can bound the variance as follows.
o
1 2er S of 0
Proof. By Lemma 31, we know a < O. We can calculate the variance as
of S 2z dr
of xzg(z) dr + 1/ S x² (q(x) dr
300
1 q(x) dx
So ((x) dn 5 ((x) dr
On one hand,
- = dx
12 l g(ag)
dx
S {(z) dx Jo q(x) dx
fe x2q(2) dx
b² lo q(x) dx
So we have
f x2 de
of
+ 21 2'g(z)
02
- g(z) de
1 + 2 ((x)
On the other hand, since 1ua| < r, by Lemma 8.
Sh. xq(xx dx
55 q(z) de
|u1= = 1 ((x) dr + 25 ((x) dx 1th ((x) dr + 2 9(x) dr
37

---

So we have
+ I q(x)
S g dx
2 J. q(a) di
or
1 1 +
< <1 2er
S x)g(z)
2 g dr
--
1 2 22))
Lemma 33. The variance o is monotonically increasing with respect to b. Furthermore, o3 2
Proof. By taking the derivative,
00
q(b)
(b² [. g(x) de - f, d2((z)dr)> >
0b
U6 ((x) do)2
So for b 0,
000 x² (() dx
0
Jo ((z) dx
Lemma 34 (Approximation for Re-weighted Second Moment). For la + bl S e,, by choosing αe,, then for some constant C' O, we huve the following inequalities.
{ an 102 gly) dy Ce S f 1ov dy
{- 1o2 dy (C.4)
b
ann't 1o ( dy - Cee S [ /
3 1o
c /0 102 gly) dy + C
bb
(C.5)
Proof. By Lemma 31, we can bound |41| as
1 < e |Mal < e
We begin by showing that S e /o32 q(y) dy is close to 1 ean (o)) dy. By Lemma 32,
of
S of <
1 2
Since O, ayy//0 an² /03 for y > 0. This implies
f c /ovi 1 dy $ / cav 102 g(v) dy.
On the other hand,
6 ay 103 (() dy of 22 9(1) dy
av 102
(a02 112 )(2)) dy
<
11-e
200g "r / dy
2c
20 //d ( dy
2e/a|e
(a(l)/())))) dy
2e|a|e²
noo
y²q(3) dy
02
38

---

2e|ate"
* /2
02
8ecr
02
The last inequality is implied by Lemma 12. Furthermore, by Lemma 33, o 2 1. So there exists constant Cj > 0 such that
I. (o q(v) dy cie I." ) dy S (- 1o dy
(C.6)
This also applies for the integral from a to oc. To be specific,
[ ad 1o jo2y² (ly) dy CIE² &
I 1 1 a(v) dy S I car 1 dy.
(C.7)
Next we will show that I ea i g dy and Js ca(o-wi) Po dy are close to each other.
Since μl < 0, a < O, we derive that ay² > aly - 21)². This implies
[ an 1op (()))))) dy > /o polo-m)?//e p
On the other hand,
c 10 (() dy 1o p a(v) dy
11- -lalla (laol)+ttooww//o] w// cav? 9 dy
la/ll
(
(y (m (onl))q(u))))))))))))))))) g(v)
dy
of
lauil
/ (y ( dy
of
Saze
for some constant C2 >
The last inequality is implied by Lemma 12 and Lemma 33. Combining two inequalities, we get
( av lo? f ((y) dy - L. cols-m)) g S I eay fot /0))))(()))))))))))))))))))))( dy (C.8)
Similarly, we will show the approximation inequality for 1 / dy. We will decompose the integral by the summation of the integral on [-a, 6ln(1/e) and (6ln(/)),,o) respectively. For the first part of the integral,
6ln(1/c)
(lm(11e)
colttu)/ob 9 dy
100 dy
(n(c/))
(e - ( -1)
"² v²9(v) dy
M1/2
co 10?
(1-e (2xtwu)) g2(( dy +
(1m(11e))
eav/ ( 2n1 (20+m1)
-1) 8 g0)( dy
c
-M1/2
The first term can bounded using e - > 1-
[ P2/2
a lo?
221 (29++1)) 1 11-e
9²2(v)) dy <
12112
at1
(-2y 11)32a(u)) dy
J-a
of
11/2
<
|a|lm] 22 dy < c
39

---

The second term can be bounded using the upper limit of the integral. For y - 61n(1/e),
Tan (2yt/1)
-15 22 (1/e) S 40
Substituting into the second term, we get
-px/2 e ou (2ptt)) - s2((v) dy S 40c S/¹ s'a(v) dy 206
6lu(1/e) end lof
Combining both terms,
(n/e)
Bln(1/e)
alltt)))/ dy I
/ (()) dy 21 (C.9)
For the remaining part of the integral, can bound using logconcave distribution's 's upper bound as in Lemma 13. For any 2 3,
(t) S (0) 2 cg > 0.
t/3 < e t/5
Then the following holds with some constant
gop2/ogg2 dy v
v/3 dy S (1 + 6 1 ))e GGl((t) S Eg
(C.10)
6 (l(///)
blu(l/c)
Similarly, we get
p a(1) dy S cgc
(C.11)
Gla(1/e)
With Equations (C.9), (C.10), (C.11), we get
VSe00 clu-m))/ot qql) dy L ca o ((v) dy ege for constant es 0
(C.12)
Combining Equations (C.6), (C.7), (C.8), (C.12), we have
Jo
mn /0 ( dy (c) 02)e < fee coo-mi of (2 dy S (o io q()))) dy
c 1032103 dy (c1 + ca)e $ L colutt))(/o ((()) dy S (
100 c00d 1o0) dy + cac
By choosing C² = é1 + 02 + Cs. we prove the lemma.
Lemma 35 (Approximated for Re-weighted Zeroth Moment). By choosing -c62 for some
constant C' O, we have the following inequalities.
and ( dy Ce $ Lee ely-m1) ((y))( dy S
1 000
jo dy (C.13)
[ av' /03 (()) (0g(/))))))) dy Ce < I xc
cdlttiillo p(v) & f ( d Ce (C.14)
The proof follows exactly from the proof of Lemma 34 by replacing y² with 1. Now we are ready to prove Lemma 5.
Lemma 5 (Quantitative Spectral Gap of Contrastive Covariance). Suppose that la + bl < é.. Choose
ag = -Cye² for some constant ca > O. Then, for an absolute constant C, the top two eigenvalues
A 2 X2 of the corresponding re-weighted covariance of P satisfy
A1 A2 > Ce2A1
40

---

Proof. By calculation, we have
Jojoz ea ='ooq((00)) dr Jo lo dy of fe (()) dx
E
ca
x²
g()))d
(a-Hi)/o1 ea x² 01010001 + 1n) dr + fa m(b- exx x² 02019(101 + p1) dx
east
x²
00
S (() dc + J (()) de
S" co(N-11)9/01 (y 11) q(v) dy + Sh cov-m))/oi p1) dy of (()) de + S q(z) dz S ( /0f m4 (ul) dy 1 c (1- dy
of q()) lo ((z) dz)
(ay ( ' c m ( dy
of (()) de + ST ((x) dx)
en( ya(v) dy So calv-m) / yd(,) dy (
2p1
(()) dr + So ((x) da
/ / g(y) dy + So calv-m)) q(v) dy
+
of
S de + So q(z) dr
The first term is close to the bound on the absolute values of last two terms. Since < O.
E cn x² while the second and third terms are close to zero. We first give and
e cdtt /0t yg(v) dy - Jo co(--11)/03 yg(v) dy
coltt /0olt yd(y) dy + calv-ni)/oi y dy
yd(v) dy + 1 valu) dy <1
Similarly,
/ol ((v) dy S.e calo-mi111o g(v) dy <
By Lemma 32, Lemma 34 and Lemma 35, we have
S ca(vtai) /ot y (lv) dy + Sh ellomm))/
of [ ((z) dx + 1h dz))dx)
2000 canz i q())) dy + C ++ 2ee
2 dyy)
of
0o c l dy
C
22 2 102 q(y)) dy + C
+
Th q(v) dy
022 Jo g(v) dy
of
2 2 000 q(v) dy
c / 9 dy
+ t for constant > 0
J q(v) dy
By combining with the second and third terms, conclude that for constants C3, C4 > 0,
E goof
e ax² _2 - C3E" < E ax
x2
< E E
ax²
x²
+ cye"
(C.15)
41

---

Similarly, we have
c E amo
-
Cye
<
E znd
cnn?
<
E
+ C,e
(C.16)
Then, we would like to compute the gap between first and second eigenvalues of the re-weighted second moment of q. We denote Q the product of and d - fold of q. For 2 i d.
E
aallall x
E
ea
ealll
mll
2
E B1ng
e
aui
E
cozz
E e x2
eaz
E eaui Bing
(
E caxt 20g
d-2
22-4
We define T(a) as follows.
T(a) = E
c
2
E
c
E
a
2
E
21
22
ag@gg
Recall that S(a) is defined in Lemma 30.
S(a) = E
E e
E 22-0
2
E e
m
z1
We calculate the difference between T(a) and S(a) using Equation (C.15) and Equation (C.16).
S(a)- T(a)
E e ar E zin4
E
car
E
E
E m2m0
2
BINF
22-0
25 m
Sezer + csed
By Lemma 30, S(a) > e for constant > 0. So we know T(a) > Ce for C> 0. Then all
proof follows as same as the case when b = 0. We write out the proof for completeness.
For S S
E P
e
2i
2
xj
E
az
2
E
ann
E
a x²
cast
(
E car²) aan
d-2
zing
x2
21
E
aa
xx|
2
=T(a)
E
E fanz
mz
Since 0g < 0, we have
E
1
2
<
E
=
1,
E
e
<
1.
21 m
x2
Also we have shown that ((as) Ce3.
So we have
E
||
E
ا||ا||
Ce E a
T~P
T~P
D~P
Finally we will show that the first eigenvector corresponds to el. For any v E IR define d(v)
@ Po
To
To
Φ(v) = E
TT
P~P
Then we know for 2 25isa d.
((e)) - p(e,) Ce ((e))
For any vector Σd
Me, we have
((v)
B ag la|
y )2
Σd i= ??
42

---

Σ ((o(es) + 2E
Σ
Σ 1i=1 1
d
itj
1
Σ (((()) +2 Σ
my Ee Eners ot caleee)) E e zz
Σ ?
Σd
1i=1 16
Σi=1
<Ø(e1)
This shows that the top eigenvalue of E is d = maxx g(v) = p(ei). In other word, the top eigenvector is e₁. Similarly the second eigenvalue is 22 max Φ(v) = o(e,), i d. So we get
\ ~ > Ce X1
43


Reviews:
[{"review_id": "S2VIuDamEV", "reviewer": "Reviewer_efHe", "summary": "This paper studies the unsupervised learning for high-dimensional halfspace under affine transformation. The goal is to estimate the normal vector of the halfspace such that the learned distribution is close to the underlying truth. The paper provides an algorithm using so-called ''contrastive moments'' with sample and time complexity guarantee.", "questions": "- Are coordinates of $P(Q)$ independent with each other before the affine transformation?\n- Can author(s) provide an real data application example for the problem setup in Definition 1, and specify the the roles of $q,Q,d, P,u$?", "limitations": "No limitation is discussed.", "rating": 6, "confidence": 1, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "- The algorithm provided achieves polynomial dependence in $d, 1/\\epsilon, 1/\\delta$ for both time and sample complexity.\n- Existing literature relies on supervised learning, or Gaussianity of the distribution, or NGCA and ICA. While this paper only requires log-concavity.\n- Techniques introduced, e.g. contrastive moments, might be of independent interest.", "weaknesses": "- The product and isotropic distribution with affine transformation assumption seems to be restrictive, can the analysis or algorithm go beyond that?\n- The presentation of the problem is hard to follow, might need more explicit mathematical definitions. For example, where is $\\tilde{P}$ in **Problem** defined.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the feedback. Regarding specific points:\n- **W1**. We clarify that our algorithm does not assume that the data is isotropic. We assume that samples are drawn from a distribution obtained after an (arbitrary) affine transformation of a product logconcave distribution. Both the underlying distribution and the affine transformation are unknown. This family is significantly more general than the Gaussian setting considered in prior work. Since no labels are given, there needs to be a (strong) distributional assumption to uniquely identify the underlying halfspace. \nWe hope that future work might further generalize these results and techniques.\n-  **W2**. We will try to clarify the presentation as much as possible.\n$\\tilde{P}$ is defined as the distribution induced by the normal vector $\\tilde{u}$ output by the algorithm along with a margin. We will make this explicit.\n- **Q1**. Yes, the coordinates are independent of each other before the affine transformation. But since an unknown affine transformation is applied, they are not independent in the given representation.\n- **Q2**. Describing the setting in Definition 1 using real-world data applications is challenging due to the disparity between theoretical constructs and practical realities. We illustrate with an example where $q$ represents a standard Gaussian density, where $q(x)=\\frac{1}{\\sqrt{2\\pi}}e^{-x^2/2}$. Let $d$ be the dimension.\nThen $Q$ refers to the density of $d$-dimensional standard Gaussian $N(0,I_d)$. Given $a<b$ (endpoints of a margin in one dimension),\n$\\hat{q}$ is obtained by isotropizing a truncated standard Gaussian density. Given a unit vector $u\\in\\mathbb{R}^d$, let $P$ be the product distribution with density $\\hat{q}$ along with $u$ direction and $q$ in all directions that are orthogonal to $u$. Then we apply an unknown affine transformation to $P$, and get $\\hat{P}$, which is a general Gaussian distribution with a margin normal to an unknown direction $\\hat{u}$.\n"}, {"review_id": "Flkmm3jmSL", "reviewer": "Reviewer_6stc", "summary": "In this work, the authors study the problem of unsupervised learning a halfspace. In their setting they have a continuous distribution (isotropic-log-concave) and they remove $\\geq \\epsilon$ mass from an interval $u\\cdot x\\in[a,b]$, and their goal is to find the half space that separates the two regions. Their idea is basically to reweight the samples and use the first two moments to find the unknown vector.", "questions": "545-546: Is this part of the proof ok? The distribution is no longer symmetric after removing the mass.\nI think this problem is closed related to learning with truncated samples. Maybe the authors should comment on this/add related work.\n\ntypos:\n550: I guess you mean that the directions are uncorrelated as after removing the mass and rotating this is not a product distribution but it is true that the directions are uncorrelated.\n529: there is a missing number.", "limitations": "no limitations.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Well written and easy to follow. The authors provide experiments a proof of concept. This is a nice problem and it was not studied before. Even if the method of attacking this problem is what someone expect, still I found the results intersting. ", "weaknesses": "1. The distributional assumptions are strong. They consider a product of the same log-concave distribution and also they assume that this distribution is symmetric. \n2. Some steps that are trivial are over-simplified where some other steps that are not easy to follow are not explained, especially in proof of lemma 4.\n3. The results are not tight as is needed a high polynomial on $\\epsilon$.\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the feedback. Regarding specific points:\n\n- **W1**. Our data distribution applies an unknown affine transformation on the product logconcave distribution. So the input data itself is neither isotropic nor a product distribution. We note that the two prominent special cases are product distributions (ICA) and Gaussians with margin. As far as we know these are the first results even under these restrictions (some form of which is necessary to guarantee uniqueness of the learning problem).\n\n- **W2**.  See responses to Q's below.\n\n- **W3**. The results are not tight in $\\epsilon$ and our experiments (Figure D.2) suggest a linear dependence on $\\epsilon$. Our primary goal for this paper was to prove that the sample and time complexity of the problem are polynomial. We agree that getting a tight bound is an important future goal.\n\n- **Q1**. In any direction orthogonal to the halfspace normal vector, the contrastive mean along the direction is zero by symmetry. Specifically since the underlying distribution $P$ is a product distribution, all orthogonal directions are independent. Removing slices in one direction orthogonal to all others does not affect the symmetry of orthogonal directions.\n\n- **Q2**.  Lemma 4 considers distribution $P$ (product distribution, before affine transformation, see Definition 1 or Figure 1.1(b)), instead of $\\hat{P}$, obtained by an unknown affine transformation of $P$. In fact, the Isotropize step in Algorithm 1 turns distribution $\\hat{P}$ to $P$.\n\n- **Q3**. We thank the reviewer for pointing this out. There is a missing number in line 529. It should be\n$$\nH(0)> \\frac{C_1 \\epsilon^{17.5}}{\\log^5(1/\\epsilon)},\\text{  for constant }C_1>0.\n$$"}, {"review_id": "Q8HoHiB8vz", "reviewer": "Reviewer_Ua7t", "summary": "This work addresses learning a halfspace with margin from unlabeled samples (which is possible due the combination of margin and distributional assumptions). They impose that the ambient distribution is an affine transformation of the d-fold product of some 1D symmetric log-concave distribution, conditioned on one coordinate lying outside of an interval with mass at least $\\varepsilon$. They provide an algorithm for recovering this distribution up to TV error $\\delta$ with time and sample complexity $poly(1/\\varepsilon,1/\\delta,d)$, based on analyzing the first two moments of a certain exponential reweighting of the empirical distribution.", "questions": "- The results are stated for non-singular affine transformations. What happens as the transformation approaches singularity? Given that there appears to be no breakdown in the run time bound in this regime, the non-singularity requirement was surprising to me", "limitations": "Yes, authors are clear about assumptions and potential impacts.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- The paper was generally well-written and organized. The proposed algorithm is easy to implement, and its analysis requires some clever new techniques.\n- I appreciate the initial simplified lemmas; they allow the reader to understand main ideas at a high-level without getting bogged down with the full details.\n- Approaches for this problem based on previous work would seem to require Gaussianity and fail to provide as strong recovery guarantees in polynomial time\n- Experiments validate their algorithm on Gaussian and non-Gaussian data", "weaknesses": "- The notion of margin seems a bit non-standard. Can the authors relate this to the standard notion (or refer to an existing example of this usage)?\n- The proven time/sample complexity, while polynomial, is quite slow\n- While the authors suspect that improved guarantees are possible for the same algorithm, it would be preferable if they could support this conjecture with experiments; the current sample sizes are quite large\n\nMinor Nits:\n- Some inconsistency in Sec 3 for whether $\\hat{q}$ is isotropized or not (it mostly is, but not in the warm up)\n- Inconsistency between single bars and double bars for the Euclidean norm (e.g. Lemma 1 uses both)\n- Inconsistency between $\\mu_i$ and $\\mu_{\\alpha_i}$ in Sec 3\n- Line 214, clause beginning with \"Since\" looks like it should be combined with following sentence\n- Line 217, should be for $x \\geq 0$?\n- Perhaps the rule of signs should be stated in the integral form for which is applied? Also, it would improve readability to mention the u-substitution used to eliminate the square in the exponential\n- Line 225, $F'(0)$ is a scalar, doesn't have a root, same with $F''(0)$ (presumably should just be $\\alpha$)\n- Line 226, doesn't $F''(0) \\neq 0$ always hold?\n- Equation after line 240, would match previous notation to use $\\hat{q}(x)$?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the careful reading of the paper and the valuable suggestions. Here are specific responses: \n- **W1**. In the literature, halfspace margin is defined as the distance between the halfspace and the data points closest to the halfspace (support vectors). In our setting (Definition 1), the margin is $(b-a)/2$. \nHere we require the density $q([a,b]) \\geq \\epsilon$.\nFrom the the property that the max density of logconcave distribution is upper bounded by a constant, we derive that\nthe margin in our setting is at least $\\epsilon/2$.\n\n- **W2&W3**. The time and sample complexity in our analysis, though polynomial in $d,1/\\epsilon$, has a high order of dependence on $1/\\epsilon$. We conjecture that the dependence can be improved.\nExperiments in the supplementary material on three representative logconcave distributions --- uniform, gaussian and exponential distributions ---  indicate that the sample complexity is possibly linear in $1/\\epsilon$ (Appendix Figure D.2). \n\n- **M1**. We apologize for the confusion caused by the inconsistency between the warm-up case and general case. We will have a separate warm-up subsection to avoid inconsistency.\nIn the warm-up case (isotropic isoperimetric distributions), $\\hat{q}$ is not isotropized. The algorithm used here is PCA, which\nis different from Algorithm 1 and we do not have the isotropize step.\nFor general distributions, the notation is consistent with Definition 1. \n\n- **M2**. We use single bars to denote the absolute value of a scalar, and double bars to denote the $l_2$ norm of a vector (line 197). In Lemma 1, the correct formula should be\n\n    $\\max(|E_{x\\sim P} e^{\\alpha_1||x||^2}u^\\top x|,  |E_{x\\sim P} e^{\\alpha_2 ||x||^2} u^\\top x|)> 0.$\n\n- **M3**. We thank the reviewers for pointing out. We will consistently write $\\mu_{\\alpha_i}$ to indicate the re-weighted mean by choosing $\\alpha_i$.\n\n- **M4**. Line 214, the whole sentence should be as follows.\n\n    We treat $F(\\alpha)$ as the integral of $a(x)e^{\\alpha x^2}$ for $x\\geq -a'$. Since $\\hat{q}(x)-\\hat{q}(-x)>0 $ for $x> b'$, we have $a(x)> 0$ for $x\\in[-a',b')$ and $a(x) < 0$ for $x> b'$. In other words, for increasing $x$, the sign of $a(x)$ only changes once.\n\n- **M5**. Yes, it should be $x\\geq 0$.\n\n- **M6**. We thank the reviewer for the suggestion.\nWe will complement with the integral formula of the Descartes Rule of Signs that we can apply to. To be specific, define\n$F(\\alpha) = \\int_0^\\infty a(x) e^{\\alpha x^2}dx.$\nThen the number of roots of $F(\\alpha)=0$ is at most the number of sign changes in $a(x),x\\geq 0$. \n\n    We sketch the proof here.\n    The theorem can be proved with induction on the number of sign changes. Let one of the sign changes occur at $x_0$. Let $F_0(\\alpha) = \\int_0^\\infty a(x) e^{\\alpha (x^2-x_{0}^2)}dx$, which has the same zeros as $F(\\alpha)$. By taking a derivative, we get $F_0'(\\alpha) = \\int_0^\\infty a(x)(x^2-x_0^2)e^{\\alpha (x^2-x_{0}^2)}dx$. The new sequence $a(x)(x^2-x_{0}^2)$ has one less sign change than $a(x)$. By a lemma stating that the zeros of a function is at most the zeros of its derivative plus one, we can complete the inductive step.\n\n- **M7&M8**. We apologize for the confusion in the proof idea of Lemma 4. In fact, for both $F'(0)$ and $F''(0)$, there exists pairs of $(a,b)$ that makes one of them to be zero. However, we can show that $F'(0)$ and $F''(0)$ cannot be zero at the same time (Lemma 24). The detailed proof is in the Appendix (starting from line 545). \nThe proof idea of Lemma 4 starting from line 225 should be as follows.\n\n    By taking the derivatives of $F(\\alpha)$, we can show that either $F'(0)\\neq 0$ or $F''(0)\\neq 0$. Then by Taylor exansion, we can choose two distinct $\\alpha$'s (near zero) so that one of the corresponding contrastive means is bounded away from zero.\n\n- **M9**. Yes, we use $\\hat{q}(x)$ to denote the isotropized density  after restricting $q$ to $\\mathbb{R}\\backslash[a,b]$ (Definition 1) in the whole paper except in the warm-up part.\n\n- **Q**. We thank the reviewer for this insightful question. \nWe require the non-singularity of the affine transformation mainly because we would like to preserve the margin after the affine transformation. What we really need is that the affine transformation does not collapse the margin direction. \n"}, {"review_id": "OPbZc4VSFd", "reviewer": "Reviewer_YLvd", "summary": "This paper proposes a non-standard approach to the problem of learning halfspaces, where instead of labelled samples, the learner only receives unlabelled ones as well as strong prior information about the unknown distribution. In particular, the marginal distribution is assumed to correspond to some affinely skewed product distribution, with identical components except from one which is truncated outside some interval. The unsupervised distribution learning problem corresponds to a supervised learning problem when the labels are determined by a halfspace in the direction of the truncation.\n\nThe main result shows that when the truncation region is wide enough but not too wide and either symmetric or bounded away from being symmetric, then the direction of truncation can be discovered efficiently from unlabelled samples. The algorithm exploits standard ideas from distribution learning (data normalization, PCA and sample re-weighing), but its proof involves careful application of appropriate tools.", "questions": "I would be interested to hear any comments that the authors have regarding the points (1,2 and 3) I made in the weaknesses section. Moreover, I have the following suggestions regarding the presentation.\n\n1. The problem definition (page 2) needs to be clarified further to avoid confusion. In particular, it is not clear what is known and what is unknown. For example, does the learner know $q,a$ and/or $b$? \n\n2. How does the paper [DK'22] compare to your results? On a more general note, I think it would be beneficial to present in section 1.2 some result on NGCA (e.g. [DK'22]) more concretely, as well as some result on supervised learning and emphasize the trade-offs when considering the problem proposed in this paper.\n\n[DK'22]: Diakonikolas, Ilias, and Daniel Kane. \"Non-gaussian component analysis via lattice basis reduction.\" Conference on Learning Theory. PMLR, 2022.\n\n3. Some typos:\n- Line 105: double \"the\".\n- Line 106: \"follows uses\" $\\to$ \"uses\".", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The paper proposes and studies an interesting connection between unsupervised and supervised learning. Moreover, I appreciated the technical work required to prove guarantees about the main algorithm, even though it is based on simple and clean algorithmic ideas.", "weaknesses": "There are several concerns I have regarding the setup, the impact and the results. In particular:\n\n1. While the model demonstrates an interesting connection between supervised and unsupervised learning, if we focus on either of these aspects, it seems less relevant. For supervised learning, the distributional assumptions are too strong (usually one either makes strong assumptions on the marginal distribution or assumes the existence of margin, but not both). For unsupervised learning, the component we want to discover is too specific (instead of a general property, like matching some Gaussian moments, it is assumed that the component is just a truncation of the distribution of the other components).\n    \n2. On the algorithmic level, the impact seems to be limited. Variants of the algorithm presented have largely appeared in the literature for similar problems.\n    \n3. The main result (Theorem 1) does not seem to be completely accurate. More specifically, there has been no account for the case where the truncation region $[a,b]$ has $|a+b|>0$ but $|a+b|\\approx 0$ (e.g., $|a+b| = 2^{-d}$). While Lemma 4 accounts for the case when $|a+b|$ is large enough, Lemma 5 only accounts for the case $|a+b|=0$. It is not clear what happens in between. In Figure 5.2, it seems that Lemma 5 could be generalized to capture cases when $|a+b|$ is positive but bounded. However, this has not been proven.\n\nOverall, the paper seems to have important unresolved technical issues and also it could highly benefit by relaxing the distributional assumptions. I would encourage the authors to continue working on the paper, but in its current form, it is below the acceptance threshold.\n\n-- The authors fixed an important technical issue in their proof (item 3 above) and I have increased my score (from 3 to 5) to reflect this.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments. Here are specific responses:\n\n- **W1**. We are solving an unsupervised learning problem --- there are no labels given. This inherently requires assuming structure on the underlying distribution to be identifiable. Halfspaces *with labels* can be learned with no distributional assumptions. However, margins, and special distributions are both considered in the literature either to improve sample complexity or in more involved models such as active learning, agnostic learning and multi-task/lifelong learning. For learning without labels, prior work is centered around ICA and NGCA; in both cases there is a product distribution to be identified and this is done with moments. In the latter, NGCA, even with the Gaussian assumption, it is nontrivial to identify the non-Gaussian component, and methods such as the ones we analyzed have been conjectured, but previously without proof. Moreover, applying moment-matching methods directly gives much worse (super-polynomial) bounds, as the exponent will depend on the moment number, which (as we mention in the paper), will need to be super-constant to identify a direction with a margin. Taking all this into account, we feel that the progress made in this paper, establishing a polytime algorithm for learning margin halfspaces without labels, for Gaussian and more general logconcave product distributions (and their affine transformations) is an exciting result, suggesting there is more to be gained in this direction of study.  \n\n    Finally, there are at least two directions that can be explored to further relax the distribution assumption. The first one is to generalize the logconcave distributions to isoperimetric distributions. The second one is to consider a soft margin, wherein the density within the margin is significantly modified without being made zero.\n\n- **W2**. Variants of algorithm have been presented in literature as is shown in the last paragraph of related work. For example, [VX11] used higher order re-weighted moment. [TV18] uses only re-weighted second moment while requiring another copy of data with the same distribution. They conjecture that new ways of re-weighted moment, as we do, could possibly work and this is what we manage to prove --- our algorithm works, using only re-weighted first and second moments. \n\n- **W3**. We apologize for not properly taking care of the \"almost symmetric\" case and we thank the review for pointing it out. We generalize Lemma 5 to the case when $|a+b|>c\\epsilon$. In fact we can show the following lemma.\n\n    **Lemma 5\\***. Let $\\mu$ be the mean of the distribution restricting $q$ to $\\mathbb{R}\\backslash [a,b]$. If $|\\mu| \\leq c\\epsilon^{10}$ for some constant $c>0$, then for an absolute constant $C$, the top two eigenvalues $\\lambda_1\\geq \\lambda_2$ of the re-weighted covariance of $P$ satisfy\n    $$\n    \\lambda_1-\\lambda_2 \\geq C\\epsilon^{9}.\n    $$\n\n    In the meantime, we will revise Lemma 4 accordingly as follows.\n\n    **Lemma 4**. If $|\\mu|>c\\epsilon^{10}$ for some constant $c>0$. Then for $\\alpha_1=-c_1 \\epsilon^{75}/d,\\alpha_2=-c_2\\epsilon^{42}/d$, the re-weighted mean of $P$ satisfies \n\n    $$\n    \\max(u^\\top \\mu_{\\alpha_1},u^\\top \\mu_{\\alpha_2}) > \\frac{C \\epsilon^{127}}{d^2}, \\text{for some constant } C>0.\n    $$\n    $$\n    \\forall v\\bot u, v^\\top \\mu_{\\alpha_1}=v^\\top \\mu_{\\alpha_2}=0.\n    $$\n\n    The proof of the contrastive covariance lemma is built upon the original proof of Lemma 5 while bounding the error caused the asymmetry of $a$ and $b$. We append the proof in the following link:\n    <https://anonymous.4open.science/r/Submission-7B72/Proof_appended.pdf>\n\n- **Q1**. In our problem, we are given only data sampled from distribution $\\hat{P}$. In other words, the learner does not know $q,a,b$.\n\n- **Q2**. We thank the reviewer for providing this reference. We will expand our discussion of related work on NGCA. Briefly,\n[DK22] considers the case when the underlying distribution along with the hidden direction is discrete or nearly discrete. For example, they consider the distribution supported on $k$ intervals, each of length at most $\\eta$. However, they require $\\eta<2^{-\\Omega(dk^2)}B^{-\\Omega(k)}$ for constant $B$ to make the algorithm works. Instead, we consider the distribution lies on two intervals contained in $(-\\infty, a],[b,\\infty)$. \"Almost-discreteness\" is essential in [DK22], and e.g., their algorithm cannot handle the case of a single Gaussian with a margin (note also that moment matching to find the margin direction could require a superconstant moment). \n\nReferences:\n\n[DK22] Diakonikolas, Ilias, and Daniel Kane. \"Non-gaussian component analysis via lattice basis reduction.\" Conference on Learning Theory. PMLR, 2022.\n\n[VX11] Vempala, Santosh S., and Ying Xiao. \"Structure from local optima: Learning subspace juntas via higher order PCA.\" arXiv preprint arXiv:1108.3329 (2011).\n\n[YV18] Tan, Yan Shuo, and Roman Vershynin. \"Polynomial time and sample complexity for non-gaussian component analysis: Spectral methods.\" Conference On Learning Theory. PMLR, 2018.\n\n\n"}, {"review_id": "oXvCTqtLc1", "reviewer": "Reviewer_rhCN", "summary": "Assuming that the data is generated from a full-rank affine transformation of a $d$-fold product distribution, one of which is divided into two groups by a halfspace. The authors address the problem of learning the halfspace by weighting the isotropized sample so that either the corresponding sample mean or the top eigenvector of the covariance matrix shifts along the normal direction to the halfspace.", "questions": "- The purpose of Lemma 1 and Lemma 2 is unclear. From a quick search in the supplement, they are not used to prove the main Theorem. And I personally think that Lemma 4 and Lemma 5 are more informative. Do the maximum of the two expectations shows up in the proof of Lemma 4?\n- What are $\\mu_{\\alpha_1}$ and $\\mu_{\\alpha_2}$ in Lemma 4?\n- What are $a'$ and $b'$ in the Proof of Lemma 1?\n- Bottom of Page 6: \"Since $\\hat{q}(x) - \\hat{q}(-x) \\geq 0$ for $x\\geq b'$.\" looks like an incomplete sentence.\n- Proof Idea of Lemma 4: I do not understand the statement \"$F'(0)$ has at most one root.\" and \"$F\"(0)$ has no root.\"\n- Do the time and sample complexities also depend on the distribution's tail decay rate?", "limitations": "The authors address some challenges of improving the sample complexity bound to linear, and extending the algorithm to more general distributions.", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "- Good presentation of theoretical results, with the proof of the main theorem summarized succinctly.\n- Interesting idea of using Descartes'  Rule of Signs to single out a nonzero mean from weighted samples.\n- Experimental results agree with the theory.\n- In contrast to prior work which focuses on Gaussian data, the proposed method extends to data generated from logconcave distributions.", "weaknesses": "- Real-world applications is still unclear to me. In what situation do we expect the set-up in Definition 1 to arise? The authors list the methods that benefit from the halfspace learning in Line 40-49, but where do these methods apply?\n- Related to the point above, the authors might want to test their method on real-world data.\n- The paper seems to have been reorganized but some notations are left unchanged---see questions below.\n ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the careful reading of the paper and the valuable suggestions. Here are specific responses:\n\n- **W1&W2**. Unsupervised halfspace learning is a new perspective on maximum margin clustering. On the practical side, unsupervised learning has a wide range of applications in computer vision, natural language processing and graph, where data might have structure. While the margin assumption we make is likely unrealistic, we expect our methods to extend to \"soft margins\" where the density in some interval is significantly lower, thereby allowing this direction to be identified. Extending this to the kernel setting, with non-linear features, could be very interesting. \n\n    One real world application that is close to our setting is to do sentimental analysis given text only (without labels). Suppose we have a powerful pre-trained model that maps the input data into embedding vectors, we can cluster the text into either positive or negative without knowing the data labels. \n\n    Our setting and method are also connected to self-supervised learning. As mentioned in line 297, contrastive learning without data augmentation is similar to the contrastive covariance part in our algorithm.\n\n- **W3**. We thank the reviewer for pointing out the issues. We will address them.\n\n- **Q1**. The purpose of Lemmas 1 and 2 is expository --- to give a qualitative bound of two key lemmas (contrastive mean and variance), with simpler proofs that convey the main intuition.  Their quantitative versions are Lemma 4 and Lemma 5, which are actually used in the proof of the main theorem. Though Lemma 4 and Lemma 5 are more informative, their proof contains many technical details.\n\n    In Lemma 1, the maximum of the two expectations being greater than zero indicates that using two different $\\alpha$'s in our algorithm will lead to a positive gap in contrastive mean. However to have a polynomial gap (as in Lemma 4), we need to prove much more work, and we do this in the Appendix.\n\n- **Q2**. $\\mu_{\\alpha_i}$ is the re-weighted mean using $\\alpha_i$, which corresponds to $\\tilde{\\mu}_i$ in Algorithm 1. We will make the notation consistent.\n\n- **Q3**. We denote the support of isotropic density $\\hat{q}$ as $\\mathbb{R}\\backslash[a',b']$, where $a'=(a-\\mu_1)/\\sigma_1, b'=(b-\\mu_1)/\\sigma_1$. The notation is defined in Appendix C. We will add the necessary parts to the main body of the paper.\n\n- **Q4**. We apologize for the confusion. The bottom of Page 6 should be as follows.\n\n    We treat $F(\\alpha)$ as the integral of $a(x)e^{\\alpha x^2}$ for $x\\geq -a'$. Since $\\hat{q}(x)-\\hat{q}(-x)>0 $ for $x> b'$, we have $a(x)> 0$ for $x\\in[-a',b')$ and $a(x) < 0$ for $x> b'$. In other words, for increasing $x$, the sign of $a(x)$ only changes once.\n\n- **Q5**. We apologize for the confusion in the proof idea of Lemma 4. In fact, for both $F'(0)$ and $F''(0)$, there exists pairs $(a,b)$ that make one of them zero. However, we can show that $F'(0)$ and $F''(0)$ cannot both be zero at the same time (Lemma 24). The detailed proof is in the Appendix (starting from line 545). \nThe proof idea of Lemma 4 starting from line 225 should be as follows.\n\n    By taking the derivatives of $F(\\alpha)$, we can show that either $F'(0)\\neq 0$ or $F''(0)\\neq 0$. Then by Taylor expansion, we can choose two distinct $\\alpha$'s (near zero) so that one of the corresponding contrastive means is bounded away from zero.\n\n- **Q6**. Yes, it is possible the time and sample complexity depend on the distribution's tail decay rate, or other properties of the distribution. Here we give a bound for general logconcave distributions. It would be interesting to see if natural assumptions such as decay rate lead to better complexity (and what the quantitative dependence would be). Figure 5.1 shows the difference between Gaussian, Uniform and Exponential, where Uniform has the best performance, and Gaussian has the worst.\n"}]

Author rebuttal:

Meta-review: All reviewers found this paper well written and the theoretical results interesting, so agreed the paper should be accepted. The authors cleared up some doubts in the discussion period, and we hope they both improve the completeness of the proof in the final version, and expand discussion of prior work mentioned by the reviewers.
Decision: Accept (poster)