Introduction

High-dimensional convex geometry is a rich topic at the intersection of geometry, probability, and analysis (see [B + 97, GW93, LL15, Tro18, Tko18, HW20], among many other works, for general overviews). Apart from its intrinsic interest, a strong motivation for the study of high-dimensional convex sets from the perspective of theoretical computer science is that convexity often translates into a form of mathematical niceness which facilitates efficient computation, as witnessed by the plethora of positive results in algorithms and optimization for convex functions and convex sets. In this work, the object of study is the convex set:

A set K ⊂ R n is convex if and only if for every two points x, y ∈ R n , any point z on the segment between x and y lies in K whenever x and y lie in K.

The above gives a "local" characterization of convex sets, where "local" refers to the fact that (aside from quantifying over all co-linear points x, z, y,) an algorithm may make three membership queries to check the condition -in particular, non-convexity can be verified with three queries. Can one relax the "for all" quantification to give a local condition which characterizes approximately convex sets? Is there an algorithm which, by making very few queries, can determine whether or not a set is (almost) convex?

A natural vantage point for this broad question is that of property testing [BLR93,RS96], which provides an algorithmic framework for studying the above questions. In our setting, we consider property testing of convex sets with respect to the standard Gaussian distribution, arguably the most natural distribution over R n . Indeed, various learning, property testing, and other algorithmic problems in the Gaussian setting have been intensively studied in theoretical computer science [KOS08, Vem10, MORS10, Kan11, Kan12, Kan14, KK14, KNOW14, Kan15, CFSS17, CDS19, DMN19, OSTK21, DMN21, HSSV22, DNS23]. Furthermore, while a large body of mathematical work (e.g. [Bor75, Bal93, LO99, Lat02, Naz03, Bor03, CEFM04, LO05, Bor08, Roy14]) investigates the geometry of high-dimensional convex sets against the Gaussian distribution, convexity over Gaussian space arises naturally within theoretical computer science in the context of algorithmic discrepancy theory [Glu89, Ban10, LM15, Rot17, LRR17, Eld22, RR23b] and lattice problems [RR23a,Rot23,RSD24].

We consider the following algorithmic task: A (randomized) testing algorithm has black-box query access to an unknown and arbitrary function f : R n → {0, 1} (the indicator function of a subset of R n ), and its goal is to make as few membership queries on f as possible while deciding whether f is convex or ε-far from convex (meaning f and any indicator of a convex set g : R n → {0, 1} disagree on x ∼ N (0, I n ) with probability at least ε). Thus, a testing algorithm gives an efficiently-checkable (randomized) condition which all convex sets satisfy, and furthermore, any set which satisfies this condition is "almost" convex (with respect to the standard Gaussian distribution). For example, the definition of a convex set naturally leads to the following property testing question, whose positive resolution would directly give a "constant-query" testing algorithm (i.e. an algorithm whose query complexity depends only on ε and not on the ambient dimension n): Does there exist a probability distribution over co-linear points x, z, y in R n such that the condition Pr[z ∈ K | x, y ∈ K] ≥ 1δ(ε) implies that the set K must be ε-close to convex with respect to the standard Gaussian? 1 In this work, we show the first non-trivial lower bounds for testing convexity under the standard Gaussian distribution. Our lower bounds not only give a negative resolution to the above question, they imply that, in a variety of property testing models (non-adaptive, adaptive, one-sided, two-sided, and tolerant), a dependence on the ambient dimension n is always necessary. Prior to this work, an O(1/ε)-query test was entirely possible for all of those models. 2 As further discussed in Section 1.3, a number of prior works have studied convexity testing in a range of different settings, yet large gaps remain in our understanding. Most closely related are the works of [KOS08], who study learning convex sets over N (0, I n ), and [CFSS17], who study testing convexity over N (0, I n ) when restricted to sample-based testers (i.e. the algorithm can only query a given number of random points independently drawn from N (0, I n )). On the upper bound side, the best algorithm for convexity testing [CFSS17] is based on [KOS08] and queries 2 Õ( √ n)/ε 2 randomly sampled points from N (0, I n ). Hence, this "sample-based" tester gives a non-adaptive property testing algorithm. 3 Turning to lower bounds, [CFSS17] showed that, when restricted to sample-based testers, (i) algorithms which incur one-sided error must make 2 Ω(n) queries, 4 and (ii) algorithms which incur two-sided error must make 2 Ω( √ n) queries. Importantly, lower bounds on sample-based testers do not imply any lower bounds for algorithms which are allowed to make unrestricted queries. There are many prominent property testing problems (e.g., linearity and monotonicity) where the complexity of sample-based testing is significantly higher than the complexity in the (standard) query-based model. 5 1.1 Our Results and Discussion This work gives the first non-trivial lower bounds for query-based convexity testing. We prove three different lower bounds for three variants of the property testing model, which we now describe. As mentioned, the best known algorithm for convexity testing is the non-adaptive algorithm of [CFSS17], which makes 2 Õ( √ n)/ε 2 non-adaptive queries (and makes two-sided error).

Our first result gives a polynomial lower bound for one-sided adaptive testers:

Theorem 1.1. (One-sided adaptive lower bound) For some absolute constant ε > 0, any one-sided (potentially adaptive) ε-tester for convexity over N (0, I n ) must use n Ω (1) queries.

We also consider a challenging and well-studied extension of the standard testing model which is known as tolerant testing [PRR06]. Recall that an (ε 1 , ε 2 )-tolerant tester for a class of functions is a testing algorithm which must accept with high probability if the input is ε 1 -close to some function in the class and reject with high probability if the input is ε 2 -far from every function in the class; thus the standard property testing model corresponds to (0, ε)-tolerant testing.

The sample-based algorithm for convexity testing that is given in [CFSS17] is based on agnostic learning results from [KOS08]. It follows easily from the analysis in [CFSS17] and results of [KOS08] that for any 0 ≤ ε 1 < ε 2 with ε 2ε 1 = ε, the [CFSS17] approach gives a 2 Õ( √ n)/ε 4 -query sample-based algorithm for (ε 1 , ε 2 )-tolerant testing of convexity. As our final result, we give a mildly exponential lower bound on the query complexity of two-sided non-adaptive tolerant convexity testing:

Theorem 1.2. (Two-sided non-adaptive tolerant testing lower bound) There exist absolute constants 0 < ε 1 < ε 2 < 0.5 such that any non-adaptive (ε 1 , ε 2 )-tolerant tester for convexity over N (0, I n ) (which may make two-sided errors) must use at least 2 Ω(n 1/4 ) queries.

Returning to the standard testing model, our final result gives a polynomial lower bound for two-sided non-adaptive testers: Theorem 1.3. (Two-sided non-adaptive lower bound) For any constant c > 0, there is a constant ε = ε c > 0 such that any non-adaptive ε-tester for convexity over N (0, I n ) (which may make two-sided errors) must use at least n 1/4-c queries.

Since q-query non-adaptive lower bounds imply (log q)-query adaptive lower bounds, Theorem 1.3 implies an Ω(log n) two-sided adaptive convexity testing lower bound. (This is in contrast to the n Ω(1) -query lower bound against one-sided adaptive testers given by Theorem 1.1.)

1.2 Techniques Our lower bounds rely on a wide range of techniques and constructions, and draw inspiration from prior work on monotonicity testing of Boolean functions f : {0, 1} n → {0, 1} [CST14, BB16, CWX17, PRW22, CDL + 24].foot_0 Indeed, a conceptual contribution of our work is to highlight a (perhaps unexpected) connection between ideas in monotonicity testing and convexity testing. Our work thus adds to and strengthens a recently emerging analogy between monotone Boolean functions and high-dimensional convex sets [DNS21,DNS22,DNS24]. Establishing this connection requires a number of technical and conceptual innovations for each of our main results; we highlight some of the key ideas below.

1.2.1

The Nazarov Body A central role in our lower bounds in Theorem 1.1 and Theorem 1.2 is played by the so-called "Nazarov body" [Naz03, KOS08,CFSS17]. This is a randomized construction of a convex set B which is a slight variation of a construction originally due to Nazarov [Naz03], which is essentially as follows: we choose N ≈ 2

√ n halfspaces H 1 , . . . , H N in the space R n , where each halfspace H i is a random halfspace at a distance roughly n 1/4 from the origin. In more detail, each halfspace is H i (x) := 1 g i • x ≥ r where r ≈ n 3/4 and g i is drawn from N (0, I n ). The convex set B is obtained by taking the intersection of all N halfspaces with Ball( √ n), the origin-centered ball of radius √ n. 7 The exact parameters r and N are set carefully so that with high probability the "Gaussian volume" of B, i.e. Pr g∼N (0,In) [g ∈ B], is a constant bounded away from 0 and 1. Note that for the Nazarov body B and any point

such that j ∈ J x iff H j (x) = 0, i.e., the point x violates the halfspace H j for all j ∈ J x . Now, define a point

of the Nazarov construction is that the Gaussian volume of the set of points which are uniquely violated, i.e., Gaussian volume of the set U , is "large" compared to the Gaussian volume of the set Ball( √ n) \ B (see Lemma 3.5

for the precise statement).

The original construction of Nazarov may be viewed as a Gaussian-space analogue of Talagrand's random CNF formula [Tal96] (see [DNS24] for a discussion of this connection). Talagrand's random CNF has been very useful in lower bounds for monotonicity testing over the Boolean hypercube, as demonstrated by [BB16, CWX17, CDL + 24]. We use our modified Nazarov body to obtain new lower bounds for convexity testing, as described below.

1.2.2 One-Sided Adaptive Lower Bound Recall that a one-sided tester always outputs "accept" on convex sets and outputs "reject" on far-from-convex sets with probability at least 2/3 -this requirement implies that the tester rejects only if a certificate of non-convexity is found (i.e. a set of queries x 1 , . . . , x t which lie in the body, and a query y in the convex hull of x 1 , . . . , x t which is not in the body). In order to argue a q-query lower bound, it suffices to (1) design a distribution D no over sets which are far-from-convex with high probability, and (2) argue that no q-query deterministic algorithm can find a certificate of non-convexity.

