Abstract We study the problem of learning an optimal subset from a larger ground set of items, where the optimality criterion is defifined by an unknown preference function. We model the problem as a discriminative structural learning problem and solve it using a Structural Support Vector Machine (SSVM) that optimizes a “set accuracy” performance measure representing set similarities. Our approach departs from previous approaches since we do not explicitly learn a pre-defifined preference function. Experimental results on both a synthetic problem domain and a real-world face image subset selection problem show that our method signifificantly outperforms previous learning approaches for such problems.