Many functions that model individual economic utility, the output of manufacturing processes, and natural phenomena in the social sciences are either convex or concave. For example, convex functions are used to model utility functions that exhibit temporal discounting, a classic effect in behavioral economics where people value immediate rewards over delayed rewards [Frederick et al., 2002, Green and Myerson, 2004]. To measure such curves, it is common practice to manipulate a variable (e.g., delay) over a fixed, uniformly spaced grid of 5 points [Fisher, 1937], collect many repeated trials of data, and fit a function of assumed parametric form (e.g., exponential or hyperbolic) using maximum likelihood estimation. This approach can be brittle to model mismatch when the true function f lies outside the assumed class of functions. Moreover, non-linear parametric families can introduce challenges for constructing faithful and accurate confidence intervals when interpolating the estimator between measured design points.

Non-parametric convex regression (c.f. Dümbgen et al. [2004]) corrects for the shortcomings of parametric methods by making no assumptions other than that f is convex. In additional to faithfully modeling a large class of functions, non-parametric methods can also be employed to construct error bars at any (see Cai et al. [2013]). Unfortunately, even with shape restrictions, non-parametric methods may require prohibitively many samples for practical use.

In this paper, we propose a more parsimonious approach to non-parametric curve estimation by allowing the design points to be chosen sequentially and adaptively. Formally, we consider the problem of estimating an unknown convex function with an estimator which is close in the metric . The estimator is constructed from sequential, noisy evaluations from an oracle F at design points

and where represents zero-mean noise. We let denote the filtration generated by the design points and measurements up to time t, and assume that the number of samples is a stopping time with respect to , where is zero mean, -subgaussian. We refer to measurement allocation strategies for which does not depend on as passive, and adaptive sampling strategies for which may depend on

Our main contributions are the following:

• Inspired by Cai et al. [2013], we introduce the local approximation modulus, a new measure of local curvature for convex functions, , and a function-specific complexity measure , called the average approximation modulus. coin- cides with the average curvature of , up to logarithmic factors and endpoint considerations. We prove a function-specific lower bound on the sample complexity of actively estimating any convex function that scales at least as , up to logarithmic factors.

• The packing argument for constructing our lower bound explicitly describes a near-optimal, clairvoyant sampling allocation tailored to ; we call this the “oracle allocation” (Proposition 3.4). This allocation is instructive as an experimental benchmark when

• We introduce an active sampling procedure and an estimator whose sample complexity forany up to logarithmic factors, nearly matching our lower bounds.

• We show that for passive designs (e.g., sampled evenly on a grid), the sample complexity necessarily scales as , where coincides with the maximum curvature. We compare and for many natural classes of functions, including quadratic functions, exponential curves, and k-piecewise linear functions. For k-piecewise linear functions, the error of our active algorithm scales no slower than , whereas passive designs scale no faster than evaluations (see Remark 3.2).

Finally, we validate our theoretical claims with an empirical study using both synthetic functions and those derived from real data. We observe that in low-noise settings or when the sampling budget is large, active sampling can substantially outperform passive uniform sampling. Moreover, our algorithm constitutes the first theoretically justified algorithm (passive or active) that guarantees uniform accuracy, even at the boundaries of the interval [Cai et al., 2013, Dümbgen et al., 2004]. Even so, comparing the performance of our active algorithm to the oracle sampling strategy suggests room for modest but non-negligible improvements.

1.1 Related Work

Castro et al. [2005] and Korostelev [1999] studied the minimax rates of active non-parametric regression, showing that active and passive learning attain the same minimax rates of convergence for Holder smooth classes, but that active learning achieves faster rates when the function is known to be well approximated by a piecewise-constant function.

Prior literature on convex and concave regression consider the passive design case, where the design points do not depend on measurements. Typically, the design points are chosen to be uniformly spaced on the unit interval, that is, for [Dümbgen et al., 2004]. If F is the set of Lipschitz, convex functions, then the of the least squares estimator decreases like , whereas if the convex function has Lipschitz gradients, the rate improves to [Dümbgen et al., 2004].

Recent work by Guntuboyina and Sen [2015] and Chatterjee [2016] has aimed at developing sharp errors bounds on the squared -norm of the least squares estimator, when samples are uniformly spaced on a grid. They show that even with this uniform allocation, the error to the true regression functions . For example, Chatterjee [2016] and Bellec et al. [2018] show that if is a k-piecewise linear function, then obtains the parametric error rate of . In a similar vein, Cai et al. [2013] proves sharp confidence intervals for for a fixed point

Our work draws heavily upon Cai et al. [2013] (who in turn build on Dümbgen et al. [2003]), whose aim was to characterize the function-specific sample complexity of estimating a convex f at a given point in the interior of [0, 1], from uniform measurements. We extend these tools to characterize the complexity of estimating f with uniform accuracy over the interval [0, 1], from measurements which may be chosen in an adaptive, function-dependent manner. We are thus able to obtain exceptionally granular, instance-specific results similar to those in the multi-arm bandit literature [Kaufmann et al., 2016], and in recent work studying the local minimax sample complexity of convex optimization [Zhu et al., 2016].

We begin by establishing preliminary notation. The class of convex functions is denoted as . For an interval , define the left-, middle- and right-endpoints as . We define the secant approximation of f on an interval

and note that for a convex function, this approximation never underestimates f; that is, one has . We denote the error of the second approximation to f on I at the midpoint as

In addition, we overload notation so that for any x, t such that , we have We now state a remarkable fact about convex functions that is at the core of our analysis.

Lemma 2.1 is a special case of a more general lemma stated in Section 6 that upper bounds the supremum of the secant approximation error by a constant using only a single point within the interval. Convexity is critical to the proof of this lemma and such a property does not hold, for instance, on merely monotonic functions. We remark that the first inequality is trivial, and the second inequality is tight in the sense that it is achieved by on interval I = [0, 1] as

The above observations motivate our strategy of approximating f with secant approximations on disjoint intervals whose union is [0, 1]. The next definition relates the secant approximation error to the required sampling density.

Definition 1 (Local Approximation Modulus) We define the -approximation modulus of f at a point as the least t such that the midpoint secant approximation to bias

Note that , because convex functions are continuous on their domain. Intuitively, is the scale at which f “looks” linear around some x, up to a tolerance from the endpoints {0, 1}, smaller values of correspond to larger complexities, because they imply that f can only be approximated by a linear function on a small interval. But if x is the near will take small values, potentially overestimating the local complexity. We remedy this issue by defining the following left- and right-approximation points:

Within , we will show that the midpoint errors concisely describe how densely one would need to sample f in the neighborhood of in order to estimate it to the desired accuracy in the -norm. Moreover, we show that it suffices to sample at constant number of design points on the end-intervals and . At a high level, the main finding of this paper is as follows:

The sample complexity of learning a particular convex function accuracy in passive sampling is parametrized by the worst-case approximation modulus

In contrast, the sample complexity of active sampling algorithms is parametrized by the average approximation modulus

We emphasize that the algorithm presented in in this work guarantees accuracy on the whole interval [0, 1], whereas many passive algorithms pointwise and risk bounds [Cai et al., 2013, Dümbgen et al., 2004] only guarantee accuracy on a strictly smaller sub-interval.

2.1 Examples

Explicit parameterizations of provide intuition for when active sampling is advantageous. In this section, we describe different scalings of for various ; later, in Remark 3.2, we explain how these scalings can imply substantial differences in sample complexity.

2.1.1 Piecewise Linear Functions

Let be a Lipschitz, piecewise linear convex function with a constant number of pieces. It follows that where is the distance to the closest knot adjoining any two linear pieces of . It follows that

2.1.2 Bounded third-derivative:

Suppose . We may apply a Taylor series to find as , which makes an explicit connection between the curvature of the function and the differences between . This suggests that if the function has areas of high but localized curvature such as or then the difference between can be as vast as

2.1.3 Quadratic Functions:

Let for some real coefficients a, b, c. Ignoring the effect of endpoints, for all x due to the function having constant curvature, so

In this section, we state a formal upper bound obtained by Algorithm 2, described in Section 4. Algorithm 2 takes in a confidence parameter , as well as a second parameter the degree to which the active sampling algorithm is ‘aggressive’; from simulations, we recommend setting . Lastly, at each round, Algorithm 2 maintains an estimator , whose performance is characterized by the following theorem:

Theorem 3.1 Let C > 0 be a universal constant, and for

Then, if Algorithm 2 is run with parameters and , with access to an oracle (1), the estimators and confidence estimates defined in Section 4.2 satisfy the following any-time guarantee:

