The Mathematics of Data (IAS/Park City Mathematics) (IAS/PARK CITY Mathematics, 25)

"Data science is a highly interdisciplinary field, incorporating ideas from applied mathematics, statistics, probability, and computer science, as well as many other areas. This book gives an introduction to the mathematical methods that form the foundations of machine learning and data science, presented by leading experts in computer science, statistics, and applied mathematics. Although the chapters can be read independently, they are designed to be read together as they lay out algorithmic, statistical, and numerical approaches in diverse but complementary ways. This book can be used both as a text for advanced undergraduate and beginning graduate courses, and as a survey for researchers interested in understanding how applied mathematics broadly defined is being used in data science. It will appeal to anyone interested in the interdisciplinary foundations of machine learning and data science."--Site web de l'éditeur Cover Title page Preface Introduction Lectures on Randomized Numerical Linear Algebra Introduction Linear Algebra Basics. Norms. Vector norms. Induced matrix norms. The Frobenius norm. The Singular Value Decomposition. SVD and Fundamental Matrix Spaces. Matrix Schatten norms. The Moore-Penrose pseudoinverse. References. Discrete Probability Random experiments: basics. Properties of events. The union bound. Disjoint events and independent events. Conditional probability. Random variables. Probability mass function and cumulative distribution function. Independent random variables. Expectation of a random variable. Variance of a random variable. Markov’s inequality. The Coupon Collector Problem. References. Randomized Matrix Multiplication Analysis of the R\scriptsize ANDM\scriptsize ATRIXM\scriptsize ULTIPLY algorithm. Analysis of the algorithm for nearly optimal probabilities. Bounding the two norm. References. RandNLA Approaches for Regression Problems The Randomized Hadamard Transform. The main algorithm and main theorem. RandNLA algorithms as preconditioners. The proof of Theorem 5.2.2. The running time of the R\scriptsize ANDL\scriptsize EASTS\scriptsize QUARES algorithm. References. A RandNLA Algorithm for Low-rank Matrix Approximation The main algorithm and main theorem. An alternative expression for the error. A structural inequality. Completing the proof of Theorem 6.1.1. Running time. References. \replace{Optimization Algorithms for Data Analysis} Introduction Omissions Notation Optimization Formulations of Data Analysis Problems Setup Least Squares Matrix Completion Nonnegative Matrix Factorization Sparse Inverse Covariance Estimation Sparse Principal Components Sparse Plus Low-Rank Matrix Decomposition Subspace Identification Support Vector Machines Logistic Regression Deep Learning Preliminaries Solutions Convexity and Subgradients Taylor’s Theorem Optimality Conditions for Smooth Functions Proximal Operators and the Moreau Envelope Convergence Rates Gradient Methods Steepest Descent General Case Convex Case Strongly Convex Case General Case: Line-Search Methods Conditional Gradient Method Prox-Gradient Methods Accelerating Gradient Methods Heavy-Ball Method Conjugate Gradient Nesterov’s Accelerated Gradient: Weakly Convex Case Nesterov’s Accelerated Gradient: Strongly Convex Case Lower Bounds on Rates Newton Methods Basic Newton’s Method Newton’s Method for Convex Functions Newton Methods for Nonconvex Functions A Cubic Regularization Approach Conclusions Introductory Lectures on Stochastic Optimization Introduction Scope, limitations, and other references Notation Basic Convex Analysis Introduction and Definitions Properties of Convex Sets Continuity and Local Differentiability of Convex Functions Subgradients and Optimality Conditions Calculus rules with subgradients Subgradient Methods Introduction The gradient and subgradient methods Projected subgradient methods Stochastic subgradient methods The Choice of Metric in Subgradient Methods Introduction Mirror Descent Methods Adaptive stepsizes and metrics Optimality Guarantees Introduction Le Cam’s Method Multiple dimensions and Assouad’s Method Technical Appendices Continuity of Convex Functions Probability background Auxiliary results on divergences Questions and Exercises Randomized Methods for Matrix Computations Introduction Scope and objectives The key ideas of randomized low-rank approximation Advantages of randomized methods Relation to other chapters and the broader literature Notation Notation The singular value decomposition (SVD) Orthonormalization The Moore-Penrose pseudoinverse A two-stage approach A randomized algorithm for “Stage A” —the range finding problem Single pass algorithms Hermitian matrices General matrices A method with complexity O(mn log k) for general dense matrices Theoretical performance bounds Bounds on the expectation of the error Bounds on the likelihood of large deviations An accuracy enhanced randomized scheme The key idea —power iteration Theoretical results Extended sampling matrix The Nyström method for positive symmetric definite matrices Randomized algorithms for computing Interpolatory Decompositions Structure preserving factorizations Three flavors of ID: row, column, and double-sided ID Deterministic techniques for computing the ID Randomized techniques for computing the ID Randomized algorithms for computing the CUR decomposition The CUR decomposition Converting a double-sided ID to a CUR decomposition Adaptive rank determination with updating of the matrix Problem formulation A greedy updating algorithm A blocked updating algorithm Evaluating the norm of the residual Adaptive rank determination without updating the matrix Randomized algorithms for computing a rank-revealing QR decomposition Column pivoted QR decomposition A strongly rank-revealing UTV decomposition The UTV decomposition An overview of randUTV A single step block factorization Four Lectures on Probabilistic Methods for Data Science Lecture 1: Concentration of sums of independent random variables Sub-gaussian distributions Hoeffding’s inequality Sub-exponential distributions Bernstein’s inequality Sub-gaussian random vectors Johnson-Lindenstrauss Lemma Notes Lecture 2: Concentration of sums of independent random matrices Matrix calculus Matrix Bernstein’s inequality Community recovery in networks Notes Lecture 3: Covariance estimation and matrix completion Covariance estimation Norms of random matrices Matrix completion Notes Lecture 4: Matrix deviation inequality Gaussian width Matrix deviation inequality Deriving Johnson-Lindenstrauss Lemma Covariance estimation Underdetermined linear equations Sparse recovery Notes Homological Algebra and Data Introduction and Motivation What is Homology? When is Homology Useful? Scheme Lecture 1: Complexes and Homology Spaces Spaces and Equivalence Application: Neuroscience Lecture 2: Persistence Towards Functoriality Sequences Stability Application: TDA Lecture 3: Compression and Computation Sequential Manipulation Homology Theories Application: Algorithms Lecture 4: Higher Order Cohomology and Duality Cellular Sheaves Cellular Sheaf Cohomology Application: Sensing and Evasion Conclusion: Beyond Linear Algebra Back Cover Data science is a highly interdisciplinary field, incorporating ideas from applied mathematics, statistics, probability, and computer science, as well as many other areas. This book provides an introduction to the mathematical methods that form the foundations of machine learning and data science.