The key will be to "hide" the non-convexity within the uniquely violated sets of the Nazarov body. Consider working in R 2n and first randomly draw an n-dimensional "control subspace" C and the orthogonal n-dimensional "action subspace" A; we embed the n-dimensional Nazarov body in the control subspace C. A point x ∈ R 2n lies in our (non-convex) body iff:

• It has Euclidean norm at most √ 2n, and in addition, x C (the projection onto the control subspace) has norm at most √ n; and

• The point x C lies within an n-dimensional Nazarov body that we randomly sample within the control subspace C; or, for every j ∈ [N ] where H j (x C ) = 0, the projection x A on the action subspace lies outside of a "strip" of width 1 along a randomly sampled direction v j in the action subspace. (See Section 4.1.2).

Consider a line through a point x ∈ R 2n in direction v j , for j ∈ [N ] such that x C lies in the uniquely violated region U j and x A lies inside the strip along v j (and therefore outside our body). Then, as the line proceeds out from x in directions v j and -v j , it remains in the uniquely violated region U j (since v j is orthogonal to C) but exits the strip, thereby entering the body and exhibiting non-convexity. By design, the uniquely violated regions and the strips are large enough to constitute a constant fraction of the space, giving the desired distance to convexity (Lemma 4.1). Intuitively, detecting non-convexity is hard because the algorithm does not know C, the halfspace H j (•), or the direction v j . In fact, we show that an algorithm which makes few queries cannot find, with probability at least 2/3, two points x, z outside the same halfspace H j (•) such that x lies inside and z outside the strip in direction v j . Roughly speaking, the proof proceeds as follows. First, we show that, except with o(1) probability, any two queries x, z which are far (at distance at least 1000 √ qn 1/4 ) cannot lie outside the same halfspace H j (•) while having projections onto C with norm at most √ n (Lemma 4.4), and moreover it is extremely unlikely for a query to be falsified by more than q halfspaces (this follows from a calculation in Lemma 3.2). The argument is geometric in nature and is given in Section 4.5, and essentially argues that it is unlikely, since the algorithm does not know the control subspace C or the vector defining the halfspace, that two far-away queries happen to uniquely falsify the same halfspace.

On the other hand, consider the halfspaces which are falsified by some query (and notice there are most q 2 such halfspaces, since each query is falsified by at most q halfspaces). Since all such queries are within distance 1000 √ qn 1/4 of each other, the projection of any two such queries onto the direction defining the strip is a segment of length O( √ q/n 1/4 ) with high probability, and the precise location of this segment is uniform(-like, from Gaussian anti-concentration) (see Section 4.5.1). Therefore, the probability of any particular segment of length O( √ q/n 1/4 ) which goes from inside to outside the strip of width 1 is roughly O( √ q/n 1/4 ). We take a union bound over the q 2 possible halfspaces, each containing at most q queries which define segments which may "cross" the strip with probability O( √ q/n 1/4 ), for a total probability of O(q 3.5 /n 1/4 ). Since this must be at least 2/3 for the algorithm to succeed, this gives the n Ω(1) lower bound.

1.2.3 Two-Sided Non-Adaptive Tolerant Lower Bound Continuing the analogy with monotonicity testing lower bounds, the proof of Theorem 1.2 is inspired by recent lower bounds on tolerant monotonicity testing, namely [PRW22] and the follow-up work of [CDL + 24]. The basic idea of [PRW22] is to construct a family of functions by randomly partitioning the space of variables into control variables and action variables: if the control variables are not balanced, i.e. there are more 1s than 0s (or vice-versa), then the function is trivially set to 1 (resp. to 0) both for f ∼ D yes and for f ∼ D no . If the control variables are balanced, then, at a high level, 1. for f ∼ D yes the function on the action variables is close to monotone; 2. for f ∼ D no the function on the action variables is far from monotone.

