Algorithmic Aspects of Machine Learning

This book bridges theoretical computer science and machine learning by exploring what the two sides can teach each other. It emphasizes the need for flexible, tractable models that better capture not what makes machine learning hard, but what makes it easy. Theoretical computer scientists will be introduced to important models in machine learning and to the main questions within the field. Machine learning researchers will be introduced to cutting-edge research in an accessible format, and gain familiarity with a modern, algorithmic toolkit, including the method of moments, tensor decompositions and convex programming relaxations. The treatment beyond worst-case analysis is to build a rigorous understanding about the approaches used in practice and to facilitate the discovery of exciting, new ways to solve important long-standing problems. Cover 1 Front Matter 3 Dedication 4 Algorithmic Aspects of Machine Learning 5 Copyright 6 Contents 7 Preface 9 1 Introduction 11 2 Nonnegative Matrix Factorization 14 3 Tensor Decompositions. Algorithms 39 4 Tensor Decompositions. Applications 58 5 Sparse Recovery 81 6 Sparse Coding 99 7 Gaussian Mixture Models 117 8 Matrix Completion 142 Bibliography 153 Index 160 Machine learning is reshaping our everyday life. This book explores the theoretical underpinnings in an accessible way, offering theoretical computer scientists an introduction to important models and problems and offering machine learning researchers a cutting-edge algorithmic toolkit.