mccourt

This is a cool post, and I really appreciate the link/references to other content. At one point I played around with parametrizing procedural generation of mazes to produce a desired length/complexity balance (https://sigopt.com/blog/building-better-multicriteria-bayesi...). Would love to try that out on a more complicated situation like the one you're working on. Thanks for the content.

You can really do training in just hours? I didn't realize how efficient current systems are for this.

This blog post lists a bunch of gradient-free optimization packages, some genetic and some Bayesian: https://sigopt.com/blog/comparison-bayesian-packages-hyperpa.... Nothing from the mathematical programming community in here, so definitely other options too (depending on what kind of problems you are trying to address).

Personally, I like Nevergrad (https://facebookresearch.github.io/nevergrad/) a lot for general purpose optimization problems -- I think it is very well implemented and has a variety of tools available. I also think the documentation is appropriately honest about what is and is not known for how these algorithms work in different circumstances.

If you want something Bayesian (sample-efficient) which is very lightweight, I like PySOT (https://pysot.readthedocs.io/en/latest/). Part of why I like it is that it's written by friends of mine, but I also legitimately like its performance across a decent set of problems.

If you want something Bayesian which has corporate support (so that you know it's updated/maintained), I would recommend Botorch/Ax from Facebook (https://botorch.org/docs/botorch_and_ax). They have done a lot of research for it (a recent preprint is here https://arxiv.org/pdf/2006.05078.pdf) and have put together a very solid implementation including considerations for running online optimization problems. I think the documentation is a bit weak, but the software and research is outstanding.

Another corporate-supported option is Optuna (https://optuna.org/) from Preferred Networks. I also know some of the people working on this and I think it is a good implementation of the kernel density estimation strategy for statistical modeling -- preferring lower computational cost and consistent timing over performance. I had difficulties running it in server mode while I was testing, but if you're running locally that will not be a problem.

As is always the case with optimization strategies, there is no one answer. Different tools perform well in different circumstances. There can be bad tools, but, likely, there will never be a best tool (in my estimation).

Great example of the fact that different circumstances require different approaches, and the fact that brute force is increasingly impractical for combinatorially complex problems. Thanks for this reference.

A very reasonable point and, certainly, the direction that parts of the computational community have embraced over the years. I will use integration as an example: classic computational methods were focused on trying to make strong assumptions about the integrand and significantly reduce the number of integrand evaluations (Gauss quadrature is the main thing that comes to mind). As computation became more accessible/parallelizable, and problems became less analytic, Monte Carlo methods have become more fundamental.

In some distributed computational settings, memory traffic is actually the main bottleneck and redundant computations are executed to reduce the need to send data (a similar situation to the one you aptly describe).

I think that, in the case of hyperparameter/meta-learning optimization (or search, depending on how you think about it) we are at a time right now where the complexity of models which can effectively be put into production is a function of our ability to, at least partially, analyze the space of possible modeling decisions. Will we escape that, and have models whose training cost is less significant than the cost of executing an "intelligent" hyperparameter search process? Maybe ... I am a GP person so I see potential in clever analysis of circumstances so that RKHS methods (for instance) can be leveraged and simplify the training process. But the current trajectory of the community has been to work on increasingly expensive models, which makes the ability to effectively use them with limited tuning/search cost still relevant.

I always appreciate articles emphasizing the importance of hyperparameter optimization; thank you for writing this. The discussion on learning rate is nice additional point to mention, though I find it a bit misleading -- earlier in the discussion you are mentioning a number of hyperparameters but then learning rate is studied in a vacuum. If other hyperparameters were varied along with the learning rate, I assume those graphics would look much more complicated.

Additionally, practical circumstances for hyperparameter tuning using Bayesian optimization often include complications: dealing with discrete hyperparameters, large parameter spaces being unreasonably costly or poorly modeled, accounting for uncertainty in your metric, balancing competing metrics, black-box constraints. Obviously, one cannot mention everything in a blog post, I just wanted to bring up that outstanding researchers in Bayesian optimization are pushing forward on all of these topics.

Regardless, thank you for continuing to hammer home the value of hyperparameter optimization. If I may, a couple links, for anyone trying to learn more:

My favorite BO intro - https://arxiv.org/abs/1807.02811 AutoML from the Freiburg crew - http://papers.nips.cc/paper/5872-efficient-and-robust-automa... Some discussion on parallelism/high dimensions - https://bayesopt.github.io/papers/2017/3.pdf Strategies for warm starting - https://ml.informatik.uni-freiburg.de/papers/18-AUTOML-RGPE....

This is a good article, but I wish it went a bit further into the complexities facing Hong Kong as it seeks its place in a 21st century where access to Chinese investments is no longer throttled by access to Hong Kong. I first lived in Hong Kong as a student in 2006 and I remember thinking that the tech push starting in Shenzhen would be dwarfed by tech growth in HK given its already prominent status in the international community and density of top notch universities.

When I visited in January, though, it felt like the opposite has happened; Tencent has grown into an international behemoth and HK has failed to really choose to invest in tech growth. I have friends at SUSTC, so I'm glad that Shenzhen is making big things happen, but it is disappointing to see HK still focused on running/growing the economy according to a 1980s playbook. Even the cyberport really ended up feeling more like just a ploy to be able to build more housing rather than an actual tech community.

Still time to make big things happen in HK, but, in my opinion, it's going to take leaders in the business community to push for it and make investments. It will also take strong collaboration with the outstanding academic community in HK to make that happen.

I'd love to hear from people currently in HK about how then view the tech sector and what their plans are.

Bayesian optimization, I am familiar with, but Q-learning, not so much. If anyone has good references on or introductions to Q-learning I would appreciate it.

Yeah, I think that's probably the split - folks from computer science/discrete math on one side and folks from engineering on the other. I grew up in math, but I was on the numerical analysis side so I definitely ended up on the MINLP side, which is why that's what I generally reference. There is certainly something elegant about ILP problems which gets lost when treating them with the sledgehammer that is gradient-based convex optimization.

Do you have a reference for fitting matrix-valued time series with nonlinear criteria? I'm familiar with the standard Box-Jenkins methods but I usually see that done with linear least-squares methods. I'd love to up my game on that front.

I'd also like to throw in some work by a former colleague of mine at Argonne, Sven Leyffer on nonlinear programming: - A compendium he co-edited named (appropriately enough) Mixed Integer Nonlinear Programming - A review paper he co-authored for Acta Numerica: http://www.mcs.anl.gov/papers/P3060-1112.pdf

Also, yeah, the "Alexander Schrijver - Theory of Linear and Integer Programming" reference is solid.

And I can absolutely agree that, as more criteria arise, the mechanism for linear scalarization probably becomes more fragile (subject to inconsistent behavior from the coefficients). As a result, something less sensitive but more robust, such as the tiered ordering, is probably preferable. But yeah, we just have not seen the demand yet. What actually seems to be most common is that people who have ~10 metrics spend some time thinking about it, and then realize that they mostly only cared about 1-2 so long as the rest did not cause problems/failures. That was part of the reason I wrote about the epsilon-constraint idea.

We do this in one sense within our company, but it's actually not within the context of a numerical multicriteria optimization problem. We are always trying to optimize around our customer's needs, which is in some ways a multicriteria problem involving balancing: 1) the "best" parameterization of a model subject to some (usually cross-validation) metric, 2) the "cost" (number of samples) required to optimize the model quality, 3) the "robustness" of (degree to which small parameter changes impact) the resulting solution, 4) the "parallel speed" (number of simultaneous suggestions) of the optimization process.

We consult with enterprise customers to understand their needs and expectations regarding these criteria to produce a sort of hierarchical ordering (as you've suggested) which helps inform our optimization procedure (maybe a customer doesn't care as much about speed but definitely cares about robustness). Obviously, it's a relatively restricted problem, and we're not considering it in a rigorous mathematical framework (just how best to serve our customers). Because these factors have no real numerical relationship, the only mechanism we can use to balance the concerns is a relative ordering, which is then manage internally. We spoke about this design at the ICML AutoML workshop this year (A Strategy for Ranking ... at https://sites.google.com/site/automl2016/accepted-papers)

Good call - if the problem is well behaved then small changes in gamma should be able to use the previous solution as an initial guess. And I absolutely agree with the robustness idea you're talking about; I was hinting at it when I was talking about the impact of choice of currency. For a well scaled problem there is a consistent and well-behaved impact on the solution for small changes in gamma. But when the currency was changed to RMB, small changes in gamma no longer had a consistent impact on the optimum.

That's very helpful. Thanks a lot!

That strategy can be viable; it's discussed in the Wikipedia article: https://en.wikipedia.org/wiki/Multi-objective_optimization#N...

As is suggested there, though, implementing this no-preference strategy requires some clean rescaling of the component functions in order to yield equal significance for all of them. If you have such a rescaling, that's outstanding; however, as I suggested in the section of the article dealing with the impact of the choice of currency, rescaling a problem may be a difficult proposition. This is especially true for problems that aren't as simple as the toy problem I've proposed here.

Good call. That's a simpler example than where I was going.

You make a perfectly accurate point that, in practice, it is unlikely one would be able to make such a prediction without significant info about the model. The above comment was meant in more of a post hoc "we've executed our multicriteria optimization, approximated our Pareto frontier, now let's make a decision" sense, not within a specific scalarization context. Indeed sensitivity analysis on the gamma parameter is very important; I tried to hint at that by showing that the interplay of the choice of currency and the gamma on the optimal value is nontrivial (though predictable since this is just a toy problem).

Do you happen to have any references talking about such sensitivity analysis on scalarization parameters? I would love to add them to my reading list. Thanks.

Our customers who are working with multicriteria problems have, thus far, had primarily two criteria, thus we have been helping them manage their two criteria problems into a scalar setting. As such, we do not, at this moment, permit the layers of ordering strategy you suggest through our API. To do so internally would introduce a complicated bifurcation between problems phrased with real-valued observations (as is our standard workflow), and the less informative comparative structure you're suggesting, whereby we would only be able to make statements about the relative order of points and not the magnitude by which they differ. If we were willing to impose a magnitude, doing so would revert the problem back into the weighted combination scalarization setting (or at least some norm-scalarization setting, if not the linear setting discussed in the post). I do not foresee us implementing such a tiered preemptive ordering any time soon.

You are absolutely correct that some sort of lexicographic ordering could exist: https://en.wikipedia.org/wiki/Lexicographical_order#Finite_s...

If such an ordering did exist, then we could certainly apply that ordering to sort results from the vector objective function so as to find the "answer" to the multicriteria problem. The Wikipedia article on multiobjective optimization discusses this strategy: https://en.wikipedia.org/wiki/Multi-objective_optimization#A.... On that note, lemme throw a shout out to the wonderful person who took the time to write that Wikipedia article - it is outstanding.

Given that, such an ordering may not be appropriate in all circumstances. Sorting objective vectors from the function suggested in this post would first sort by "time to destination" and then break ties in "time to destination" with "cost of trip". That would mean that (1, 1000) < (1.0000001, 2), but I think most people would be willing to arrive 0.0000001 hours later to save 998 dollars. The flexibility in interpreting the vector objective and making tradeoffs is why the standard lexicographic ordering is not always appropriate.

Does that help?

First off, I am very hesitant to say anything about biconvex problems - I only see them in passing and they are definitely not in my wheelhouse. If anyone out there is an expert, or even just has a solid (basic) reference on biconvex problems, please feel free to drop some knowledge on me.

For this particular problem, which has only one input variable, yes the answer can be resolved with a good-old fashioned Plug-In-The-Answer strategy. For problems with more than one input variable, that will almost certainly not be the case.

Really, all I was trying to say there at the end is that converting the multicriteria problem to a constraint based problem has potential benefits over scalarization. Speaking only for myself, I always default to treating multicriteria problems in some sort of norm-scalarized sense: minimize ||g|| for some vector norm. I thought it was valuable to remind myself, and maybe others, that there are other ways to naturally rephrase multicriteria problems as scalar optimization problems. I'm definitely not saying anything about how easy it is to solve, as in general these constrained problems are going to be harder than the non-constrained linear (or norm) scalarization.

I wrote this post and am also happy to comment. Hopefully we'll be following this up soon with a post on treating robustness and cost simultaneously in a multicriteria setting. Also, special thanks again to Devon Sigler at the University of Colorado Denver for his help editing this post.

There's a couple different points there, so lemme see if I can answer each of them.

First off, the use of the term "kernel trick" appears, I think, primarily within the machine learning community. It refers to the idea that some other (likely more useful) representation of the data of interest exists, but that the representation might be in a much larger, or even infinite-dimensional, space. Fortunately, in the context of certain algorithms such as support vector machines, that representation never appears by itself ... it only appears when inner-producted (not a word) with another such representation associated with some other piece of data. For certain representations, that inner product can be represented by a reproducing (also called positive definite) kernel, and thus can be computed without ever forming the larger representation. This concept appears in Wikipedia https://en.wikipedia.org/wiki/Reproducing_kernel_Hilbert_spa..., both for the Hilbert space inner product and for the Mercer's series representation. Unfortunately, as is the case with a lot of higher math on Wikipedia, it's more useful as a reference for an expert than to get you rolling on a new topic.

As far as kernel methods in general, those pop up all over the place, including in the context of Gaussian processes. Gaussian process regression (GPR), also called kernel-based approximation in the numerical analysis community, is one great example of that. I generally try to think of it not as an infinite dimensional linear regression method, but rather as a constrained optimization problem. There are infinitely many functions that pass through a given set of data, thus asking for the "one" is ill-posed ... I am interested in the most well-behaved one. We define the behavior of a function as its RKHS-norm, and the function that minimizes that norm, but still respects the observed data, is the solution to the GPR problem.

Regarding why SigOpt performs better than a good old-fashioned grid, that can be for multiple reasons. Probably the most important one, at least in my mind, is that SigOpt is not trying to create some perfect model of the function at hand - SigOpt is only interested in optimizing that function. That drives every decision we make, and actually it is something I often need to remind myself of because I grew up in approximation theory. A basic design of experiments is interested in understanding how the function works everywhere, but we can save some expense by more swiftly discarding regions unlikely to contain the optimum.

As far as why RKHS in particular work very well - that deals with the optimality theorems underlying approximation using reproducing kernels. Assuming you have a reasonable function on a reasonable domain it probably belongs to a RKHS - such functions can be represented very effectively by an appropriate kernel. Now, determining that kernel can be a complicated task (maximum likelihood estimation or cross-validation are common tools) but if you have an acceptable kernel you can make strong statements about the quality of the model. Because the quality of the model is constantly improving, the GP-backed optimization tool is constantly providing a better representation of the true function, and thus pointing towards the optimum more quickly.

There's another more fundamental reason why searching on a grid in higher dimensions is trouble, and it deals with the fact that the ratio of the volume of a sphere and of a cube with the same radius decreases as the dimension increases. This means that there is increasingly much volume away from the center of a box in increasingly many dimensions. Using a grid to try and fill that space becomes unacceptably costly. Of course, Gaussian processes have their own issues for larger problems (>30 dimensions, maybe) but SigOpt has more than just Gaussian processes behind the scenes. Also, there have been improvements over the years in GP performance in higher dimensions (for example, http://epubs.siam.org/doi/abs/10.1137/10080138X).

There's some pretty solid notes for graduate students on this topic at http://math.iit.edu/~fass/590/. That was the class I took to first learn this stuff as a student and I've tried to contribute back to them over the years. It comes at the topic first from the math side, not the stats side, but there's some stats stuff in there as well. Chapter 8 of those slides contains that theorem regarding the minimum-norm interpolant.

Hope that helps.

Dear apathy (love the name), I wrote that post and am really glad that you liked it. I had another more recent one that focused on a different topic but had a solid paragraph right at the beginning that also stepped through some of the history. It might be useful because it had a bunch of links trying to join content between GP stuff, kriging and RKHS. It is linked below. Have a great day.

http://blog.sigopt.com/post/147952139093/sigopt-fundamentals...

I have been waiting for someone to do this analysis; I had been thinking for a while that there was something more "boring" about his iPhone tweets. Thanks!

Great article and great paper. Similar set of questions that get asked as part of AutoML, including the idea of hyper-heuristics, but in the AI community instead of data science. Thanks for the insights.

That's very helpful. Thanks for the link.