I’ve started doing more machine learning research lately, which means I’ve been sullying my delicate theorist’s hands testing out my algorithms on data. Perhaps the most (over) used dataset is the MNIST handwritten digits collection, which was been put into MATLAB form by Sam Roweis (RIP). As a baseline, I wanted to see how an SVM would perform after I projected the data (using PCA) into the top 100 dimensions. The primal program is
s.t.
I chose some “reasonable” value for C and tried to train a classifier on all pairs of points and got the following error rates on the test set (in percentages, rounded).
0 0 0 0.56 0.43 0 0.33 0.45 2.37 0 0.04 0.06 1.17 0.23 0 1.02 0.11 1.89 3.77 0.72 0 0.52 0 1.31 0.08 0.60 1.66 0 0.01 0.15 1.01 0.80 0.80 0.42 0 0 0.43 1.15 2.22 2.69 0.38 3.41 0.54 0.47 0 0.20 0.14 0.85 1.13 3.03 1.02 0 3.82 1.27 0
This is digits from 0 to 9, so for example, the training error for classifying 0 versus 1 was zero percent, but it’s about 3.8 percent error to decide between 9 and 7. I did this to try and get a sense of which digits were “harder” for SVM to distinguish between so that I could pick a good pair for experiments, or better yet, to pick a pair based on a target error criterion. Running experiments on Gaussian synthetic examples is all fine and good, but it helps to have a range of data sets to test out how resilient an algorithm is to more noise, for example.
balls (people) and 
bins/categories (days), how big should 
, as we know, but we can expand this to deal with approximate matches (you need only 7 people to get 2 birthdays in the same week with probability around 1/2). If you want to put a graph on it you can ask social-network coincidence questions and get some scalings as a function of the number of edges and number of categories — here there are 
which I had found interesting:
.
, but by another quantity:
is given by the following definition.
and 
be random variables with joint distribution 
. We define
,
denotes the 
-marginal distribution of 
and the supremum on the right hand side is over all probability distributions 
that are different from the probability distribution 
. If either 
to be 0.
have joint distribution 
(I know I am changing notation here but it’s easier to explain). The key to showing their result is through deriving variational characterizations of 
and 
in terms of the function
, and 
? If either 
. However, 
and there exists a sequence of variables 
satisfying the Markov chain such that 
such that the ratio approaches 
-dimensional data points ![\{ \mathbf{x}_i : i \in [n] \}](http://s0.wp.com/latex.php?latex=%5C%7B+%5Cmathbf%7Bx%7D_i+%3A+i+%5Cin+%5Bn%5D+%5C%7D&bg=ffffff&fg=29303b&s=0 "\{ \mathbf{x}_i : i \in [n] \}")
the Lasso tries to fit the model 
by minimizing the 
penalized squared error
.
so the data is ![\{(\mathbf{X}_i, Y_i) : i \in [n] \}](http://s0.wp.com/latex.php?latex=%5C%7B%28%5Cmathbf%7BX%7D_i%2C+Y_i%29+%3A+i+%5Cin+%5Bn%5D+%5C%7D&bg=ffffff&fg=29303b&s=0 "\{(\mathbf{X}_i, Y_i) : i \in [n] \}")
. The assumptions are on the random variables 
is bounded, the variable 
, and 
, where 
and 
are unknown constants. Basically that’s all that’s needed — given a bound on 
, he derives a bound on the mean-squared prediction error.
, can be improved to 
. Most often this involves additional assumptions on the loss functions (which can sometimes get a bit baroque and hard to check). This paper considers constant step-size algorithms but where instead they consider the averaged iterate $\latex \bar{\theta}_n = \sum_{k=0}^{n-1} \theta_k$. I’m trying to slot this in with other things I know about stochastic optimization still, but it’s definitely worth a skim if you’re interested in the topic.
