Learning and Testing Convex Functions
Abstract
We consider the problems of learning and testing real-valued convex functions over Gaussian space. Despite the extensive study of function convexity across mathematics, statistics, and computer science, its learnability and testability have largely been examined only in discrete or restricted settings – typically with respect to the Hamming distance, which is ill-suited for real-valued functions.
In contrast, we study these problems in high dimensions under the standard Gaussian measure, assuming sample access to the function and a mild smoothness condition, namely Lipschitzness. A smoothness assumption is natural and, in fact, necessary even in one dimension: without it, convexity cannot be inferred from finitely many samples. As our main results, we give:
-
Learning Convex Functions: An agnostic proper learning algorithm for Lipschitz convex functions that achieves error using samples, together with a complementary lower bound of samples in the correlational statistical query (CSQ) model.
-
Testing Convex Functions: A tolerant (two-sided) tester for convexity of Lipschitz functions with the same sample complexity (as a corollary of our learning result), and a one-sided tester (which never rejects convex functions) using samples.
Keywords and phrases:
Property testing, learning theory, Gaussian distribution, convex functionsCategory:
RANDOMFunding:
Renato Ferreira Pinto Jr.: Supported by an NSERC Postdoctoral Fellowship and by NSF grant CCF-2106429.Copyright and License:
2012 ACM Subject Classification:
Theory of computation Sample complexity and generalization bounds ; Theory of computation Models of learning ; Computing methodologies Supervised learning by regression ; Theory of computation Convex optimizationAcknowledgements:
The authors would like to thank Ramon van Handel for several enjoyable discussions concerning Question 5. E.M. would like to thank Dan Mikulincer for interesting discussions.Editors:
Mohit Singh and Tom GurSeries and Publisher:
Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik
1 Introduction
Few mathematical ideas are as pervasive or as powerful as convexity: recall that a function is convex if for every and , we have . The mathematics of convex functions has been intensively studied for over a century, and continues to be central to a number of theoretical and applied disciplines ranging from mathematical analysis to machine learning [68, 15]. Within mathematical programming, for example, convexity of the objective function often governs computational tractability; to quote Rockafellar [69], “the great watershed in optimization isn’t between linearity and nonlinearity, but convexity and non-convexity.”
This centrality of convexity motivates the following basic questions, which form the focus of this work:
How many samples are needed to learn a convex function?
How many samples are needed to test if a function is essentially convex?
We study each of these questions through the lens of theoretical computer science, viewing the former as a problem in learning theory [48] and the latter in property testing [36, 7]. For these problems to be well-defined, we must first specify a distance metric between functions on . Throughout this work, we employ the distance where denotes the measure corresponding to the -dimensional standard Gaussian distribution .
Unsurprisingly, given their fundamental nature, both problems have been studied previously:
-
There is work in statistics [72, 40, 41, 61, 32] that deals with optimal rates for convex regression where the perspective is that the dimension is fixed, and the number of samples is very large (could be more than exponential) and the question is to study the error rate as the number of samples goes to infinity. This is different than the standard perspective in learning theory where we are interested to more exactly quantify the number of samples needed as a function of the dimension.
-
Turning to the problem of testing convexity, prior work has largely concerned discrete or highly constrained settings. Much of this literature [65, 6, 63, 5, 4, 54] focuses on testing functions over finite domains or ranges under the Hamming distance, reflecting the field’s early connections to complexity theory [13, 71]. A few works such as [6] extend this line of work to real-valued functions under metrics, but still assume bounded range and full query access.
We refer the reader to Section 1.2 for a detailed discussion of related work on both testing and learning convex functions.
In this work, we study both agnostic proper learning and (tolerant) testing of convexity in high dimensions, in the statistically natural setting where one only has access to samples labeled by an unknown function . The query-access model used extensively in property testing, while natural and powerful for applications to complexity theory [13, 71], is ill-suited to statistical problems. By contrast, sample-based access is the standard framework in settings such as empirical risk minimization, convex regression, and stochastic optimization, where functions are observed only through (possibly noisy) random samples rather than arbitrary queries [67, 51, 44, 14, 73, 39].
Before proceeding, we note that some smoothness assumption is essential for both problems: without any regularity, convexity cannot be meaningfully inferred from finitely many samples, even in one dimension. Accordingly, we restrict attention to Lipschitz functions – a natural and mild assumption also adopted in prior work on convex regression [61].
1.1 Our Results
We begin by introducing notation that will be used throughout the paper. Given a function , we will write for the distance of to its nearest convex -Lipschitz function. More formally,
where
The metric is a standard choice in learning theory, property testing, and derandomization (see, for example, [52, 60, 78, 43, 53, 20, 22, 28, 23, 49, 26, 27], among many others).
Although we focus on learning and testing convex functions over Gaussian space, all of our techniques and results extend naturally to functions over under the uniform measure. We adopt the Gaussian setting as it is a more canonical model for studying real valued learning and testing problems.
1.1.1 Agnostic Proper Learning and Sample-Based Testing of Convex Functions
We construct an agnostic proper learning algorithm for Lipschitz convex functions with the following guarantees:
Theorem 1 (Agnostic proper learning of Lipschitz convex functions).
Let and suppose is a -Lipschitz function. There exists an algorithm which, given i.i.d. access to labeled samples where , draws samples, runs in time , and outputs a function such that
Additionally, the function is convex and -Lipschitz.
Note that our learning algorithm is agnostic in the sense that it produces a nearly optimal (convex) hypothesis even if the input function is arbitrarily far from convex, as long as it satisfies the Lipschitz condition.
Using the proof of the Theorem above and the “testing-via-learning” paradigm [37], we obtain a tolerant testing algorithm for Lipschitz convex functions:
Theorem 2 (Tolerant two-sided testing of Lipschitz convex functions).
Let and suppose is -Lipschitz. There is an algorithm which, given i.i.d. labeled samples where , draws samples, runs in time , and has the following performance guarantee:
-
If , then it outputs “accept” with probability ;
-
If , then it outputs “reject” with probability .
In particular, setting shows that for every fixed , there exists an (essentially) -time algorithm that distinguishes Lipschitz convex functions from those that are -far (in ) from all Lipschitz convex functions. The “testing-via-learning” approach underlies the best known sample-based testing algorithms for several other function classes including convex subsets of [52, 20], monotone Boolean functions [17, 56, 58], and -monotone Boolean functions [8].
Our proof of Theorem 1 proceeds in two steps:
-
1.
Low-Degree Approximation. We begin with a standard observation (see, for example, Theorem 4.1 of [2] or alternatively [46, 23]) that every -Lipschitz function over Gaussian space is well-approximated in by a -degree polynomial. This allows us to learn such an approximation from random samples via polynomial regression.
-
2.
Convex Regression. We then convexify the learned polynomial by projecting it onto the space of convex functions via convex regression [61]. This step is essential to obtain a proper learner – one whose output lies within the target class of convex -Lipschitz functions. For our tolerant testing result, this is essential: the “testing via learning” reduction requires the learner to be proper.
Although the first step is conceptually straightforward, it has an independent implication:
Any -Lipschitz function can be learned – and hence tested – from random samples in an information-theoretic sense.
Note, however, that this guarantee is purely information-theoretic and does not yield a computationally efficient learning algorithm for the function class. In general, however, fitting a function from the target class to the observed samples may be computationally intractable. The main conceptual contribution of Theorem 1 is that we may combine standard low-degree learning with tools specific to convexity to obtain a proper learning algorithm.
Accordingly, the second step above introduces the main technical challenge: ensuring that the projection onto convex functions can be performed in finite (albeit exponential) time while preserving the error bound. Using queries to the learned low-degree approximation on a sufficiently fine grid, we learn via convex regression a function (namely a supremum of affine functions) which approximates well on a discrete grid. Following [61], quadratic constraints in the convex regression ensure that is -Lipschitz. However, convex regression says nothing about the quality of the approximation over (continuous) Gaussian space, and the low-degree need not inherit the Lipschitz behavior of . To bridge this gap, we draw on Hermite analysis to show that the low-degree approximation is -Lipschitz for some over a large box in , where both and the size of the box can be controlled in terms of , and . This lets us recover an approximation guarantee for the convex against the original target function .
1.1.2 Lower Bounds for Learning Convex Functions
We complement this upper bound with corresponding lower bounds for learning convex functions. In the information-theoretic setting, we show that learning an arbitrary linear function to constant accuracy requires queries, not just samples; see the full version. We further strengthen this by proving a quantitatively sharper bound for algorithms in the correlational statistical query (CSQ) model:
Theorem 3 (CSQ lower bound; informal, see full version).
Suppose algorithm , given access to -Lipschitz function via correlational statistical queries, outputs a function satisfying . Then requires correlational statistical queries with tolerance .
CSQ algorithms only have access to the input via approximate inner product queries of the form , for query chosen by the algorithm; we formally define the CSQ model in the full version. This model captures, for example, gradient descent with respect to squared loss, and the algorithm attaining our upper bound from Theorem 1 via low-degree approximation is a CSQ algorithm. Thus, Theorem 3 poses a barrier to improving upon the low-degree learning approach: any agnostic learning algorithm that fits the CSQ model, even if it uses properties of convex functions to do something more sophisticated than low-degree approximation, must use statistical queries.
Our proof relies on the construction of a large family of functions with low pairwise-correlation, which is the standard approach for showing weak learning lower bounds in the CSQ model [12, 75, 33]. Additionally, we require each function in to be non-trivially correlated with a convex Lipschitz function – namely a “projected ReLU”, which is a function of the form for some . This implies that an agnostic learning algorithm for convex functions gives a weak learner for , and yields our CSQ lower bound.
Our construction and proof strategy are inspired by and leverage the results of [30], who showed an lower bound for agnostically learning ReLUs under the Gaussian distribution using statistical queries. While one might hope to immediately conclude the same lower bound for agnostically learning convex functions in our model (since ReLUs are convex), the key difference is that in our setting the input must be Lipschitz, whereas [30] build their hard family of inputs from Boolean functions. We adapt their construction to our purposes via careful application of the Ornstein-Uhlenbeck noise operator , which satisfies a few crucial properties for our application:
-
It takes bounded functions into Lipschitz ones, so that from a hard input , we may obtain a hard Lipschitz input .
-
It satisfies the self-adjointness property , which allows us to map the approximation quality of a learned hypothesis for the Lipschitz input into the approximation quality of hypothesis for the hard input .
-
Lipschitz functions are stable under noise in the sense that , which informally implies that most of the “signal” in the reduction survives our application of noise.
1.1.3 One-Sided Testing of Lipschitz Convex Functions
Our final result is a one-sided testing algorithm for Lipschitz convex functions – that is, an algorithm which never rejects a Lipschitz convex function. In general, there can be dramatic separations between the complexity of one-sided and two-sided testing (cf. [37, §1.5]), and in particular, testing by learning is not a suitable approach to one-sided testing. Therefore, this goal requires us to exploit the properties of convex and Lipschitz functions in a different way. Our result is:
Theorem 4 (One-sided testing of Lipschitz convex functions).
Let be -Lipschitz, and let . There is an algorithm, One-Sided-Tester (Algorithm 1), which, given access to i.i.d. labeled samples where , makes draws, runs in time , and has the following performance guarantee:
-
If is convex, then One-Sided-Tester outputs “accept” with probability ;
-
If , then One-Sided-Tester outputs “reject” with probability .
Our tester operates by constructing an empirical convex envelope (cf. Definition 19) of the sampled function values, which can be viewed as the function analogue of the convex hull of a collection of points. Given random samples , the tester checks whether coincides with its empirical convex envelope at these points. If is convex, this always holds; conversely, we show that if is -Lipschitz and -far from convex, then with sufficiently many samples the test will detect a violation with high probability. See Figure 1 for an illustration of the empirical convex envelope.
In particular, our analysis implies an associated agnostic learning guarantee in : we show that when the input function is an -Lipschitz convex function, the empirical convex envelope learned by One-Sided-Tester uniformly approximates the convex envelope of over all but an exponentially-small fraction of Gaussian space. Thus, the algorithm may also be viewed as a form of uniform convex regression.
1.2 Related Work
We briefly situate our results within the broader work on learning and testing convexity.
Learning Convex Functions
As discussed earlier, the statistical perspective for convex regression is interested in the error rate as the number of samples goes to infinity for fixed dimensions. This falls under the broader umbrella of shape-constrained regression. We refer the interested reader to [72, 40, 41, 61, 32] and the references therein for further background. By contrast, our results address the more general problem of agnostic proper learning from i.i.d. samples, with the goal of establishing PAC-style sample-complexity bounds rather than asymptotic error rates.
We note that low-degree approximation of Lipschitz functions over Gaussian space has been used a few times in the past; see, for example, [2, 46, 23]. Such approximations also are the source of sample-complexity bounds appearing in several agnostic learning problems beyond convexity, e.g., in the context of learning halfspaces [31, 57]. However, with the exception of [2], most of these works focus on Boolean-valued function classes rather than real-valued ones.
Approximation Theory
As indicated earlier in Section 1.1, our upper bounds for convexity testing follow from semi-agnostic learning algorithms for convex functions under the Gaussian distance. Related problems have been studied in approximation theory, both in the low-dimensional setting [74, 70] as well as in high-dimensions [45], with exponential-in- sample lower bounds known for deterministic approximation under distance [45].
More broadly, classical results in convex approximation typically focus on deterministic settings, approximating a convex function by piecewise-linear or polynomial surrogates and bounding the error in terms of smoothness or curvature (see, e.g., [29, 45]). Our setting differs in that we consider randomized, sample-based approximation under a fixed measure, leading to dimension-dependent but probabilistic guarantees.
Testing Convexity over Discrete Domains
The computational problem of recognizing convexity of quartic polynomials is known to be NP-hard [1]. (Deciding convexity of polynomials of odd-degree or quadratics is trivial, making degree the first interesting case.) See [1] and the references therein for a history of the computational problem of recognizing exact convexity of functions. The relaxed problem of recognizing approximate convexity of functions has primarily been considered in the discrete setting. The study of testing convexity of functions under the Hamming distance was initiated by Parnas, Ron, and Rubinfeld [64], where convexity is defined as non-negativity of a discrete second-derivative. Their was later extended by Ben-Eliezer [5], who obtained improved quantitative bounds; by Pallavoor, Raskhodnikova, and Verma [63], who gave an improved bound parametrized by the size of the range of the function being tested; by Blais, Raskhodnikova, and Yaroslavtsev [11], who gave lower bounds on testing convexity of real-valued functions over the hypergrid ; and by Belovs, Blais, and Bommireddi [4], 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” , and the hypergrid . These results, however, do not have any bearing on this work due to differences in domain and choice of distance metric.
Testing of Convexity
The work most closely related to ours is that of Berman, Raskhodnikova, and Yaroslavtsev [6], who study testing of convexity of an unknown where is endowed with the uniform measure. They provide tight bounds in the one-dimensional setting and exponential-in- bounds for the high-dimensional case (see Corollary B.3 of [6]). Our results, in contrast, apply specifically to Lipschitz functions , giving polynomial-in- complexity algorithms for every fixed choice of the distance parameter . (We remark that our exponential-in- algorithm from Theorem 4 has the additional property of being a tester with one-sided error, which does not follow from a black-box application of testing-by-learning.)
Although one might hope to relate the two settings, this connection does not appear to be straightforward. The two frameworks are best viewed as complementary: ours imposes regularity assumptions that enable polynomial dependence on , whereas [6] addresses unrestricted (i.e., possibly highly irregular) albeit bounded functions at exponential cost. Indeed, assuming Lipschitzness or bounded gradient is the standard regularity condition in convex analysis, optimization, and high-dimensional learning, and thus provides a more natural setting for analytic property testing.
Testing Set Convexity
A different line of research considers testing convexity of high-dimensional sets (i.e., Boolean-valued indicator functions of subsets of ). Rademacher and Vempala [66] established exponential-in- upper bounds for testing set convexity under the Lebesgue measure; they also gave a strong lower bound against a simple “line” tester for convexity. The [66] lower bound was subsequently strengthened by Blais and Bommireddi [10]. For testing set convexity under the Gaussian measure, the best-known upper bound follows from the agnostic learning algorithm for convex sets due to Klivans, O’Donnell, and Servedio [52].
Strong lower bounds for sample-based testing under the Gaussian measure were established by Chen, Freilich, Servedio, and Sun [20], and the first lower bounds in the query model were obtained recently by Chen, De, Nadimpalli, Servedio, and Waingarten [21]. While our work shares conceptual and technical similarities with [52, 20, 21], there does not appear to be a reduction or formal connection between the two settings. In particular, natural attempts to reduce testing convexity of functions to testing convexity of sets (such as mapping a function to its epigraph) fail to preserve the relevant distance measures, so neither problem appears to subsume the other.
Finally, beyond the Gaussian setting, the work of Black, Blais, and Harms [9] also considers consider testing and learning convex subsets of the ternary hypercube .
1.3 Discussion
As evidenced above, convexity is a powerful and pervasive principle whose associated computational problems are notoriously challenging and enjoy long lines of study from a plethora of perspectives. We view the present work as a first step in posing and investigating the problems of learning and testing convex functions in the continuous setting from the perspective of learning theory and property testing. Our results establish that these problems are computationally feasible, albeit not at present with efficient algorithms, and suggest barriers to be tackled for overcoming this limitation: any agnostic learning algorithm with truly sample complexity, beating the low-degree learning bound from Theorem 1, must not be a CSQ algorithm (Theorem 3); and any algorithm (for learning or testing) with subexponential running time must bypass the grid-based approaches of Theorems 1 and 4.
We conclude with a number of open directions suggested by our work.
Analogy with Boolean Monotonicity
Convexity is formally connected to the monotonicity of the gradient: in one dimension, a function is convex if and only if its derivative is monotone, and more generally, convexity corresponds to the monotonicity of the gradient map. This connection suggests a natural analogy between convexity and monotonicity, and one might hope that insights from the rich body of work on learning and testing monotone Boolean functions can inform the study of convex function learning and testing.
For learning, our results may at first appear considerably stronger than existing bounds for learning monotone Boolean functions. (Recall that the sample complexity of agnostically learning monotone Boolean functions over is [17].) However, this stems from the -Lipschitz assumption in our setting, which has no meaningful analog in the Boolean function setting. While all Boolean functions are technically -Lipschitz, the underlying metric geometry differs between the Boolean setting and Gaussian space: in the Boolean space (see, for example, [55]), the typical (Hamming) distance between points in dimension is of order while in the Gaussian space the typical distance is of order . So, at least in some sense, our polynomial agnostic learning algorithm does correspond to the results for learning monotone functions with samples.
As for testing, in the Boolean setting the analogous quantity to is the distance to monotonicity , which has been extensively investigated in a rich line of work on monotonicity testing [38, 18, 50]. Classical Boolean monotonicity testers rely on upper bounds on in terms of the directed edge boundary, and these structural relationships can be viewed as strengthenings of the classical edge-isoperimetric inequalities on the hypercube [59, 76].
This analogy raises a natural question: can likewise give rise to structural inequalities that quantify the “non-convexity” of real-valued functions? Motivated by the role of the directed edge boundary in monotonicity testing, the following question suggests itself:
Question 5.
Given an -Lipschitz function , is
where is the negative-definite part of ?
If true, such an inequality would likely imply a convexity tester based on random samples of (or queries simulating) the Hessian of , mirroring how monotonicity testers – both in discrete and continuous settings – leverage local gradient information [50, 34]. Beyond its algorithmic implications, this inequality would also be of intrinsic geometric interest, as it would relate a global measure of non-convexity (namely, ) to local curvature data through the Hessian.
As a step toward understanding , we establish in the full version a quantitative relationship between and the negative degree-2 Hermite coefficients of , which yields a lower bound on in terms of their magnitude.
We note that an independent line of work has identified an unexpected but powerful analogy between monotone Boolean functions and convex subsets of Gaussian space [24, 28, 25, 26, 27]. It is natural to ask which aspects of this correspondence extend further to the setting of convex functions over Gaussian space. As a first step in this direction, we note that [24] establishes a quantitative sharpening of Hu’s correlation inequality for symmetric convex sets [47], in the spirit of Talagrand’s quantitative correlation inequality [77].
Testing Lower Bounds
Since we are concerned with functions whose outputs are real-valued, standard information-theoretic approaches to proving lower bounds become infeasible. A basic but significant obstacle – shared with many real-valued testing problems – is that each sample reveals a real number , which, at least naively, may contain an arbitrarily large amount of information. Presently, there is no general framework for establishing lower bounds for testing convexity of real-valued functions, even in the purely sample-based setting.
Therefore, we pose the following two questions on the true sample complexity of testing convexity of Lipschitz functions in the two-sided and one-sided error regimes. For two-sided testing, it is conceivable – again in analogy with monotonicity testing – that some polynomial dependence on is unavoidable. We ask:
Question 6.
Does testing convexity of -Lipschitz functions under the Gaussian distribution (with two-sided error) require samples? What if arbitrary queries are allowed?
Even for one-sided testing algorithms, we currently lack any nontrivial lower bounds on the sample complexity of testing convexity. It is instructive to recall how an exponential lower bound is obtained for the analogous problem in the setting of set convexity [20]. In particular, Lemma 29 of [20] establishes that for sufficiently small constant , if points are drawn independently from , then with high probability no point lies in the convex hull of the others. Consequently, such a draw of samples is consistent with the indicator function of a convex set, and a one-sided sample-based tester cannot detect any violation of convexity.
The difficulty in our setting is that a sample with no witnessed violation of convexity need not be consistent with any -Lipschitz function that is convex. In particular, a naive interpolation through the sampled points may fail to be -Lipschitz. Thus, it is not immediate that a one-sided tester must accept unless the sample explicitly contains a convexity violation. This leads to the following question:
Question 7.
Is there a tester for convexity of -Lipschitz functions under the Gaussian distribution with one-sided error and sample complexity that is sub-exponential in ?
Sample vs. Runtime Gaps
We note that while Theorem 1 achieves a sample complexity of , its runtime remains exponential in . An analogous gap long persisted for properly learning monotone Boolean functions from samples: the best-known sample complexity was , whereas the best runtime was . Recent work by [56, 58] closed this gap, giving a -time agnostic proper learner. It is natural to ask whether a similarly efficient proper learning algorithm exists for convex functions, potentially closing the gap between information-theoretic and computational efficiency in our setting as well.
Lower Bounds in the Full SQ Model
Our lower bound from Theorem 3 applies to correlational statistical query (CSQ) algorithms, a setting that already captures the algorithm attaining our upper bound. Recall that CSQ algorithms only have access to the input via approximate inner product queries of the form . In contrast, the full SQ model allows approximate oracle access to for general query functions .
In the (distribution-specific) setting of Boolean functions, the CSQ model is equivalent to the full SQ model [16], because SQ queries to Boolean functions may be simulated using correlational queries. However, the same is not true in the real-valued setting, where there exist separations between the CSQ and SQ models, for example for the problem of ReLU regression [42]. Indeed, proving lower bounds against SQ algorithms in the real-valued setting is a notoriously challenging problem; see [35, 19] and the discussion therein. We leave as an open question whether our CSQ lower bound can be extended to the full SQ model, or whether our problem witnesses a separation between these models.
Organization
In the rest of this paper, we outline the proofs of our main upper bound results – Theorems 1, 2, and 4. We defer proofs of technical lemmas and our lower bounds to the full version.
2 Preliminaries
We use boldfaced letters – such as – to denote random variables (which may be real-valued, vector-valued, function-valued, or set-valued; the intended type will be clear from the context). We write to indicate that the random variable is distributed according to the probability distribution . Throughout, will denote the unit sphere in . We will write for the -ball of radius , i.e.,
Hermite Analysis over Gaussian Space
Our notation and terminology follow Chapter 11 of [62]. We say that an -dimensional multi-index is a tuple , and we define .
For , we write to denote the space of functions that have finite second moment under the Gaussian distribution, i.e., if
When the dimension is clear from context, we will write instead. We view as an inner product space with
We will sometimes write for notational convenience. We recall the Hermite basis for :
Definition 8 (Hermite basis).
The Hermite polynomials are the univariate polynomials defined as
In particular, we have
| (1) |
The following fact is standard:
Fact 9 (Proposition 11.33 of [62]).
The Hermite polynomials form a complete, orthonormal basis for . For the collection of -variate polynomials given by where
forms a complete, orthonormal basis for .
Given a function and , we define its Hermite coefficient on as . It follows that can be uniquely expressed as
with the equality holding in ; we will refer to this expansion as the Hermite expansion of . One can check that Parseval’s and Plancharel’s identities hold in this setting:
We recall the Gaussian Poincaré inequality (see, e.g., [3]):
Proposition 10.
Suppose is differentiable. Then
3 Agnostic Proper Learning and Two-Sided Sample-Based Testing
Write for the class of convex, -Lipschitz functions:
Recall our notation for the distance to the set of convex -Lipschitz functions, which we may now write as
By convention, given a function , by “sample from ” we mean a sample of the form where . The main result in this section is the following.
Theorem 1 (Agnostic proper learning of Lipschitz convex functions). [Restated, see original statement.]
Let and suppose is a -Lipschitz function. There exists an algorithm which, given i.i.d. access to labeled samples where , draws samples, runs in time , and outputs a function such that
Additionally, the function is convex and -Lipschitz.
Combining the agnostic proper learning algorithm with a distance estimation step, we obtain a sample-based tolerant tester for Lipschitz convex functions:
Theorem 2 (Tolerant two-sided testing of Lipschitz convex functions). [Restated, see original statement.]
Let and suppose is -Lipschitz. There is an algorithm which, given i.i.d. labeled samples where , draws samples, runs in time , and has the following performance guarantee:
-
If , then it outputs “accept” with probability ;
-
If , then it outputs “reject” with probability .
Proof.
Note that
by the Poincaré inequality (Proposition 10), the fact that is -Lipschitz, and the fact that constant functions are convex. Hence we may assume that , since otherwise the tester can immediately accept.
On input , the tester uses the learning algorithm from Theorem 1 to learn a function satisfying with probability at least ; assume henceforth that this event occurs. It then takes samples , and accepts if and only if
The sample and time complexity claims are immediate, and we now prove correctness. Let , so that and . Define the centered function . Then is centered and -Lipschitz, and hence sub-Gaussian with sub-Gaussian norm . Then
By the sub-Gaussianity of , we have and . Moreover, we have
We conclude that . By Chebyshev’s inequality,
for suitable choice of . Suppose . Then if , we obtain
and the tester accepts. On the other hand, suppose . Then, recalling that is a convex, -Lipschitz function, we obtain
and the tester rejects. By a union bound, the tester correctly accepts/rejects except with probability at most , which may be made as small as desired by a standard majority vote.
Proof of the Main Result
We require the following lemmas, whose proofs we defer to the full version. The first lemma says that a Lipschitz function is well-approximated by its low-degree Hermite expansion. This fact has been observed before, e.g. in [2, 46] for domain ; here we give a Gaussian version. Recall the notation for the degree- Hermite expansion of .
Lemma 11 (Lipschitz functions are approximately low-degree).
Let , let be -Lipschitz, and let . Then .
Additionally, we now give upper bounds on the number of samples required to approximately learn the low-degree Hermite coefficients of a Lipschitz function. We assume for simplicity that has expectation bounded by some constant (this assumption is not essential, and the general case is recovered in the proof of Theorem 1).
Lemma 12 (Learning a single Hermite coefficient).
Let , , , and let be -Lipschitz and satisfy . Then
suffice to compute an estimate satisfying with probability at least . The running time is polynomial in the number of samples.
We have the following immediate consequence:
Corollary 13 (Learning a low-degree expansion).
Let , , , and let be -Lipschitz and satisfy . Then
suffice to obtain coefficient estimates , for all with , such that the function satisfies with probability at least . The running time is polynomial in the number of samples.
We will require a simple a priori upper bound on the Lipschitz constant of the low-degree approximation above in terms of distance to the origin:
Lemma 14 (Lipschitz constant of low-degree polynomials).
Let be a degree- polynomial. Then for all , we have
The next lemma says that, given query access to a Lipschitz function which is close to some convex Lipschitz function over a ball, we may learn (via convex regression) a good convex approximation to using a finite number of queries. We will apply this result to an approximation of the low-degree restriction over the restriction of the Gaussian measure to a sufficiently large ball. It is convenient to work with the centered radius- -ball , i.e. an axis-aligned hypercube.
Remark 15.
This number of queries used for the convex regression is exponential in ; however, we make these queries to the learned approximation rather than the input function , so we pay this cost in the running time but not in the sample complexity.
Lemma 16 (Learning a Lipschitz convex approximation).
Let , and let be the probability measure conditioned to . There exists an algorithm which, given parameters , with , and query access to some -Lipschitz function , makes queries to and outputs a function that is a nearly optimal convex approximation of over with respect to -Lipschitz functions, in the following sense: for all convex, -Lipschitz , we have
The running time is polynomial in the number of queries.
To translate back and forth between full Gaussian space and its restriction to an -ball, while approximately preserving the distance between Lipschitz functions, we use the following lemma.
Lemma 17 (Restricting Gaussian space to a box).
There exists a universal constant such that the following holds. Let , , and let . Let be probability measure conditioned to . Then for all -Lipschitz functions such that for some , we have
Remark 18.
The condition that for some in Lemma 17 holds in particular if , since otherwise the choice of radius is large enough to yield (say) , a contradiction.
Equipped with these results, we may prove Theorem 1.
Proof of Theorem 1.
We first claim that we may assume without loss of generality that . Indeed, the algorithm may first compute an approximation of up to additive error using samples (by Chebyshev’s inequality, since by Proposition 10, and the Lipschitz assumption), then proceed with the modified input function and shift the final output again by .
We may also assume that (by rescaling the input and if necessary) and that (otherwise, we get by the triangle and Poincaré inequalities, and we may immediately output the constant zero function).
Let and . The algorithm first uses
to learn, via Corollary 13, a degree- approximation satisfying with probability at least ; assume henceforth that this event occurs. By Lemma 11 and the triangle inequality, we have . Note that satisfies .
Let be large enough to ensure that, when we set
as the upper bound on the Lipschitz constant of over via Lemma 14, we obtain
for sufficiently large choice of absolute constant so that, by Lemma 17, ball gives an -approximation for the distance between and -Lipschitz functions for parameter . (One may check that it is possible to choose satisfying this.)
Let be the function produced by Lemma 16 with input , the choice of above, and parameters , and . Note that the number of queries to , and thus the running time of this step, is
We claim that satisfies the guarantee of Theorem 1. We already have that , so it remains to show that . Let be any function satisfying (which exists because is -close to the constant function by the Poincaré inequality), so that . We have
| (Lemma 17, see below) | ||||
| (Lemma 16) | ||||
| (Lemma 17 via Remark 18) | ||||
To justify the first use of Lemma 17, we claim that satisfies at some point . Indeed, note that the function satisfies (by Lemma 17 via Remark 18) ; hence, if we had for all , we would obtain , contradicting Lemma 16.
Since the above holds for all sufficiently close to , we obtain as desired.
4 One-Sided Sample-Based Testing
We now turn to convexity testing algorithms with one-sided error, i.e., algorithms that never incorrectly reject a convex function. Our main result here is the following:
Theorem 4 (One-sided testing of Lipschitz convex functions). [Restated, see original statement.]
Let be -Lipschitz, and let . There is an algorithm, One-Sided-Tester (Algorithm 1), which, given access to i.i.d. labeled samples where , makes draws, runs in time , and has the following performance guarantee:
-
If is convex, then One-Sided-Tester outputs “accept” with probability ;
-
If , then One-Sided-Tester outputs “reject” with probability .
Note that in contrast to our upper bound for standard testing (Theorem 2), our sample complexity is exponentially worse.
Our one-sided testing algorithm proceeds by constructing an empirical convex envelope of the function using labeled samples. We will ensure by design that when is convex, its empirical convex envelope is close (in an sense) to . On the other hand, when is far from convex, it will be far from its empirical convex envelope, which will be revealed by the samples. The strong guarantee of the convex envelope may be contrasted with our two-sided tester from Theorem 2, which also proceeds via learning but rather in sense (which is a weaker guarantee that more precisely matches our target metric for testing).
4.1 The Empirical Convex Envelope
We will require the following definition:
Definition 19 (Empirical convex envelope).
For a function and points , we define the empirical convex envelope of with respect to as the function defined by
Informally, is the “largest” convex function that is below on all the sampled points . We record two immediate properties of the empirical convex envelope for future use:
Lemma 20.
Suppose is -Lipschitz, and let . Let be the empirical convex envelope of with respect to .
-
1.
The empirical convex envelope is convex and -Lipschitz.
-
2.
Furthermore, if is itself convex, then for all , .
Proof.
Note that convexity of is immediate from Definition 19 since the supremum of affine functions is convex. Additionally, the constraint that ensures that is -Lipschitz. Together, these imply the first item.
We now turn to the second item. Since for all by construction, it remains to show that for . This is readily seen to hold by taking and . Since is -Lipschitz, and by Rademacher’s theorem Lipschitz functions are differentiable almost everywhere, it follows that . Since is a supremum over all feasible and , it follows that .
Next, we note that the empirical convex envelope can be computed on an input by the quadratically constrained convex program CECE (short for “compute empirical convex envelope”) given in Figure 2.
Lemma 21.
Let be -Lipschitz, and let . Let be the empirical convex envelope of with respect to . Then for each , the program is feasible and satisfies . Additionally, CECE runs in time .
Here, we are assuming the real-valued model of computation, where infinite-length real-valued computations can be achieved with one unit operation. However, our results work equally well in the bounded-bit model, where we use and assume finite bits of precision, with some minor (and routine) modifications to the analysis.
Proof.
Note that the quadratic program in Figure 2 coincides with the definition of the empirical convex envelope from Definition 19, and so correctness holds. (Feasibility can be verified by taking and small enough, since the set is finite.) The runtime is also immediate via standard guarantees for solving convex programs [15].
| maximize | |||
| subject to | |||
4.2 Algorithm 1 and Technical Results
We now formally describe our one-sided convexity testing algorithm, One-Sided-Tester(cf. Algorithm 1). We also record some useful lemmas before proving Theorem 4. For the remainder of this section, we set , where are as in Theorem 4.
The first lemma shows that the distance from to its convex envelope can be well-approximated by considering only the points in the set .
Lemma 22.
Let be a set of points in . Let be a -Lipschitz function and let be its empirical convex envelope with respect to . Then for all , we have
Proof.
Fix . For each , we have
| (triangle inequality) | ||||
| ( are -Lipschitz) |
as desired.
The following lemma shows that with high probability, a draw of roughly samples from will be sufficiently “dense” in , which will help us bound the error term in Lemma 22. The proof computes a lower bound of the Gaussian density inside , and then uses a union bound to show that, with high constant probability, each small cube in a partition of contains at least one sample.
Lemma 23.
Let be as in Algorithm 1, and suppose are i.i.d. draws. Then with probability , for all we have
Proof.
Note that . Partition into a hypergrid of at most (hyper)cubes, each of side length . Suppose for every cube in the grid there exists a point in the cube. Then note that
thanks to our choice of .
Thus, in order to establish Lemma 23, it suffices to show that after drawing samples, with probability at least , every cube in the hypergrid contains at least one sample. We will show this by taking a union bound over the cubes in the hypergrid.
In this argument, it will be necessary to consider the cube in the hypergrid with minimal Gaussian measure. Note that the maximum norm of any point in the hypergrid is at most . Therefore for all , we have
Since the Lebesgue measure of any cube is , the minimum Gaussian measure of any of the cubes in our hypergrid is at least
The probability that independent draws from all fail to land in this cube is
Applying a union bound, it follows that the probability that there exists a cube in the hypergrid not containing any sample is at most
and it is readily verified that this is at most for our choice of and , for some universal constant .
Finally, the next lemma shows that, under the density condition above, if and agree on all points in then they are close in .
Lemma 24.
Suppose is an -Lipschiz function and is a set of points in such that for all , there exists such that , for . Let be the empirical convex envelope of with respect to . If for all , then .
Proof.
We decompose into the regions inside and outside and apply Lemma 22:
which is less than for large enough .
4.3 Proof of Theorem 4
Proof.
First, note that the sample complexity of One-Sided-Tester is as desired. We establish correctness as well as the runtime bound below, starting with the former.
Correctness.
We first show that if is -Lipschitz and convex, then One-Sided-Tester accepts with probability . Indeed, Algorithm 1 only outputs “reject” when for some , which cannot happen by Lemmas 20 and 21.
For soundness, suppose that , so that in particular . Suppose the algorithm samples a set of points in such that for all , there exists such that , for ; by Lemma 23 this occurs with probability at least . In this case the algorithm rejects, because it would only accept if we had for every ; since for each by Lemma 21, this would imply via Lemma 24 that , a contradiction. Therefore the algorithm rejects with probability at least .
Runtime.
Note that Step 1 takes time and Step 2 takes time
Finally, Step 3 requires time by Lemma 21. It follows that Algorithm 1 uses time .
References
- [1] Amir Ali Ahmadi, Alex Olshevsky, Pablo A Parrilo, and John N Tsitsiklis. NP-hardness of deciding convexity of quartic polynomials and related problems. Mathematical programming, 137:453–476, 2013. doi:10.1007/s10107-011-0499-2.
- [2] Alexandr Andoni, Rina Panigrahy, Gregory Valiant, and Li Zhang. Learning sparse polynomial functions. In Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms, pages 500–510. SIAM, 2014. doi:10.1137/1.9781611973402.37.
- [3] Dominique Bakry, Ivan Gentil, and Michel Ledoux. Analysis and Geometry of Markov Diffusion Operators. Grundlehren der mathematischen Wissenschaften. Springer Cham, 2014. doi:10.1007/978-3-319-00227-9.
- [4] Aleksandrs Belovs, Eric Blais, and Abhinav Bommireddi. Testing convexity of functions over finite domains. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2030–2045. SIAM, 2020. doi:10.1137/1.9781611975994.125.
- [5] Omri Ben-Eliezer. Testing Local Properties of Arrays. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019), Leibniz International Proceedings in Informatics (LIPIcs), pages 11:1–11:20, 2019. doi:10.4230/LIPIcs.ITCS.2019.11.
- [6] Piotr Berman, Sofya Raskhodnikova, and Grigory Yaroslavtsev. -testing. In Proceedings of the forty-sixth annual ACM symposium on Theory of computing, pages 164–173, 2014. doi:10.1145/2591796.2591887.
- [7] Arnab Bhattacharyya and Yuichi Yoshida. Property Testing: Problems and Techniques. Springer, 2022. doi:10.1007/978-981-16-8622-1.
- [8] Hadley Black. Nearly optimal bounds for sample-based testing and learning of k-monotone functions. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024), pages 37–1. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024. doi:10.4230/LIPIcs.APPROX/RANDOM.2024.37.
- [9] Hadley Black, Eric Blais, and Nathaniel Harms. Testing and Learning Convex Sets in the Ternary Hypercube. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024), pages 15–1. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024. doi:10.4230/LIPIcs.ITCS.2024.15.
- [10] Eric Blais and Abhinav Bommireddi. On testing and robust characterizations of convexity. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM, pages 18:1–18:15, 2020. doi:10.4230/LIPIcs.APPROX/RANDOM.2020.18.
- [11] Eric Blais, Sofya Raskhodnikova, and Grigory Yaroslavtsev. Lower bounds for testing properties of functions over hypergrid domains. In 2014 IEEE 29th Conference on Computational Complexity (CCC), pages 309–320. IEEE, 2014. doi:10.1109/CCC.2014.38.
- [12] Avrim Blum, Merrick L. Furst, Jeffrey C. Jackson, Michael J. Kearns, Yishay Mansour, and Steven Rudich. Weakly learning DNF and characterizing statistical query learning using fourier analysis. In Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, pages 253–262. ACM, 1994. doi:10.1145/195058.195147.
- [13] Manuel Blum, Michael Luby, and Ronitt Rubinfeld. Self-testing/correcting with applications to numerical problems. In Proceedings of the twenty-second annual ACM symposium on Theory of computing, pages 73–83, 1990. doi:10.1145/100216.100225.
- [14] Léon Bottou. Large-scale machine learning with stochastic gradient descent. In Proceedings of COMPSTAT 2010, pages 177–186. Physica-Verlag HD, 2010. doi:10.1007/978-3-7908-2604-3_16.
- [15] Stephen P Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, 2004. doi:10.1017/CBO9780511804441.
- [16] Nader H. Bshouty and Vitaly Feldman. On using extended statistical queries to avoid membership queries. J. Mach. Learn. Res., 2:359–395, 2002. URL: https://jmlr.org/papers/v2/bshouty02a.html.
- [17] Nader H Bshouty and Christino Tamon. On the Fourier spectrum of monotone functions. Journal of the ACM (JACM), 43(4):747–770, 1996. doi:10.1145/234533.234564.
- [18] Deeparnab Chakrabarty and Comandur Seshadhri. A monotonicity tester for boolean functions over the hypercube. In Proceedings of the forty-fifth annual ACM symposium on Theory of Computing, pages 411–418, 2013. doi:10.1145/2488608.2488660.
- [19] Sitan Chen, Aravind Gollakota, Adam R. Klivans, and Raghu Meka. Hardness of noise-free learning for two-hidden-layer neural networks. In Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NeurIPS 2022, 2022. URL: http://papers.nips.cc/paper_files/paper/2022/hash/45a7ca247462d9e465ee88c8a302ca70-Abstract-Conference.html.
- [20] X. Chen, A. Freilich, R. Servedio, and T. Sun. Sample-based high-dimensional convexity testing. In Proceedings of the 17th Int. Workshop on Randomization and Computation (RANDOM), pages 37:1–37:20, 2017. doi:10.4230/LIPIcs.APPROX-RANDOM.2017.37.
- [21] Xi Chen, Anindya De, Shivam Nadimpalli, Rocco A Servedio, and Erik Waingarten. Lower bounds for convexity testing. In Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 446–488. SIAM, 2025. doi:10.1137/1.9781611978322.13.
- [22] Anindya De, Elchanan Mossel, and Joe Neeman. Is your function low dimensional? In Alina Beygelzimer and Daniel Hsu, editors, Conference on Learning Theory, COLT 2019, volume 99 of Proceedings of Machine Learning Research, pages 979–993. PMLR, 2019. URL: http://proceedings.mlr.press/v99/de19a.html.
- [23] Anindya De, Elchanan Mossel, and Joe Neeman. Robust testing of low dimensional functions. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 584–597, 2021. doi:10.1145/3406325.3451115.
- [24] Anindya De, Shivam Nadimpalli, and Rocco A. Servedio. Quantitative correlation inequalities via semigroup interpolation. In 12th Innovations in Theoretical Computer Science Conference, ITCS 2021, volume 185 of LIPIcs, pages 69:1–69:20, 2021. doi:10.4230/LIPIcs.ITCS.2021.69.
- [25] Anindya De, Shivam Nadimpalli, and Rocco A. Servedio. Convex influences. In Mark Braverman, editor, 13th Innovations in Theoretical Computer Science Conference, ITCS, volume 215 of LIPIcs, pages 53:1–53:21, 2022. doi:10.4230/LIPIcs.ITCS.2022.53.
- [26] Anindya De, Shivam Nadimpalli, and Rocco A. Servedio. Testing Convex Truncation. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 4050–4082, 2023. doi:10.1137/1.9781611977554.ch155.
- [27] Anindya De, Shivam Nadimpalli, and Rocco A Servedio. Gaussian approximation of convex sets by intersections of halfspaces. In 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS), pages 1911–1930. IEEE, 2024. doi:10.1109/FOCS61266.2024.00115.
- [28] Anindya De and Rocco Servedio. Weak learning convex sets under normal distributions. In Conference on Learning Theory, pages 1399–1428. PMLR, 2021. URL: http://proceedings.mlr.press/v134/de21a.html.
- [29] Ronald A. DeVore and George G. Lorentz. Constructive Approximation, volume 303 of Grundlehren der Mathematischen Wissenschaften. Springer-Verlag, Berlin, 1993.
- [30] Ilias Diakonikolas, Daniel Kane, and Nikos Zarifis. Near-optimal SQ lower bounds for agnostically learning halfspaces and relus under gaussian marginals. In Hugo Larochelle, Marc’Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, 2020. URL: https://proceedings.neurips.cc/paper/2020/hash/9d7311ba459f9e45ed746755a32dcd11-Abstract.html.
- [31] Ilias Diakonikolas, Daniel M Kane, Vasilis Kontonis, Christos Tzamos, and Nikos Zarifis. Agnostic proper learning of halfspaces under gaussian marginals. In Conference on Learning Theory, pages 1522–1551. PMLR, 2021. URL: http://proceedings.mlr.press/v134/diakonikolas21b.html.
- [32] Lutz Dümbgen. Shape-constrained statistical inference. Annual Review of Statistics and Its Application, 11, 2024. doi:10.1146/annurev-statistics-033021-014937.
- [33] Vitaly Feldman. A complete characterization of statistical query learning with applications to evolvability. J. Comput. Syst. Sci., 78(5):1444–1459, 2012. doi:10.1016/j.jcss.2011.12.024.
- [34] Renato Ferreira Pinto Jr. Directed Isoperimetry and Monotonicity Testing: A Dynamical Approach. In 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS), pages 2295–2305. IEEE, 2024. doi:10.1109/FOCS61266.2024.00134.
- [35] Surbhi Goel, Aravind Gollakota, and Adam R. Klivans. Statistical-query lower bounds via functional gradients. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, 2020. URL: https://proceedings.neurips.cc/paper/2020/hash/17257e81a344982579af1ae6415a7b8c-Abstract.html.
- [36] Oded Goldreich. Introduction to Property Testing. Cambridge University Press, 2017. doi:10.1017/9781108135252.
- [37] Oded Goldreich, Shari Goldwasser, and Dana Ron. Property testing and its connection to learning and approximation. Journal of the ACM (JACM), 45(4):653–750, 1998. doi:10.1145/285055.285060.
- [38] Oded Goldreich, Shafi Goldwassert, Eric Lehman, and Dana Ron. Testing monotonicity. In Proceedings 39th Annual Symposium on Foundations of Computer Science (Cat. No. 98CB36280), pages 426–435. IEEE, 1998. doi:10.1109/SFCS.1998.743493.
- [39] Bram L Gorissen, İhsan Yanıkoğlu, and Dick Den Hertog. A practical guide to robust optimization. Omega, 53:124–137, 2015. doi:10.1016/j.omega.2014.12.006.
- [40] Piet Groeneboom and Geurt Jongbloed. Nonparametric estimation under shape constraints. Cambridge University Press, 2014. doi:10.1017/CBO9781139020893.
- [41] Adityanand Guntuboyina and Bodhisattva Sen. Nonparametric shape-restricted regression. Statistical Science, 33(4):568–594, 2018. doi:10.1214/18-STS665.
- [42] Anxin Guo and Aravindan Vijayaraghavan. Agnostic Learning of Arbitrary ReLU Activation under Gaussian Marginals. In The Thirty Eighth Annual Conference on Learning Theory, volume 291 of Proceedings of Machine Learning Research, pages 2592–2631. PMLR, 2025. URL: https://proceedings.mlr.press/v291/guo25a.html.
- [43] Prahladh Harsha, Adam Klivans, and Raghu Meka. An invariance principle for polytopes. Journal of the ACM (JACM), 59(6):1–25, 2013. doi:10.1145/2395116.2395118.
- [44] Trevor Hastie, Robert Tibshirani, and Jerome Friedman. The Elements of Statistical Learning: Data Mining, Inference, and Prediction. Springer, 2 edition, 2009. doi:10.1007/978-0-387-84858-7.
- [45] Aicke Hinrichs, Erich Novak, and Henryk Woźniakowski. The curse of dimensionality for the class of monotone functions and for the class of convex functions. Journal of Approximation Theory, 163(8):955–965, 2011. doi:10.1016/j.jat.2011.02.009.
- [46] Daniel Hsu, Clayton H. Sanford, Rocco A. Servedio, and Emmanouil Vasileios Vlatakis-Gkaragkounis. On the Approximation Power of Two-Layer Networks of Random ReLUs. In Conference on Learning Theory, COLT 2021, volume 134 of Proceedings of Machine Learning Research, pages 2423–2461. PMLR, 2021. URL: http://proceedings.mlr.press/v134/hsu21a.html.
- [47] Yaozhong Hu. Itô-wiener chaos expansion with exact residual and correlation, variance inequalities. Journal of Theoretical Probability, 10(4):835–848, 1997. doi:10.1023/A:1022654314791.
- [48] Michael J Kearns and Umesh Vazirani. An introduction to computational learning theory. MIT Press, 1994. URL: https://mitpress.mit.edu/books/introduction-computational-learning-theory.
- [49] Zander Kelley and Raghu Meka. Random Restrictions and PRGs for PTFs in Gaussian Space. In 37th Computational Complexity Conference (CCC 2022), Leibniz International Proceedings in Informatics (LIPIcs), pages 21:1–21:24, 2022. doi:10.4230/LIPIcs.CCC.2022.21.
- [50] Subhash Khot, Dor Minzer, and Muli Safra. On monotonicity testing and Boolean isoperimetric-type theorems. SIAM Journal on Computing, 47(6):2238–2276, 2018. doi:10.1137/16M1065872.
- [51] Anton J. Kleywegt, Alexander Shapiro, and Tito Homem-de Mello. The sample average approximation method for stochastic discrete optimization. SIAM Journal on Optimization, 12(2):479–502, 2002. doi:10.1137/S1052623499363220.
- [52] A. Klivans, R. O’Donnell, and R. Servedio. Learning geometric concepts via gaussian surface area. In 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 541–550, 2008. doi:10.1109/focs.2008.64.
- [53] Pravesh Kothari, Amir Nayyeri, Ryan O’Donnell, and Chenggang Wu. Testing surface area. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014. SIAM, 2014. doi:10.1137/1.9781611973402.89.
- [54] Abhiruk Lahiri, Ilan Newman, and Nithin Varma. Parameterized convexity testing. In Symposium on Simplicity in Algorithms (SOSA), pages 174–181. SIAM, 2022. doi:10.1137/1.9781611977066.12.
- [55] Jane Lange, Ephraim Linder, Sofya Raskhodnikova, and Arsen Vasilyan. Local lipschitz filters for bounded-range functions with applications to arbitrary real-valued functions. In Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2881–2907. SIAM, 2025. doi:10.1137/1.9781611978322.93.
- [56] Jane Lange, Ronitt Rubinfeld, and Arsen Vasilyan. Properly learning monotone functions via local correction. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 75–86. IEEE, 2022. doi:10.1109/FOCS54457.2022.00015.
- [57] Jane Lange and Arsen Vasilyan. Robust learning of halfspaces under log-concave marginals. In Advances in Neural Information Processing Systems, volume 38, 2025. URL: https://proceedings.neurips.cc/paper_files/paper/2025/hash/91a5bb5e5939cb075f5f2464d7b8bbf0-Abstract-Conference.html.
- [58] Jane Lange and Arsen Vasilyan. Agnostic proper learning of monotone functions: beyond the black-box correction barrier. SIAM Journal on Computing, 55(3):FOCS23–1–FOCS23–32, 2026. doi:10.1137/24M1630463.
- [59] Grigorii Aleksandrovich Margulis. Probabilistic characteristics of graphs with large connectivity. Problemy peredachi informatsii, 10(2):101–108, 1974. URL: http://mi.mathnet.ru/ppi1034.
- [60] K. Matulef, R. O’Donnell, R. Rubinfeld, and R. Servedio. Testing halfspaces. SIAM J. on Comput., 39(5):2004–2047, 2010. doi:10.1137/070707890.
- [61] Rahul Mazumder, Arkopal Choudhury, Garud Iyengar, and Bodhisattva Sen. A computational framework for multivariate convex regression and its variants. Journal of the American Statistical Association, 114(525):318–331, 2019. doi:10.1080/01621459.2017.1407771.
- [62] R. O’Donnell. Analysis of Boolean Functions. Cambridge University Press, 2014. URL: http://www.cambridge.org/de/academic/subjects/computer-science/algorithmics-complexity-computer-algebra-and-computational-g/analysis-boolean-functions.
- [63] Ramesh Krishnan S Pallavoor, Sofya Raskhodnikova, and Nithin Varma. Parameterized property testing of functions. ACM Transactions on Computation Theory (TOCT), 9(4):1–19, 2017. doi:10.1145/3155296.
- [64] Michal Parnas, Dana Ron, and Ronitt Rubinfeld. On testing convexity and submodularity. SIAM Journal on Computing, 32(5):1158–1184, 2003. doi:10.1137/S0097539702414026.
- [65] Michal Parnas, Dana Ron, and Ronitt Rubinfeld. Tolerant property testing and distance approximation. Journal of Computer and System Sciences, 72(6):1012–1042, 2006. doi:10.1016/j.jcss.2006.03.002.
- [66] Luis Rademacher and Santosh Vempala. Testing geometric convexity. In Foundations of Software Technology and Theoretical Computer Science (FSTTCS), pages 469–480, 2005. doi:10.1007/978-3-540-30538-5_39.
- [67] Herbert Robbins and Sutton Monro. A stochastic approximation method. The Annals of Mathematical Statistics, 22(3):400–407, 1951. URL: https://www.jstor.org/stable/2236626.
- [68] R. Tyrrell Rockafellar. Convex Analysis, volume 28 of Princeton Landmarks in Mathematics and Physics. Princeton University Press, 1970.
- [69] R Tyrrell Rockafellar. Lagrange multipliers and optimality. SIAM review, 35(2):183–238, 1993. doi:10.1137/1035044.
- [70] Günter Rote. The convergence rate of the sandwich algorithm for approximating convex functions. Computing, 48(3):337–361, 1992. doi:10.1007/BF02238642.
- [71] Ronitt Rubinfeld and Madhu Sudan. Robust characterizations of polynomials with applications to program testing. SIAM Journal on Computing, 25(2):252–271, 1996. doi:10.1137/S0097539793255151.
- [72] Emilio Seijo and Bodhisattva Sen. Nonparametric least squares estimation of a multivariate convex regression function. The Annals of Statistics, 39(3):1633, 2011. doi:10.1214/10-AOS852.
- [73] Shai Shalev-Shwartz and Shai Ben-David. Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press, 2014. URL: http://www.cambridge.org/de/academic/subjects/computer-science/pattern-recognition-and-machine-learning/understanding-machine-learning-theory-algorithms.
- [74] Gyorgy Sonnevend. An optimal sequential algorithm for the uniform approximation of convex functions on . Applied Mathematics and Optimization, 10(1):127–142, 1983. doi:10.1007/BF01448382.
- [75] Balázs Szörényi. Characterizing statistical query learning: Simplified notions and proofs. In Algorithmic Learning Theory, 20th International Conference, ALT, pages 186–200. Springer, 2009. doi:10.1007/978-3-642-04414-4_18.
- [76] Michel Talagrand. Isoperimetry, logarithmic sobolev inequalities on the discrete cube, and margulis’ graph connectivity theorem. Geometric & Functional Analysis GAFA, 3(3):295–314, 1993. doi:10.1007/BF01895691.
- [77] Michel Talagrand. How much are increasing sets positively correlated? Combinatorica, 16(2):243–258, 1996. doi:10.1007/BF01844850.
- [78] Santosh S. Vempala. Learning Convex Concepts from Gaussian Distributions with PCA. In 51th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 124–130, 2010. doi:10.1109/FOCS.2010.19.
