Covering numbers

Stochastic Optimization

Core-sets and importance sampling

VC dimension

Inverse Problems

Stochastic gradient descent (SGD)

Noncommutative Chernoff bounds

Rademacher complexity

Learning representations

Online Learning

Graph

Metric embedding

Kaczmarz algorithm

Matrix approximation

Restricted isometries

Randomized algorithm

Diagonally dominant systems

Compressed Sensing

Random Matrices

Statistical complexity

CS 294 - The Mathematics of Information and Data UC Berkeley Fall 2013 This course investigates the mathematical principles behind data and information analysis. It brings together concepts from statistics, optimization, and computer science, with a focus on large deviation inequalities, and convex analysis. It's tailored towards advanced graduate students who wish to incorporate these theories into their research. This course will explore the foundations of an emerging discipline: the mathematics of information and data. Through recent and classic texts in mathematical statistics, optimization, and computer science, we will find unifying themes in these three disciplinary approaches. We will draw connections between how we analyze running time, statistical accuracy, and implementation of data-driven computations. We will focus in particular on large deviation inequalities, convex analysis and their applications in minimax statistics; sparse and stochastic optimization; and discrete and convex geometry. This course is ideal for advanced graduate students who would like to apply these theoretical and algorithmic developments to their own research. The current list of topics (which will change depending on the course we chart) is:

1. Stochastic Optimization
    - stochastic gradients, online learning, and the Kaczmarz algorithm
    - core sets and importance sampling
    - randomized algorithms for linear systems
1. Random Matrices
    - Elementary analysis of random matrices
    - Graph sparsification, frames, and matrix approximation
    - Noncommutative Chernoff Bounds
1. Average Case Analysis of Optimization Problems
    - covering numbers, VC dimension, rademacher complexity
    - metric embedding and restricted isometries
    - compressed sensing and all that it has wrought Consent of the instructor is required. Graduate level courses in probability and optimization will be necessary. 

CS 294 - The Mathematics of Information and Data

Theoretical Computer Science

Covering number

Covering numbers

1 courses cover this concept

CS 294 - The Mathematics of Information and Data