3
$\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.

Improve this question
$\endgroup$
8
  • 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, 2017 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, 2017 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, 2017 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, 2017 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, 2017 at 23:05

1 Answer 1

Reset to default
6
+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:

Improve this answer
$\endgroup$
8
  • 5
    $\begingroup$ All deep learning is nowadays done with gradient descent. Saying that it's not "practically useful" is preposterous. $\endgroup$
    – amoeba
    Apr 19, 2017 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 Eisa
    Apr 22, 2017 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, 2017 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, 2017 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, 2017 at 21:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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