Stochastic Optimization for Large-scale Machine Learning

Advancements in the technology and availability of data sources have led to the `Big Data' era. Working with large data offers the potential to uncover more fine-grained patterns and take timely and accurate decisions, but it also creates a lot of challenges such as slow training and scalability of machine learning models. One of the major challenges in machine learning is to develop efficient and scalable learning algorithms, i.e., optimization techniques to solve large scale learning problems. Stochastic Optimization for Large-scale Machine Learning identifies different areas of improvement and recent research directions to tackle the challenge. Developed optimisation techniques are also explored to improve machine learning algorithms based on data access and on first and second order optimisation methods. Key Features: Bridges machine learning and Optimisation. Bridges theory and practice in machine learning. Identifies key research areas and recent research directions to solve large-scale machine learning problems. Develops optimisation techniques to improve machine learning algorithms for big data problems. The book will be a valuable reference to practitioners and researchers as well as students in the field of machine learning.

List of FiguresList of TablesPreface Section I BACKGROUND Introduction1.1 LARGE-SCALE MACHINE LEARNING1.2 OPTIMIZATION PROBLEMS1.3 LINEAR CLASSIFICATION1.3.1 Support Vector Machine (SVM)1.3.2 Logistic Regression1.3.3 First and Second Order Methods1.3.3.1 First Order Methods1.3.3.2 Second Order Methods1.4 STOCHASTIC APPROXIMATION APPROACH1.5 COORDINATE DESCENT APPROACH1.6 DATASETS1.7 ORGANIZATION OF BOOK Optimisation Problem, Solvers, Challenges and Research Directions2.1 INTRODUCTION2.1.1 Contributions2.2 LITERATURE2.3 PROBLEM FORMULATIONS2.3.1 Hard Margin SVM (1992)2.3.2 Soft Margin SVM (1995)2.3.3 One-versus-Rest (1998)2.3.4 One-versus-One (1999)2.3.5 Least Squares SVM (1999)2.3.6 v-SVM (2000)2.3.7 Smooth SVM (2001)2.3.8 Proximal SVM (2001)2.3.9 Crammer Singer SVM (2002)2.3.10 Ev-SVM (2003)2.3.11 Twin SVM (2007)2.3.12 Capped lp-norm SVM (2017)2.4 PROBLEM SOLVERS2.4.1 Exact Line Search Method2.4.2 Backtracking Line Search2.4.3 Constant Step Size2.4.4 Lipschitz & Strong Convexity Constants2.4.5 Trust Region Method2.4.6 Gradient Descent Method2.4.7 Newton Method2.4.8 Gauss-Newton Method2.4.9 Levenberg-Marquardt Method2.4.10 Quasi-Newton Method2.4.11 Subgradient Method2.4.12 Conjugate Gradient Method2.4.13 Truncated Newton Method2.4.14 Proximal Gradient Method2.4.15 Recent Algorithms2.5 COMPARATIVE STUDY2.5.1 Results from Literature2.5.2 Results from Experimental Study2.5.2.1 Experimental Setup and Implementation Details2.5.2.2 Results and Discussions2.6 CURRENT CHALLENGES AND RESEARCH DIRECTIONS2.6.1 Big Data Challenge2.6.2 Areas of Improvement2.6.2.1 Problem Formulations2.6.2.2 Problem Solvers2.6.2.3 Problem Solving Strategies/Approaches2.6.2.4 Platforms/Frameworks2.6.3 Research Directions2.6.3.1 Stochastic Approximation Algorithms2.6.3.2 Coordinate Descent Algorithms2.6.3.3 Proximal Algorithms2.6.3.4 Parallel/Distributed Algorithms2.6.3.5 Hybrid Algorithms2.7 CONCLUSION Section II FIRST ORDER METHODSMini-batch and Block-coordinate Approach3.1 INTRODUCTION3.1.1 Motivation3.1.2 Batch Block Optimization Framework (BBOF)3.1.3 Brief Literature Review3.1.4 Contributions3.2 STOCHASTIC AVERAGE ADJUSTED GRADIENT (SAAG) METHODS3.3 ANALYSIS3.4 NUMERICAL EXPERIMENTS3.4.1 Experimental setup3.4.2 Convergence against epochs3.4.3 Convergence against Time3.5 CONCLUSION AND FUTURE SCOPE Variance Reduction Methods4.1 INTRODUCTION4.1.1 Optimization Problem4.1.2 Solution Techniques for Optimization Problem4.1.3 Contributions4.2 NOTATIONS AND RELATED WORK4.2.1 Notations4.2.2 Related Work4.3 SAAG-I, II AND PROXIMAL EXTENSIONS4.4 SAAG-III AND IV ALGORITHMS4.5 ANALYSIS4.6 EXPERIMENTAL RESULTS4.6.1 Experimental Setup4.6.2 Results with Smooth Problem4.6.3 Results with non-smooth Problem4.6.4 Mini-batch Block-coordinate versus mini-batch setting4.6.5 Results with SVM4.7 CONCLUSION Learning and Data Access5.1 INTRODUCTION5.1.1 Optimization Problem5.1.2 Literature Review5.1.3 Contributions5.2 SYSTEMATIC SAMPLING5.2.1 Definitions5.2.2 Learning using Systematic Sampling5.3 ANALYSIS5.4 EXPERIMENTS5.4.1 Experimental Setup5.4.2 Implementation Details5.4.3 Results5.5 CONCLUSION Section III SECOND ORDER METHODS Mini-batch Block-coordinate Newton Method6.1 INTRODUCTION6.1.1 Contributions6.2 MBN6.3 EXPERIMENTS6.3.1 Experimental Setup6.3.2 Comparative Study6.4 CONCLUSION Stochastic Trust Region Inexact Newton Method7.1 INTRODUCTION7.1.1 Optimization Problem7.1.2 Solution Techniques7.1.3 Contributions7.2 LITERATURE REVIEW7.3 TRUST REGION INEXACT NEWTON METHOD7.3.1 Inexact Newton Method7.3.2 Trust Region Inexact Newton Method7.4 STRON7.4.1 Complexity7.4.2 Analysis7.5 EXPERIMENTAL RESULTS7.5.1 Experimental Setup7.5.2 Comparative Study7.5.3 Results with SVM7.6 EXTENSIONS7.6.1 PCG Subproblem Solver 17.6.2 Stochastic Variance Reduced Trust Region Inexact Newton Method7.7 CONCLUSION Section IV CONCLUSIONConclusion and Future Scope8.1 FUTURE SCOPE 142 Bibliography Index

Dr. Vinod Kumar Chauhanis a Research Associate in Industrial Machine Learning in the Institute for Manufacturing, Department of Engineering at University of Cambridge UK. He has a PhD in Machine Learning from Panjab University Chandigarh India. His research interests are in Machine Learning, Optimization and Network Science. He specializes in solving large-scale optimization problems in Machine Learning, handwriting recognition, flight delay propagation in airlines, robustness and nestedness in complex networks and supply chain design using mathematical programming, genetic algorithms and reinforcement learning.