Naoki Hamada

Ryosuke Ota, Reiya Hagiwara, Naoki Hamada et al.

In multi-objective optimization, designing good benchmark problems is an important issue for improving solvers. Controlling the global location of Pareto optima in existing benchmark problems has been problematic, and it is even more difficult when the design space is high-dimensional since visualization is extremely challenging. As a benchmarking with explicit local Pareto fronts, we introduce a benchmarking based on basin connectivity (3BC) by using basins of attraction. The 3BC allows for the specification of a multimodal landscape through a kind of topological analysis called the basin graph, effectively generating optimization problems from this graph. Various known indicators measure the performance of a solver in searching global Pareto optima, but using 3BC can make us localize them for each local Pareto front by restricting it to its basin. 3BC's mathematical formulation ensures the accurate representation of the specified optimization landscape, guaranteeing the existence of intended local and global Pareto optima.

Yusuke Mizota, Naoki Hamada, Shunsuke Ichiki

A multi-objective optimization problem is $C^r$ weakly simplicial if there exists a $C^r$ surjection from a simplex onto the Pareto set/front such that the image of each subsimplex is the Pareto set/front of a subproblem, where $0\leq r\leq \infty$. This property is helpful to compute a parametric-surface approximation of the entire Pareto set and Pareto front. It is known that all unconstrained strongly convex $C^r$ problems are $C^{r-1}$ weakly simplicial for $1\leq r \leq \infty$. In this paper, we show that all unconstrained strongly convex problems are $C^0$ weakly simplicial. The usefulness of this theorem is demonstrated in a sparse modeling application: we reformulate the elastic net as a non-differentiable multi-objective strongly convex problem and approximate its Pareto set (the set of all trained models with different hyper-parameters) and Pareto front (the set of performance metrics of the trained models) by using a Bézier simplex fitting method, which accelerates hyper-parameter search.

Akinori Tanaka, Akiyoshi Sannai, Ken Kobayashi et al.

Bézier simplex fitting algorithms have been recently proposed to approximate the Pareto set/front of multi-objective continuous optimization problems. These new methods have shown to be successful at approximating various shapes of Pareto sets/fronts when sample points exactly lie on the Pareto set/front. However, if the sample points scatter away from the Pareto set/front, those methods often likely suffer from over-fitting. To overcome this issue, in this paper, we extend the Bézier simplex model to a probabilistic one and propose a new learning algorithm of it, which falls into the framework of approximate Bayesian computation (ABC) based on the Wasserstein distance. We also study the convergence property of the Wasserstein ABC algorithm. An extensive experimental evaluation on publicly available problem instances shows that the new algorithm converges on a finite sample. Moreover, it outperforms the deterministic fitting methods on noisy instances.

Akinori Tanaka, Akiyoshi Sannai, Ken Kobayashi et al.

The Bezier simplex fitting is a novel data modeling technique which exploits geometric structures of data to approximate the Pareto front of multi-objective optimization problems. There are two fitting methods based on different sampling strategies. The inductive skeleton fitting employs a stratified subsampling from each skeleton of a simplex, whereas the all-at-once fitting uses a non-stratified sampling which treats a simplex as a whole. In this paper, we analyze the asymptotic risks of those Bézier simplex fitting methods and derive the optimal subsample ratio for the inductive skeleton fitting. It is shown that the inductive skeleton fitting with the optimal ratio has a smaller risk when the degree of a Bezier simplex is less than three. Those results are verified numerically under small to moderate sample sizes. In addition, we provide two complementary applications of our theory: a generalized location problem and a multi-objective hyper-parameter tuning of the group lasso. The former can be represented by a Bezier simplex of degree two where the inductive skeleton fitting outperforms. The latter can be represented by a Bezier simplex of degree three where the all-at-once fitting gets an advantage.

Naoki Hamada

Quite a few studies on real-world applications of multi-objective optimization reported that their Pareto sets and Pareto fronts form a topological simplex. Such a class of problems was recently named the simple problems, and their Pareto set and Pareto front were observed to have a gluing structure similar to the faces of a simplex. This paper gives a theoretical justification for that observation by proving the gluing structure of the Pareto sets/fronts of subproblems of a simple problem. The simplicity of standard benchmark problems is studied.

Naoki Hamada, Katsumi Homma, Hiroyuki Higuchi et al.

The recent development of multi-agent simulations brings about a need for population synthesis. It is a task of reconstructing the entire population from a sampling survey of limited size (1% or so), supplying the initial conditions from which simulations begin. This paper presents a new kernel density estimator for this task. Our method is an analogue of the classical Breiman-Meisel-Purcell estimator, but employs novel techniques that harness the huge degree of freedom which is required to model high-dimensional nonlinearly correlated datasets: the crossover kernel, the k-nearest neighbor restriction of the kernel construction set and the bagging of kernels. The performance as a statistical estimator is examined through real and synthetic datasets. We provide an "optimization-free" parameter selection rule for our method, a theory of how our method works and a computational cost analysis. To demonstrate the usefulness as a population synthesizer, our method is applied to a household synthesis task for an urban micro-simulator.