Roughly speaking, the analysis in [PRW22] shows that unless the algorithm queries two points such that both these points (a) have the same setting of the control variables, and (b) the control variables are balanced, the algorithm cannot distinguish between f ∼ D yes and f ∼ D no . As the control and action variables are partitioned at random, it turns out that satisfying both (a) and (b) is not possible for a non-adaptive algorithm unless the algorithm makes 2 Ω( √ n) many queries. In particular, [PRW22] shows that distinguishing between functions which are c 1 / √ n-close to monotone versus c 2 / √ n-far from monotone (where

queries.

The main modification in [CDL + 24] vis-a-vis [PRW22] is the following: one can think of the balanced setting of the control variables in the construction described above as the "minimal satisfying assignments" of the Majority function. In [CDL + 24], the Majority function is replaced by Talagrand's random monotone DNF [Tal96], a well-studied function in Boolean function analysis and related areas [MO03,OW07]. The specific properties of Talagrand's monotone DNF allows [CDL + 24] to obtain a 2 n 1/4 query lower bound for non-adaptive testers where the functions in D yes are c 1 -close to monotone and functions in D no are c 2 -far from monotone, where c 2 > c 1 are positive constants.

For Theorem 1.2, the goal is to obtain lower bounds for tolerant convexity testing rather than monotonicity testing. Towards that goal, let us assume that the ambient space is R n+1 . We choose a random n-dimensional subspace C and think of it as the control subspace, and we view its one-dimensional orthogonal complement as the action subspace A (analogous to the notion of control and action variables in [PRW22, CDL + 24]). 8 We embed the Nazarov body B (described earlier) in the control subspace. We define the D yes and D no distributions in analogy with [CDL + 24], roughly as follows: for x ∈ R n+1 , 1. If the projection x C does not lie in the uniquely violated set of B, then f (x) is defined the same way for f ∼ D yes and f ∼ D no ;

2. If the projection x C lies in the uniquely violated set, then f (x) is set differently for f ∼ D yes and f ∼ D no (depending on the projection x A to the action subspace). In particular, for f ∼ D yes , f is defined in such a way that f -1 (1) is close to a convex set, and for f ∼ D no , f is defined in such a way that f -1 (1) is far from every convex set. This crucially uses the fact that the Gaussian volume of U is "large" compared to the Gaussian volume of the set Ball( √ n) \ B, as mentioned in our earlier discussion of the Nazarov body.

At a high level, the indistinguishability argument showing that q = 2 Ω(n 1/4 ) non-adaptive queries are required to distinguish f ∼ D yes from f ∼ D no is a case analysis based on the distance between any given pair of query vectors x and y (see Lemma 5.3 and Lemma 5.4), combined with a union bound over all q 2 possible pairs of query vectors. Roughly speaking, if xy is small, then the way that f depends on the projection to the action subspace makes it very unlikely to reveal a difference between f ∼ D yes and f ∼ D no . On the other hand, if xy is large, then it is very unlikely for x and y to lie in the same set U i , which must be the case for the pair x, y to reveal a difference between f ∼ D yes and f ∼ D no . There are many technical issues and geometric arguments required to carry out this rough plan, but when all the dust settles the argument gives a 2 Ω(n 1/4 ) lower bound for tolerant convexity testing.

1.2.4 Two-Sided Non-Adaptive Bound Our approach to prove Theorem 1.3 is inspired by the lower bounds of [CDST15] on non-adaptive monotonicity testing. As in most property testing lower bounds for non-adaptive algorithms, the high-level approach is to use Yao's principle; we follow [CDST15] in that we use a suitable high-dimensional central limit theorem as the key technical ingredient for establishing indistinguishability between the yes-and no-distributions. In [CDST15] both the yes-and no-functions are linear threshold functions over {-1, +1} n , but since any linear threshold function is trivially a convex set, the [CDST15] construction cannot be directly used to prove a convexity testing lower bound. Instead, in order to ensure that our no-functions are both indistinguishable from the yes-functions and are far from every convex set, we work with degree-2 polynomial threshold functions (PTFs) over R n rather than linear threshold functions over {-1, +1} n . At a high level, degree-2 PTFs of the form i λ i x 2 i where each λ i is positive (note that any such PTF is a convex set) play the "yes-function" role that monotone LTFs play in the [CDST15] argument, and degree-2 PTFs of the form i λ i x 2 i where a constant fraction of the λ i 's are negative play the "no-function" role that far-from-monotone LTFs play in the [CDST15] argument. We show that having a constant fraction of the λ i 's be negative is sufficient, in the context of our construction, to ensure that no-functions are far from convex, and we show that the multi-dimensional central limit theorem used in [CDST15] can be adapted to our context to establish indistinguishability and thereby prove the desired lower bound.

Related Work

A number of earlier papers have considered different aspects of convexity testing. One strand of work deals with testing convexity of (real-valued) functions f : [N ] → R, where convexity means the second derivative is positive.foot_4 This study was initiated by Parnas et al. [PRR03], and extended by Pallavor et al. [PRV18], who gave an improved result parameterized by the image size of the function being tested; by Blais et al. [BRY14b], who gave lower bounds on testing convexity of real-valued functions over the hypergrid [N ] d ; and by Belovs et al. [BBB20], who gave upper and lower bounds on the number of queries required to test convexity of real-valued functions over various discrete domains including the discrete line, the "stripe" [3] × [N ], and the hypergrid [N ] d . (See also the work of Berman et al. [BRY14a], who investigated a notion of "L 1 -testing" real-valued functions over [N ] d for convexity.)

A different body of work, which is closer to this paper, deals with testing convexity of high-dimensional sets (equivalently, Boolean indicator functions). The earliest work we are aware of along these lines is that of Rademacher and Vempala [RV05]. 10 In their formulation, a body

for every convex set C, where Leb(•) denotes the Lebesgue volume (note that, in contrast, our model uses absolute volume under the Gaussian measure, rather than relative volume under the Lebesgue measure). Moreover, [RV05] allow the testing algorithm access to a black-box membership oracle (as in our model) as well as a "random sample" oracle which can generates a uniform random point from K (for testing with respect to relative measures, such an oracle is necessary). The main positive result of [RV05] is a (cn/ε) n sample-and query-algorithm for testing convexity in their model. [RV05] also give an exponential lower bound for a simple "line segment tester," which checks whether a line segment connecting two (uniformly random) points from the body is contained within the body. This lower bound was strengthened and extended to an exponential lower bound for a "convex hull tester" in recent work of Blais and Bommireddi [BB20]. We note that the negative results of [RV05] and [BB20], while they deal with natural and interesting candidate testing algorithms, only rule out very specific kinds of testers and do not provide lower bounds against general testing algorithms in their framework.

The most closely related work for us is the study of sample-based testing algorithms for convexity under the N (0, I n ) distribution [CFSS17]. As was mentioned earlier, [CFSS17] gave a 2 Õ( √ n)/ε 2 -sample algorithm for convexity testing and showed that any sample-based tester must use 2 Ω( √ n) samples; we remark that lower bounds for sample-based testers do not have any implications for query-based testing.foot_6 Finally, another closely related paper is the recent work of Blais et al. [BBH24] which gives nearly matching upper and lower bounds of 3 Ω( √ n)

queries for one-sided non-adaptive convexity testing over {-1, 0, 1} n . [BBH24] cites the high-dimensional Gaussian testing problem as motivation for their study of the ternary cube, and asks "Can queries improve upon the bounds of [CFSS17,HY22] for testing convex sets with samples in R n under the Gaussian distribution?" (Question 1.15 of [BBH24]). Our work makes progress on this question by establishing the first lower bounds for query-based testing under the Gaussian distribution.

Preliminaries

We use boldfaced letters such as x, X, etc. to denote random variables (which may be real-or vector-valued; the intended type will be clear from the context). We write x ∼ D to indicate that the random variable x is distributed according to probability distribution D. We will frequently identify a set K ⊆ R n with its 0/1-valued indicator function, i.e., K(x) = 1 if x ∈ K and K(x) = 0 otherwise. We write ln to denote natural logarithm and log to denote base-two logarithm.

Geometry

We write S n-1 for the unit sphere in R n , i.e. S n-1 = {x ∈ R n : x = 1} where x denotes the ℓ 2 -norm of x. We write Ball(r) ⊆ R n to denote the ℓ 2 -ball of radius r in R n , i.e.

Ball(r) := x ∈ R n : x ≤ r .

We will frequently write Ball := Ball( √ n). We recall the following standard bound on the volume of spherical caps (see e.g. Lemma 2.2 of [B + 97]):

, where u ∼ S n-1 , i.e. u is a Haar random vector drawn uniformly from the unit sphere S n-1 .

2.2 Gaussian and Chi-Squared Random Variables For µ ∈ R n and Σ ∈ R n×n , we write N (µ, Σ) to denote the n-dimensional Gaussian distribution centered at µ and with covariance matrix Σ. In particular, identifying 0 ≡ 0 n and writing I n for the n×n identity matrix, we will denote the n-dimensional standard Gaussian distribution by N (0, I n ). We write Vol(K) to denote the Gaussian measure of a (Lebesgue measurable) set K ⊆ R n , i.e.

Vol(K) := Pr

g∼N (0,In)

We recall the following standard tail bound on Gaussian random variables: Then for all r > 0, we have

where ϕ is the one-dimensional standard Gaussian density which is given by

It is well known that if g ∼ N (0, I n ), then g is distributed according to the chi distribution with n degrees of freedom, i.e. g ∼ χ(n). It is well known (see e.g. [Wik23]) that the mean of the χ 2 (n) distribution is n, the median is n(1 -Θ(1/n)), and for n ≥ 2 the probability density function is everywhere at most 1. We note that an easy consequence of these facts is that the origin-centered ball Ball(

We will require the following tail bound on χ 2 (n) random variables:

Then for any t > 0, we have

and Pr

2.3 Property Testing and Tolerant Property Testing Let P conv := P conv (n) denote the class of convex subsets of R n , i.e.

Given a set K ⊆ R n , we define its distance to convexity as dist(K,

where K L = (K \ L) ∪ (L \ K) denotes the symmetric difference of K and L. In particular, we will say that K is ε-close to (resp. ε-far from) a convex set if dist(K, P conv ) ≤ ε (resp. ≥ ε).

Definition 1. (Property testers and tolerant property testers

An algorithm A is an ε-tester for convexity if, given black-box query access to an unknown set K ⊆ R n , it has the following performance guarantee:

• If K is convex, then A outputs "accept" with probability at least 2/3;

• If dist(K, P conv ) ≥ ε, then A outputs "reject" with probability at least 2/3.

An algorithm A is an (ε 1 , ε 2 )-tolerant tester (or simply an (ε 1 , ε 2 )-tester) for convexity if it has the following performance guarantee:

• If dist(K, P conv ) ≤ ε 1 , then A outputs "accept" with probability at least 2/3;

• If dist(K, P conv ) ≥ ε 2 , then A outputs "reject" with probability at least 2/3.

In particular, note that every ε-tester is a (0, ε)-tolerant tester.

Our query-complexity lower bounds for non-adaptive property testing algorithms are obtained via Yao's minimax principle [Yao77], which we recall below. (We remind the reader that an algorithm for the problem of (ε 1 , ε 2 )-tolerant testing is correct on an input function f provided that it outputs "yes" if f is ε 1 -close to the property and outputs "no" if f is ε 2 -far from the property; if the distance to the property is between ε 1 and ε 2 then the algorithm is correct regardless of what it outputs.) Theorem 2.1. (Yao's principle) To prove an Ω(q)-query lower bound on the worst-case query complexity of any non-adaptive randomized testing algorithm, it suffices to give a distribution D on instances such that for any q-query non-adaptive deterministic algorithm A, we have

where 0 ≤ c < 1 is a universal constant.

Nazarov's Body

Our constructions in Sections 4 and 5 will employ modifications of a probabilistic construction of a convex body due to Nazarov [Naz03]. Nazarov's randomized construction yields a convex set with asymptotically maximal Gaussian surface area [Bal93,Naz03], and modifications thereof have found applications in learning theory and polyhedral approximation [KOS08,DNS24]. Definition 2. (Nazarov's body) For r, N > 0, we write Naz(r, N ) to be the distribution over convex subsets of R n where a draw B ∼ Naz(r, N ) is obtained as follows:

2. Output the convex set B ⊆ R n where

Note that for any fixed

where Φ(•) is the univariate Gaussian cumulative density function. Consequently, because of the independence of g i , we have

Note that B can be also written as

For each i ∈ [N ], we define F i (for "flap") to be points in Ball( √ n) which are falsified by H i , i.e.

Given a non-empty T ⊆ [N ], we write F T := i∈T F i . We will be interested in points in Ball( √ n) that are falsified by a unique halfspace H i and denote the set of such points as U i (for "unique"):

3.1 Useful Estimates Suppose N satisfies N = n ωn (1) ; in both Sections 4 and 5 we will take N = 2 √ n . Let c 1 > 0 be a parameter; in Section 4, we will set c 1 = ln 2 ± O(1)/N , and in Section 5 we will take c 1 to be a suitable small absolute constant. Throughout this section we will take r to be the unique positive number such that

Gaussian tail bounds allow us to relate r and N :

Lemma 3.1. We have

contradicting Equation (3.4). Next, it follows from Proposition 2.1 and Equation (3.4) that

The upper bound implies that

In particular, this implies that

Next, note that the lower bound from Equation (3.5) implies that

This in turn implies that

The result follows from Equations (3.6) and (3.7).

We need the following lemma which will be useful in analyzing our construction in Section 4.

Proof. Note that

where the penultimate equality relies on Equation (3.4).

We will also require a lower bound on the expected volume of

where the penultimate inequality follows from Equation (3.4) and the final inequality relies on the fact that (1y) z ≥ 1yz.

Next, at the cost of 0.01 probability mass (thanks to Proposition 2.2), we can assume that

It follows that

.

Standard Gaussian tail bounds give that

(Proposition 2.1)

where the last line uses our bounds on r from Lemma 3.1 and our bounds on c 1 from the statement of the current lemma. Putting everything together and recalling that c 1 < 0.9, we get that for n large enough,

thanks to Equation (3.4). Consequently, we have

completing the proof.

Next we show that the volume of i U i is highly concentrated:

Proof. Let Naz * (r, N ) be the same distribution as Naz(r, N ) except that when drawing B, each g i is drawn from

we have

Moreover, it suffices to show that when B ∼ Naz * (r, N ), we have

with probability at least 1o(1). To this end, we recall McDiarmid's inequality:

. . , X S be independent random variables taking values in a set Ω. Let G : Ω S → R be such that for all i ∈ [S] we have

Then for all τ > 0, we have

We will take S = N , X i to be the halfspaces H i and G(•) to be the volume of i∈[N ] U i , as we draw B ∼ Naz * (r, N ). Given the way g i is drawn in B ∼ Naz * (r, N ), the volume of each H i is always at least (using

It follows from McDiarmid that Equation (3.12) holds with probability at least 1o(1).

Finally, the following lemma will allow us to obtain bounds on the distance to convexity of the "yes"-and "no"-distributions in Section 5: Lemma 3.5. For r satisfying Equation (3.4), we have

Proof. Fix x ∈ R n and i ∈ [N ]. Recall Equation (3.8). On the other hand, we have

where we once again used Equation (3.2). It follows from Equations (3.8) and (3.13) that for x ∈ Ball( √ n) (i.e

x ≤ √ n), we have

where Equation (3.14) relies on the fact that x ≤ √ n and Φ(•) being increasing, Equation (3.15) relies on our definition of r from Equation (3.4), and Equation (3.16) relies on Bernoulli's inequality: (1y) z ≥ 1yz. (Note that for x with x > √ n, we have Pr[x ∈

To conclude, we have

where Equation (3.17) follows from the earlier calculation, completing the proof.

4 One-Sided Adaptive Lower Bound For this section, it will be most convenient for us to work over R 2n . Let us restate Theorem 1.1 in this setting:

Theorem 4.1. (One-sided adaptive lower bound, restated) For some absolute constant ε > 0, any onesided ε-tester for convexity over N (0, I 2n ) (which may be adaptive) must use n Ω(1) queries.

At a high level, the proof of Theorem 1.1 works by (1) first defining a distribution D no of "no-functions" (Boolean-valued functions over R 2n , or equivalently, subsets of R 2n ), and showing that an Ω(1) fraction of draws from D no yield sets which are Ω(1)-far from convex; and (2) then arguing that for a suitable absolute constant c > 0, any n c -query algorithm (even an adaptive one) has only an o(1) probability of querying a set of points whose labels are inconsistent with every convex set in R 2n . In the next subsection we describe the distribution D no .

4.1 The distribution D no of far-from-convex sets 4.1.1 Setup We will see that every function f in the support of D no outputs 0 on every input point x ∈ R 2n with x > √ 2n. To describe how f behaves within the √ 2n-ball, denoted by

we require some more setup.

The "control subspace," the "action subspace," and the Nazarov body. Let C be a Haar random n-dimensional subspace of R 2n ; we call C the control subspace. Let A be the orthogonal complement of C (which is also an n-dimensional subspace); we call A the "action subspace." Given a vector x ∈ R n , we write x C to denote the orthogonal projection of x onto C and we write x A to denote the orthogonal projection of x onto A, so every vector satisfies x = x A + x C . Fix N := 2 √ n (we assume without loss of generality that n is a perfect square, so N is an integer). For this choice of N , let B ∼ Naz(r, N, C) where Naz(r, N, C) is as defined in Definition 2 but with the n-dimensional control subspace C playing the role of R n . (We emphasize that B ∼ Naz(r, N, C) is a subset of R 2n which is an "n-subspace junta," meaning that for any x ∈ R 2n , membership of x in B depends only on x C .) We take r to be the unique positive number such that

In other words, we choose r to be the unique value such that any point x with

by the Taylor expansion of e -ln(2)/N and setting of r (Lemma 3.1).

The "action directions." For each i ∈ [N ], draw a random vector v i from the standard Normal distribution N (0, I n ) over the n-dimensional action subspace A (independent of everything else). We say that v i is the action direction for the i-th flap F i of the Nazarov body B. We note that for every pair i, j ∈ [N ], the vector g i defining the i-th halfspace H i of the Nazarov body is orthogonal to the vector v j (because g i ∈ C and v j ∈ A).

4.1.2

The distribution D no For a fixed setting of the control subspace C and the (orthogonal) action subspace A, of H := (H 1 , . . . , H N ) (which also specifies B and F i 's) and of v := (v 1 , . . . , v N ), we define the function f C,A, H, v : R 2n → {0, 1} as follows:

A random function f ∼ D no is drawn as follows: first we draw a Haar random n-dimensional subspace C; then A is taken to be the n-dimensional (Haar random) orthogonal complement of C; then we draw B ∼ Naz(r, N, C) (which gives a draw of H as in Equation (3.1)); then we draw v = (v 1 , . . . , v N ) from A as described above; then we set the function f to be f C,A, H, v .

4.2 Sets in D no are far from convex We need a constant fraction of the no-functions to be constant-far from convex. This is given by the following lemma:

Lemma 4.1. With probability Ω(1) over a draw of f ∼ D no , we have that Vol(f g) = Ω(1) for every g : R 2n → {0, 1} that is the indicator function of a convex set in R 2n .

We require a few definitions. Define ThinShell : (1). We view the draw of f as taking place in two stages: in the first one C, A, and g = (g 1 , . . . , g N ) are drawn, and in the second one v = (v 1 , . . . , v N ) is drawn. Observe that the set U depends only on the first stage. Say that any outcome of the first stage for which Vol[U ∩ ThinShell] = Ω(1) holds is a good outcome of the first stage, so an Ω(1) fraction of outcomes of the first stage are good.

Fix any good outcome C, A, g of the first stage (note that this fixes U 1 , . . . , U N and hence U ), and consider a draw of x ∼ N (0, I 2n ). We have the following claim: Claim 3. For a suitable absolute constant a > 0, we have

). Proof. Since we have fixed a good outcome C, A, g of the first stage, we have that Pr x∼N (0,I2n) [x ∈ U ∩ThinShell] ≥ c for some absolute constant c > 0. Moreover, every outcome of x ∈ U ∩ ThinShell has x C ≤ √ n, since U is a subset of B. So to prove the claim we need only show that Pr x∼N (0,I2n)

We first observe that by standard bounds on the chi-square distribution (Proposition 2.2), we have that

Let us say that an outcome of v for which f (x) = 0, f (x + ) = 1, f (x -) = 1 is a fine outcome of v for x. We will use the following claim:

Claim 4. For any fixed x that lies in U ∩ ThinShell and has

Proof. Since x ∈ U i ∩ ThinShell for some i, it must be the case that also x + , x -∈ U i (because every possible outcome of v i is orthogonal to every possible outcome of g j for every j ∈ [N ]). So v is fine if and only if

Now since v i is drawn from a standard N (0, I n ) distribution over the subspace A, a routine calculation using (i) Equation (4.19); (ii) the fact that v iv i , x x x 2 and v i , x are independent and are distributed as a draw from the χ 2 (n -1) distribution and a draw from N (0, x A 2 ) respectively; and (iii) the fact that a draw from the χ 2 (n -1) distribution takes value n(1 ± o(1)) except with vanishingly small probability, gives that Equation (4.18) holds with Ω(1) probability.

As an immediate consequence of Claim 4, we get that an Ω(1) fraction of outcomes of v are such that (4.20)

Fix any outcome v of v for which Equation (4.20) holds. To conclude the proof of Lemma 4.1, we observe that since x ∈ U i implies that x + , x -are also in U i , it follows that any z ∈ R n can participate in at most three triples of the form (x, x -, x + ), so the maximum possible degree of overlap across all of the triples is at most a factor of three. Moreover, for any x ∈ ThinShell, it holds that

, and hence the pdf of the χ 2 (2n) distribution is within a constant factor on each of the three inputs x , x + and x - (so the N (0, I 2n ) Gaussian's pdf is within a constant factor on each of the three inputs x, x + , x -). Combining this with Claim 3, we get that for an Ω(1) fraction of outcomes of f ∼ D no , the value of f needs to be altered on at least an Ω(1) fraction of inputs drawn from N (0, I n ) in order to "repair" all of the violating triples (x, x + , x -) for which x ∈ U ∩ ThinShell and

√ n], and consider the "completion" of the draw of f ∼ D no (i.e. the draw of B ∼ Naz(r, N, C) which induces an outcome of U ). We have

, so to complete the proof of Lemma 4.1 it suffices to show that (5.29) = Ω(1). We have

where the first equality is Equation (3.4) and the second is because c 1 = Θ(1). Similar to the proof of Lemma 3.3, we have

(Proposition 2.1)

= Θ(1), using Lemma 3.1.

So

where the first equality is by Equation (3.4). This concludes the proof of Lemma 4.1.

Proof of Theorem 1.1

Definition 5. (One-sided Adaptive Algorithms as Binary Trees) Fix n, q ∈ N. A q-query one-sided deterministic algorithm, Alg, for testing convexity in R 2n is specified by a rooted binary tree of depth q where each node contains the following information:

• Each node v which is a not a leaf contains a query vector x v ∈ R 2n , as well as two out-going edges, one labeled 0 and one labeled 1, to nodes which we label v(0) and v(1), respectively.

• Each leaf node v contains an output o v which is set to "accept" or "reject." Let Q 1 (or Q 0 ) denote the set of points queried along the path that are labelled 1 (or 0, respectively). Then o v is set to be "reject" if and only if

By adding nodes which repeat the queries, we may assume, without loss of generality, that the depth of every leaf of the tree is exactly q.

A q-query deterministic algorithm Alg executes on a function f : R 2n → {0, 1} by taking the natural root-to-leaf path given by following the function values which the oracle returns at the queries within each of the nodes. In particular, we will make repeated use of the following definitions which capture the execution of the algorithm Alg on a function f :

• The node v 0 is the root of the tree, which is the starting point of the root-to-leaf path. Then, the nodes v 1 , . . . , v q indicate the root-to-leaf path generated by executing the algorithm on the function f . In particular, at time step t ∈ {0, . . . , q -1}, we have

• The set Q 0 is defined to be ∅, and for t ∈ {0, . . . , q -1} the set Q t+1 is defined to be

is the set of vectors that are queried at time steps prior to t + 1.

Once the algorithm reaches the leaf node v q , the algorithm outputs o v q , and we will refer to Alg(f ) as the output ("accept" or "reject") produced by the algorithm. It is trivial to see that since any q-query deterministic algorithm corresponds to a tree of depth q, the total number of query vectors x v ∈ R 2n across all nodes of the tree is at most 2 q . Our goal is to show that, if Alg is a q-query deterministic algorithm which makes one-sided error, then

Recall that implicit in a fixed function f in the support of D no are the control and action subspaces C, A ⊂ R 2n , as well as the vectors g 1 , . . . , g N ∈ C and v 1 , . . . , v N ∈ A, and that g 1 , . . . , g N define B, H i and F i regions. In order to simplify our notation, we will often refer to a subset of the queries Qk for any k ≤ q whose norm on the control subspace is bounded,

Toward showing the above upper bound, we define two important events (which will depend on the draw f ∼ D no ).

Definition 6. Given Alg and a function f from D no , we consider the following three events:

• E 1 (f ): This event occurs if at the end of the execution of Alg on f , every point x ∈ Qq lies in at most q flaps, and for every flap F i with Qq ∩ F i = ∅, (4.24)

xy ≤ 1000 √ qn 1/4 for all x, y ∈ Qq ∩ F i .

• E 2 (f ): This event occurs if at the end of the execution of Alg on f , for every flap F i with Qq ∩ F i = ∅ and every x, y ∈ Qq ∩ F i , we have

Theorem 1.1 follows immediately from the following three lemmas:

Lemma 4.3. Let Alg be a one-sided, deterministic, q-query algorithm for testing convexity. Then, if Alg(f ) outputs "reject," the event E 2 (f ) occurred.

Lemma 4.4. Let Alg be a one-sided, deterministic, q-query algorithm. Then,

Lemma 4.5. Let Alg be a one-sided, deterministic, q-query algorithm, where q ≤ n 0.05 . Then,

Proof. [Proof of Theorem 1.1 Assuming Lemmas 4.3 to 4.5] We upper bound the expression

using Lemmas 4.4 and 4.5.

Proof of Lemma 4.3

Since Alg is a q-query deterministic algorithm which has one-sided error, in order for the algorithm to output "reject," the set Q q queried by the root-to-leaf path obtained by executing Alg on f must contain x 1 , . . . , x ℓ , y ∈ Q q satisfying y ∈ conv(x 1 , . . . , x ℓ ), f (y) = 0, and f (x

In particular, from y ∈ conv(x 1 , . . . , x ℓ ), we must have that, for any vector u ∈ R 2n , there exists a j ∈ [ℓ] such that x j , u ≥ y, u . This implies that:

• We must have that all x 1 , . . . , x ℓ satisfy (x i ) C 2 ≤ √ n, and y C 2 ≤ √ n, and this means these vectors lie in Qq . The part of (

On the other hand, if

√ n, letting u ∈ C be the unit vector u = y C / y C 2 , there exists an x j with

and hence f (x j ) = 0, which would be a contradiction with f (x j ) = 1.

• We must have y / ∈ B since f (y) = 0. As a result, there is a nonempty T such that y ∈ F T . In addition, f (y) = 0 implies that there exists an i ∈ T such that y ∈ F i but

Given that y ∈ F i , setting u = g i , there exists an x j such that x j , g i > y, g i ≥ r and thus, x j ∈ F i . It follows from f (x j ) = 1 and the construction that

This concludes the proof using i, y and x j .

Proof of

Lemma 4.4 To prove Lemma 4.4, we introduce five new, easy-to-analyze events E 1,1 , E 1,2 , E 1,3 , E 1,4 and E 1,5 , show that each happens with probability at least 1o(1), and that E 1,1 ∩ E 1,2 ∩ E 1,3 ∩ E 1,4 ∩ E 1,5 implies E 1 . For the n-dimensional subspace C ⊂ R 2n (in particular, the control subspace for f ), we denote Shell(C) := {x ∈ R 2n : √ n -100q ≤ x C 2 ≤ √ n}, where x C denotes the orthogonal projection of x onto the subspace C. • E 1,1 (f ): This event occurs if no query x in Alg with x C 2 ≤ √ n lies in |T |≥q F T defined by f ; • E 1,2 (f ): This event occurs if no query x in Alg satisfies x / ∈ Shell(C) and x / ∈ B (or equivalently, x C 2 <

√ n -100q and x ∈ F i for some i ∈ [N ]);

x, g i ≥ r + 100qn 1/4 , for some i ∈ [N ];

• E 1,4 (f ): This event does not occur if there exist i ∈ [N ] and two queries x, z in Alg where (i) x C and z C are not scalar multiples of each other, z C = (1 + a)x C + by denotes the unique decomposition with x C ⊥ y, y 2 = 1 and b > 0, such that x ∈ F i and | y, g i | ≥ 100 √ q.

• E 1,5 (f ): The event occurs whenever every pair x, y ∈ Alg satisfy xy 2 ≤ 2 (xy) C 2 .

We first prove that E 1 (f ) is implied by the five events together. Then, we show that each of the events holds individually with probability 1o(1). By a union bound over the five events, this gives Lemma 4.4.

Lemma 4.6.

Proof. Recall that Qq denotes the set of (at most q) queries made by Alg when running on f whose orthogonal projections onto C each have norm at most √ n. First E 1,1 (f ) implies that the number of "nonempty" flaps i ∈ [N ],

i.e. flaps F i that have Qq ∩ F i = ∅, is at most q 2 . Fix any nonempty flap F i and any two points x, z ∈ Qq ∩ F i . First consider the case that x C and z C are scalar multiples of each other. Note that we have x, z ∈ Shell(C) by E 1,2 (f ) and thus, (xz) C 2 ≤ 100q (since they are scalar multiples of each other). By E 1,5 (f ), xz 2 ≤ 200q, which is consistent with the requirement of E 1 (f ) since q = o( √ qn 1/4 ).

So consider the case when x C , z C are not scalar multiples of each other, and let z C = (1 + a)x C + by be the unique decomposition with x C ⊥ y and y ∈ C with y 2 = 1 and b > 0. Let α :

so that we may use E 1,5 (f ) to deduce that (4.24) holds for x and z.

We have z C

By E 1,2 (f ), we have x ∈ Shell(C) and thus, x C 2 ≥ √ n -100q. Plugging this in, we have

Let's consider two cases:

Case 1: a ≥ -200q/ √ n. We have from Equation (4.26) (note that the coefficient of a is negative and is a value larger than -2n)

and we get Equation (4.25).

Case 2: a < -200q/ √ n. In this case, using r ≤ z, g i , x, g i ≤ r + 100qn 1/4 (where the first inequality is because x, z ∈ F i and the second is from E 1,3 (f )) gives

and hence,

Recalling that a < 0, dividing through by -a we get

by the setting of r in Lemma 3.1. Recalling Equation (6.54), we get

as was to be shown.

Event E 1,1 (f ). We now show that with probability at least 1o(1) over the draw of f ∼ D no , all 2 q queries specified by Alg avoid the region which is the intersection of at least q flaps. Consider any fixed query x and fix any setting of the control subspace C ⊂ R 2n with x C 2 ≤ √ n. Using Lemma 3.2 (and the fact

so that a union bound over 2 q queries gives (2c 1 ) q /q! = o(1) for large q.

Event E 1,2 (f ). Similarly to above, we proceed by a union bound over all 2 q queries. We consider a fixed control subspace C and we let x be a query with

by the setting of r from Lemma 3.1. The desired claim then follows from a union bound over all 2 q queries. Event E 1,3 (f ). Consider any query x, and consider a fixed setting of the control subspace C with x C 2 ≤ √ n.

Then,

where the computation proceeds similarly to E 1,2 (f ).

Event E 1,4 (f ). For a fixed control subspace C, we may consider two arbitrary queries x, z among the set of all 2 q queries with x C 2 , z C 2 ≤ √ n. This gives 2 2q possible settings of the unit vector y which is orthogonal to x C . In order for the event to fail, there must exists some i ∈ [N ] where g i , x C ≥ r and | g i , y | ≥ 100 √ q.

Furthermore, since x C and y are orthogonal, these two events are independent:

hence, we may take a union bound over all i ∈ [N ] and all 2 2q pairs of vectors x and z.

Event E 1,5 (f ). Finally, consider any two vectors x and y which are queries among the 2 q possible queries in Alg. The Johnson-Lindenstrauss lemma (see Theorem 5.3.1 in [Ver18]) says that a random n-dimensional subspace C of R 2n will satisfy (xy) C 2 ≥ (1/ √ 2ε) xy 2 except with probability exp -Ω(ε 2 n) . Thus, for large enough n, xy 2 ≤ 2 (xy) C 2 except with probability exp -Ω(n) , and since q n, we may union bound over all 2 2q pairs of queries in Alg. 4.5.1 Proof of Lemma 4.5 For E 2 (f ) ∩ E 1 (f ) to happen, there must exist a level k ∈ [q] such that • After the the first k -1 queries Q = Qk-1 , E 1 (f ) holds, i.e., the number of flaps F i with Q ∩ F i = ∅ is at most q 2 . In every such F i , every two points in Q ∩ F i have distance at most 1000 √ qn 1/4 and share the same value of

which we denote by b i ∈ {0, 1}.

• Let y be the k-th query. There exists an i such that Q ∩ F i = ∅ and y ∈ F i such that

for all x ∈ Q ∩ F i (the number of such i is at most q) but

We prove below that when q ≤ n 0.05 , the probability of the event above for a fixed k is o(1/q) and thus, Lemma 4.5 follows by applying a union bound on k. This follows from a union bound on all i ∈ [N ] such that Q ∩ F i = ∅ and every x ∈ Q ∩ F i satisfies (Equation (4.27)), taking X (or z) below as Q ∩ F i (or y, respectively) projected on the space orthogonal to g i and b as b i .

Lemma 4.7. Let b ∈ {0, 1}, and let X be a set of at most q points in Ball( √ 2n) and y ∈ Ball( √ 2n). Suppose that every pair x ∈ X and y satisfy (xy) A 2 ≤ 1000 √ qn 1/4 .

Then over the draw of v ∼ N (0, I n ) in A, the probability of

Before proving Lemma 4.7, we show how it implies Lemma 4.5 from a union bound. In particular, we have concluded that

q × u.b over i q 2 ×O √ q log n/n 1/4 = O(q 3.5 log n/n 1/4 ).

Proof. [Proof of Lemma 4.7] Fix a point x * ∈ X. We show that (1) the probability of

b for all x is at least Ω(1); and (2) the probability of

is at most O( √ q log n/n 1/4 ). The lemma then follows.

To analyze (2), we consider any 0 < γ ≤ √ n/4 and any sign ξ ∈ {-1, 1}. We have that a draw of a Gaussian v lying in the action subspace A satisfies

where we have used Gaussian anti-concentration (to conclude it does not lie within an interval of width 2γ/ x * A 2 ), as well as Gaussian tail-bounds to say g is is larger than √ n/(4 x * A 2 ). The minimum over τ > 0 is meant to quantify over possible values of x * A 2 . Letting γ = 50000 √ qn 1/4 log n allows us to conclude that the probability that v, x * lies within distance γ of -√ n/2 or √ n/2 is at most O( √ q log n/n 1/4 ).

On the other hand, given that (yx * ) A ≤ 1000 √ qn 1/4 , we also have that

which is smaller than any inverse polynomial in n. Therefore, we have that, except with probability at most O( √ q log n/n 1/4 ), for both ξ ∈ {-1, 1},

≤ 50000 √ qn 1/4 log n; and

When these two events occur, event (2) cannot occur, which shows that (2) occurs with probability at most O( √ q log n/n 1/4 ).

To conclude (1), we note that any

, which shows that conditioning on event (1) does not significantly affect the probability of (2).

A Mildly-Exponential Lower Bound for Non-Adaptive Tolerant Testers

We will prove the following:

Theorem 5.1. (Two-sided non-adaptive tolerant testing lower bound) There exist absolute constants 0 < ε 1 < ε 2 < 0.5 such that any non-adaptive (ε 1 , ε 2 )-tolerant tester for convexity over N (0, I n ) (which may make two-sided errors) must use at least 2 Ω(n 1/4 ) queries.

5.1 The D yes and D no Distributions Before specifying the D yes and D no distributions, we first describe some necessary objects.

The Control and Action Subspaces. Throughout, we will work over R n+1 for convenience. Let A denote a random 1-dimensional subspace of R n+1 , i.e. A = {tv : t ∈ R} where v ∼ S n is a Haar-random unit vector.

Let C be the orthogonal complement of A; note that C is a random n-dimensional subspace of R n+1 . We call C the control subspace and we call A the action subspace.

Given a vector x ∈ R n , we write x C to denote the projection of x onto C and we write x A to denote the projection of x onto A, so every vector satisfies x = x A + x C . Recalling that A is a 1-dimensional subspace, when there is no risk of confusion we write x A to denote the scalar value t such that x A = tv.

Constants. We will use four positive absolute constants c 0 , c 1 , c 2 and τ in the construction. Here c 0 is the constant hidden in the statement of Lemma 3.3. We set c 1 , c 2 and τ as follows: Functions on the Action Subspace. Let c 2 be the absolute constant given in Equation (5.28). Intuitively, 2c 2 will be the Gaussian measure of two symmetric intervals in the action subspace A. More formally we define

Using the absolute constant τ given in Equation (5.28), we also define the interval

and we observe that a random draw of x from N (0, I n+1 ) has x ∈ I with probability at least 1τ . We write Shell n+1 to denote the corresponding spherical shell in R n+1 , i.e.

Finally, let P be a uniformly random subset of [N ].

For a fixed setting of C (which defines the complementary A), B (which in turn defines H i , F i , the F T 's, and U i ), and P , we define the function g C,B,P : R n+1 → {0, 1, 0 , 1 } as follows:

The D yes and D no Distributions. To sample a set from either D yes or D no , first draw C, B, P as described above; note that this induces a draw of A, H i , F i , the F T 's, and U i . Draws from D yes and D no are identical on points x ∈ R n+1 where g C,B,P (x) ∈ {0, 1}; on the other values, however,

• For functions in D yes , we set 0 → 0 and 1 → 1.

• For functions in D no , we set

where we define

See Figures 2 and 3 for illustrations of D yes and D no .

Distance to Convexity

Recall that a draw of a function from either D yes or D no induces a draw of B, C, and P . First, we give an upper bound on the expected distance to convexity of a function drawn from D yes . Let ε 1 be the constant given by

Proposition 5.1. We have dist(f yes , P conv ) ≤ ε 1 with probability at least 0.5 when f yes ∼ D yes .

Proof. Consider a fixed choice of C, B and P . We then consider the convex set G C,B,P ⊂ R n+1 defined as the intersection of H i (for i ∈ P ) and the set {x : x C 2 ≤ √ n}. By construction, the set G C,B,P is a convex set. Let g C,B,P denote the corresponding indicator function. We now analyze the distance between the functions g C,B,P (where, as for functions in the support of D yes , we identify 0 with 0 and 1 with 1) and g C,B,P . First of all, by construction, if g C,B,P (x) = 1, then g C,B,P (x) is also 1. So to bound the distance, we note that there are three possible ways in which g C,B,P (x) can be 0 but g C,B,P (x) can be 1: 1. x ∈ ∪ |T |≥2 F T ; 2. x ∈ Shell n+1 ; 3. There is some i ∈ [N ] such that x ∈ U i and x A ∈ Curb. By definition, (i) the Gaussian volume of the first set is Vol(∪ |T |≥2 F T ); (ii) the Gaussian volume of the second set is bounded by τ ; (iii) the Gaussian volume of the third set is bounded by Vol(Curb) which by definition is 2c 2 Thus, for a specific instantiation of C, B and P , dist(g C,B,P , P conv ) ≤ 2c 2 + τ + Vol   |T |≥2 F T   .

The claim follows from Markov's inequality, that the last term on the RHS above is at most twice the expectation with probability at least 1/2. Next, we give a lower bound on the expected distance to convexity of a function drawn from D no . Let ε 2 be the constant given as

Proposition 5.2. We have dist(f no , P conv ) ≥ ε 2 with probability at least 1o(1) when f no ∼ D no .

Proof. As before, consider a fixed choice of C, B and P . Take any x C such that x C ∈ U i for some i ∈ P and x C ≥ √ n + 1 -2 ln(2/τ ) (which is the left end of I). For any such x C , the line along x A looks like the picture at the top of Figure 3, except that the function is set to 0 when x C makes x go outside of Shell n+1 . Given that x C ≤ √ n, this only happens when |x A | is at least Ω(n 1/4 ) given that τ ≤ 1/10000 in Equation (5.28).

As a result, the distance to convexity along this line in the action space (with x C fixed) is at least Vol(Middle) = (1 -2c 2 )/3. This follows immediately from the fact that Middle is a symmetric interval about 0 and the choice of parameters in the definition of Middle.

Given that the mass of x with

The result follows by a straight forward modification of Lemma 3.4 to show that with probability at least 1o(1),

Setting Parameters. We verify that ε 2ε 1 = Ω(1):

(where the last line is by Lemma 3.3) which is Ω(1) given choices of c 0 , c 1 , c 2 and τ made in Equation (5.28).

Proof of Theorem 1.2

We introduce some helpful notation and outline the high-level structure of the argument.

Setup and Outline of Argument

We introduce the following notation: Notation 7. Given an outcome of the control subspace C and of Nazarov's body

within C as defined earlier, for x ∈ R n+1 we define the set S B (x) as

Note that if x and y have x C = y C , then S B (x) = S B (y), i.e. only the C-part of x affects S B .

We define the regions Left, Middle, Right ⊂ R as follows:

Note that Left Middle Right Curb = R (where as before we identify R with an outcome of the one-dimensional action subspace A).

To establish indistinguishability, we show that no non-adaptive deterministic algorithm A that makes q = 2 c3n 1/4 queries, for some sufficiently small constant c 3 , can distinguish D yes from D no . Specifically, for any nonadaptive deterministic algorithm A with query complexity q, we show that (5.30) Pr

To this end, we define Bad to be the following event:

Bad: There are x, y ∈ Shell n+1 queried by A that (i) satisfy S B (x) = S B (y) = {ℓ} for some ℓ ∈ [N ] (or equivalently, x, y ∈ U ℓ for some ℓ), and (ii) have x A , y A belonging to two distinct sets among Left, Middle, Right.

We will first show in Lemma 5.1 that A can distinguish D yes from D no only when Bad occurs. On the other hand, in Lemma 5.2, we show Bad occurs with probability o(1) when the number of queries is q = 2 c3n 1/4 and c 3 is sufficiently small. Lemmas 5.1 and 5.2 together establishe Equation (5.30); the proof of this is analogous to the proof of Theorem 1 in Section 4.2 of [CDL + 24] and we refer the reader to [CDL + 24] for full details. Theorem 1.2 then follows from Equation (5.30) via Yao's minimax principle (Theorem 2.1).

Indistinguishability of D yes and D no

We write A(f ) to denote the sequence of q answers to the queries made by A to f . We write view A (D yes ) (respectively view A (D no )) to be the distribution of A(f yes ) for f yes ∼ D yes (respectively f no ∼ D no ). The following claim asserts that conditioned on Bad not happening, the distributions view A (D yes | Bad ) and view A (D no | Bad ) are identical.

Proof. Let Q be the set of points queried by A. Recall that the distributions of the subspaces C and action variables A are identical for D yes and D no . So fix an arbitrary outcome of the n-dimensional subspace C and the orthogonal one-dimensional subspace A. As the distribution of the Nazarov body B ∼ Naz(r, N, C) is also identical for D yes and D no , we fix an arbitrary outcome B of B. Let f be a random function drawn from either D yes or D no .

Note that for any point x ∈ R n+1 such that |S B (x)| = 1 or x / ∈ Shell n+1 or x A ∈ Curb, by construction we have that f (x) can be determined directly in the same way for both D yes and D no (no query is required). So it suffices for us to consider the points x such that |S B (x)| = 1, x ∈ Shell n+1 , and x A / ∈ Curb. We call these points important points.

We divide these important points into disjoint groups according to S B (x). More precisely, for every ℓ ∈

denote the function f (x) restricted to X ℓ (where as stated above, f denotes either a function drawn from D yes or from D no ). The condition that Bad does not happen implies that either x A ∈ Left for all x ∈ Q ∩ X ℓ , or x A ∈ Middle for all x ∈ Q ∩ X ℓ , or x A ∈ Right for all x ∈ Q ∩ X ℓ . In particular, this means f ℓ (x) = f ℓ (y) for all x, y ∈ Q ∩ X ℓ , and this holds for both D yes and D no .

Since f ℓ (x) are the same for all x ∈ Q ∩ X ℓ , the distribution of f ℓ is actually one random bit. Indeed, f ℓ (x) = 0 with probability 1/2 and f ℓ (x) = 1 with probability 1/2 (because each element ℓ ∈ [N ] belongs to P with probability 1/2) independently, and this holds for both D yes and D no . This completes the proof of the lemma.

Next, we show that Bad happens with probability o(1) (recall that q = 2 c3n 1/4 ). The proof of the following lemma follows the proof of an analogous lemma from [CDL + 24]: Lemma 5.2. For any fixed set of points

Proof. Fix a pair of query points x, y ∈ R n+1 that belong to Q. By the definition of Bad, we may assume without loss of generality that x, y ∈ Shell n+1 . Let Bad x,y be the event that Recall that each of the two intervals defining Curb (cf. Section 5.3.1) has the same width which we will denote ρ(c 2 ) for succinctness, i.e.

On one hand, for (b) to happen on x, y, we must have ( )

On the other hand, (a) means Proof. Fix x, y such that x-y ≤ cn 3/8 . For succinctness we write z to denote x-y, so z ∈ R n+1 and z ≤ cn 3/8 ; our goal is to show that |z A | ≤ ρ(c 2 ) except with probability at most 2 -4c3n 1/4 . Since A is a Haar-random direction in R n+1 , the distribution of z A is the same as the distribution of z • v 1 where v ∼ S n-1 . Hence by standard bounds on spherical caps (Lemma 2.1),

Taking t = √ 8c 3 • n 1/8 , this probability is at most e -4c3n 1/4 < 2 -4c3n 1/4 . So we set our threshold as

2c3 , and the lemma is established. By a union bound over all (at most 2 2c3n 1/4 ) pairs of points x, y from Q, we get that

which completes the proof.

Proof of Lemma 5.4

For the remainder of this section, we will always assume that x, y ∈ Shell n+1 satisfy xy > cn 3/8 . Note that we can view the construction g C,B,P as a two stage process:

• We first draw C, which is a Haar random n dimensional subspace of R n+1 .

• We then draw B ∼ Naz(r, N, C), and we draw P as a uniformly random subset of [N ].

We require the following claim:

Claim 8. Suppose x, y ∈ Shell n+1 satisfy xy > cn 3/8 . Then with probability at least -2 -Ω(n 1/4 ) over the outcomes of C, we have

Proof. Fix x, y ∈ Shell n+1 such that xy > cn 3/8 . Because A is drawn Haar-randomly (and since it defines C), it follows from Lemma 2.1 that

Let t = βn 1/8 for a suitable constant β > 0. The previous inequality gives

Thus, with probability 1e -β 2 n 1/4 /2 , we have

As x ∈ Shell n+1 and thus x ≤ 2 √ n, it follows that the last expression is at least x -1. Identical calculations yield the corresponding lower bounds on y C and (xy) C .

Fix an outcome C of C such that Equation (5.32) holds. For convenience, we will write x for x C , y for y C , both of which lie in R n . For the rest of the argument, we will work over C, i.e. we view sets such as H ℓ , H ℓ and B as lying in C (which we identify with R n ) rather than in R n+1 .

The following argument is analogous to (parts of) the proof of Lemma 15 of [CDL + 24]. Recall

By Claim 8, we have that

Pr [ ] ≤ 2 -Ω(n 1/4 ) + Pr Observe that the event "S B (y ) = {1}" that we are conditioning on is an event over the random draw of B, i.e. over the draw of g 1 , . . . , g N . To analyze this event it is helpful to introduce the following notation: For z ∈ R n , define

Consequently, the event "S B (y ) = {1}" is the same as the event g 1 ∈ hfsp(y ) ∧ g i / ∈ hfsp(y ) for i ∈ {2, . . . , N } .

We may fix any outcome g 2 * , . . . , g N * of g 2 , . . . , g N all of which lie outside of hfsp(y ), and we get (writing g to denote (g 1 , . . . , g N )) that

where Equation (5.34) uses Pr[X| ℓ E ℓ ] ≤ sup ℓ Pr[X|E ℓ ] as earlier; Equation (5.35) uses that if g 1 ∈ hfsp(y ) then in order to have S B (x ) = S B (y ) it must be the case that g 1 ∈ hfsp(x ) ∩ hfsp(y ); and Equation (5.36) is because the event g 1 ∈ hfsp(x ) ∩ hfsp(y ) is independent of the outcome of g 2 , . . . , g S . So in what follows our goal is to upper bound (5.36). In other words, recalling that we write Vol(K) to denote the Gaussian measure of the set K (cf. Section 2.2), our goal is to obtain an upper bound on (5.37)

(5.36) = Vol(hfsp(x ) ∩ hfsp(y )) Vol(hfsp(x )) , which is a two-dimensional problem because the only thing that matters about the outcome of g ∼ N (0, I n ) vis-a-vis (5.37) is the projection of g in the directions of x and y . Towards this goal, we recall the following tail bound for bivariate Gaussian random variables:

Proposition 5.3. (Equation (2.11) of [Wil05]) Suppose (Z 1 , Z 2 ) ∼ N (0, Σ) where

Then for h, k > 0, we have

Let g ∼ N (0, I n ). Define the random variables

and set h := r x , k := r y . It is immediate that

Furthermore, note that Var[Z 1 ] = Var[Z 2 ] = 1. We also have ρ :

x y . Thanks to Claim 8, we have (cn 3/8 -1) 2 ≤ x -

Using Claim 8 and the fact that x, y ∈ Shell n+1 , we have that x , y ≥ √ n + 1 -2 ln(2/τ ) -1 and combining this with Equation (5.38) gives

Note that Vol(hfsp(x )) = Φ(-h). Consequently, using Proposition 5.3 we get

and we will obtain an upper bound on this in the remainder of this section. In particular, note that

Recall that x , y ≤ √ n and that x ≥ √ n + 1-2 ln(2/τ )-1. Hence, for n large enough and an appropriate constant τ , we have (5.40)

and consequently, we get that

for an appropriate choice of τ . The final inequality relies on the above lower bound on x and Lemma 3.1. An identical calculation gives that ρk -h ≤ -Ω(1). It follows that

where the final inequality relies on a standard Gaussian tail bound (cf. Proposition 2.1). To see Equation (5.41), note that exp   r 2

x 2 1 -

where we used Lemma 3.1 and Equation (5.38). Equation (5.42) immediately follows from Equation (5.39). Finally, note that Equation (5.43) completes the proof.

6 Two-Sided Non-Adaptive Lower Bound Our goal in this section is to prove Theorem 1.3 restated below:

Theorem 6.1. (Two-sided non-adaptive lower bound) For any constant c > 0, there is a constant ε = ε c > 0 such that any non-adaptive ε-tester convexity over N (0, I n ) (which may make two-sided errors) must use at least n 1/4-c queries.

Setup

We recall some necessary tools and results from [CDST15].

Distributions with Matching Moments

The first results we need, stated below as Propositions 6.1 and 6.2, establish the existence of two finitely supported random variables that match the first ℓ moments of a univariate Gaussian, for any ℓ. Crucially, one of the random variables is supported entirely on non-negative reals, while the other puts nonzero probability on negative values (so if ℓ is any fixed constant, it puts a constant amount of probability on negative values): As a result, we have

and

Combining these, we have the proposition.

We adopt the following notation: for J = (J 1 , . . . , J q ) ∈ N q a q-dimensional multi-index, we let |J| denote J 1 + • • • + J q and let J! denote J 1 !J 2 ! • • • J q !. We write #J to denote |{i ∈ [q] : J i = 0}| (and we observe that #J ≤ |J|). Given X ∈ R q we write X J to denote q i=1 (X i ) Ji , and we write X| J ∈ R #J to denote the projection of X onto the coordinates for which J i = 0. For f : R q → R, we write f (J) to denote the J-th derivative, i.e.

.

We recall the standard multivariate Taylor expansion: Fact 6.1. (Multivariate Taylor expansion) Given a smooth function f : R q → R and k ∈ N,

for X, ∆ ∈ R q , where τ is uniform random over the interval [0, 1].

We recall the standard Berry-Esseen theorem for sums of independent real random variables (see for example, [Fel68]), which is a quantitative form of the Central Limit Theorem: For g ∼ N (0, I n ), the value n i=1 g 2 i is distributed according to a chi-squared distribution with n degrees of freedom, denoted χ(n) 2 . We recall the following tail bound: Lemma 6.1. (Tail bound for the chi-squared distribution, from

Following [CDST15], our proof will employ a carefully chosen "mollifier," i.e. a particular smooth function which approximates the indicator function of a set (the use of such mollifiers is standard in Lindeberg-type "replacement method" analyses). We will use a specific mollifier, given in [CDST15], whose properties are tailored to our sets of interest (unions of orthants). The key properties of this mollifier are as follows: Proposition 6.4. ( [CDST15] Proposition 4.3: "product mollifier") Let O be a union of orthants in R q . For all ε > 0, there exists a smooth function Ψ O : R q → [0, 1] with the following properties:

6.1.3 Clipping Given C > 0, we define the "clipping" function clip C : R n → {0, 1} which, on input a vector x ∈ R n , outputs 1 if and only if x ≤ √ n + C.

6.2

The Yes-and No-Distributions Let c > 0 (this is the c of Theorem 1.3 ). Let u and v be the random variables given by Propositions 6.1 and 6.2, where we take ℓ to be the smallest odd integer that is at least 1/c and take µ = µ(ℓ).

A set K drawn from our "yes-distribution" D yes has indicator function defined as follows:

• First, choose a Haar random orthonormal basis normalized so that each vector has Euclidean length 1/ √ n, and denote those vectors a (1) , . . . , a (n) . (So a (1) ∈ R n is a Haar random unit vector in R n scaled by 1/ √ n; a (2) is Haar random over the radius-(1/ √ n) sphere in the (n -1)-dimensional subspace of R n that is orthogonal to a (1) ; and so on.)

• Then n independent draws u 1 , . . . , u n are made from the real random variable u of Proposition 6.1.

(Here C > 0 is a suitable constant, depending only on c but not on n, that will be fixed later in our argument.)

A set K drawn from our "no-distribution" D no is defined very similarly, with the only difference being that v takes the place of u:

• The vectors a (1) , . . . , a (n) are chosen exactly as in the yes-case.

• Then n independent draws v 1 , . . . , v n are made from the real random variable v of Proposition 6.2.

(Here C > 0 is the same constant as in the yes-case.)

We remark that our yes-and no-functions differ from the yes-and no-functions of [CDST15] in a number of ways: Our functions involve a random orthonormal basis, they are degree-2 polynomial threshold functions rather than linear threshold functions, and they involve clipping. (In contrast the [CDST15] functions do not involve choosing a random orthonormal basis, are LTFs, and do not incorporate any clipping.)

Distance to Convexity

We first consider yes-functions. Since u is supported on non-negative real values and a (1) , . . . , a (n) are orthogonal vectors, every outcome of 1 u 1 (a (1)

is the indicator function of a ball in R n , and the intersection of a ball and an ellipsoid is a convex set, we immediately have the following: Corollary 6.1. For every C > 0, every K ⊂ R n in the support of D yes is convex.

The following lemma shows that a constant fraction of draws of K ∼ D no are constant-far from being convex (intuitively, this is because with extremely high probability a constant fraction of the coefficients v 1 , . . . , v n are negative, which causes the degree-2 PTF to be far from an ellipsoid): Lemma 6.2. For a suitable choice of the constant C > 0, with probability at least 1/2 a random K ∼ D no is κ-far from convex (where κ > 0 depends on µ and ℓ and hence only on c).

Proof. By the rotational symmetry of the N (0, I n ) distribution, we may assume that the orthonormal basis a (1) , . . . , a (n) is the canonical basis e 1 , . . . , e n scaled by 1/ √ n. Thus a draw of K ∼ D no (after a suitable rotation)

Given this, it suffices to show that a random set (6.46)

is 2κ-far from convex with probability at least 1/2. If we have this, then since K has distance at most κ from K (which holds for a suitable choice of the constant C, using Lemma 6.1), the lemma follows.

To analyze Equation (6.46), we begin by recalling that by Proposition 6.2, the random variable v has probability p i > 0 of taking value d i for 1 ≤ i ≤ ℓ , where ℓ is some value that is at most ℓ + 1, and we have

Fix any outcome (v 1 , . . . , v n ) of (v 1 , . . . , v n ) such that the event on the LHS of Equation (6.48) is satisfied. In the rest of the proof we will argue that for such an outcome the set (6.49)

corresponding to Equation (6.46) is Ω(1)-far from convex.

For each i ∈ [ℓ ], let S i ⊂ [n] denote the set of indices j ∈ [n] such that v j = d i . Let c i be such that |S i | = p i n + c i √ n, and observe that |c i | ≤ c i . For ease of notation we may suppose that S 1 consists of the first coordinates {1, . . . , p 1 n + c 1 √ n} (this is without loss of generality by the rotational invariance of N (0, I n )).

Fix any i ∈ {2, . . . , ℓ } and consider the tuple of random Gaussian coordinates (x j ) j∈Si for a draw of x = (x 1 , . . . , x n ) ∼ N (0, I n ). We have

and by the Berry-Esseen theorem (Theorem 6.2), we get that (6.50) Pr

for suitable positive absolute constants A 2 , . . . , A ℓ (depending on the p i 's and the c i 's but not on n).

Let A := ℓ • max{|d 2 |, . . . , |d ℓ |} • max{A 2 , . . . , A ℓ }.. By a union bound applied to Equation (6.50) over all i ∈ {2, . . . , ℓ }, with probability at least 9/10 we have that (6.51)

let us say that any such outcome of (x j ) j∈S2∪

•••∪S ℓ is good. Fix any good outcome (x j ) j∈S2∪•••∪S ℓ of the last n-(p 1 n+c 1 √ n) coordinates of x ∼ N (0, I n ), and let A ∈ [-A, A] be the value such that the LHS of Equation (6.51) is equal to ℓ i=2 d i p i n + A √ n. Recalling Equation (6.47), for this good outcome of the last n -(p 1 n + c 1 √ n) coordinates, the set (6.49) (viewed as an indicator function of coordinates 1, . . . , p 1 n + c 1 √ n) becomes (6.52) 1   p1n+c 1 √ n j=1 d 1 x 2 j ≤ p 1 d 1 n -A √ n   . sphere of radius r/ √ n. Hence, writing u ∼ S n-1 to denote a Haar random point from the n-dimensional unit sphere, we have Pr (a (j) • X t * ) 2 ≥ 10 ln n n = Pr u∼S n-1 |u 1 |r √ n ≥ √ 10 ln n √ n ≤ Pr u∼S n-1 u 1 ≥ √ 10 ln n r ≤ Pr u∼S n-1 u 1 ≥ 3 √ ln n √ n (using r ≤ √ n + C)

≤ e -(9/2) ln n = 1/n 9/2 , using a standard bound on spherical caps (see Lemma 2.1). Since there are only qn < n 5/4 many pairs (t, j) ∈ [q]×[n], a union bound concludes the proof.

Fix a = (a (1) , . . . , a (n) ) to be any non-bad outcome of a. Recalling Equation (6.54), by Lemma 6.3 it suffices to show that d TV (R a yes , R a no ) ≤ o(1); this is our goal in the rest of the proof. Let S ∈ R q be the random column vector whose t-th entry is u 1 (a (1) • X t * ) 2 + • • • + u n (a (n) • X t * ) 2 -µ, and let T ∈ R q be the random column vector whose t-th entry is

The response vector R a yes is determined by the orthant of R q in which S lies and the response vector R a no is determined by the orthant of R q in which T lies. So to prove a q-query monotonicity testing lower bound for non-adaptive algorithms, it suffices to upper bound In what follows, we will show that d UO (S, T ) ≤ o(1) when q = O(n 1/4-c ). To this end, let O denote a union of orthants such that and then apply Proposition 6.3 to bound (6.56).

For all i ∈ {0, 1 . . . , n} we introduce the R q -valued hybrid random variable Q (i) whose t-th coordinate is

Observe that Q (0) = S and Q (n) = T . Informally, we are considering a sequence of hybrid distributions between S and T obtained by swapping out each of the u-summands for a corresponding v-summand one by one. The main idea is to bound the difference in expectations (6.58)

)] for each i, since summing (6.58) over all i ∈ [n] gives an upper bound on

using the triangle inequality.

To bound (6.58), we define the R q -valued random variable R -i whose t-th coordinate is (6.59) (R -i ) t = i-1 j=1 v j (a (j) • X t * ) 2 + n j=i+1 u j (a (j) • X t * ) 2 .

Writing Φ(v i , a (i) ) to denote the random vector in R q whose t-th coordinate is v i (a (i) • X t * ) 2 and likewise for Φ(u i , a (i) ), we have that

Truncating the Taylor expansion of Ψ O at the ℓ-th term (Fact 6.1), we get (6.60)

where τ is a random variable uniformly distributed on the interval [0, 1] (so the very last expectation is with respect to τ , v i and R -i ). Writing the analogous expression for E[Ψ O (R -i + Φ(v i , a (i) ))], we observe that by Propositions 6.1 and 6.2 the first sums are equal term by term, i.e. we have

O (R -i ) • (Φ(u i , a (i) )) J

for each |J| ≤ h. Thus we may cancel all but the last terms to obtain

Observe that there are |{J ∈ N q : |J| = ℓ + 1}| = Θ(q ℓ+1 ) many terms in this sum. Recalling that each value of (a (j) • X t * ) 2 is at most 10 log n n (because ā is not bad), that both u i and v i are supported on at most ℓ + 1 real values that depend only on ℓ (by Propositions 6.1 and 6.2), and Proposition 6.4, we have that for any τ > 0 (we will choose a value for τ soon), (6.61)

.

Summing over all i ∈ [n] costs us a factor of n and so we get Equation (6.62) gives us the desired bound on Equation (6.57); it remains only to apply Proposition 6.3 to finish the argument. To do this, let

(B τ corresponds to the region A \ A in of Proposition 6.3). Since both v and u are supported on values of magnitude O ℓ (1), using the one-dimensional Berry-Esseen inequality (Theorem 6.2) and a union bound across the q coordinates we get that (6.63)

Pr[S ∈ B τ ], Pr[T ∈ B τ ] ≤ O ℓ (qτ ) + O ℓ (q/ √ n).

So by applying Proposition 6.3, we get that d UO (S, T ) ≤ O ℓ (qτ ) + O ℓ (q/ √ n) + O ℓ (1) • q τ ℓ+1 • (10 log n) (ℓ+1)/2 n (ℓ-1)/2 .

Choosing τ = 1/n 1/4 and recalling that ℓ is the smallest odd integer that is at least 1/c, we get that for q = O(n 1/4-c ) the RHS above is O ℓ ((10 log n) (ℓ+1)/2 n -c ). This is o(1) for any constants c > 0, ℓ ∈ N, and the proof of Theorem 1.3 is complete.