29
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ It's unclear if you're objecting to the convex part, the optimization part, or both. $\endgroup$ – user541686 Jan 26 '18 at 1:01
  • $\begingroup$ 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. $\endgroup$ – xji Feb 7 '18 at 23:06
  • $\begingroup$ 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. $\endgroup$ – bruziuz Apr 26 '18 at 19:05
  • $\begingroup$ 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. $\endgroup$ – bruziuz Apr 26 '18 at 19:07
  • $\begingroup$ FYI "Convex optimization can not be used for deep learning - S.Boyd" -- youtu.be/uF3htLwUHn0?t=2810 $\endgroup$ – bruziuz Apr 26 '18 at 19:08
63
$\begingroup$

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.

Example of real-life, non-convex loss landscape.

(source: https://www.cs.umd.edu/~tomg/projects/landscapes/ and arXiv:1712.09913)

Nonetheless, as mentioned in other answers, convex optimization is faster, simpler and less computationally intensive, so it is often easier to "convexify" a problem (make it convex optimization friendly), then use non-convex optimization. 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 he 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 recent research topic (see also arXiv:1712.07897).

| cite | improve this answer | |
$\endgroup$
  • 5
    $\begingroup$ this answer seems not addressing "convex" $\endgroup$ – Haitao Du Jan 25 '18 at 19:41
  • $\begingroup$ @hxd1011 I commented on it. $\endgroup$ – Tim Jan 26 '18 at 9:14
  • $\begingroup$ Great answer! Really addresses how critical optimization is to ML, and how ML simplifies by using convex approximations that work with gradient descent. $\endgroup$ – ChuckCottrill Jan 28 '18 at 4:51
  • $\begingroup$ This should be the accepted answer. $\endgroup$ – Jan Kukacka Feb 4 '18 at 21:58
13
$\begingroup$

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".

| cite | improve this answer | |
$\endgroup$
  • 3
    $\begingroup$ 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. $\endgroup$ – prosfilaes Jan 27 '18 at 16:14
  • $\begingroup$ 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. $\endgroup$ – Digio Feb 13 '19 at 9:47
2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • 33
    $\begingroup$ 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. $\endgroup$ – Tim Jan 25 '18 at 10:24
  • $\begingroup$ @Tim: True, I should have phrased that differently. $\endgroup$ – Toby Jan 25 '18 at 10:29
  • 17
    $\begingroup$ if you agree, then you should probably rephrase it. $\endgroup$ – Tim Jan 25 '18 at 16:05
  • 19
    $\begingroup$ This answer is patently wrong. A significant number of machine learning problems boil down to optimization problems. $\endgroup$ – Skander H. Jan 26 '18 at 6:38
  • 2
    $\begingroup$ 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. $\endgroup$ – Jan Kukacka Feb 4 '18 at 21:56
2
$\begingroup$

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".

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

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!

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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)

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Silverfish Jul 18 '18 at 2:51
  • $\begingroup$ 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. $\endgroup$ – bruziuz Jul 18 '18 at 11:33
  • 1
    $\begingroup$ @Silverfish I updated, now it's long text instead of one sentence. $\endgroup$ – bruziuz Jul 18 '18 at 14:16

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.