Rademacher complexity

Stochastic Optimization

Core-sets and importance sampling

VC dimension

Inverse Problems

Stochastic gradient descent (SGD)

Noncommutative Chernoff bounds

Learning representations

Online Learning

Graph

Metric embedding

Kaczmarz algorithm

Matrix approximation

Restricted isometries

Randomized algorithm

Diagonally dominant systems

Compressed Sensing

Random Matrices

Covering numbers

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

Monte Carlo method

Sample Complexity

Randomized Algorithms

Large Deviation Bounds

Packet Routing

Martingales

Probabilistic Method

Hashing

Markov Chains

CSCI 1550/2450 Probabilistic Methods in Computer Science Brown University Spring 2022 This analytical course dives into the mathematical underpinnings of computing successes like machine learning and cryptography, emphasizing the role of probability, randomness, and statistics. Students will explore mathematical models, theorems, and proofs. Practical implementations are not covered, focusing instead on the theories driving computational probabilities. CSCI 1550/2450 is a course on the mathematics that motivates, formulates, and explains many of the great successes of computing, including statistical machine learning, Monte Carlo methods, and modern cryptography. Probability, randomness, and statistics play a key role in these and almost any other modern computer science application. This course introduces the novel mathematical and computation methods that were developed at the interplay of probability and computing. The course focuses on mathematical models, theorems and proofs, and leaves implementation and experiments to other courses. - CSCI 1550/2540 is a theory/analytical course - analysis, theorems, no implementations.
- The course covers modern mathematics at the interface of probability theory and computation
- Formulates, and explains many of the great successes of computing, such as machine learning, cryptography, modern finance, computational biology, etc.
- This course focuses on tools, not particular applications. CS145 or equivalent (first three chapters in the course textbook). ## Textbook

The textbook for the course is *[Probability and Computing Randomization and Probabilistic Techniques in Algorithms and Data Analysis, 2nd Edition](https://www.amazon.com/Probability-Computing-Randomization-Probabilistic-Techniques/dp/110715488X/ref=dp_ob_title_bk)* by [Michael Mitzenmacher](http://www.eecs.harvard.edu/%7Emichaelm/) and [Eli Upfal](/people/eli).

[Errata for the 1st Printing](http://www.eecs.harvard.edu/%7Emichaelm/MUErrataPrint1.pdf), [Errata for the 2nd Printing](http://www.eecs.harvard.edu/%7Emichaelm/MUErrataPrint2.pdf)

CSCI 1550/2450 Probabilistic Methods in Computer Science

Mathematical Foundations

Rademacher complexity

2 courses cover this concept

CS 294 - The Mathematics of Information and Data

CSCI 1550/2450 Probabilistic Methods in Computer Science