# Introduction

### Introduction

In this lecture we give an introductory example for learning problem.

## What we will learn:

• learning rectangles.

• approximation error.

• union bound.

# Statistical Learning Theory

### The PAC Model

In this lecture we introduce the Probably Approximately Correct (PAC) Model for classification.

## What we will learn:

• General Setup

• Expected error

• The PAC Model

• Half spaces

• Empirical Risk Minimization

• Agnostic vc. Realizable model

# Statistical Learning Theory

### VC Dimension

In this lecture we introduce the notion of VC dimension and discuss the fundamental theorem of learning

## What we will learn:

• Sample complexity lower bounds

• VC dimension

• VC dimension of rectangles.

• VC dimension of halfspaces

• The fundamental theorem of learning

• proper vs. improper learning

# Statistical Learning Theory

### Nerual Networks

In this lecture we discuss the class of neural network in the lens of the PAC model

## What we will learn:

• The class of neural network.

• Expressivity of NN.

• Compositional properties of VC dimension

# Computational Learning Theory

### Learning Halfspaces

In this lecture we begin to discuss the algorithmic aspects of learning and review learning algorithms for half spaces

## What we will learn:

• Linear programming

• Perceptron

• Kernel trick and kernelized perceptron

# Computational Learning Theory

### Hardness of Learning

In this lecture we reivew over computational lower bounds for learning

## What we will learn:

• Class of DNF and hardness of proper learning.

• Hardness of (improper) binary classification.

# Computational Learning Theory

### Boosting

In this lecture we discuss the algorithmic tool of Boosting, and the reduction from strong learning to weak learning

## What we will learn:

• Weak learnability.

• Multiplicative Weight algorithm

• application to boosting.

# Stochastic Convex Optimization

### Learning with Convex Functions

In this lecture we shift from binary learning to real-valued functions learning. Discussing convex functions.

## What we will learn:

• Convexity

• Convex functions

• Convex sets.

• Convex learning problems

• Linear regression

• Support Vector Machines.

# Stochastic Convex Optimization

### Generalization bounds (real-valued losses)

In this lecture we generalize our techniques to prove generalization bounds to real-valued losses instead of binary losses.

## What we will learn:

• Covering numbers

• learning norm-bounded linear models.

# Stochastic Convex Optimization

### Optimization Algorithms

In this lecture we will analyze two optimization algorithms for learning: GD and SGD

## What we will learn:

• General Setup for convex optimization

• zero/first order oracle.

• Linear projections.

• Lipschitness.

• Stochastic Gradient Descent (SGD) algorithm.

# Stochastic Convex Optimization

### Backpropogation algorithm

In this lecture we will discuss the application of gradient descent methods for non-convex optimization (such as neural networks).

## What we will learn:

• Backpropogation algorithm

# Stochastic Convex Optimization

### Kernel Methods

In this lecture we revisit kernel methods and show how they can be used in the framework of convex problems.

## What we will learn:

• Reproducing Kernel Hilbert Spaces.

• Kernelized SGD

# Online Learning

### Online Learning

In this lecture we introduce the model of online learning

## What we will learn:

• Problem Setup.

• Examples

• online shortest path.

• portfolio selection.

• Online Gradient Descent (OGD) algorithm.

# Online Learning

### Partial Feedback

In this lecture we extend the online learning model to the setting of partial feedback

## What we will learn:

• The Multi-armed bandit problem.

• Exp3 algorithm.