Active Learning Using Smooth Relative Regret Approximations with
  Applications
  The disagreement coefficient of Hanneke has become a central data independent
invariant in proving active learning rates. It has been shown in various ways
that a concept class with low complexity together with a bound on the
disagreement coefficient at an optimal solution allows active learning rates
that are superior to passive learning ones.
  We present a different tool for pool based active learning which follows from
the existence of a certain uniform version of low disagreement coefficient, but
is not equivalent to it. In fact, we present two fundamental active learning
problems of significant interest for which our approach allows nontrivial
active learning bounds. However, any general purpose method relying on the
disagreement coefficient bounds only fails to guarantee any useful bounds for
these problems.
  The tool we use is based on the learner's ability to compute an estimator of
the difference between the loss of any hypotheses and some fixed "pivotal"
hypothesis to within an absolute error of at most $\eps$ times the
