# Comparing the Training Costs of Machine Learning Algorithm: A Mathematical Perspective

Recently, I was looking at the optimization functions required in training Kernel Based Methods compared to Neural Networks.

1) Kernel Methods:

For instance, I was looking at the optimization in Support Vector Machines:

And Gaussian Process Regression:

The optimized hyperparameters $$\Theta^\star$$ are determined by the log marginal [11] as $$\Theta^\star = \arg \max \log p(y \mid \mathcal{X}, \Theta)$$ Thus, considering hyperparameters, a more general equation of predictions at the new testing point is [2] $$\bar{f}_\star \mid \mathcal{X}, y, \mathcal{X}_\star, \Theta \sim \mathcal{N}(\bar{f}_\star, \operatorname{cov} f_\star )\big)$$

2) Neural Networks:

My Question: We often hear the reason that Neural Networks were initially less popular than Kernel Based Methods is because (deep) Neural Networks typically require significantly more computational resources to train compared to Kernel Based Methods.

I have informally heard that Gaussian Process Regression scales better to larger data sets (based on a choice of kernel function, the data can be directly entered into the structural form of the Gaussian Process), and I have also informally heard that training Neural Networks are generally considered to be extremely computationally expensive - but just by looking at the functions associated with each model that require to be optimized, how can we understand the differences in computational costs between Kernel Based Methods and Neural Networks from a mathematical perspective? Is there something aspect of the optimization equation that can mathematically explain why Kernel Methods are said to be computationally cheaper than Neural Networks?

Thanks!

References:

Note 1: For example, imagine that optimizing "Loss Function A" requires 5 computations per iteration and optimizing "Loss Function B" requires 4 computations per iteration - assuming that each computation has the same cost, we could naturally conclude that the Machine Learning algorithm associated with "Loss Function A" would be more "computationally expensive to optimize" compared to the Machine Learning algorithm associated with "Loss Function B" : Could a similar conclusion be made about the comparing the computational costs for training Deep Neural Networks and Kernel Methods?

Note 2: The Loss Function of a Deep Neural Network is a function that contains many parameters. Optimizing a Loss Function with fewer parameters is computationally cheaper than optimizing a Loss Function with more parameters (i.e. additional costs can be attributed to each new parameter). On the other hand, Kernel Methods are said to be non-parametric - however, I am thinking that some "relaxation" technique is somehow typically used in Kernel that might simplify the optimization problem? (https://shuzhanfan.github.io/2018/05/understanding-mathematics-behind-support-vector-machines/)

• Please change your image [2], I tried to edit as to remove the superfluous links and it was soooo confusing! :) Commented Apr 2, 2022 at 7:56
• By the way, for maintainability reasons, it is better to rewrite the equations using mathjax ratter than posting an image thereof. I'll do that to remove [2]. Commented Apr 2, 2022 at 7:59
• Computational cost is determined by actual math operations. Mathematically, you can compare each method's cost by the big-O notation or $\mathcal{O}(n)$ order where $n$ is an arbitrary size of your training data. Commented May 5, 2022 at 10:17

From my understanding of these two methods, the general saying that deep neural networks are more costly can be due to the fact that the number of parameters in deep neural networks are usually much larger than the dimension of data in problem. As for the kernel methods such as SVM, the dimension of parameter $$w$$ is linear with respect to dimension of data $$x$$.

The above analysis is based on the computational cost in one iteration. Additional consideration shall be the convergence speed. For this part, it depends on the problem structure (properties like convexity), which I am not so familiar with the specific results.