Paper: Self-Improved Gaps Almost Everywhere for the Agnostic Approximation of Monomials

Self-Improved Gaps Almost Everywhere for the Agnostic Approximation of Monomials

Richard Nock and Frank Nielsen

Abstract:
Given a learning sample, we focus on the hardness of finding monomials having low error, inside the interval bounded below by the smallest error achieved by a monomial (the best rule), and bounded above by the error of the default class (the poorest rule). It is well known that when its lower bound is zero, it is an easy task to find, in linear time, a monomial with zero error. What we prove is that when this bound is not zero, regardless of the location of the default class in (0,1/2), it becomes a huge complexity burden to beat significantly the default class. In fact, under some complexity-theoretic assumptions, it may already be hard to beat the trivial approximation ratios, even when relaxing the time complexity constraint to be quasi-polynomial or sub-exponential. Our results also hold with uniform weights over the examples.

in press. Publisher home page

BibTex entry:

@InProceedings{Agnostic-2007, 
author = {Richard Nock and Frank Nielsen}, 
title = {Self-Improved Gaps Almost Everywhere for the Agnostic Approximation of Monomials}, 
booktitle = {Theoretical Computer Science (Elsevier)}, 
year = 2007,
note = {accepted}
}

Last updated, February 2007.