CRII: III: Scaling up Distance Metric Learning for Large-scale Ultrahigh-dimensional Data

University Of Iowa, Iowa City IA

Investigators

Abstract

This project is to research and develop highly scalable stochastic optimization algorithms for distance metric learning (DML) for large-scale ultrahigh-dimensional (LSUD) data. DML is a fundamental problem in machine learning aiming to learn a distance metric such that intra-class variation is small and inter-class variation is large. When the scale and dimensionality of data is very large, the computational cost of DML is prohibitive. Domains utilizing machine learning techniques such as computer vision, natural language processing and bioinformatics will be directly impacted by this research. For example, one application is fine-grained image classification, e.g., categorizing different types of flowers or models of vehicles from pictures (this application will be used as one criteria to evaluate success of the research.) The research will enable data scientists to extract more knowledge from massive high-dimensional data complementing the White House BIG DATA Initiative to analyze large and complex data sets. Beyond its research impact, this project will facilitate the development of a new machine learning course at the University of Iowa (UI), and contribute to training future professionals in big data analytics. Broader impact will be further affected by dissemination of results through publications, open-sourced software, etc. This project addresses the computational challenges of LSUD-DML by scaling up the state of the art stochastic gradient descent (SGD) methods. A key computational bottleneck in applying SGD to DML is to project the updated solution into a complicated feasible domain at each iteration. The innovative proposed ideas lie at reducing the total cost of projections by (i) constructing and exploring a low-rank structured stochastic gradient to reduce the cost of projection, and (ii) dividing iterations into epochs and performing a projection-efficient SGD at each epoch to reduce the number of projections. Investigating data-dependent sampling strategies (i.e., selective sampling, importance sampling, and a combination of both) for LSUD-DML will further scale up the proposed methods. This research will provide experimental evidence regarding the scalability of the proposed algorithms while revealing insights into the proposed techniques and various analytical tradeoffs. For further information see the project web site at: http://homepage.cs.uiowa.edu/~tyng/dml.html.