# Introduction

### Introduction

In this lecture we review the basic concepts and discuss some introductory examples.

## What we will learn

• Introduction

• Examples: Linear Regression, Logistic Regression, SVM

• Convex Functions

• Convex Sets

• Convex Problem

• Scope and Summary

# Introduction

### Convex Optimization

In this lecture we review the basic concepts and provide preliminary results.

## What we will learn

• Basic notations and definitions.

• Separation Theorems.

• First-order optimality conditions.

• Convex problems.

• First order oracle.

# Optimization

### Cutting plane methods

In this lecture, we review cutting plane methods which are first order optimization methods

## What we will learn

• Center of Gravity.

• Separation oracle.

• Linear programs

• Semi-definite programs.

• Ellipsoid Method.

# Optimization

### 4

In this lecture we introduce the gradient descent method and analyze it.

## What we will learn

•  Linear projections

• Lipschitness

• GD Analysis

• General case

• Strong convexity

• Smooth functions

• well conditioned functions.

# Generalization

### Stochastic optimization

In this lecture we begin to discuss the setting stochastic convex optimization, or learning convex functions.

## What we will learn

• General setup

• Empirical risk

• Hoeffding's inequality

• Uniform convergence

• Empirical risk minimization

# Generalization

### Uniform Convergence Bounds

In this lecture we discuss generalization and provide the first technique to prove generalization: u.c. bounds.

## What we will learn

• Covering Numbers.

• Union Bound.

• Ɛ-approximation

• General Linear Models.

• Mcdiarmid's Inequality.

• Dimension independent generalization bounds.

• Regularization.

# Generalization

### Stability

In this lecture we discuss an alternative technique to prove generalization bounds, stability

## What we will learn

• Uniform Stability

• Analysis of uniformly stable algorithms

•  Regularization (revisited)

• Uniform convergence lower bounds

# Generalization

### 8

In this lecture we introduce and analyze stochastic gradient descent

## What we will learn

•  Noisy first-order oracle.

• SGD algorithm.

•  Azuma's Inequality.

•  Fast rates.

• Generalization lower bounds.

• Identifying a biased coin.

•  Pinsker's Inequality.

• Optimality of SGD.

# Algorithms

### Stability Analysis for GD

In this lecture we provide algorithmic dependent generalization analysis, for GD.

## What we will learn

• Stability by proximity and,

analysis for strongly convex functions

• Expansiveness and, analysis for smooth functions

• Stability for general convex functions

# Algorithms

### Generalization Lower Bounds

In this lecture we provide generalization lower bounds that are algorithmic specific

## What we will learn

• Generalization lower bound for  smooth functions.

• Generalization lower bound for general functions

• Revisiting the role of regularization.

• Full batch methods.