Answers.Body: <p>SVM complexity is <span class="math-container">$O(\max(n,d)\min(n,d)^2)$</span> according to Chapelle, Olivier. &quot;Training a support vector machine in the primal.&quot; Neural Computation 19.5 (2007): 1155-1178.</p>
  <p><span class="math-container">$n$</span> is the number of instances and <span class="math-container">$d$</span> is the number of dimensions. I'm assuming that you have more instances than dimensions giving a complexity of <span class="math-container">$O(nd^2)$</span>. Hopefully this explains fully why reducing the number of dimensions will reduce the training time.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-10-17T13:36:20.963Z
Answers.Text: thank you for your answer. but; is this true after using RBF kernel? because its map data form original feature space to an other space.  The SVM used this space for training, which means its don't matter the dimension of original space.
Answers.UserDisplayName: alighorbani
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-10-18T00:26:21.450Z
Answers.Text: I do know that the RBF kernel does not scale well with training samples or input feature dimensions, so I would assume unfavourable complexity would still hold in terms of input dimensions. But that's about the extent of my knowledge sorry!
Answers.UserDisplayName: Cameron Chandler
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-10-17T09:28:43.253Z
Answers.LastActivityDate: 2020-10-17T09:28:43.253Z
Answers.UserDisplayName: Cameron Chandler
Body: <p>Training an SVM with an RBF kernel model with <code>c = 5.5</code> and <code>gamma = 1.06</code>, for a 5-class classification problem on the NSL-KDD train data-set with 122 features using one vs rest strategy takes <span class="math-container">$2162$</span> seconds. Also, considering binary classification (<code>c = 10</code>, <code>gamma = 4</code>), it takes <span class="math-container">$520.56$</span> seconds.</p>
  <p>After dimensionality reduction, from 122 to 30, using a sparse auto-encoder, the training time falls dramatically, from <span class="math-container">$2162$</span> to <span class="math-container">$240$</span> and <span class="math-container">$520$</span> to <span class="math-container">$170$</span>, while using the same hyperparameters for the RBF-kernel.</p>
  <p>What is the reason for that? Is it not true that using kernel neutralized the effect of high dimensions?</p>
  
Tags: <machine-learning><training><autoencoders><support-vector-machine><feature-selection>
Title: Why does the training time of SVMs dramatically decrease after applying dimensionality reduction to the features?
UserDisplayName: alighorbani
ThreadText: # Why does the training time of SVMs dramatically decrease after applying dimensionality reduction to the features?
  
  (Asked by: username_0 on 2020-10-16)
  
  Training an SVM with an RBF kernel model with `c = 5.5` and `gamma = 1.06`, for a 5-class classification problem on the NSL-KDD train data-set with 122 features using one vs rest strategy takes $2162$ seconds. Also, considering binary classification (`c = 10`, `gamma = 4`), it takes $520.56$ seconds.
  
  After dimensionality reduction, from 122 to 30, using a sparse auto-encoder, the training time falls dramatically, from $2162$ to $240$ and $520$ to $170$, while using the same hyperparameters for the RBF-kernel.
  
  What is the reason for that? Is it not true that using kernel neutralized the effect of high dimensions?
  
  **Tags:** machine-learning, training, autoencoders, support-vector-machine, feature-selection
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2020-10-17. Score: 1 | Accepted answer
  
  SVM complexity is $O(\max(n,d)\min(n,d)^2)$ according to Chapelle, Olivier. "Training a support vector machine in the primal." Neural Computation 19.5 (2007): 1155-1178.
  
  $n$ is the number of instances and $d$ is the number of dimensions. I'm assuming that you have more instances than dimensions giving a complexity of $O(nd^2)$. Hopefully this explains fully why reducing the number of dimensions will reduce the training time.
  
  > **Comments:**
  > **username_0**: thank you for your answer. but; is this true after using RBF kernel? because its map data form original feature space to an other space.  The SVM used this space for training, which means its don't matter the dimension of original space.  
  > **username_1**: I do know that the RBF kernel does not scale well with training samples or input feature dimensions, so I would assume unfavourable complexity would still hold in terms of input dimensions. But that's about the extent of my knowledge sorry!  
  
  ---
  
  