Published In Improved Guarantees for Learning via Similarity Functions

We continue the investigation of natural conditions for a similarity function to allow learning, without requiring the similarity function to be a valid ker-nel, or referring to an implicit high-dimensional space. We provide a new notion of a “good sim-ilarity function ” that builds upon the previous def-inition of Balcan and Blum (2006) but improves on it in two important ways. First, as with the pre-vious definition, any large-margin kernel is also a good similarity function in our sense, but the trans-lation now results in a much milder increase in the labeled sample complexity. Second, we prove that for distribution-specific PAC learning, our new no-tion is strictly more powerful than the traditional notion of a large-margin kernel. In particular, we show that for any hypothesis class C there exists a similarity function under our definition allowing learning with O(log |C|) labeled examples. How-ever, in a lower bound which may be of indepen-dent interest, we show that for any class C of pair-wise uncorrelated functions, there is no kernel with margin γ ≥ 8/ |C | for all f ∈ C, even if one allows average hinge-loss as large as 0.5. Thus, the sample complexity for learning such classe