# Why study convex optimization for theoretical machine learning?

I am working on theoretical machine learning — on transfer learning, to be specific — for my Ph.D.

• Out of curiosity, why should I take a course on convex optimization?

• What take-aways from convex optimization can I use in my research on theoretical machine learning?

• It's unclear if you're objecting to the convex part, the optimization part, or both. Jan 26, 2018 at 1:01
• Note that the answer you accepted is plainly wrong. Maybe you can take a look at this question again and choose an answer that makes much more sense.
– xji
Feb 7, 2018 at 23:06
• Convex Optimization and Math Optimization is a tool to build models - this technics are used to construct models/do control/find parameters of understandable phenomen up to some uncertanty. Apr 26, 2018 at 19:05
• Machine Learning is about building function approximation like couning methods, and as far as you known one of concept select function which approximately minimize loss (which is non-convex or even worst include indicator variables), so ML play nice with non-convex optimization. Apr 26, 2018 at 19:07
• FYI "Convex optimization can not be used for deep learning - S.Boyd" -- youtu.be/uF3htLwUHn0?t=2810 Apr 26, 2018 at 19:08

Machine learning algorithms use optimization all the time. We minimize loss, or error, or maximize some kind of score functions. Gradient descent is the "hello world" optimization algorithm covered on probably any machine learning course. It is obvious in the case of regression, or classification models, but even with tasks such as clustering we are looking for a solution that optimally fits our data (e.g. k-means minimizes the within-cluster sum of squares). So if you want to understand how the machine learning algorithms do work, learning more about optimization helps. Moreover, if you need to do things like hyperparameter tuning, then you are also directly using optimization.

One could argue that convex optimization shouldn't be that interesting for machine learning since instead of dealing with convex functions, we often encounter loss surfaces like the one below, that are far from convex.

Nonetheless, as mentioned in other answers, convex optimization is faster, simpler, and less computationally intensive. For example, gradient descent and alike algorithms are commonly used in machine learning, especially for neural networks, because they "work", scale, and are widely implemented in different software, nonetheless, they are not the best that we can get and have their pitfalls, as discussed by Ali Rahimi's talk at NIPS 2017.

On another hand, non-convex optimization algorithms such as evolutionary algorithms seem to be gaining more and more recognition in the ML community, e.g. training neural networks by neuroevolution seems to be a recent research topic (see also arXiv:1712.07897).

• this answer seems not addressing "convex" Jan 25, 2018 at 19:41
• @hxd1011 I commented on it.
– Tim
Jan 26, 2018 at 9:14
• Great answer! Really addresses how critical optimization is to ML, and how ML simplifies by using convex approximations that work with gradient descent. Jan 28, 2018 at 4:51
• This should be the accepted answer. Feb 4, 2018 at 21:58
• What source would you recommend please @Tim for first course on convex optimization if any?
– Avv
Oct 8, 2021 at 1:20

I think there are two questions here.

• Why study optimization
• Why convex optimization

I think @Tim has a good answer on why optimization. I strongly agree and would recommend anyone interested in machine learning to master continuous optimization. Because the optimization process / finding the better solution over time, is the learning process for a computer.

I want to talk more about why we are interested in convex functions. The reason is simple: convex optimizations are "easier to solve", and we have a lot of reliably algorithm to solve.

But is the world convex? No. Why obsessed with convexity? Check this metaphor

A policeman sees a drunk man searching for something under a streetlight and asks what the drunk has lost. He says he lost his keys and they both look under the streetlight together. After a few minutes the policeman asks if he is sure he lost them here, and the drunk replies, no, and that he lost them in the park. The policeman asks why he is searching here, and the drunk replies, "this is where the light is".

• But metaphorically, that's why you get a flashlight. Searching for the keys in the dark is hard to impossible, so you adapt the problem into one you know how to solve. If you work on a problem with non-convex algorithms and come up with a solution that will cost 3 million dollars, and I work a similar problem with convex optimization and take my answer and find a solution to the non-convex problem that costs 2 million dollars, I've found a better answer. Jan 27, 2018 at 16:14
• This answer is flawed on so many levels. Comparing convex analysis to the streetlight effect is just wrong. I would advise you to refer to the introductory textbook Convex Optimization by Boyd and Vandenberghe in order to learn more on the topic. Feb 13, 2019 at 9:47

As hxd1011 said, convex problems are easier to solve, both theoretically and (typically) in practice. So, even for non-convex problems, many optimization algorithms start with "step 1. reduce the problem to a convex one" (possibly inside a while loop).

