Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I think this is my first research-level question, so I'm going to ask it here first before going to Math Overflow.

In most tutorial papers like Burges, the Vapnik-Chervonenkis dimension is introduced as a way of bounding the expected error of a learning machine by the sum of its training error and a slightly more complicated expression which is $O(\sqrt{log(n)})$:

$Error \leq \text{training error} + \sqrt{h(\log(2N/h)+1)-\log(\eta/4)\over N}$

The VC dimension $h$ is the number of points in two classes in some feature space that may be properly divided by a classifier operating on that space, where 'properly' here means with zero error regardless of the combination of classes assigned to the point. An example is the perceptron, which can learn any binary function except XOR, which means that its VC dimension is 3. This gives a highly conservative upper bound which enables one to select a learning machine with the smallest VC dimension $h$ that gives low training error.

Regularization, on the other hand, is a method of penalizing some feature of the solution generated by the learning machine. An example is $L_2$ regularization (Tikhonov):

$Cost(\mathbf{w}) = ||\mathbf{y} - \mathbf{w}^H\mathbf{X}||^2 + \lambda||\mathbf{w}||^2$

The first term is the mean-squared error, where $\mathbf{y}$ is a vector of desired outputs, and $\mathbf{X}$ is a matrix of corresponding observed features of the data for each $y$. The weight vector $\mathbf{w}$ here represents a linear function mapping the features to an estimate of the desired output (normally the nonlinear case is handled by kernel methods). The important thing here is the penalty $\lambda$, which indicates how much you pay for a 'big' weight vector (in the $L_2$ sense).

I have done a couple of searches and not seen anything characterizing the connection between these two methods, other than one informal ranking by conservativeness.

Does anyone know what regularization does to your VC dimension? Intuitively I feel that something like $L_1$ regularization would immediately start cutting it down, but I can't visualize what would happen. If there are papers I wouldn't mind referring to those.

share|cite|improve this question

If you consider Rademacher complexity instead, here are 2 papers that may be relevant

share|cite|improve this answer
Hey, these are pretty cool! Thanks! – Trevor Alexander Dec 30 '13 at 0:09

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.