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