The curse of dimensionality? (linear SVMs) How do you know whether you suffer from it? 
Let's suppose I have a 2 class problem - 2000 training examples and 30 features. While it works good for the most part, sometimes I get edge cases that are so horribly misclassified. I feel like it's because there is a lot of dimensions and too little examples.
I feel like the dimensionality is affecting my results - is there a way to check if it's true?
Do I need to have several examples for each combination of the feature values? With 30 features from which each can have hundreds of values, this would require ENORMOUS amount of data...
How much improvement can I anticipate if I were to increase the training set size to 4000 examples, 8000 examples, 16000 examples etc. - is there a rule of thumb when trying to figure this out?
 A: 30 features is a not a high amount. A large amount of features in SVM standards signifies (hundreds of) thousands of features.  You don't need to have thousands of examples to obtain a good decision boundary with such few features. In fact, 2000 examples is probably already plenty. 
If you get fairly poor results (after tuning the hyperparameters properly!) you are likely in a situation that requires a nonlinear decision boundary. This is very common in low dimensional problems. I suggest trying with an RBF kernel to see if your results improve.
A: The performance bounds on which the maximal margin classifier is based are independent of the dimension of the feature space (which is the dimension of the input vector in the case of a linear SVM), but instead depend on the margin.  This is the reason that the SVM with an infinite dimensional feature space (e.g. that induced by the radial basis function kernel) can still give good generalisation performance.  However, this requires careful tuning of the regularisation parameter.
Instead of the complexity of the model being defined in terms of the number of model parameters (which is a traditional view in statistics), the parameter C is used to define a nested set of classes of models of increasing complexity.  The task is then to produce a model that explains the data from the model class of the least complexity.  This is known as structural risk minimisation.
In other words the linear SVM is robust to the curse of dimensionality provided the C parameter is tuned very carefully.  As @Marc Claesen suggests (+1), if the model still doesn't give good performance, it is probably a non-linear problem and an RBF kernel is a good option.  Sadly structural risk minimisation does not apply to the problem of optimising the kernel parameters, but you can't have everything!
Proper cross-validation is generally a good guide (but make sure you tune the hyper-parameters independently in each fold).  If you want to estimate the performance improvement from gathering more data, the simplest thing to do is to generate a plot of the cross-validation error as a function of the number of training patterns (i.e. a learning curve).  
