Solved – What concepts in optimization do I need for machine learning

Question

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.

Answer 1

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:

• Continuous optimization
  • Toy algorithms: gradient descent, simplex method
  • Powell's method
  • BFGS
  • Model trust methods
• Stochastic optimization
  • Simulated annealing
  • Genetic algorithms and swarm methods
  • Stochastic gradient descent
• Constrained optimization
  • Barrier methods
  • Linear programming (with interior-point methods)
  • Integer programming
• Dynamic programming