Joumal of Machine Leaming Research 20(2019)1-41 Submitted 12/17:Revised 8/18:Published 2/19 Robust Frequent Directions with Application in Online Learning Luo Luo RICKY @SJTU.EDU.CN Cheng Chen JACK_CHEN1990@SJTU.EDU.CN Department of Computer Science and Engineering Shanghai Jiao Tong University 800 Dongchuan Road,Shanghai,China 200240 Zhihua Zhang* ZHZHANG@MATH.PKU.EDU.CN National Engineering Lab for Big Data Analysis and Applications School of Mathematical Sciences Peking University 5 Yiheyuan Road,Beijing,China 100871 Wu-Jun Li LIWUJUN@NJU.EDU.CN National Key Laboratory for Novel Software Technology Collaborative Innovation Center of Novel Software Technology and Industrialization Department of Computer Science and Technology Nanjing University 163 Xianlin Avenue,Nanjing,China 210023 Tong Zhang TONGZHANG @TONGZHANG-ML.ORG Computer Science Mathematics Hong Kong University of Science and Technology Hong Kong Editor:Qiang Liu Abstract The frequent directions(FD)technique is a deterministic approach for online sketching that has many applications in machine learning.The conventional FD is a heuristic procedure that often outputs rank deficient matrices.To overcome the rank deficiency problem,we propose a new sketching strategy called robust frequent directions(RFD)by introducing a regularization term.RFD can be derived from an optimization problem.It updates the sketch matrix and the regularization term adaptively and jointly.RFD reduces the approximation error of FD without increasing the computational cost.We also apply RFD to online learning and propose an effective hyperparameter- free online Newton algorithm.We derive a regret bound for our online Newton algorithm based on RFD,which guarantees the robustness of the algorithm.The experimental studies demonstrate that the proposed method outperforms state-of-the-art second order online learning algorithms. Keywords:Matrix approximation,sketching,frequent directions,online convex optimization, online Newton algorithm 1.Introduction The sketching technique is a powerful tool to deal with large scale matrices(Ghashami et al.,2016; Halko et al.,2011;Woodruff,2014),and it has been widely used to speed up machine learning *Corresponding author. C2019 Luo Luo,Cheng Chen,Zhihua Zhang,Wu-Jun Li and Tong Zhang. License:CC-BY 4.0.see https://creativecommons.org/licenses/by/4.0/.Attribution requirements are provided at http://jmlr.org/papers/v20/17-773.html.Journal of Machine Learning Research 20 (2019) 1-41 Submitted 12/17; Revised 8/18; Published 2/19 Robust Frequent Directions with Application in Online Learning Luo Luo RICKY@SJTU.EDU.CN Cheng Chen JACK CHEN1990@SJTU.EDU.CN Department of Computer Science and Engineering Shanghai Jiao Tong University 800 Dongchuan Road, Shanghai, China 200240 Zhihua Zhang∗ ZHZHANG@MATH.PKU.EDU.CN National Engineering Lab for Big Data Analysis and Applications School of Mathematical Sciences Peking University 5 Yiheyuan Road, Beijing, China 100871 Wu-Jun Li LIWUJUN@NJU.EDU.CN National Key Laboratory for Novel Software Technology Collaborative Innovation Center of Novel Software Technology and Industrialization Department of Computer Science and Technology Nanjing University 163 Xianlin Avenue, Nanjing, China 210023 Tong Zhang TONGZHANG@TONGZHANG-ML.ORG Computer Science & Mathematics Hong Kong University of Science and Technology Hong Kong Editor: Qiang Liu Abstract The frequent directions (FD) technique is a deterministic approach for online sketching that has many applications in machine learning. The conventional FD is a heuristic procedure that often outputs rank deficient matrices. To overcome the rank deficiency problem, we propose a new sketching strategy called robust frequent directions (RFD) by introducing a regularization term. RFD can be derived from an optimization problem. It updates the sketch matrix and the regularization term adaptively and jointly. RFD reduces the approximation error of FD without increasing the computational cost. We also apply RFD to online learning and propose an effective hyperparameter￾free online Newton algorithm. We derive a regret bound for our online Newton algorithm based on RFD, which guarantees the robustness of the algorithm. The experimental studies demonstrate that the proposed method outperforms state-of-the-art second order online learning algorithms. Keywords: Matrix approximation, sketching, frequent directions, online convex optimization, online Newton algorithm 1. Introduction The sketching technique is a powerful tool to deal with large scale matrices (Ghashami et al., 2016; Halko et al., 2011; Woodruff, 2014), and it has been widely used to speed up machine learning ∗. Corresponding author. c 2019 Luo Luo, Cheng Chen, Zhihua Zhang, Wu-Jun Li and Tong Zhang. License: CC-BY 4.0, see https://creativecommons.org/licenses/by/4.0/. Attribution requirements are provided at http://jmlr.org/papers/v20/17-773.html