Optimization for Learning and Control Comprehensive resource providing a masters’ level introduction to optimization theory and algorithms for learning and control Optimization for Learning and Control describes how optimization is used in these domains, giving a thorough introduction to both unsupervised learning, supervised learning, and reinforcement learning, with an emphasis on optimization methods for large-scale learning and control problems. Several applications areas are also discussed, including signal processing, system identification, optimal control, and machine learning. Today, most of the material on the optimization aspects of deep learning that is accessible for students at a Masters’ level is focused on surface-level computer programming; deeper knowledge about the optimization methods and the trade-offs that are behind these methods is not provided. The objective of this book is to make this scattered knowledge, currently mainly available in publications in academic journals, accessible for Masters’ students in a coherent way. The focus is on basic algorithmic principles and trade-offs. Optimization for Learning and Control covers sample topics such as: Optimization theory and optimization methods, covering classes of optimization problems like least squares problems, quadratic problems, conic optimization problems and rank optimization. First-order methods, second-order methods, variable metric methods, and methods for nonlinear least squares problems. Stochastic optimization methods, augmented Lagrangian methods, interior-point methods, and conic optimization methods. Dynamic programming for solving optimal control problems and its generalization to reinforcement learning. How optimization theory is used to develop theory and tools of statistics and learning, e.g., the maximum likelihood method, expectation maximization, k-means clustering, and support vector machines. How calculus of variations is used in optimal control and for deriving the family of exponential distributions. Optimization for Learning and Control is an ideal resource on the subject for scientists and engineers learning about which optimization methods are useful for learning and control problems; the text will also appeal to industry professionals using machine learning for different practical applications.

Table of Contents:
Preface xvii Acknowledgments xix Glossary xxi Acronyms xxv About the Companion Website xxvii Part I Introductory Part 1 1 Introduction 3 1.1 Optimization 3 1.2 Unsupervised Learning 3 1.3 Supervised Learning 4 1.4 System Identification 4 1.5 Control 5 1.6 Reinforcement Learning 5 1.7 Outline 5 2 Linear Algebra 7 2.1 Vectors and Matrices 7 2.2 Linear Maps and Subspaces 10 2.3 Norms 13 2.4 Algorithm Complexity 15 2.5 Matrices with Structure 16 2.6 Quadratic Forms and Definiteness 21 2.7 Spectral Decomposition 22 2.8 Singular Value Decomposition 23 2.9 Moore-Penrose Pseudoinverse 24 2.10 Systems of Linear Equations 25 2.11 Factorization Methods 26 2.12 Saddle-Point Systems 32 2.13 Vector and Matrix Calculus 33 3 Probability Theory 40 3.1 Probability Spaces 40 3.2 Conditional Probability 42 3.3 Independence 44 3.4 Random Variables 44 3.5 Conditional Distributions 47 3.6 Expectations 48 3.7 Conditional Expectations 50 3.8 Convergence of Random Variables 51 3.9 Random Processes 51 3.10 Markov Processes 53 3.11 Hidden Markov Models 53 3.12 Gaussian Processes 56 Part II Optimization 61 4 Optimization Theory 63 4.1 Basic Concepts and Terminology 63 4.2 Convex Sets 66 4.3 Convex Functions 72 4.4 Subdifferentiability 80 4.5 Convex Optimization Problems 84 4.6 Duality 86 4.7 Optimality Conditions 90 5 Optimization Problems 94 5.1 Least-Squares Problems 94 5.2 Quadratic Programs 96 5.3 Conic Optimization 97 5.4 Rank Optimization 103 5.5 Partially Separability 106 5.6 Multiparametric Optimization 109 5.7 Stochastic Optimization 111 6 Optimization Methods 118 6.1 Basic Principles 118 6.2 Gradient Descent 124 6.3 Newton’s Method 128 6.4 Variable Metric Methods 134 6.5 Proximal Gradient Method 137 6.6 Sequential Convex Optimization 141 6.7 Methods for Nonlinear Least-Squares 142 6.8 Stochastic Optimization Methods 144 6.9 Coordinate Descent Methods 153 6.10 Interior-Point Methods 155 6.11 Augmented Lagrangian Methods 161 Part III Optimal Control 173 7 Calculus of Variations 175 7.1 Extremum of Functionals 175 7.2 The Pontryagin Maximum Principle 179 7.3 The Euler-Lagrange Equations 183 7.4 Extensions 185 7.5 Numerical Solutions 188 8 Dynamic Programming 206 8.1 Finite Horizon Optimal Control 206 8.2 Parametric Approximations 211 8.3 Infinite Horizon Optimal Control 213 8.4 Value Iterations 215 8.5 Policy Iterations 216 8.6 Linear Programming Formulation 220 8.7 Model Predictive Control 221 8.8 Explicit MPC 225 8.9 Markov Decision Processes 226 8.10 Appendix 233 Part IV Learning 243 9 Unsupervised Learning 245 9.1 Chebyshev Bounds 245 9.2 Entropy 246 9.3 Prediction 254 9.4 The Viterbi Algorithm 259 9.5 Kalman Filter on Innovation Form 261 9.6 Viterbi Decoder 264 9.7 Graphical Models 266 9.8 Maximum Likelihood Estimation 269 9.9 Relative Entropy and Cross Entropy 271 9.10 The Expectation Maximization Algorithm 273 9.11 Mixture Models 274 9.12 Gibbs Sampling 277 9.13 Boltzmann Machine 278 9.14 Principal Component Analysis 280 9.15 Mutual Information 283 9.16 Cluster Analysis 288 10 Supervised Learning 297 10.1 Linear Regression 297 10.2 Regression in Hilbert Spaces 300 10.3 Gaussian Processes 302 10.4 Classification 304 10.5 Support Vector Machines 306 10.6 Restricted Boltzmann Machine 310 10.7 Artificial Neural Networks 312 10.8 Implicit Regularization 316 11 Reinforcement Learning 327 11.1 Finite Horizon Value Iteration 327 11.2 Infinite Horizon Value Iteration 330 11.3 Policy Iteration 332 11.4 Linear Programming Formulation 337 11.5 Approximation in Policy Space 338 11.6 Appendix - Root-Finding Algorithms 342 12 System Identification 350 12.1 Dynamical System Models 350 12.2 Regression Problem 351 12.3 Input-Output Models 352 12.4 Missing Data 355 12.5 Nuclear Norm system Identification 357 12.6 Gaussian Processes for Identification 358 12.7 Recurrent Neural Networks 360 12.8 Temporal Convolutional Networks 360 12.9 Experiment Design 361 Appendix A 373 A.1 Notation and Basic Definitions 373 A.2 Software 374 References 379 Index 387