Journal article
On Data Preconditioning for Regularized Loss Minimization
Machine learning, Vol.103(1), pp.57-79
04/01/2016
DOI: 10.1007/s10994-015-5536-6
Abstract
In this work, we study data preconditioning, a well-known and long-existing technique, for boosting the convergence of first-order methods for regularized loss minimization in machine learning. It is well understood that the condition number of the problem, i.e., the ratio of the Lipschitz constant to the strong convexity modulus, has a harsh effect on the convergence of the first-order optimization methods. Therefore, minimizing a small regularized loss for achieving good generalization performance, yielding an ill conditioned problem, becomes the bottleneck for big data problems. We provide a theory on data preconditioning for regularized loss minimization. In particular, our analysis exhibits an appropriate data preconditioner that is similar to zero component analysis whitening. Exploiting the concepts of numerical rank and coherence, we characterize the conditions on the loss function and on the data under which data preconditioning can reduce the condition number and therefore boost the convergence for minimizing the regularized loss. To make the data preconditioning practically useful, we propose an efficient preconditioning method through random sampling. The preliminary experiments on simulated data sets and real data sets validate our theory.
Details
- Title: Subtitle
- On Data Preconditioning for Regularized Loss Minimization
- Creators
- Tianbao Yang - University of IowaRong Jin - Michigan State UniversityShenghuo Zhu - Alibaba GroupQihang Lin - University of Iowa
- Resource Type
- Journal article
- Publication Details
- Machine learning, Vol.103(1), pp.57-79
- Publisher
- Springer Nature
- DOI
- 10.1007/s10994-015-5536-6
- ISSN
- 0885-6125
- eISSN
- 1573-0565
- Number of pages
- 23
- Grant note
- 1463988 / Div Of Information & Intelligent Systems; National Science Foundation (NSF); NSF - Directorate for Computer & Information Science & Engineering (CISE) IIS-1463988; IIS-1545995 / NSF; National Science Foundation (NSF)
- Language
- English
- Date published
- 04/01/2016
- Academic Unit
- Computer Science; Business Analytics
- Record Identifier
- 9984259478402771
Metrics
22 Record Views