In the case of the default parameter setting , we find that, for a possibly larger universal constant

Up to constants and logarithmic factors, the sample complexity is dominated by the term corresponds to the standard rate for estimating a scalar. The dependence on captures the number of points required to estimate f with a discretized proxy.

To better understand why is the appropriate quantity to consider, we now introduce a construction of local packings of , centered at a given . Recall that denotes the error of the secant approximation to f on the midpoint of I, constructed using the endpoints . We note that if any algorithm, even an active one, does not measure f on an interval , then one cannot distinguish between f and the alternative function . Thus, a key step to showing that approximately lower bounds the number of evaluations is to show that it approximately lower bounds the number of intervals . This is achieved in the following theorem proved in Section 5.3:

be a convex function, , and define

where is defined analogously. Then, there is an such that the points such that the intervals

have disjoint interiors, are contained in and satisfy . Moreover, the interval endpoints overlap so that

Note that corresponds to the actual size of the explict packing, and is a computable lower bound on . We now consider the class of alternative functions

We observe that , and by definition, if are distinct, then In particular, given any set of points , then there exist two convex functions in , such that for all i and . In Section 5.2, we formalize this argument to yield the following theorem:

be as in Lemma 3.2, and let and be as given by Equation (7). Let Alg be any active algorithm that returns an estimator a stopping time , and satisfies the correctness guarantee

Then the stopping time , under observations from f, is lower bounded by

and the average sample complexity over is at least

The above bounds hold when is replaced by

Remark 3.1 The additional logarithmic factor that arises in (9) is due to the fact that estimating a function corresponds to correctly performing simultaneous hypothesis tests, regarding the value of g on each of the intervals . However, for any fixed (and, in particular, f = g), one can devise an algorithm that does not suffer this logarithmic factor by ‘biasing’ the algorithm towards that function.

In addition to providing a lower bound, the packing of Theorem 3.2 defines a near-optimal covering as well, in the sense that it defines a sampling allocation that can be used to test the hypothesis that, for a given . Formally, we have the following:

Proposition 3.4 For every function , there exists a

a deterministic sampling allocation , and a test function constructed from the allocation

The design is explicitly constructed in Section 5.3 by augmenting the -intervals in Theorem 3.2 with at most three additional intervals to ensure coverage of all of [0, 1]. Crucially, we made use of the fact that intervals share endpoints, and have secant error exactly equal to . In light of Theorem 3.3, we see that the design is optimal for verifying that to scaling by constant factors. For this reason, we refer to this construction as the oracle allocation since it precisely characterizes the optimal sampling allocation taken if one . In general, this allocation may be too optimistic, since an algorithm which does not know the true cannot choose this allocation a fortiori.

3.1 Comparison between Upper and Lower Bounds

For the purpose of comparing upper and lower bounds, we will consider running Algorithm 2 with the setting ; any constant bounded away from zero will yield qualitatively similar results. We find that the upper bound of Theorem 3.1 and lower bound of Theorem 3.3 nearly match, with the following exceptions:

1. The upper bound involves a doubly logarithmic factor that depends on . This is a consequence of the law of the iterated logarithm, which Algorithm 2 uses to maintain uniform correctness of its confidence intervals over time.

2. Theorem 3.1 is given in terms of , whereas our lower bound is stated in terms of . The two quantities can be related by the following proposition, proved in Section 6.4.

cω

Hence, ignoring the contributions of the endpoints , rescaling by a multiplicative constant by at most c.

3. Lastly, the upper and lower bounds differs in that requires dividing through by . We conjecture that the lower bound more accurately reflects the true sample complexity; see Remark A.1.

3.2 Sample Complexity for Passive Designs

In this section, we show that the sample complexity for estimating a convex function f with an approximately uniform passive design up to error is governed by the parameter

Theorem 3.6 Consider a (possibly randomized) passive design , which is uniform in the sense that, for some , and any interval I = [a, b] with , one has that . Then, for a universal constant c, any and all such that , there exists an alternative

The proof for the above theorem is as follows. Let

which intuitively corresponds to the point with the highest local curvature. Further, let , so that . If we consider the alternative function

