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. 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. Cover 1 Half Title 2 Title Page 4 Copyright Page 5 Dedication 6 Contents 8 List of Figures 14 List of Tables 16 Preface 18 SECTION I: BACKGROUND 20 CHAPTER 1: Introduction 22 1.1. LARGE-SCALE MACHINE LEARNING 23 1.2. OPTIMIZATION PROBLEMS 23 1.3. LINEAR CLASSIFICATION 24 1.3.1. Support Vector Machine (SVM) 24 1.3.2. Logistic Regression 26 1.3.3. First and Second Order Methods 26 1.3.3.1. First Order Methods 26 1.3.3.2. Second Order Methods 27 1.4. STOCHASTIC APPROXIMATION APPROACH 27 1.5. COORDINATE DESCENT APPROACH 27 1.6. DATASETS 27 1.7. ORGANIZATION OF BOOK 28 CHAPTER 2: Optimization Problem, Solvers, Challenges and Research Directions 30 2.1. INTRODUCTION 30 2.1.1. Contributions 32 2.2. LITERATURE 32 2.3. PROBLEM FORMULATIONS 34 2.3.1. Hard Margin SVM (1992) 34 2.3.2. Soft Margin SVM (1995) 35 2.3.3. One-versus-Rest (1998) 36 2.3.4. One-versus-One (1999) 37 2.3.5. Least Squares SVM (1999) 38 2.3.6. v-SVM (2000) 38 2.3.7. Smooth SVM (2001) 39 2.3.8. Proximal SVM (2001) 40 2.3.9. Crammer Singer SVM (2002) 41 2.3.10. Ev-SVM (2003) 42 2.3.11. Twin SVM (2007) 42 2.3.12. Capped lp-norm SVM (2017) 43 2.4. PROBLEM SOLVERS 48 2.4.1. Exact Line Search Method 50 2.4.2. Backtracking Line Search 50 2.4.3. Constant Step Size 51 2.4.4. Lipschitz and Strong Convexity Constants 51 2.4.5. Trust Region Method 51 2.4.6. Gradient Descent Method 51 2.4.7. Newton Method 52 2.4.8. Gauss-Newton Method 53 2.4.9. Levenberg-Marquardt Method 53 2.4.10. Quasi-Newton Method 54 2.4.11. Subgradient Method 54 2.4.12. Conjugate Gradient Method 55 2.4.13. Truncated Newton Method 55 2.4.14. Proximal Gradient Method 56 2.4.15. Recent Algorithms 56 2.5. COMPARATIVE STUDY 57 2.5.1. Results from Literature 57 2.5.2. Results from Experimental Study 58 2.5.2.1. Experimental Setup and Implementation Details 58 2.5.2.2. Results and Discussions 58 2.6. CURRENT CHALLENGES AND RESEARCH DIRECTIONS 60 2.6.1. Big Data Challenge 60 2.6.2. Areas of Improvement 60 2.6.2.1. Problem Formulations 60 2.6.2.2. Problem Solvers 61 2.6.2.3. Problem Solving Strategies/Approaches 62 2.6.2.4. Platforms/Frameworks 63 2.6.3. Research Directions 64 2.6.3.1. Stochastic Approximation Algorithms 64 2.6.3.2. Coordinate Descent Algorithms 64 2.6.3.3. Proximal Algorithms 64 2.6.3.4. Parallel/Distributed Algorithms 65 2.6.3.5. Hybrid Algorithms 65 2.7. CONCLUSION 65 SECTION II: FIRST ORDER METHODS 68 CHAPTER 3: Mini-batch and Block-coordinate Approach 70 3.1. INTRODUCTION 70 3.1.1. Motivation 71 3.1.2. Batch Block Optimization Framework (BBOF) 73 3.1.3. Brief Literature Review 75 3.1.4. Contributions 76 3.2. STOCHASTIC AVERAGE ADJUSTED GRADIENT (SAAG) METHODS 76 3.3. ANALYSIS 79 3.4. NUMERICAL EXPERIMENTS 82 3.4.1. Experimental Setup 82 3.4.2. Convergence against Epochs 83 3.4.3. Convergence against Time 84 3.5. CONCLUSION AND FUTURE SCOPE 84 CHAPTER 4: Variance Reduction Methods 86 4.1. INTRODUCTION 86 4.1.1. Optimization Problem 87 4.1.2. Solution Techniques for Optimization Problem 87 4.1.3. Contributions 88 4.2. NOTATIONS AND RELATED WORK 89 4.2.1. Notations 89 4.2.2. Related Work 89 4.3. SAAG-I, II AND PROXIMAL EXTENSIONS 90 4.4. SAAG-III AND IV ALGORITHMS 91 4.5. ANALYSIS 92 4.6. EXPERIMENTAL RESULTS 114 4.6.1. Experimental Setup 114 4.6.2. Results with Smooth Problem 114 4.6.3. Results with Non-smooth Problem 115 4.6.4. Mini-batch Block-coordinate versus Mini-batch setting 117 4.6.5. Results with SVM 117 4.7. CONCLUSION 118 CHAPTER 5: Learning and Data Access 120 5.1. INTRODUCTION 120 5.1.1. Optimization Problem 121 5.1.2. Literature Review 122 5.1.3. Contributions 123 5.2. SYSTEMATIC SAMPLING 123 5.2.1. Definitions 124 5.2.2. Learning Using Systematic Sampling 125 5.3. ANALYSIS 126 5.4. EXPERIMENTS 128 5.4.1. Experimental Setup 128 5.4.2. Implementation Details 129 5.4.3. Results 129 5.5. CONCLUSION 132 SECTION III: SECOND ORDER METHODS 134 CHAPTER 6: Mini-batch Block-coordinate Newton Method 136 6.1. INTRODUCTION 136 6.1.1. Contributions 137 6.2. MBN 137 6.3. EXPERIMENTS 138 6.3.1. Experimental Setup 139 6.3.2. Comparative Study 139 6.4. CONCLUSION 140 CHAPTER 7: Stochastic Trust Region Inexact Newton Method 142 7.1. INTRODUCTION 142 7.1.1. Optimization Problem 143 7.1.2. Solution Techniques 144 7.1.3. Contributions 144 7.2. LITERATURE REVIEW 145 7.3. TRUST REGION INEXACT NEWTON METHOD 147 7.3.1. Inexact Newton Method 147 7.3.2. Trust Region Inexact Newton Method 147 7.4. STRON 148 7.4.1. Complexity 150 7.4.2. Analysis 150 7.5. EXPERIMENTAL RESULTS 151 7.5.1. Experimental Setup 151 7.5.2. Comparative Study 152 7.5.3. Results with SVM 152 7.6. EXTENSIONS 152 7.6.1. PCG Subproblem Solver 153 7.6.2. Stochastic Variance Reduced Trust Region Inexact Newton Method 154 7.7. CONCLUSION 156 SECTION IV: CONCLUSION 158 CHAPTER 8: Conclusion and Future Scope 160 8.1. FUTURE SCOPE 161 Bibliography 164 Index 176 machine,learning;,stochasitc,optimization;,Big,Data;,algorithms machine learning,stochasitc optimization,Big Data,algorithms "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. The book will be a valuable reference to practitioners and researchers as well as students in the field of machine learning"-- Provided by publisher