| Paper ID | D6-S5-T3.2 |
| Paper Title |
FROS: Fast Regularized Optimization by Sketching |
| Authors |
Yingzhen Yang, Arizona State University, United States; Ping Li, Baidu Research, United States |
| Session |
D6-S5-T3: Dimension Reduction |
| Chaired Session: |
Monday, 19 July, 23:20 - 23:40 |
| Engagement Session: |
Monday, 19 July, 23:40 - 00:00 |
| Abstract |
Randomized algorithms are important for solving large-scale optimization problems. In this paper, we propose Fast Regularized Optimization by Sketching (FROS) as an efficient solver for a general class of regularized optimization problems. FROS first generates a sketch of the original data matrix, then solves the sketched problem. Different from existing randomized algorithms, FROS handles general Frechet subdifferentiable regularization functions in an unified framework. It is proved that FROS achieves relative-error bounds for the approximation error between the optimization results of the sketched problem and that of the original problem for all convex and certain non-convex regularization. We further propose Iterative FROS which reduces the approximation error exponentially by iteratively invoking FROS. To the best of our knowledge, our results are among the very few results in approximation error of sketching algorithms for a broad class of optimization problems with general regularization. Experimental results demonstrate the effectiveness of the proposed FROS and Iterative FROS algorithms.
|
