### Abstract

We consider the problem of learning of an arbitrary function selected from the non-smooth class of functions that are of bounded variation. Bounds on the prediction errors resulting from sequential type algorithms are achieved for various scenarios. It is shown that for any algorithm there exists a sequence of samples and a function that results in a unit error at each step. If the samples are i.i.d. uniform then there exists an algorithm such that for any function of bounded variation the expected error is less than O(log n/n). Furthermore, for any algorithm there exists a function such that the expected error is greater than O(1/n). We then introduce a mixed sampling setting in which an adversary can choose points but the actual samples are drawn uniformly from a δ neighborhood of his selection. We show that there exists an algorithm such that for any function of bounded variation and for any sequence of adversary-chosen points the expected cumulative error is less than O(√n log n). Finally, results are derived for the uniform sampling case with noisy observations. We show that the order of growth of the expected error with noise sequences in l_{1} remains unaltered. However, for i.i.d. zero mean and finite variance noise there exists an algorithm with expected error less than O(1/n^{1/3}), and for i.i.d. Gaussian noise any algorithm has expected error of at least O(1/√n).

Original language | English (US) |
---|---|

Title of host publication | Proc 6 Annu ACM Conf Comput Learn Theory |

Publisher | Publ by ACM |

Pages | 439-445 |

Number of pages | 7 |

ISBN (Print) | 0897916115, 9780897916110 |

DOIs | |

State | Published - Jan 1 1993 |

Event | Proceedings of the 6th Annual ACM Conference on Computational Learning Theory - Santa Cruz, CA, USA Duration: Jul 26 1993 → Jul 28 1993 |

### Publication series

Name | Proc 6 Annu ACM Conf Comput Learn Theory |
---|

### Other

Other | Proceedings of the 6th Annual ACM Conference on Computational Learning Theory |
---|---|

City | Santa Cruz, CA, USA |

Period | 7/26/93 → 7/28/93 |

### All Science Journal Classification (ASJC) codes

- Engineering(all)

## Fingerprint Dive into the research topics of 'On-line learning of functions of bounded variation under various sampling schemes'. Together they form a unique fingerprint.

## Cite this

*Proc 6 Annu ACM Conf Comput Learn Theory*(pp. 439-445). (Proc 6 Annu ACM Conf Comput Learn Theory). Publ by ACM. https://doi.org/10.1145/168304.168392