Roi Livni
רועי לבני
Home
Publications
Courses
Contact
More
The Basic Model and Introduction
Basic Concepts
Convex Sets
Convex Functions
Convexity Preserving Operations
Convex Programs
Linear Regression
GLMs
SVMs
Regularizations
Scope and Summary
Basic properties of convex functions
Separation Theorems.
(Sub)gradient.
Existence
Properties
First-order optimality conditions.
Unconstrained formulation
Contrained formulation
Optimization model and first-order optimization methods
First Order Model
Cutting Plane Methods
CoG
Ellipsoid method
Gradient Descent with Analysis
(Sub)Gradient Method
(Detour)- Online Linear Regret
Projected (sub)Gradient Descent
GD Analysis for convex Lipschitz functions
Structural Assumptions
Strong Convexity
Smoothness
Well-Condtioned
The Learning Model
Stochastic Optimization Model
Learning
Empirical Risk
Uniform convergence
Union Bound
Generalization and Uniform Convergence Property
Covering Numbers.
Rademacher Complexity.
Norm Dependent Bounds.
Further generalization Bounds for ERMs and stable algorithms.
Empirical Risk Minimizers
Stability
Stability through Strong Convexity
Regularized Empirical Risk Minimizers
Stability analysis under convexity, strong convexity and smoothness
The Strongly Convex Case
Regularization
The General Case
The Smooth Case
Analysis of SGD
Stochastic Gradient Descent
Fast Rates for Strongly Convex Functions
mini-batch SGD
We use Lecam's method for the first generalization lower bounds
Information-Theoretic bounds
(Detour) The problem of a biased-coin.
Lower Bounds for convex Lispchitz functions.
Lower Bounds for Strongly Convex functions.
We develop stronger lower bounds for ERMs
Empirical misaglinment bounds
Feldman's function
Lower Bounds for Uniform Convergence
Lower Bounds for Empirical Risk Minimizers
We develop further tools to introduce, algorithm dependent, generalization lower bounds.
The Sample Dependent Oracle Model
Lower bounds for Gradient Descent
