  One of the central problems studied in the theory of machine learning is the
question of whether, for a given class of hypotheses, it is possible to
efficiently find a {consistent} hypothesis, i.e., which has zero training
error. While problems involving {\em convex} hypotheses have been extensively
studied, the question of whether efficient learning is possible for non-convex
hypotheses composed of possibly several disconnected regions is still less
understood. Although it has been shown quite a while ago that efficient
learning of weakly convex hypotheses, a parameterized relaxation of convex
hypotheses, is possible for the special case of Boolean functions, the question
of whether this idea can be developed into a generic paradigm has not been
studied yet. In this paper, we provide a positive answer and show that the
consistent hypothesis finding problem can indeed be solved in polynomial time
for a broad class of weakly convex hypotheses over metric spaces. To this end,
we propose a general domain-independent algorithm for finding consistent weakly
convex hypotheses and prove sufficient conditions for its efficiency that
characterize the corresponding hypothesis classes. To illustrate our general
algorithm and its properties, we discuss several non-trivial learning examples
to demonstrate how it can be used to efficiently solve the corresponding
consistent hypothesis finding problem. Without the weak convexity constraint,
these problems are known to be computationally intractable. We then proceed to
show that the general idea of our algorithm can even be extended to the case of
extensional weakly convex hypotheses, as it naturally arise, e.g., when
performing vertex classification in graphs. We prove that using our extended
algorithm, the problem can be solved in polynomial time provided the distances
in the domain can be computed efficiently.
