I do have a tangential technical question for someone who knows more math than I do.
A kernel SVM always finds (one-of) the global best fit lines in the kernel space.
A gradient descent model explicitly converges to one of the nearest local minimas by definition.
Does this paper conclude that the local minimas that neural networks converge to are one of the many equivalent global maxima ? Won't this be a major revelation by itself ?
I don't have a strong math background but I think during the optimisation process of finding the hyperplane, the solver (algorithm that attempts to find best separating hyperplane) uses soft margin to allow mis-classified instances. Its tolerance is controlled by a hyper-parameter so it will comprise to find the best fit within the set parameter. So it is a 'best solution' with a condition. However there are many variations of implementations from different solvers to handle it.
Binary decision trees are basically super optimizers: minimizing the number of gates needed to make a Chip's logic (multiply circuits or whatever)
Sure, and unbreakable crypto is notoriously difficult to make
Not really. It's the unbreakable AND efficient requirement combined that's hard.
Just run anything over a random xor shift add kernel about 1 million times and it's unbreakable (so long as xor / shift forms a bijection). It's just inefficient.
Finding the smallest number of iterations that works is the hard part. Usually, people try to break it (ex, AES was originally broken over 4 iterations) then double or triple your best attempt, and you are set.
AES is now broken over 5 iterations IIRC, but still a long way to go to break full 8 iteration AES.
More modern ciphers (SHA512) are like 80 iterations of a simpler kernel.
Even 'broken' ciphers like TEA or RC4 are hard to break in practice if you just increase the iteration count up the wazzoo. The problem is: AES gets to security in just 8 iterations.
So to be better than AES requires both efficiency AND security. After all, 100 iterations of AES is going to be more secure if you don't care about efficiency. (10x more iterations than the default spec)
In the context of this paper, you can think of the "gradient descent step" as optimizing the parameters of the kernel (i.e. the parameters that generate the kernel space). There are no explicitly optimality guarantees beyond those of standard gradient descent.
The "SVM step" would still find a global optima within the kernel space, but the qualifications of the previous step mean that the kernel space generated might be useless.
I don't think the output of the conversion is guaranteed to be equivalent to a hyperplane learned by an SVM.
I didn't have time to read the paper, but reading the abstract I don't see a claim that the gradient descent model approximated by a kernel machine is equivalent to an optimal fit obtained by SVM maximum margin hyperplane fitting.
I assume one likely ends up with different hyperplane fits from converting a NN/gradient-desc-learned model to kernel machine vs learning a kernel machine directly via SVM learning.
No, not necessarily. The objective functions used to train neural networks are generally non-convex (the nets themselves being non-convex as well), but are traditionally trained using stochastic gradient descent (and its variants).
This really threw me off when I first started learning about ANNs, coming from a traditional econometrics background. B-but ... the parameters aren’t identified!
Comments
I do have a tangential technical question for someone who knows more math than I do.
A kernel SVM always finds (one-of) the global best fit lines in the kernel space.
A gradient descent model explicitly converges to one of the nearest local minimas by definition.
Does this paper conclude that the local minimas that neural networks converge to are one of the many equivalent global maxima ? Won't this be a major revelation by itself ?
I don't have a strong math background but I think during the optimisation process of finding the hyperplane, the solver (algorithm that attempts to find best separating hyperplane) uses soft margin to allow mis-classified instances. Its tolerance is controlled by a hyper-parameter so it will comprise to find the best fit within the set parameter. So it is a 'best solution' with a condition. However there are many variations of implementations from different solvers to handle it.
Example:https://towardsdatascience.com/support-vector-machine-simply...
Isn't one of the features of high-dimensional spaces that local minima are rare and there's usually some direction that slopes towards a lower loss?
I mean, obviously not in the general case. Cryptography is designed to be a high dimensional space with pretty much no slope.
I'd assume that a lot of the binary decision tree / chip level optimizations are similar: almost no slope worth analyzing.
Sure, and unbreakable crypto is notoriously difficult to make. I wouldn't expect a situation like that to come up in a real-world problem.
Binary decision trees are basically super optimizers: minimizing the number of gates needed to make a Chip's logic (multiply circuits or whatever)
Not really. It's the unbreakable AND efficient requirement combined that's hard.
Just run anything over a random xor shift add kernel about 1 million times and it's unbreakable (so long as xor / shift forms a bijection). It's just inefficient.
Finding the smallest number of iterations that works is the hard part. Usually, people try to break it (ex, AES was originally broken over 4 iterations) then double or triple your best attempt, and you are set.
AES is now broken over 5 iterations IIRC, but still a long way to go to break full 8 iteration AES.
More modern ciphers (SHA512) are like 80 iterations of a simpler kernel.
Even 'broken' ciphers like TEA or RC4 are hard to break in practice if you just increase the iteration count up the wazzoo. The problem is: AES gets to security in just 8 iterations.
So to be better than AES requires both efficiency AND security. After all, 100 iterations of AES is going to be more secure if you don't care about efficiency. (10x more iterations than the default spec)
In the context of this paper, you can think of the "gradient descent step" as optimizing the parameters of the kernel (i.e. the parameters that generate the kernel space). There are no explicitly optimality guarantees beyond those of standard gradient descent.
The "SVM step" would still find a global optima within the kernel space, but the qualifications of the previous step mean that the kernel space generated might be useless.
I don't think the output of the conversion is guaranteed to be equivalent to a hyperplane learned by an SVM.
I didn't have time to read the paper, but reading the abstract I don't see a claim that the gradient descent model approximated by a kernel machine is equivalent to an optimal fit obtained by SVM maximum margin hyperplane fitting.
I assume one likely ends up with different hyperplane fits from converting a NN/gradient-desc-learned model to kernel machine vs learning a kernel machine directly via SVM learning.
Nitpick: Minima is already plural.
Doesn’t gradient descent use a convex cost function so that it always generates a global minimum?
No, not necessarily. The objective functions used to train neural networks are generally non-convex (the nets themselves being non-convex as well), but are traditionally trained using stochastic gradient descent (and its variants).
This really threw me off when I first started learning about ANNs, coming from a traditional econometrics background. B-but ... the parameters aren’t identified!