All Dates/Times are Australian Eastern Standard Time (AEST)

Technical Program

Paper Detail

Paper IDD6-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.