then by construction, and f differ only on and . So if Alg can estimate f up to -norm error , then Alg can distinguish between f and . Consequently, standard information-theoretic arguments (Section 5.2) imply that any sampling algorithm must collect samples within . Theorem 3.6 then follows by the uniformity of the sampling procedure. In the case where the design is passive but not uniform, it is possible that the design performs well on particular functions . In Remark A.2, we show that nevertheless, if the design is not uniform, it will underperform on a ‘translation’ of f.

Remark 3.2 (Piecewise linear) If f is Lipschitz and piecewise linear with a constant number of pieces, then from Section 2.1 we have whereas . Theorem 3.6 implies that any passive sampling procedure requires measurements whereas Theorem 3.1 says that our active sampling procedure takes just . Thus, after n total samples the of passive sampling decays no faster than whereas active sampling decays like

We now introduce the recursive secant approximation algorithm for learning a convex function with noise. We begin by sampling each endpoint {0, 1} once. Subsequently, let t = 3, 4, . . . denote the number of samples taken, and let denote a binary tree of intervals contained in [0, 1], where

the children of an interval I are given by and . We let denote the set of leaves of . By construction, immediately satisfies the following properties stipulated in Lemma 4.1:

Lemma 4.1 For any , we have for any ; ; and

At each round t, we maintain three estimates of f. First, an estimator defined only at the points . Second, a secant-approximation estimator which extends the domain of

Note that is well defined, since by Lemma 4.1, for all , (a) there exists an such that and (b) if for , then x is a common endpoint of and , and thus the secant approximations coincide at Lastly, since is not guaranteed to be convex when measurements are noisy, we define an estimator projection onto

By definition so that by the triangle inequality. When not clear from context, we employ the use of a subscript t on to denote these functions once t samples have been taken.

4.1 Recursive Secant Approximation without Noise

To build intuition for Algorithm 2, we consider the following noiseless variant of our main algorithm, Algorithm 1, where the oracle returns noiseless queries F(x) = f(x). In this case, is set to be equal to f(x) at each point x that is queried, and a placeholder value of elsewhere. The algorithm maintains the invariant that, for all and have been measured and recorded in . Moreover, since the queries are noiseless, the secant approximation and no projection is required.

At each round, Algorithm 1 queries the interval for which the secant bias largest; note that if there is an interval has not been sampled, then will be queried, with ties broken arbitrarily. In preparation for the analysis of the noise-tolerant algorithm, we shall analyze the stopping time:

We shall prove the following proposition:

Proposition 4.2 For all . Moreover, for any we have

Proof Since for all queried points x, we have that, for . Moreover, since for any is constructed using secant approximations on a refinement of the intervals (see Lemma 6.1.)

It remains to bound . Let denote the set of points sampled at the start of round t; in the noiseless setting, , but bounding will be of broader interest for the noise-tolerant algorithm. Since are the endpoints of the intervals , which are adjacent, we have . Moreover, if denotes the parent-intervals of , we have . Thus, to bound , it suffices to bound . We adopt the shorthand

We now make a key observation about , which will allow us to relate to : for every , we have ; if not, then at the round at which I is bisected, we have , which implies that , a contradiction. The following lemma, proved in Section 4.4, shows that the inequality implies that the average modulus on each I cannot be too small.

Lemma 4.3 Let , and suppose that . Then for any ,

As a consequence, for any . To relate to the integral , we observe that the intervals are disjoint except at their endpoints, which yields

We remark that our bound on only used the fact that at time we had for each . This observation will be essential in generalizing to the setting with a noise oracle.

4.2 Recursive Secant Approximation with Noise

We now describe how to generalize Algorithm 1 to allow for noisy observations. Fix some time t and let be the collection of noisy function evaluation pairs. Recall that is independent, mean-zero -sub-Gaussian distributed noise, i.e. . In the algorithm, will denote the number of times the point been sampled so that if , and otherwise. Lastly, we let denote an anytime confidence interval such that

For example, suffices but we recommend using Kaufmann et al. [2016, Theorem 8]. In general can be chosen to be monotically decreasing in the t-argument, and increasing in the -argument. In addition to , we maintain a function such that

We shall let denote the event inside the probability operator in the above display. Finally, define confidence bounds

Crucially, our confidence bounds ensure the following sandwich relation, proved in Section 4.5:

Lemma 4.4 On , the following holds for all and

As a consequence, we find that

