randomized algorithm is a type of algorithm, similar to relaxation.

• Make a hard problem easier by changing the problem
• What if, instead of guaranteeing we find the best/correct answer, we only provide some chance of finding the best/correct answer?

Las Vegas algorithms

see Las Vegas algorithm

best and average case randomness

Two notions of randomized algorithm runtime: expected running time (you pick randomness, what’s the worst case input running time) vs worst-case running time (adversary picks randomness, what’s the worst case running time?).

Key Sequence

Notation

New Concepts

• randomized algorithm
  • Las Vegas algorithm
  • best and average case randomness
• bogo sort
• quicksort

Important Results / Claims

Questions

Interesting Factoids

Three models of fitting. Consider trying to fit some dataset \(|D|= n\) that’s roughly quadratic with…

• a linear model: underfit, high bias (i.e. “model imposes bias of linearity on data”)
• a nth order polynomial: overfit, high variance (i.e. “a small perturbation of data brings lots of change”)

Its important to pay attention if you are having high bias of high variance—solutions of each is different from each other.

intuition of overfitting

See overfit

Some ideas of model validation

Cross Validation

Hold-out cross-validation

For instance, you can do:

• 70% for training
• 30% hold out cross validation for testing

But at very large dataset scales, the validation size can be capped at a fixed size (so you can hold out like 0.1% or something but still have 10k samples).

k-fold cross validation

1. shuffle the data
2. divide the data into \(k\) equal sized pieces
3. repeatedly train the algorithm on 4/5 of the data, test on remaining 1/5

In practice people do 10 folds.

Model selection:

• choose some parameters
• evaluate every model using a Model Evaluation method of some kind
• and in production…
  • k-fold or LOOCV: retrain best model on all data
  • Hold-out cross-validation: optionally retrain, if you have time

A special case of model selection is feature selection:

• choose a subset of the most relevant features to train on
• note that power set is \(2^{m}\) in size; so instead of doing this we train \(O\qty(n)\) by starting out with an empty set, and then adding features sequentially that would give us the best performance