4 ms·
The author of this post has rediscovered some fundamental ideas in optimization just by tinkering around! Neat! > The objective function for linear regression
by benrbray 7y ago
The author of this post has rediscovered some fundamental ideas in optimization just by tinkering around! Neat!
> The objective function for linear regression is quadratic (and convex). This explains why Newton's method finds the optimum in one step--the local quadratic approximation turns out to be a global approximation!
> Notice, however, that Newton's method requires us to invert the Hessian matrix (f''), which is expensive in general. I don't think autograd software can get around this limitation.
> The KeepStepping optimizer is performing "gradient descent with line search", which is a more Googleable term.
For more about optimization for solving linear systems (as is the case for linear regression), I recommend Shewchuk 1994, "Conjugate Gradient without the Agonizing Pain" [1], which has some nice geometric insight.
[1]: http://www.cs.cmu.edu/~quake-papers/painless-conjugate-gradient.pdf http://www.cs.cmu.edu/~quake-papers/painless-conjugate-gradi...
- klipt 7y agoYeah I remember being told that quasi-Newton methods can get close to the final answer in just one step in my undergraduate statistics class. But what works for traditional statistics (like matrix inversion) tends to have the wrong big-O for big data. Would be nice though if there were a website somewhere that summarized the state of the ML-applicable optimization field with links to papers in order of increasing complexity. Instead there are like a billion websites rehashing basic SGD that seem to dominate search results. Although I guess most of the easy to use methods like Adam are already baked into all the frameworks.
- benrbray 7y agoJust like you say, I've also recently found it much harder to google for survey articles too. I know they do exist somewhere, but I can't seem to find the magic words I need to enter into the search bar! We seem to be returning to a world where the only reliable way to find information is to stumble upon someone's webpage (e.g. [1]) who has curated a list of links. [1]: http://www.math.columbia.edu/~khovanov/resources/ http://www.math.columbia.edu/~khovanov/resources/
- rmrfstar 7y agoAnother amazing resource is [1]. Seriously one of the best purchases I have ever made, and I spend a lot more on books than I should. [1] https://mitpress.mit.edu/books/algorithms-optimization https://mitpress.mit.edu/books/algorithms-optimization
- sandeeps_ 7y agoAwesome! I have always been looking for a book like this. Thanks for sharing. A quick look at the book tells me that this is a handbook of different optimization techniques that can be used under different conditions. Do you know if there's a python/matlab version of the examples mentioned in the book?
- rmrfstar 7y agoThe book ships with Julia examples, but most of the algorithms are available in cvxpy [1], scipy.optimize [2] and matlab optimization toolboxes [3]. [1] https://www.cvxpy.org/ https://www.cvxpy.org/ [2] https://docs.scipy.org/doc/scipy/reference/tutorial/optimize.html https://docs.scipy.org/doc/scipy/reference/tutorial/optimize... [3] https://www.mathworks.com/products/optimization.html https://www.mathworks.com/products/optimization.html
- LudwigNagasena 7y ago>The author of this post has rediscovered some fundamental ideas in optimization just by tinkering around! Neat! I checked the guy’s LinkedIn, he has 5 years of econometrics and data science education. I am honestly perplexed how anything in this article could come off as new to someone with such background.
- currymj 7y agototally possible to learn a lot of economics and statistics and never have formal coursework in numerical methods for optimization.
- benrbray 7y agoSeems to be the case here. Regardless of the author's educational background, kudos to them for continuing to dive deeper into the math. After a math degree and three years of graduate school, I still run into blind spots almost every day, for topics that people across the hall from me would consider elementary.