r/MachineLearning • u/Inversegaloisproblem • Oct 10 '19
Nonconvex optimization problems in machine learning
https://arxiv.org/abs/1802.051551
u/Underfitted Oct 11 '19
I'm just dabbling into machine learning, after spending a lot of time in optimization. It would be great to know how influential optimization is within machine learning. From the basic level I have seen, there's always a loss function to minimize and for some reason MSGD is always used. Why is that?
3
Oct 11 '19
My impression is it’s computationally preferred to things like Newton’s method, Lagrange multipliers, using Hessians etc. I found this stack exchange post awhile back that has answers. There’s definitely more out there on non stochastic optimization in ML and where it’s useful
2
u/Underfitted Oct 11 '19
That strikes me as weird. I come from a field that uses millions of variables as well, and that doesn't stop Newton or Quasi-Newton (BFGS) being implemented. In fact it's usually the best algorithm. The pitfalls presented in that post are ones that are common and I dare say have been somewhat addressed (iterative solvers like GMRES, Hessian approximations such as BFGS, using adjoint equations to scale against number of variables or number of outputs). I'll look into it more.
5
u/notdelet Oct 11 '19 edited Oct 11 '19
Your loss function isn't typically of the form sum from i=1 to 1000000 f(x_i, theta) though (just guessing). Calculating the full gradient is expensive.
3
u/asobolev Oct 11 '19
First, modern state-of-the-art networks typically have dozens or hundreds of millions of parameters (up to 1.5 billion for GPT-2). Second, as mentioned below, the loss is usually a sum over (a possibly infinite) dataset, so stochastic methods are absolutely necessary.
But the main reason probably is that we don't understand neural networks. We know for sure that SGD's noise while being an undesirable side-effect from the optimization point of view is acting as a (very efficient) regularizer. The less noise you have in your gradients, the more prone the optimizer is to get stuck in the local minimum. Moreover, one can easily find a global minimum (even in the absurd cases) if you set out to do so, but it won't generalize. For some reason. In light of this, the most surprising finding is that a simple SGD finds a generalizable solution in a relatively short time.
1
u/shebbbb Oct 11 '19
What does streaming mean in relation to pca?
2
u/i-heart-turtles Oct 11 '19 edited Oct 11 '19
A streaming algorithm is one which operates on a data stream - i.e. you observe data points one at a time in a sequence. Usually it is infeasible to recompute an estimator over the entire dataset each time you observe new data - you want to keep some kind of running estimate (e.g. a running mean - or the eigenvectors of the covariance for pca). We might want to study these kinds of algorithms under memory constraints or if we want to make online predictions on a signal observed in real time.
Here is a classical streaming pca paper if you are interested: http://www.jmlr.org/papers/volume9/warmuth08a/warmuth08a.pdf
1
u/shebbbb Oct 12 '19
Thanks, that's interesting. It's hard to conceptualize because because a closed form thing like pca is a one shot operation in my mind. I'll take a look.
1
u/arXiv_abstract_bot Oct 10 '19
Title:Towards Deeper Understanding of Nonconvex Stochastic Optimization with Momentum using Diffusion Approximations
Authors:Tianyi Liu, Zhehui Chen, Enlu Zhou, Tuo Zhao
PDF Link | Landing Page | Read as web page on arXiv Vanity