A similar thing happens with nonlinear rootfinding. Usually the solution (e.g., with Newton's method) goes "step 1. Reduce to a linear problem, because we know how to solve those".

The most important takeaway is that machine learning is applied to problems where there is no optimal solution available. The best you can do is find a good approximation.

In contrast, when you have an optimisation problem, there is an optimal solution, but it usually cannot be found in reasonable time or with reasonable processing power.

The tools and algorithms you use are fundamentally different. So while I would say that there is no immediate benefit of taking an optimisation class, it is always good to know a bit about related fields. If you can recognise an optimisation problem you'll know that you should not tackle it with machine learning algorithms but with optimisation algorithms instead. That alone is worth a lot I'd say.

• Yes, in machine learning we are looking for the best approximations. But you are wrong by saying that both things are "fundamentally different". ML algorithms use optimization to minimize loss functions and find the optimal parameters given the data and objective. When you are tuning your hyperparameters, you are looking for optimal combination of them. In each of the cases you are maximizing or minimizing something to achieve your goal, so you are using some kind of optimization.
– Tim
Jan 25, 2018 at 10:24
• @Tim: True, I should have phrased that differently.
– Toby
Jan 25, 2018 at 10:29
• if you agree, then you should probably rephrase it.
– Tim
Jan 25, 2018 at 16:05
• This answer is patently wrong. A significant number of machine learning problems boil down to optimization problems. Jan 26, 2018 at 6:38
• The claim that in "optimization problems the optimal solution usually cannot be found" is incorrect. Especially in the context of convex optimization (which is what OP is asking about), the optimal solution can be easily found (for example gradient descent with decaying learning rate is guaranteed to converge to the optimum of a convex function). The big problem is that many problems in the machine learning are non-convex. Feb 4, 2018 at 21:56

If your interests lie in (convex) optimisation applied to deep learning (you mention transfer learning, which is widely used in practice with neural networks) applications, I strongly encourage you to consider reading chapter 8 (optimization for training deep neural networks) of http://www.deeplearningbook.org/

There is a discussion of convex optimisation, and why it has not yet been so successful when applied deep neural networks. Of course, perhaps you could do research in this area that will change the current consensus!

As I heard from Jerome H. Friedman methods developed in Machine Learning is in fact not belong to Machine Learning community by itself.

From my point of view Machine Learning is more like a collection of various methods from another fields.

From point of view of Statistical Learning the three main questions for regression and classification are:

1. What is function family from which you pull approximator

2. What is a criteria how you pull a function

3. What is a method to find the best function

To operate in some constructive way on (1) - it's not so obvious how use math optimizaion can help

To operate in some constructive way on (2) - it's obvious that objective is the goal. And math optimizaion can help on it.

To operate in some constructive way on (3) - you need math optimization.

There several parts of math optimization:

1. Convex Optimization/Convex Analysis - very cool area of math. Non-differentiablity is not a problem. And there are 50 generalization of convex functions from which more two usefull in terms of application is quasiconvex and log-concave.

Also there are ways how to deal "stochasticity" in some way, even "Nobody know how to solve stochastic convex optimization"

1. NonConvex Optimization - usually people by this mean something which is continious objective, but curvature can vary. People in this planet don't know how to solve it precisely. And in fact all mehtods make leverage into (1)

2. Combinatorial optimizaion - it's even more wild then (2), now for parameters that you find you even can not apply minus operator. One example is "regions" in Decision Trees. So there are two way how to deal with it: a) Convexify problem and use methods from (1) b) Make brute force. Doesn't work for huge number of parameters. c) Make brute force but with some greedy steps. It's something that CART do.

So at least I think I convice you that:

I) Convex Optimization is central thing for most optimization problems.

II) "01:15 Optimization is in fact more bigger subject then ML or AI, but it's bigger subject in fact." (https://www.youtube.com/watch?v=uF3htLwUHn0&t=992s)

• This is a little brief by the standards of this site as an answer - do you think you could expand on it? Otherwise it might best be suited as a comment. Jul 18, 2018 at 2:51
• Ok. I will expand, but in fact it's possible to write an article about connection with various fields. In fact I asked Stephen P. Boyd about question relative to did people think about previously and when -- youtu.be/XV1E-Jnc4SU?t=242. He said that this days world have been fractured. Jul 18, 2018 at 11:33
• @Silverfish I updated, now it's long text instead of one sentence. Jul 18, 2018 at 14:16