Convex Optimization for Machine Learning

✍ Scribed by Changho Suh

• Publisher: Now Publishers Inc
• Year: 2022
• Tongue: English
• Leaves: 379
• Category: Library

✦ Synopsis

This book covers an introduction to convex optimization, one of the powerful and tractable optimization problems that can be efficiently solved on a computer. The goal of the book is to help develop a sense of what convex optimization is, and how it can be used in a widening array of practical contexts with a particular emphasis on Machine Learning.

The first part of the book covers core concepts of convex sets, convex functions, and related basic definitions that serve understanding convex optimization and its corresponding models. The second part deals with one very useful theory, called duality, which enables us to: (1) gain algorithmic insights; and (2) obtain an approximate solution to non-convex optimization problems which are often difficult to solve. The last part focuses on modern applications in Machine Learning and Deep Learning.

A defining feature of this book is that it succinctly relates the "story" of how convex optimization plays a role, via historical examples and trending Machine Learning applications. Another key feature is that it includes programming implementation of a variety of Machine Learning algorithms inspired by optimization fundamentals, together with a brief tutorial of the used programming tools. The implementation is based on Python, CVXPY, and TensorFlow.

Since one of the key tools in convex optimization is an algorithm that requires computation on a computer, it is crucial to know how to implement algorithms using software tools. We employ Python as a major programming platform. To solve traditional convex optimization problems such as linear program, least squares, and semi-definite program, we utilize an easy-to-use and high-level language, CVXPY, running in Python. To implement Machine Learning and Deep Learning algorithms, we employ TensorFlow, one of the most popular Deep Learning frameworks. TensorFlow provides numerous powerful built-in functions that ease performing many important procedures in deep learning. One of the key benefits of TensorFlow is that it is fully integrated with Keras, the most high-level library with a focus on enabling fast user experimentation. Keras allows us to go from idea to implementation with very few steps.

This book does not follow a traditional textbook-style organization, but is streamlined via a series of lecture notes that are intimately related, centered around coherent themes and concepts. It serves as a textbook mainly for a senior-level undergraduate course, yet is also suitable for a first-year graduate course. Readers benefit from having a good background in linear algebra, some exposure to probability, and basic familiarity with Python.

✦ Table of Contents

Copyright
Preface
Chapter 1 Convex Optimization Basics
1.1 Overview of the Book
1.2 Definition of Convex Optimization
1.3 Tractability of Convex Optimization and Gradient Descent
Problem Set 1
1.4 Linear Program (LP)
1.5 LP: Examples and Relaxation
1.6 LP: Algorithms
1.7 LP: CVXPY Implementation
Problem Set 2
Problem Set 2
1.8 Least Squares (LS)
1.9 LS: Test Error, Regularization and CVXPY Implementation
1.10 LS: Computed Tomography
Problem Set 3
Problem Set 3
1.11 Quadratic Program
1.12 Second-order Cone Program
1.13 Semi-definite Program (SDP)
1.14 SDP Relaxation
Problem Set 4
Problem Set 4
Chapter 2 Duality
2.1 Strong Duality
2.2 Interior Point Method
Problem Set 5
2.3 Proof of Strong Duality Theorem (1/2)
2.4 Proof of Strong Duality Theorem (2/2)
Problem Set 6
2.5 Weak Duality
2.6 Lagrange Relaxation for Boolean Problems
2.7 Lagrange Relaxation for the MAXCUT Problem
Problem Set 7
Chapter 3 Machine Learning Applications
3.1 Supervised Learning and Optimization
3.2 Logistic Regression
3.3 Deep Learning I
3.4 Deep Learning II
3.5 Deep Learning: TensorFlow Implementation
Problem Set 8
3.6 Unsupervised Learning: Generative Modeling
3.7 Generative Adversarial Networks (GANs)
3.8 GANs: TensorFlow Implementation
Problem Set 9
3.9 Wasserstein GAN I
3.10 Wasserstein GAN II
3.11 Wasserstein GAN: TensorFlow Implementation
Problem Set 10
3.12 Fair Machine Learning
3.13 A Fair Classifier and Its Connection to GANs
3.14 A Fair Classifier: TensorFlow Implementation
Problem Set 11
Chapter A Python Basics
A.1 Jupyter Notebook
A.2 Basic Python Syntaxes
A.2.1 Data Structure
A.2.2 Package
A.2.3 Visualization
Chapter B CVXPY Basics
Chapter C TensorFlow and Keras Basics
References
Index
About the Author