10 ms·
A Global Optimization Algorithm Worth Using
- splike 9y agoAm I wrong in thinking that this algorithm could only be applied to continuous variables/hyperparameters?
- alexbeloi 9y agoAnyone considering using this for continuous hyper-parameter optimization in machine learning should be warned that the automatic Lipschitz constant optimization (the novelty of the method) will very likely not work well with a noisy objective function (any stochastic learning algorithm). edit: Any grad students looking for a paper idea might consider extending this result to allow stochastic objective functions satisfying a stochastic Lipschitz condition.
- eesmith 9y agoQuoting from the linked-to page: > However, if you want to use LIPO in practice there are some issues that need to be addressed. The rest of this blog post discusses these issues and how the dlib implementation addresses them. First, if f(x) is noisy or discontinuous even a little it's not going to work reliably since k will be infinity. > ... Now each sample from f(x) has its own noise term, σi, which should be 0 most of the time unless xi is really close to a discontinuity or there is some stochasticity. Is that not what you were pointing out?
- WeaselNo7 9y agoI don't speak fluent maths, but i'm extremely interested. Is anyone in a position to explain what the initial equation for U(x) means? I'll be in your debt forever!
- bumbledraven 9y agoThe doc uses x to refer to the new point, and x_i for the ith previously evaluated point. To reduce ambiguity, i'll use a capital X to refer to the new point. The equation says that U(X) is equal to the minimum value of the expression f(x_i) + k * (Euclidean distance from x to x_i), where i ranges over integers 1 to t. In Go pseudo-code: func U(X []float64, x [][]float64, f func([]float64) float64, k float64) float64 { min := math.Inf(1) for _, x_i := range x { e := f(x_i) + k * EuclideanDistance(X, x_i) if e < min { min := e } } return min }
- math_and_stuff 9y agoConsider the case where f is an elementary function of one variable and you know that its slope between any two points is at most k and at least -k. And suppose you want an upper bound on f(0) but you know the values of f(-2) and f(3). Then f(0) <= f(-2) + 2 * k and f(0) <= f(3) + 3 * k. Taking the minimum of these two right-hand sides leads to a formula analogous to the one for U(x) that you're asking about (with the norm || x - x_i || taking the place of |0 - (-2)| and |0 - 3| in our example).
- WeaselNo7 9y agoVery kind, thank you for the explanation!
- enriquto 9y agoif you can program, you can read maths (understanding its purpose is a different issue) this formula defines a function U(x). This means that it gives a recipe that takes a number x and produces a number U(x). The recipe depends on an already prepared set of ingredients: a set of numbers x1, x2, ..., xt, k, and another function f. Now, given a number x, to compute U(x), you first compute all the numbers f(xi)-k*|x-xi|, and then you pick the smallest one. This smallest value is then U(x). The graph below the formula displays its interpretation. The graph of the function f is the red curve, the points (xi, f(xi)) are the black dots, and U(x) is in green.
- petters 9y agoOf course, global optimization using the Lipschitz constant has been around for decades. As far as I understand, this paper also estimates the constant. Is that the novelty or is it the convergence proofs? Another method for global optimization is interval arithmetic, but it is not a black-box method.
- kxyvr 9y agoI'm also curious what this adds that's new. I'll add one other bit: If anyone ever claims they have an efficient global optimization algorithm for continuous optimization, ask whether or not P=NP. We can encode the integer constraint that x \in {0,1} as x(x-1)=0, so if we can find the global optimum to a continuous problem efficiently, then we can do the same for a discrete. That's probably unlikely, so I'm always a bit skeptical. By the way, the parent mentioned interval arithmetic. If anyone is looking for optimization algorithm look for "interval Newton". It's a cool algorithm.
- yorwba 9y agoNot all continuous optimization algorithms can handle arbitrary equality constraints, especially if they effectively make the optimization domain discrete. You might be able to do an encoding of NP-complete problems that is purely continuous, but if I read the LIPO paper correctly, there is a known exponential lower bound for their problem, so that would just make the NP-complete problem harder. Instead, the algorithm promises to actually match that lower bound, while always being at least as good as random search, and offering exponentially large improvements in certain cases. Not exactly the kind of claim that has implications for P =? NP.
- deleted 9y ago[deleted]
- tobmlt 9y agoInterval Newton is probably my favorite algorithm. Intervals in concert with the fixed point theorems - amazing stuff. (and all the rest! - contractors, inclusion/exclusion tests exploiting derivative info, etc.) Good tools for optimization, indeed.
- beagle3 9y agoI do not have anything to contribute regarding this specific optimization algorithm, but I want to recommend the dlib [0] library it comes from, which is a very high quality library that has machine learning algorithms, numerical analysis algorithms, image processing, network, threading, gui, and a few other things. The (sole, afaik) library author and maintainer Davis King is also extremely responsive and helpful. dlib and Davis deserve a lot more recognition. [0] http://dlib.net http://dlib.net
- cjalmeida 9y agoDlib saved me a few times and I have a lot to thank David. However I just wish it's Python binding were published as binary wheels. Dlib is very large and the compilation times suck when installing from pip. In fact, I might as well contact him and help setup this!
- deleted 9y ago[deleted]
- mjn 9y agoThe strategy that the dlib implementation uses of combining a global optimization method (LIPO) with one that works better locally (TR) reminds me of another recent paper I ran across, which takes a black-box global optimization algorithm (StoSOO) and improves local convergence behavior using CMA-ES [1]. A main difference seems to be that StoSOO focuses on robustness to noisy functions more than LIPO does. [1] https://link.springer.com/article/10.1007/s10898-016-0482-9 https://link.springer.com/article/10.1007/s10898-016-0482-9 / http://ssamot.me/papers/global-optimisation.pdf http://ssamot.me/papers/global-optimisation.pdf
- amelius 9y agoWhat is the worst-case time complexity in terms of N local minima, and D variables?
- robotresearcher 9y agoNot defined. It's continuous optimization.
- zawerf 9y agoCan someone explain the intuition behind how the lipschitz constant k is chosen? It seems like even in his demo video, k starts off underestimated which made the upperbound not a upperbound (f is sometimes above the green line U) and is only slowly corrected towards the end. Why does it still work?
- kevinwang 9y agoIs the algorithm used here the Shubert-Piyavskii Method?
- wenc 9y agoThere's a whole class of deterministic Global Optimization solvers on COIN-OR [0] that don't seem to get noticed outside the Operations Research/Applied math community. (many are free and open source, e.g. Couenne) These solvers (BARON [1], ANTIGONE [2], Couenne [3] etc.) are capable of solving nonconvex global optimization problems that are structurally more complicated (i.e. non-ML applications) than the ones presented in the article linked above. They employ a bunch of mathematically-rigorous methods such as interval analysis, branch-and-cut and McCormick relaxations. There's a treasure trove of little ideas from decades of global optimization research that I feel the Deep Learning community could benefit from taking a peek at. [0] https://neos-server.org/neos/solvers/index.html https://neos-server.org/neos/solvers/index.html [1] http://archimedes.cheme.cmu.edu/?q=baron http://archimedes.cheme.cmu.edu/?q=baron [2] http://helios.princeton.edu/ANTIGONE/index.html http://helios.princeton.edu/ANTIGONE/index.html [3] https://www.coin-or.org/Couenne/ https://www.coin-or.org/Couenne/
- blt 9y agoThanks for sharing this!
- perturbation 9y agoSpeaking of optimization libraries, I've been checking out https://developers.google.com/optimization/ https://developers.google.com/optimization/ for scheduling and assignment problems. The documentation is not... wonderful, but it has a lot of examples and a decent Python API. I recently did an "Intro to OR" class and most of the tools we used were proprietary. I've been looking for more open source tools (and more info on OR in general, I think it's fascinating!). Edit: NLOpt (https://nlopt.readthedocs.io/en/latest/ https://nlopt.readthedocs.io/en/latest/) is also a nice suite of optimization algorithms for non-linear optimization.
- wenc 9y agoI highly recommend taking a look at the COIN-OR (Computational Infrastructure for Operations Research) project page. All the code is open-source. There are some amazing solvers in that list. https://www.coin-or.org/projects/ https://www.coin-or.org/projects/ The only issue is that much of the code on that site is very cutting-edge and academic. You may need to read a few benchmarks/publications to figure which solvers are production quality and which are not. That said, a handful of these free solvers are so well-written that they exceed the performance of many commercial solvers for certain types of optimization problems. (A notable exception is MIPs. Commercial MIP solvers like Gurobi or CPLEX are orders of magnitude better than the open-source CBC or GLPK. CBC is still pretty ok though, and I bundle it when I need to include a free solver in my code to solve smaller problems.)
- AllegedAlec 9y agoWould it be possible to make the hyperparameters optimizable? Maybe it's the biologist in me, but I can't really see a reason why you couldn't just let the algorithm decide for itself which values of those parameters would work best.
- archgoon 9y agoI don't understand; the entire article is entirely about methods of doing that.
- AllegedAlec 9y agoMaybe I wasn't clear, or misunderstood some of the article, but I thought the article was about optimising the hyperparameters before the machine learning part happens. I meant optimising the parameters during the machine learning iterations.
- pklehre 9y agoThis reminds me of self-adaptive evolutionary algorithms.
- aldanor 9y agoVery cool! I'd like to share another global optimization algorithm 'worth using' that I've recently discovered for myself: Hyperband [0]. It's extremely simple to implement (i.e. a dozen lines of code), is based on successive halving principle and is particularly suitable for iterative machine learning algorithms where early stopping is applicable (i.e. NN, GBM). [0] https://people.eecs.berkeley.edu/~kjamieson/hyperband.html https://people.eecs.berkeley.edu/~kjamieson/hyperband.html