Project: CRII: III: Scaling up Distance Metric Learning for Large-scale Ultrahigh-dimensional Data (NSF IIS-1463988)

 

PI: Tianbao Yang, Department of Computer Science, University of Iowa

 

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.

 

Students

  1. Yi Xu, Zhe Li

Publications

  1. Yichi Xiao, Zhe Li, Tianbao Yang, Lijun Zhang. SVD-free Convex-Concave Approaches for Nuclear Norm Regularization. International Joint Conference on Artificial Intelligence (IJCAI), 2017. (PDF)
  2. Yi Xu, Qihang Lin, Tianbao Yang. Stochastic Convex Optimization: Faster Local Growth Implies Faster Global Convergence. International Conference on Machine Learning (ICML), 2017. (PDF)
  3. Lijun Zhang, Tianbao Yang, Rong Jin. Empirical Risk Minimization for Stochastic Convex Optimization: O(1/n)- and O(1/n^2)-type of Risk Bounds. International Conference on Learning Theory (COLT), 2017. (PDF)
  4. Tianbao Yang,Qihang Lin, Lijun Zhang. A Richer Theory of Convex Constrained Optimization with Reduced Projections and Improved Rates. International Conference on Machine Learning (ICML), 2017. (PDF)
  5. Mingrui Liu, Tianbao Yang. Adaptive Accelerated Gradient Converging Methods under Holderian Error Bound Condition. Neural Information Processing Systems (NIPS), 2017. (PDF)
  6. Yi Xu, Mingrui Liu, Qihang Lin, Tianbao Yang. ADMM without a Fixed Penalty Parameter: Faster Convergence with New Adaptive Penalization. Neural Information Processing Systems (NIPS), 2017. (PDF)
  7. Yi Xu, Qihang Lin, Tianbao Yang. Adaptive SVRG Methods under Error Bound Conditions with Unknown Growth Parameter. Neural Information Processing Systems (NIPS), 2017. (PDF)
  8. Yi Xu, Haiqing Yang, Lijun Zhang, Tianbao Yang. Efficient Non-oblivious Randomized Reduction for Risk Minimization with Improved Excess Risk Guarantee. Thirty-First AAAI Conference on Artificial Intelligence, 2016. (PDF)
  9. Tianbao Yang, Lijun Zhang, Rong Jin, Jinfeng Yi. Tracking Slowly Moving Clairvoyant: Optimal Dynamic Regret of Online Learning with True and Noisy Gradient. International Conference on Machine Learning (ICML), 2016. (PDF)
  10. Lijun Zhang, Tianbao Yang, Rong Jin, Zhi-Hua Zhou. Sparse Learning for Large-scale and High-dimensional Data: A Randomized Convex-concave Optimization Approach. Algorithmic Learning Theory, 2016. (PDF)
  11. Lijun Zhang, Tianbao Yang, Rong Jin, Zhi-Hua Zhou. Online Stochastic Linear Optimization under One-bit Feedback. International Conference on Machine Learning (ICML), 2016. (PDF)
  12. Jianhui Chen, Tianbao Yang, Qihang Lin, Lijun Zhang, Yi Chang. Optimal Stochastic Strongly Convex Optimization with a Logarithmic Number of Projections. Uncertainty in Artificial Intelligence Conference (UAI), 2016. (PDF)
  13. Chuang Gan, Tianbao Yang, Boqing Gong. Learning Attributes Equals Multi-Source Domain Generalization. Computer Vision and Pattern Recognition (CVPR), 2016. (PDF)
  14. Yi Xu, Yan Yan, Qihang Lin, Tianbao Yang. Homotopy Smoothing for Non-Smooth Problems with Lower Complexity than O(1/ε). Neural Information Processing Systems (NIPS), 2016. (PDF)
  15. Zhe Li, Boqing Gong, Tianbao Yang. Improved Dropout for Shallow and Deep Learning. Neural Information Processing Systems (NIPS), 2016. (PDF)
  16. Tianbao Yang, Rong Jin, Shenghuo Zhu, Qihang Lin. On Data Preconditioning for Regularized Loss Minimization. Machine Learning Journal, 2015(PDF)
  17. Lijun Zhang, Tianbao Yang, Rong Jin, Zhi-Hua Zhou, Stochastic Optimization for Kernel PCA, AAAI Conference on Artificial Intelligence, 2016 (PDF)
  18. Zhe Li, Tianbao Yang, Lijun Zhang, Rong Jin, Fast and Accurate Refined Nystrom based Kernel SVM, AAAI Conference on Artificial Intelligence, 2016 (PDF)
  19. Tianbao Yang, Lijun Zhang, Rong Jin and Shenghuo Zhu, An Explicit Sampling Dependent Spectral Error Bound for Column Subset Selection, International Conference of Machine Learning (ICML), 2015 (PDF)
  20. Tianbao Yang, Lijun Zhang, Rong Jin and Shenghuo Zhu, Theory of Dual-sparse Regularized Randomized Reduction, International Conference of Machine Learning (ICML), 2015 (PDF)
  21. Saining Xie, Tianbao Yang, Xiaoyu Wang and Yuanqing Lin, Hyper-class Augmented and Regularized Deep Learning for Fine-grained Image Classification, IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2015 (PDF)
  22. Jianhui Chen, Tianbao Yang and Shenghuo Zhu, Efficient Low-Rank Stochastic Gradient Descent Methods for Solving Semi-definite Programming, International Conference on Artificial Intelligence and Statistics (AISTATS), 2014 (PDF)

Software

    Dual Sparse Regularized Birds: This implemented a distributed program for learning from randomized reduced data (assume given and partitioned) with dual sparse regularization. It also includes the recovery code for recovering a full model from dual variables learned from low-dimensional data. [Code] [Documentation]
    ASSG: This implemented an accelerated stochastic subgradient method for solving large-scale machine learning problems. [Code] [Documentation]

Acknowlewdgement and Disclaimer

    This material is based upon work supported by the National Science Foundation under Grant No. IIS-1463988. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation.