5 ms·

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

by screye 6y ago

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 ?

andreareina 6y ago
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?
- dragontamer 6y ago
  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.
  - sp332 6y ago
    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.
    - dragontamer 6y ago
      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)
dumb1224 6y ago
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-explained-fee28eba5496 https://towardsdatascience.com/support-vector-machine-simply...
altarius 6y ago
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.
kaczordon 6y ago
Doesn’t gradient descent use a convex cost function so that it always generates a global minimum?
- wxnx 6y ago
  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).
  - mrtranscendence 6y ago
    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!
wxnx 6y ago
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.
edjrage 6y ago
Nitpick: Minima is already plural.

by screye 6y ago

andreareina 6y ago

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?

dragontamer 6y ago
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.
- sp332 6y ago
  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.
  - dragontamer 6y ago
    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)

dumb1224 6y ago

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-explained-fee28eba5496 https://towardsdatascience.com/support-vector-machine-simply...

altarius 6y ago

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.

kaczordon 6y ago

Doesn’t gradient descent use a convex cost function so that it always generates a global minimum?

wxnx 6y ago
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).
- mrtranscendence 6y ago
  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!

wxnx 6y ago

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.

edjrage 6y ago

Nitpick: Minima is already plural.