We develop an efficient optimization procedure for learning linear
transformations of data to produce structured outputs, e.g., nearest-neighbor
rankings or connectivity graphs induced by distance. The proposed method
solves a semi-definite programming problem by reducing to a sequence of small
quadratic programs, resulting in significant reductions in training
complexity. Experiments demonstrate that the proposed method is robust,
efficient, and outperforms alternative methods in high-noise settings.
Pre-2018 CSE ID: CS2012-0979
