A bstract

1
Introduction
We consider the learning of real-valued functions of a single [0,1]-valued variable in a model introduced by Mycielski [11], and independently by Littlestone and Warmuth [10]. A learning problem consists of a class F of such functions. We assume that a function f ∈ F is hidden from the learner, and that learning proceeds in trials, where in the fth trial, the learning algorithm receives x, € [0,1] from the environment, is required to output a prediction ˆ γ; of f( x i ), then finds out the value of f( x i ). For each p ≥ 1, the p-performance of a learning algorithm A for F on a finite sequence σ = { x t } i < m ∈ [0, 1] and an f ∈ F is 1
The p-performance of A on F is then defined to be
We will focus primarily on the choices p ∈ {1,2}. Extending the terminology of [8], we define opt, (F) = inf L, (A, F). We limit our attention to continuous functions that are piecewise twice differentiable (i.e., twice differ- entiable except on a finite set). Let's call such functions well-behaved. We wish to model the intuition that, for many functions encountered in practice, similar inputs tend to yield similar outputs. Toward this end, for q E {1, 2, 00}, we will study the class F g of well-behaved functions whose first derivatives have q-norm at most 1. Recall that, for 1 < q < ∞, the q-norm of a function f defined on [0, 1] is defined to be
and that the infinity norm of f is the limit, as q approaches infinity, of its q-norm. The infinity norm roughly corresponds to the maximum value of |f(x)|, and the one-norm, to the average, while the two-norm lies somewhere in between. Thus, F ∞ roughly corresponds to the class of functions that are never very steep, and F 1 to the class of functions that are not very steep on average. In this paper, we determine the value of opt p ( F q ) for each ( p, q ) E {1, 2} × {1, 2, ∞}. Our main negative result is that opt 1 (Foo) = 00. This result, loosely speaking, says that even the assumption that the hidden function never has slope greater than one is not sufficiently strong to enable an algorithm to obtain any finite bound on the sum of the absolute values of the differences between predictions and true values. Our main positive result concerns the algorithm which at each trial linearly interpolates between pre­ viously seen function values, and extrapolates by predicting with the value of the hidden function at the nearest previously seen point. 2 We show that the worst-case sum of squared errors made by this algorithm while learning F 2 is 1. A trivial lower bound establishes the fact that this algorithm is optimal for F 2 with respect to the worst-case sum of squared errors, and therefore that opt 2 ( F 2 ) = 1. Since, as is easily verified, the 1-norm of a function is at most its 2-norm which is in turn at most its ∞norm, we have that F ∞ ⊆ F 2 ⊆ F 1 . Combining the first inclusion with the positive result above implies that opt 2 (F ∞ ) ≤ 1. Again, a trivial lower bound shows that this is the best possible, and therefore that opt 2 (F ∞ ) = 1. Similarly, it follows from our main negative result that opt 1 (F 1 ) ≥ opt 1 (F 2 ) ≥ opt 1 (F ∞ ) = ∞. A simple argument establishes that opt, (F1) = ∞ for all p ≥ 1. We next show that
for 0 < ε < 1. Combining this with the aforementioned results about F ∞ , we may conclude that opt α ( F ∞ ) < ∞ exactly when p > 1. For this upper bound, we analyze the algorithm which simply predicts with the value of the hidden function at the nearest previously seen element of the domain, which, though intuitively worse than the “linear interpolation” algorithm, is easier to analyze. We also prove that for 0 < c < 1, we have
which implies that optn(F2) is also finite exactly when p > 1. Finally, we consider bounded length sequences of trials, showing that the sum of (unsquared) errors made by either of the above algorithms learning F ∞ and F 2 respectively on trial sequences of length m is at most e(1+(log, m)/2). We prove a lower bound of Ω( √log m) on the worst-case sum of unsquared errors necessary for learning F 2 on sequences of m trials. Our analyses can be extended to classes of functions defined on an arbitrary interval, and to classes formed through arbitrary bounds on the various norms of the derivatives. Furthermore, the algorithms we describe do not make use of knowledge of the endpoints of the interval, or of knowledge of how steep the target function tends to be. Therefore, we may even view our upper bounds as applying to arbitrary well-behaved functions of the entire real line, where the maximum magnitude of an element of the domain encountered in a sequence of trials, as well as the steepness of the target function, appears in the bound. Our results may also be generalized to functions whose range is vector-valued, by treating each component of the predictions and true values separately. We have stated the results in their present form to facilitate presentation of lower bounds, as well as to cut down on unnecessary notation, as we feel that the essence of the problems is captured in the simple cases. Faber and Mycielski [3] proved, using a different algorithm, that opt 2 (F2) < 1. This result amounts to a special case of a beautiful theorem about learning linear functionals defined on Hilbert spaces using a generalization of the Widrow-Hoff algorithm [6, 12], and their paper contains numerous other applications of their Hilbert space results. Nevertheless, we feel it is interesting that even the very simple linear interpolation algorithm is optimal for F 2 with respect to worst-case on-line sums of squared errors. The difference in complexity of the algorithms is illustrated by the fact that the fth prediction of the linear interpolation algorithm trivially can be made in O(logt) time, whereas the best known bound on the time required for the algorithm of [3] is O(t) [2]. In recent work pursued subsequently to this research, Cesa-Bianchi, Long and Warmuth [2] generalized the results of Faber and Mycielski to show that a modification of the algorithm of [3] was optimal in the model of their paper, in which a smooth function only approximately maps x,'s to y; 's. Many statisticians, and, more recently, computational learning theorists (see e.g., [4] [1] [5]) have studied the induction of classes of functions obtained through smoothness constraints. The spirit of their work differs from ours in several ways. First, their theorems usually concern functions of potentially many real variables, where ours, at present, apply only to functions of a single real variable. On the other hand, the previous work usually involves use of probabilistic assumptions on the generation of the xi's, for instance that they are drawn independently from a fixed distribution on whatever domain, whereas our results do not use such assumptions. These assumptions have enabled researchers to prove bounds on the expected "loss" on a particular trial. In worst-case models such as that considered here, such "instantaneous" bounds are clearly impossible (see [8]). Finally, in many cases, we are able to obtain upper and lower bounds that match, including constants, which is often not the case for the previously studied problems.
2
Some negative results
In this section, we describe several settings in which no algorithm can acheive any finite bound on the cumulative loss. We begin by showing that opti (Foo) = 00. In contrast, we will show in Section 3 that optz(Foo) = 1. In our analysis, it will be convenient to consider classes of functions defined on [0, a] for a > 0, constrained by the values of the functions at 0 and a For a, b ∈ [0, 1], define Ga,s to be the class of well-behaved functions g defined on [0, a] for which g (0) = 0 and g(a) = b, with the further restriction that g'(x) < 1 for all x on which g' is defined. The following lemmas may be easily verified, e.g., by using reductions between real-valued learning problems [9] to scale, translate and reflect appropriately. Lemma 1  For any a,c > 0,opt 1 (Gca,o) = c opt 1 (Ga,o) Lemma 2 Choose a,b,c,d ∈ R. Let H be the class of well-behaved functions f from [a,b] to R for which f(a) = c and f(b) = d, which also have the property that f'(x) < 1 wherever f' is defined. Then opt 1 (H) = opt 1 (G | δ – α |, | c – α |) Next, we reduce the problem of proving a lower bound for Ga,s to smaller subproblems. Lemma 3 If 0 ≤ b ≤ a/2, then
Proof: Choose an algorithm A for learning Ga,s and c > 0. Let fil be A's first prediction, given that x 1 = a/2. Assume as a first case that fi > b/2. By Lemma 2 and the definition of opt 1 , there exist m 1 , m 2 E N, x2, …, xm1+1 E [0, a/2], xm1+2, …, xm1+m2+1 E [a/2, b], and well-behaved functions f1 : [0, a/2] → R f2 : [a/2,6] → R whose derivatives are never more than one where they are defined such that fi(a/2) = f2(a/2) = 0, and
しHence, if f is taken to be the union of f 1 and f 2 , then f E Ga,s, and if σ = (xi)imi+mi+i, then L 1 ( A, f, σ) ≥ (opt 1 (G α/ 2,0) − c) + (opt 1 (G α/ 2,6) − c). The case in which fi < b/2 is handled similarly, and the fact that c > 0 was chosen arbitrarily completes ■ the proof. Using essentially the same proof, one can establish the following. Lemma 4 If 0 < b < 1/2, then In the next lemma, opti(Ga,s) is bounded below by a suitable function of opti(G1,s). Lemma 5 For j ∈ N and b = 2-3a,
Proof : By iterating Lemma 3, concentrating on the second part, we get
Applying Lemma 1, we get
This completes the proof. We put these together to prove the main result of this section. ■ Theorem 6  opt 1 ( F ∞ ) = ∞. Proof : We will show that even for G1,0 C F ∞ , opt1 (G1,0) = ∞. Choose b = 2-(j+1) for some j ∈ N. Then
We can now solve this for opt 1 (G1,o) to get
■ Since opt 1 (F ∞ ) ≥ opt 1 (F 1,0) and j was chosen arbitrarily, opt 1 (F ∞ ) = ∞ As discussed earlier, since F ∞ ⊆ F q , q ≥ 1, this theorem has the following corollary. Corollary 7 opt 1 (F g ) = ∞ for all q ≥ 1. We may fairly easily see that the assumption that the average value of the (absolute) slope is at most one is not strong enough for practically any positive results in our model. Theorem 8  If p ∈ R, p ≥ 1, opt o ( F 1 ) = ∞. Proof: The class F 1 includes all continuous twice differentiable increasing functions with f(0) = 0 and f(1) = 1, since for such functions,
The adversary picks x 1 = 1/2 and then chooses f(x 1 ) = 0 or f(x 1 ) = 1, whichever gives greater error. Suppose f(x 1 ) = 1. Then the adversary picks x 2 = 1/4, and continues the same scheme. If f(x 1 ) = 0, the adversary picks x 2 = 3/4 and repeats, et cetera. At each trial the loss is at least 1/2 P . Using longer and I longer sequences of trials of this type, the total loss can be made arbitrarily large.
3
Some positive results
In this section we prove that a very simple algorithm performs optimally with respect to sums of squared errors when the hidden function is in F2, establishing an alternative proof that opt,(F2) = 1. Loosely speaking, this result implies that the assumption that the average value of the square of the target function's derivative is at most 1 is strong enough for an algorithm to obtain finite worst case bounds on its cumulative squared error. We showed in Section 2 that opt 2 ( F 1 ) = 00. Suppose S = {(ui, vi) : 1 < i < m} is a finite subset of [0, 1] × R such that
Define fs : [0, 1] → R as follows: for all x, fs(x) = 0, and
if | S | > 1. For f : [0, 1] → R, define the action of f, denoted by J[f], to be
Note that ||f'||2 ≤ 1 exactly when J[f] ≤ 1, and therefore that F 2 can also be thought of as the set of functions whose action is at most 1. The following lemma concerning the function of minimum action subject to certain constraints is well known, and can be proved fairly easily, for instance, through application of an elementary result from the Calculus of Variations (see [7, Theorem 2.2]3). Lemma 9 Choose m ∈ N. Let ( u 1 , v 1 ), ..., ( um, vm ) be a sample. Let S = {( u i, v i ) : 1 ≤ i ≤ m }. If f is a well-behaved function consistent with (U1, V1), ..., (Um, Vm), then J[f] ≥ J[fs] The following lemma concerns the change in the action of fs when we add an example to S. Lemma 10 Choose m ∈ N. Let (u1,v1),…,(um,vm) be a sample with 0 ≤ u1 < u2 < · · · < um ≤ 1. Let S = {(u;,v;) : 1 ≤ i ≤ m}. Choose an example (x,y) ∈ [0,1] × R.  Then
If there exists 1 ≤ j ≤ m such that | x − u j | = | x − u j + 1 | = m in j | x − u j | , then
Proof: The lemma is trivial if x < u 1 or x > u,m, and if there is a j for which x = u j . Assume that there is a j such that uj < x < uj+1 If a = uj+1 − uj, b = f(uj+1) − f(uj), c = xi − uj, and e = (fs(xi) − f(xi)) = (fi − f(xi)) (see Figure 1), we can easily see that
yielding (4) in the case c = a — c. In general, (5) implies
5 completing the proof.ロNow we are ready for the learning result. Consider the learning algorithm LININT defined by L ININT(0, x 1) = 0 and ŷt = LININT(((x1,y1), ...,(xt-1,yt-1)), xt) = f((x1,y1),...,(xt-1,yt-1)}(xt) for t > 1. That is, LININT linearly interpolates between previously seen points, and extrapolates using the value of the hidden function at the nearest previously seen element of the domain. Note that before each trial t, LININT can be thought of as formulating the hypothesis f{{ ε , θ , },...,( ε , , θ ,
Theorem 11
L 2 (LININT, F 2 ) ≤ 1.
Proof: Choose a target function f ∈ F 2 and a sequence x 1 , x 2 , ... of elements of [0,1]. Assume without loss of generality that the x t 's are distinct. By Lemma 10, we have that the action of the algorithm's hypothesis increases by at least ( ˆ θ t — f( x t )) 2 on each trial t > 1. Since the function hypothesized after trial 1 is constant, and therefore has action 0, and since, by Lemma 9, the action of LININT's hypothesis is always at most that of the target function, which in turn is at most 1, we may conclude that E t > 1 ( ˆ ˆ θ − f ( x i ))² ≤ 1. We may apply this result to obtain an alternative proof of a result of Faber and Mycielski [3], who analyzed another, more complicated, algorithm for their upper bounds.
Theorem 12 ([3])

Proof: The previous theorem implies that opt 2 (F2) ≤ 1. To see that opt 2 (F2) ≥ 1, consider an adversary which gives a first example of (0,0), and a second example of (1,±1), depending on whether an algorithm's prediction is positive or negative. This completes the proof. □ As discussed in the introduction, the fact that F ∞ ⊆ F 2 , together with the same adversary argument as above, trivially yields the following. Corollary 13 opt²( F ∞ ) = 1. This corollary tells us that, with respect to worst-case cumulative squared error, the assumption that the derivative of a hidden function is never more than 1 doesn't give the learner any more power than the assumption that the average value of the square of the derivative is at most one. 4
More general loss functions
4
Recall that in Section 3, we proved that opt 2 (F oo) = opt 2 (F 2 ) = 1, and in Section 2, we proved that opt 1 ( F ∞ ) = opt 1 ( F 2 ) = ∞. This brings up a natural question: For which p are opt 0 ( F ∞ ) and opt 0 ( F 2 ) finite? This question is resolved in this section: we show that optp(Foo) and optp(F2) are finite whenever p > 1. The following lemma will be useful in both analyses. Lemma 14 Choose a sequence x 1 , x 2 , … of elements of [0, 1]. For each t > 1, let
Proof: Choose a sequence x 1 , x 2 , ... of elements of [0, 1]. Assume without loss of generality that the x i 's are distinct. For each t ∈ N, let S t = {x i : i < t } = { u i , i : i < t } , where u1,1 < u2,1 < . . . u1,1 (the ui,1 's are {x1, . . , x1 } in sorted order). For each t, let st = ui,1 - ui,1 First, we claim that
Choose a trial t for which x t < u 1 t _ 1 . In such a case, we have
since d, < 1 and p > 1. Similarly, if x, > u,-1,t-1, then s, - s,-1 > d,. Since, trivially, s, never decreases, and 0 ≤ s t ≤ 1, we have (6). Next, we claim that
For each t, let
Choose a trial t for which xi E [ui,t-1, ui,-1,t-1]. Let i be such that xi E (ui,t-1,ui+1,t-1). Let a = Ui+1,i-1 - ui,i-1. Assume, as a first case, that x, is closest to ui,i-1 (the other case may be handled similarly). Then d t = x t − u i t − 1 ≤ a / 2. We have
By differentiating, we may easily see that this expression, as a function of a, is decreasing when a, d, > 0. Thus, it is maximized, subject to a ≥ 2 d t , when a = 2 d t . Plugging into (8) and simplifying, we get H t − H t − 1 ≤ (2 − 2 r )d f  < 0 . Since, trivially, 0 ≤ H i ≤ 1 for all t, and H i never increases (on any trial), we have (7). Combining (6) and (7) yields the desired bound. We begin with F ∞ . We will make use of the following simple lemma, whose proof is omitted. It establishes the fact that functions in F ∞ satisfy a Lipschitz condition. Lemma 15  If f ∈ F ∞ , then for all x, y ∈ [0, 1], we have
A bound on opt 1+ ( F ∞ ) follows immediately from the previous two lemmas. Recall that opt 2 ( F ∞ ) = 1, and therefore opt a (F ∞ ) = 1 for all p ≥ 2. For this reason, the theorem (also Theorem 17 below) is only interesting for c < 1.
Proof: Consider the algorithm A which simply predicts with the function value at the nearest previously seen point (and arbitrarily on the first trial). Choose a sequence x 1 , …, x m of elements of [0, 1] and f ∈ F ∞ Let 92, …, 9m be the predictions of this "nearest neighbor" algorithm on trials 2 through m, and let p = 1 + c. We have
completing the proof of the first inequality of the theorem. The second follows immediately using the fact ■ that for all x, 1 + x < e *. Next, we prove a very similar bound on opt 1+ t ( F2 ). Theorem 17 If c > 0,
Proof: Choose c > 0 and let p = 1 + c. Choose a sequence x 1 , . . , x m of elements of [0, 1] and f ∈ F ∞ . Let Ì2, ..., Ìm be the predictions of LININT on trials 2 through m, and for each t > 1, let d, = min,<! |z, = x, | and let e t = | f i — f ( x t ) |. Applying Lemma 10, we have that the action of LININT's hypothesis increases by at least c?/di on each trial. By Lemma 9, the action of LININT's hypothesis is always at most 1. Thus,
Since, by Lemma 14, we have
our analysis proceeds by breaking up the trials, and applying (9) to those trials where d, is relatively small, and (10) to the trials where di is relatively large. More specifically, we have
by (10). Also,
by (9). Combining with (11) yields the first inequality. The second follows immediately using the fact that l + x < e r for all x I
Bounded-length trial sequences
5
In Section 2, we showed that opt 1 (F ∞ ) = opt 1 (F 2 ) = ∞. In other words, we showed that finite bounds on the sum of absolute differences between predictions and true values could not be obtained for any algorithm using only the assumption that the hidden function was in F ∞ , and therefore, for any algorithm using only the weaker assumption that the hidden function was in F2. Our adversaries used many trials, forcing small errors on each trial. The fact that opt 2 < ∞ for both these classes suggests that this behavior was necessary, since, as the error on a trial approaches 1, squaring the error has no effect. If, in fact, any adversary which forces infinite cumulative error for algorithms learning F ∞ must force small errors on each trial, this is good news for the learner, since, even if one's total error is unbounded, if it is accumulating slowly, nontrivial learning is taking place. In this section, we show that, indeed, the "nearest neighbor" algorithm studied in the previous section accumulates error slowly while learning F cc . We show that on any sequence of m trials consistent with a function in F oo, the sum of unsquared errors made by the nearest neighbor algorithm is O(log m). We also show that the "linear interpolation" algorithm studied in Section 3 achieves the same bound on its cumulative (unsquared) error on any sequence of m trials consistent with a function in F 2 . For a class F of functions from [0, 1] to R, define
where A ranges over learning algorithms. Both proofs make use of the following inequality, which follows immediately by the standard convexity argument. Lemma 18 For any n ∈ N,p > 1,x ∈ R n
We begin with F ∞ Theorem 19  For all m ≥ 3,
Proof: Choose x 1 , ..., x m , and f ∈ F ∞ . We claim that if A is the nearest neighbor algorithm, then
Let ˆ γ 1 , …, ˆ γ m be the sequence of predictions made by A. Let ˆ r ∈ R m be defined by Choose ε > 0. By Theorem 16, we have
Applying Lemma 18, we have
Suppose ε = 1/(ln m − 1). Then
This completes the proof. □ With minor modifications, the above argument, together with Theorem 17, yields the following. Theorem 20  For m > 3,
We also have the following lower bound. Theorem 21  For m ∈ N, m ≥ 2,
Proof: Let k = [log2m]. To ease the notation, in this proof we will number trials from 0. Let xo = 1. Choose an algorithm A for learning F2. For i ∈ N, j ∈ Z, 0 ≤ j ≤ 2i−1 − 1, let
For example, x 1 = 1/2, x 2 = 1/4, x 3 = 3/4, x 4 = 1/8, x 5 = 3/8, x 6 = 5/8, .... fo,fi,...,f2e_1 and y1,..,y2e_1 i to be part of stage i. For each trial t in stage i < k , define y t to be
whichever is furthest from fi , and let fi be the function which linearly interpolates {(0,0), (1,0)} U {(x, y,) : s < t }  Let f = f 2 k − 1 First, for each trial f in stage i < k,
Hence,
All that remains is to show that f E F2. By (4) of Lemma 10, for all t in stage i < k, Therefore, since J[fo] = 0,
completing the proof. ■
6
Acknowledgements
We'd like to thank Ethan Bernstein, Tom Cover, David Haussler, Wolfgang Maass, Erik Ordentlich, Shang- Hua Teng and Manfred Warmuth for helpful conversations about this research, and Nicolò Cesa-Bianchi, Phil Chou, Yoav Freund, Les Niles, Madhukar Thakur and Lynn Wilcox for their comments on earlier drafts of this work. Don Kimber was supported by NSF Grant IRI-87-19595. Phil Long was supported by a UCSC Chancellor's dissertation-year fellowship, a Lise Meitner Postdoctoral Fellowship from the FWF of the Austrian Government, and by AFOSR grant F49620-92-J-0515.