using the while loop of Line 10. This is to ensure that the stochastic variance always dominates the bias of the approximation. The parameter appears to have little effect on performance as long as it is smaller than 1; we recommend setting . The definition of in the algorithm is motivated by the sandwich relationship (Lemma 4.4) noted above. And in each case, is chosen in order to minimize the maximum confidence bound relevant to the interval . The values of

4.3 Proof of Upper Bound, Theorem 3.1

Recall the definition set , and we shall assume that holds. Fix an be as in Algorithm 2 Line 5, and define the stopping time

The correctness guarantee is a direct consequence of (14) since on . Because is only updated using a decreasing sequence of values of , the guarantee immediately holds for all . In order to upper bound , we have the identity

Thus, a crucial part of bounding is showing that we do not ; this is accomplished by relating the stopping condition to the sampling rule.

As a consequence,

where the second line uses the fact that is monotone in its second argument, and . We can upper bound the inversion of to yield (see e.g. Kaufmann et al. [2016])

To wrap up, it suffices to prove that for some

Recalling the argument from Section 4.1, it suffices only to verify that, if the secant approximation error of its parent is lower bounded by . We prove this as follows: fix some for . If is the parent of I then there exists some previous time s < t such that

that is, . On the other hand, to split on we must also have that

Together, these two displays imply . Rearranging, we find which proves what we set out to verify.

4.4 Proof of Lemma 4.3

Fix . This proof relies on the following upper-continuity property of , whose proof is deferred to Section 6.2:

, and suppose that

which proves one side of the integral. A similar argument holds for

4.5 Proof of Lemma 4.4

Define . First note that

using the fact that the secant approximations are affine on Lemma 2.1. Adding and subtracting

whence we conclude . For the lower bound, we see

so that

Remark 4.1 In the proof of Lemma 4.4 we lower bound quite loose since this quantity is also lower bounded by and can be at least a factor of two smaller. Nevertheless, using matching upper and lower bounds for substantially simplifies clutter in the algorithm. It is straightforward to modify the algorithm to use these non-matching upper and lower bounds for superior empirical performance, and, indeed, our experiments implement this modification.

4.6 Proof of Lemma 4.5

Fix an , and let be the last round at which was sampled; note then that . It suffices to bound . If is a new, just-bisected interval then we must have that by the sampling rule (was sampled only a single time.

Otherwise, has been sampled more than once and This means that for one has that

where the last line follows by the sampling rule. It suffices for the right-hand side to be less than to meet the stopping condition.

5.1 Proof of Theorem 3.2

We construct the packing by choosing a sequence of interval midpoints and interval lengths , such that the intervals overlap only at their endpoints, and such that . To do this, we define . By definition of , we have the equality , and for each

One can think of as as the equivalent of , but starting at rather than zero. Note that is non-decreasing and continuous in t (Lemma 6.3), and thus, if there exists a such that , then the supremum in the definition of will be attained for a . Thus, we will terminate the construction at i = n, where n is the first number satisfying , or . Note that . Collecting what we have established thus far,

1. . By Lemma 6.4, it follows that

2. By definition, . And, by the stopping condition,

3. Hence, since , we have that , and that have disjoint interiors.

To conclude, we adopt an argument similar to the proof of Proposition 4.2. For ease of notation, define . We start off by showing thatfor

one has

and thus the number of intervals satisfies

Finally, we remove the last interval . Since the right endpoint the intervals are contained within , and we have

Note then that we may take

5.1.1 Proof of Lemma 5.1

We first need a technical lemma, which we prove in Section 6.5.

We shall now establish; the bound on the integral over is analogous. We can write as , where and . Now, set . Using Lemma 5.2, we can integrate

where (a) is precisely Lemma 5.2. Lastly, we can bound , since

5.2 Proof of Noisy Lower Bound, Theorem 3.3

It suffices to prove the theorem with N replaced by , since ; the case where is addressed at the end of the section. Let Alg be any algorithm satisfying the correctness guarantee (8) for some denote the law under g and Alg. Consider the local alternative class and intervals , where are defined Theorem 3.2 and (7), respectively. Let denote the random variable corresponding to the number of times Alg samples in the interior of , and observe that since the intervals in i have disjoint interiors, the stopping time

We can reduce to a multiple hypothesis testing problem by recalling that, for , . Hence, for , the events are pairwise disjoint. Further, by (8), one has . We also recall Birge’s inequality:

denote a family of probability distributions on a space denote pairwise disjoint events. If

To apply Birge’s inequality, we first compute for any such that g(x) = h(x) for all denote the and , which is equal to

where (i) uses the fact that g and h differ only on uses the fact that, on , one of {g, h} is equal to , one is equal to , and thus by Lemma 2.1, we have that

First part of Theorem 3.3: For each , let denote the alternative corresponding to the vector in (7). Hence, differ only on

Birge’s inequality with

We rearrange to get , and sum over to obtain

Hence, applying Birge’s inequality with , and the disjoint events , we have that for any

where the last inequality uses the KL-computation above, and the fact that differ only on

small (even zero), we still have the bounds for every . To this end, fix ; we show . Let h be the alternative to g in which differs only on , and let denote the event that Alg never samples in . Note then that for any event A,

where we used that

. When , we can consider the single alternative function , the above arguments show that one needs at least samples to distinguish between

5.3 Proof of Proposition 3.4

Recall that the construction of the packing in Theorem 3.2 in Section 5.3 is constructed with n = intervals of the form . Define the interval and . The following fact is straightforward to verify using the construction in Section 5.3:

Fact 5.4 The intervals , and satisfy

Let . We collect -samples at each , and define to denote the empirical mean of these samples. We then define our test function to be

It now suffices to show that and for satisfying . By standard sub-gaussian concentration,

which immediately implies that . To prove the other direction, it suffices to prove the following lemma:

Lemma 5.5 If satisfies , then there exists an such that

Indeed, by Lemma 5.5, the triangle inequality, and (19) we have

Proof [Proof of Lemma 5.5] We prove the contrapositive. Suppose that and let We then have that

Lastly, we observe that . Moreover, for all (in particular ), we have , which is by assumption. Thus, we can bound . Putting things together, , as needed.

In this section, we introduce structural tools regarding convex functions, and use these tools to concludes the proof of the technical lemmas used above. The first guarantee is that the error of secant approximation is monotone in the following sense:

Next, we state a generalization of Lemma 2.1:

be convex. For any , one has that

We observe that Lemma 2.1 follows as a corollary by choosing and considering the maximum over

The remainder of the section is organized as follows. In Section 6.1, we prove Lemma 6.2 and in Section 6.2, we prove Lemma 4.6. We then introduce further technical lemmas in Section 6.3, which we use to prove Proposition 3.5 in Section 6.4, and Lemma 5.2 in 6.5. The proof of Lemma 6.1 is given in Section 6.6.

6.1 Proof of Lemma 6.2

Note that adding an affine function to f does not change the value of we may assume that . Without loss of generality, we may also take and . With these simplifications, , and hence our goal is show that

or equivalently, that

To this end, fix a subgradient and some . By the definition of the subgradient, it holds that

By choosing t = 0 and t = z in the above display, we verify that (a) , and (b) . Combining (a) and (b), and noting that

as needed. On the other hand, suppose . Noting that the function is convex and satisfies

6.2 Proof of Lemma 4.6

For any

First suppose that

On the other hand, if , then similarly we have

By definition, and combining the above pieces, we get

6.3 Additional Structural Lemmas

Before continuing, we state three additional structural results that we shall need throughout. First, we observe that the following secant approximation functions are monotone:

Lemma 6.3 For any convex function , the functions and (defined on the appropriate domains) are all non-decreasing in

Proof The mononoticity of is a consequence of the monotonicity of secant approximations, Lemma 6.1. Here, we will prove that is non-decreasing; that is non-decreasing will follow by a similar argument. Write . Since continuously differentiable convex functions are dense in class, we may assume exists. Thus,

The next result states that the continuity modulus can be regarded as the inverse function of the secant error function , in the following sense:

Lemma 6.4 For any , and is equal to the unique satisfying

Lemmas 6.3 and 6.4 are used in Section 5.3, which proves the packing given in Theorem 3.2. Next, we have a ‘change-of-scale’ lemma, whose proof is at the heart of Proposition 3.5 and Lemma 5.2:

, which implies that ωφ, which is defined for t , convex, and satisfies . A standard computation (Lemma 6.6) shows that, for any , one has

where (i.a) and (i.b) are by Lemma 6.4, and (ii) uses the fact that (this is immediate from the definition of

6.4 Proof of Proposition 3.5

Let , and observe that , and similarly for

By Lemma 6.5, we have

Next, let ; we show that . Indeed, let . Since and is monotone, we have . By definition, both . Hence, Lemma 6.5 and the bound

as needed. Hence,

The case similarly yields

Putting everything together,

6.5 Proof of Lemma 5.2

We may assume without loss of generality that . For ease of notation, set

noting that is the secant approximation bias on the interval . Since , we have that

First, if

On the other hand, if

In either case , which conclude the proof.

6.6 Proof of Lemma 6.1

We begin with a simple technical lemma.

Lemma 6.6 Let be a convex function satisfying . Then for all ,

, where the first equality uses and the second uses convexity.

We are now ready to prove Lemma 6.1: Proof [Proof of Lemma 6.1] It suffices to prove that this is the case when a = c or d = b, since then . We assume without loss of generality that a = c. Then, it suffices to show that, for is non-decreasing. We have

where is convex (sum of affine function and convex function as is convex), and , we conclude by Lemma 6.6 that is non-decreasing, as needed.

In this section, we validate our theoretical results through empirical comparisons of active and passive sampling using simulated data and data drawn from the behavioral literature. In all experiments, a query at results in an observation depends on the experiments and is known to the algorithm. We construct our confidence intervals using Kaufmann et al. [2016, Theorem 8], scaled by . Further implementation details are described in Section 7.3.

7.1 Piecewise Linear Function

We begin by comparing the performance of the active and passive methods on a piecewise linear function, , over the domain . We consider the noise level . As discussed in Remark 3.2, theory predicts that, up to logarithmic factors, the error incurred by passive sampling scales as , whereas active sampling attains the parameteric rate . As a benchmark, we plot a passive algorithm based on constrainted least squares (see, e.g. Dümbgen et al. [2004]), and also plot the error incurred by sampling according to an “oracle allocation”, which samples f at the endpoints {0, 1}, as well as the inflection point x = 0.2. The implementation details are deferred to the end of the section.

Figure 1: Comparison of active, passive and oracle performance on . The x-axis is the number of samples taken, and the y-axis is error. Dotted lines denote a least-squares trendline. A slope of suggests a rate of

Figure 1 corroborates our theoretical predictions. The dotted trend lines correspond to a least-squares fit to the logarithm of the x and y coordinates, so that the displayed slopes approximate the exponent in the rate at which the errors decay. In particular, we see that the slope of the line corresponding to passive sampling is close to indicating a rate approximately equal to , and the slopes for the active and oracle methods are close to . Observe that the oracle method still significantly outperforms the active sampling algorithm, perhaps explained by the additional superfluous locations the active procedure samples at to achieve -error relative to the oracle method.

7.2 Data Derived Function

Next, we evaluate the performance of our active algorithm on a convex function derived from real data. 250 participants were asked to choose between a hypothetical reward of $100 given immediately and a reward of $115 given at a time x = 0, 1, 2, . . . , 64 days in the future (times were randomized and rescaled to be in [0, 1]). We fit a convex function to this data using least squares and sampled from it as above; the function is displayed in Figure 2.

Figure 2: Data-derived discount function. Here, the x value corresponds for the days for which the reward is delayed, and y is the fraction of the population who would accept the delay for greater monetary reward.

Figure 3: Comparison of active and passive performance on the function depicted in Figure 2. The x-axis is the number of samples taken, and the y-axis is error. Dotted lines denote a least-squares trendline.

In Figure 3, we compare the performance of the active and passive algorithms for the function f depicted in Figure 2. Again, the dotted trend lines correspond to a least-squares fit to the logarithmic of the x and y coordinates. We find that the passive algorithm appears to obtain a rate of , and the error of the active algorithm has a scaling closer to that of the parametric rate.

For insight into why the active algorithm fares better on this f, we can examine the oracle allocations, as constructed in Proposition 3.4. We find that at higher levels of granularity, f is well approximated by a piecewise linear function, and thus an oracle would only sample at a few, key design points (Figure 4):

Figure 4: A plot of the design points correspond to the oracle allocation constructed in Proposition 3.4, for granularities . Bar height is equal to 1000 divided by the number of design points.

Notice that as the granularity decreases, the oracle allocation refines its design points, dividing the function into regions in which the piecewise-linear approximation holds to a higher accuracy.

7.3 Implementation

The passive algorithm samples at design points along a dyadic sequence The algorithm then estimates using the following constrained least squares problem.

We found in practice that this least squares minimization performs surprising well in practice, drastically outperforming projections in the -norm. We used this observation to modify the implementation of our active algorithm. At each round, the active algorithm alternates between sampling a design points as in Algorithm 2, and sampling dyadic sequences supported on . We then return using the constrained least-squares problem in (23). In addition, our implementation makes use of the sharper upper- and lower-confidence bounds described in Remark 4.1.

Pierre C Bellec et al. Sharp oracle inequalities for least squares estimators in shape restricted regression. The Annals of Statistics, 46(2):745–780, 2018.

Stéphane Boucheron, Gábor Lugosi, and Pascal Massart. Concentration inequalities: A nonasymptotic theory of independence. Oxford University Press, 2013.

T Tony Cai, Mark G Low, Yin Xia, et al. Adaptive confidence intervals for regression functions under shape constraints. The Annals of Statistics, 41(2):722–750, 2013.

Rui Castro, Rebecca Willett, and Robert Nowak. Faster rates in regression via active learning. Advances in Neural Information Processing Systems, 18, 2005.

Sabyasachi Chatterjee. An improved global risk bound in concave regression. Electronic Journal of Statistics, 10(1):1608–1629, 2016.

Lutz Dümbgen, Sandra Freitag, and Geurt Jongbloed. Consistency of concave regression with an application to current-status data. Mathematical Methods of Statistics, 13:69–81, 2004.

Lutz Dümbgen et al. Optimal confidence bands for shape-restricted curves. Bernoulli, 9(3):423–449, 2003.

Ronald Aylmer Fisher. The design of experiments. Oliver And Boyd; Edinburgh; London, 1937.

Shane Frederick, George Loewenstein, and Ted O’donoghue. Time discounting and time preference: A critical review. Journal of economic literature, 40(2):351–401, 2002.

Leonard Green and Joel Myerson. A discounting framework for choice with delayed and probabilistic rewards. Psychological Bulletin, 130(5):769–792, 2004.

Adityanand Guntuboyina and Bodhisattva Sen. Global risk bounds and adaptation in univariate convex regression. Probability Theory and Related Fields, 163(1-2):379–411, 2015.

Emilie Kaufmann, Olivier Cappé, and Aurélien Garivier. On the complexity of best-arm identification in multi-armed bandit models. The Journal of Machine Learning Research, 17(1):1–42, 2016.

Alexander Korostelev. On minimax rates of convergence in image models under sequential design. Statistics & Probability Letters, 43(4):369–375, 1999.

Yuancheng Zhu, Sabyasachi Chatterjee, John Duchi, and John Lafferty. Local minimax complexity of stochastic convex optimization. Advances in Neural Information Processing Systems, 29, 2016.

Remark A.1 (Gap Between Upper and Lower Bounds) Let f be a k-piecewise linear function f. Then there exists a set of k intervals such that f is linear on each interval; measuring f at would be enough to estimate f with zero error over [0, 1]. Hence, we must have . On the other hand, , and indeed one can show that for a k-piecewise linear function, , yielding the necessary cancelation. As with the term scales at most as for most reasonable functions, and can be bounded by for any twice-differentiable function f. Overall, we conjecture that the true sample complexity lies closer to , because in the noiseless setting, one can approximate left- and right-derivatives of f to arbitrary accuracy using just two points. This makes it possible to learn a 2-piecewise linear function with a constant number of function evaluations, rather than the implied by

Remark A.2 (Sub-Optimality of Non-Uniform Designs) In this remark, we argue that although non-uniform designs can improve upon uniform designs for some functions of interest, in general they provide no benefit.

To present the argument, we begin with by recalling the proof of Theorem 3.6. We argued that given and , then unless a design collects samples in the interior of the interval , the alternative function

Without uniformity, we cannot rule out that the design concentrates its samples in . Nevertheless, we can show that there is a function “similar” to f which incurs the same lower bound. For ease, assume that f is right differentiable at x = 1 and left differentiable at Letting and denote the right- and left-derivative, we can define the shift function as

We observe that is convex, and if is as above, then for any , one can verify that

Then, for any interval for which , there exists a such that . Hence, if , then even if the passive

design can estimate f correctly, it will fail to distinguish between the shifted function shifted alternative:

As a consequence, any algorithm which is -correct for all , and alternatives defined above must collect at least samples. The above argument can also be extended to the case where the shift is chosen at random (as opposed to depending on the design).