2
$\begingroup$

I am a Math/CS dual major. As part of my math major, I have the option of taking optimization and mathematical programming classes. I am also interested in machine learning. I know that a lot of machine learning algorithms are theoretically grounded in optimization techniques. I have to decide which optimization classes to take. What optimization concepts should I make sure I cover? Some examples of topics in the classes: gradient descent, conjugate gradient descent, BFGS, KKT, simplex method, ellipsoid method, golden section, knapsack problems, SDP, SOCP, Barrier methods, Mehrotra Predictor-Corrector.

What topics do I need to know?

Could someone answer? I need to choose classes relatively soon.

$\endgroup$
  • 3
    $\begingroup$ For sure: gradient descent. Worthwhile: simplex method, KKT. The Knapsack problem belongs to combinatorial optimization. I would not immediately associate combinatorial optimization with machine learning. (EDIT: the internet disagrees with me). It is a very interesting subject. I recommend looking into it. $\endgroup$ – workingonit Apr 15 '17 at 21:13
  • 2
    $\begingroup$ Convex optimization is useful (many of the topics you mention are special cases). Also, integer optimization starts being used in statistics so maybe also in machine learning ... $\endgroup$ – kjetil b halvorsen Apr 15 '17 at 21:56
  • $\begingroup$ I wouldn't take the whole class on optimization unless that's what you're interested in. Otherwise conceptually it's just finding the minimum of some function, there's nothing particularly interesting in it for statistics and ML per se. $\endgroup$ – Aksakal Apr 16 '17 at 1:28
  • $\begingroup$ I am a CS Math Dual Major. I have to take a certain number of math classes. I might as well take one's that relate to CS $\endgroup$ – Halbort Apr 16 '17 at 3:10
  • 1
    $\begingroup$ As you are at an institution, probably the Math and/or CS dept. has an "undergrad advisor" person. An in person conversation with one or both of these is probably a better bet than asking here (also in the context of your graduation requirements & learning goals ... i.e. solving the real-world "knapsack problem" facing you!) $\endgroup$ – GeoMatt22 Apr 17 '17 at 23:05
4
+50
$\begingroup$

Conceptually, the only thing you need to know to understand machine learning algorithms is "there is an optimum, and we can find it". Practically, it's always useful to have some idea how optimization is happening "under the hood". At very least, it will give you some insight into how the the performance and storage requirements of your ML algorithms are likely to scale with data size and dimension, and under what circumstances you are likely to run into problems. Of course, optimization is a rich and interesting area of its own, which will exercise your brain and round out your CS education even if you never do machine learning.

As requested in a comment, here is a list of important topics in optimization:

$\endgroup$
  • 4
    $\begingroup$ All deep learning is nowadays done with gradient descent. Saying that it's not "practically useful" is preposterous. $\endgroup$ – amoeba Apr 19 '17 at 11:41
  • 1
    $\begingroup$ I'd like to chime in and underscore what @amoeba said. There was definitely a period where interior point methods and quasi-Newton methods were the standard, but nowadays, with the size of data, simple gradient descent and variants is back in focus. $\endgroup$ – Mustafa S Eisa Apr 22 '17 at 5:23
  • 1
    $\begingroup$ @MustafaSEisa Yes. I downvoted this answer now, because I think it's very importantly misleading statement. $\endgroup$ – amoeba Apr 22 '17 at 8:47
  • 1
    $\begingroup$ Re: gradient descent & machine learning, the more appropriate Wikipedia article would be this. (See also here.) $\endgroup$ – GeoMatt22 Apr 22 '17 at 15:01
  • 1
    $\begingroup$ Okay, I removed my downvote, but you are still calling gradient descent a "toy algorithm" in your list. Seriously, there is nothing "to disagree" about here; you are probably unfamiliar with modern deep learning. Look it up. Neural network that famously won over best human in Go last year (en.wikipedia.org/wiki/AlphaGo) was trained with [stochastic] gradient descent (web.iitd.ac.in/~sumeet/Silver16.pdf), like pretty much all other deep networks nowadays. This is just absolutely not a toy algorithm. (cc to @GeoMatt22) $\endgroup$ – amoeba Apr 22 '17 at 21:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.