Recent years have seen advances in optimizing large scale statistical estimation problems. In statistical learning settings iterative optimization algorithms have been shown to enjoy geometric convergence. While powerful, such results only hold for the original dataset, and may face computational challenges when the sample size is large. In this paper, we study sketched iterative algorithms, in particular sketched-PGD (projected gradient descent) and sketched-SVRG (stochastic variance reduced gradient) for structured generalized linear model, and illustrate that these methods continue to have geometric convergence to the statistical error under suitable assumptions. Moreover, the sketching dimension is allowed to be even smaller than the ambient dimension, thus can lead to significant speed-ups. The sketched iterative algorithms introduced provide an additional dimension to study the trade-offs between statistical accuracy and time.
|Original language||English (US)|
|Title of host publication||Proceedings of the 28th International Joint Conference on Artificial Intelligence, IJCAI 2019|
|Publisher||International Joint Conferences on Artificial Intelligence|
|Number of pages||7|
|State||Published - 2019|
|Event||28th International Joint Conference on Artificial Intelligence, IJCAI 2019 - Macao, China|
Duration: Aug 10 2019 → Aug 16 2019
|Name||IJCAI International Joint Conference on Artificial Intelligence|
|Conference||28th International Joint Conference on Artificial Intelligence, IJCAI 2019|
|Period||8/10/19 → 8/16/19|
Bibliographical noteFunding Information:
The research was also supported by NSF grants IIS-1563950, IIS-1447566, IIS-1447574, IIS-1422557, CCF-1451986, CNS-1314560, IIS-0953274, IIS-1029711, NASA grant NNX12AQ39A, and gifts from Adobe, IBM, and Yahoo.
© 2019 International Joint Conferences on Artificial Intelligence. All rights reserved.