Bi-objective Stochastic Simulation Optimization on Integer Lattices via Scalarization

First-Order Methods for Distributionally Robust Constrained Optimization

This paper proposes a tractable stochastic approach based on an entropic regularization of the distributionally robust value function, which makes it possible to compute stochastic gradient estimators, and the combination of these estimators with a stochastic Frank-Wolfe algorithm, allowing us to optimize the regularized robust objective while naturally handling constraints.

TSMOO: Solving Multi-Objective Experimentation with Constrained Thompson Sampling

Quadratic Optimization over Probability Measures with Coupling Constraints

We consider solving an optimization instance in which the objective is quadratic and where the decision variable is a probability measure. Our class of problems are motivated by applications arising from optimal transport (with the Gromov-Wasserstein problem being a prominent example) as well as energy landscape minimization. Because the objective depends quadratically on the decision variable, our class of problems fall outside the standard modeling framework of the Generalized Moment Problems (which requires the objective to be linear). To this end, we propose a hierarchy of convex relaxations based on searching over probability measures over products of the base space. These have a natural interpretation with the moment Sum-of-squares hierarchy-a prominent framework for solving polynomial optimization instances, which we adapt to accommodate probability measures. A key conceptual contribution is to introduce a notion of positive-semidefiniteness that extends the usual notion over matrices. Under the assumption that the decision variables satisfy certain marginal constraints (as in the Kantorovich formulation of the optimal transport problem), we establish convergence of our hierarchy towards the globally optimal solution. Under the additional assumption that the objective is a polynomial, we propose a moment-SOS type hierarchy of finite dimensional semidefinite programs whose optimal solution converges to that of the original quadratic optimization over measures. We demonstrate our framework with numerical experiments. More generally, optimization over measures where the objective and/or constraint depends on the decision in a polynomial way is a fundamental problem. It is hoped that our work provides a road-map as to how the ideas of the SOS-ordinarily developed for polynomial optimization-may be applied to a broader class of non-linear problems involving measures.

Recursive rounding of sample size estimation for multi-fidelity Monte Carlo

In multifidelity Monte Carlo (MFMC), optimal sample allocations are typically derived from a continuous relaxation of a variance minimization problem, with integer solutions obtained through post hoc rounding. Such rounding procedures may fail to fully exploit the available cost budget, particularly under tight cost budgets or when model costs vary significantly. In this work, we reformulate the MFMC allocation problem as a variance-constrained cost minimization problem that is equivalent to the standard budget-constrained formulation at the continuous level. This reformulation admits a recursive structure that enables the construction of an integer allocation strategy based on Bellman's principle of optimality. Since the resulting MFMC allocation has a mathematical structure similar to the optimal multilevel Monte Carlo (MLMC) allocation, the proposed strategy naturally extends to MLMC. The resulting algorithm constructs integer-valued sample allocations that more closely follow the continuous variance--cost tradeoff while using the prescribed variance tolerance more efficiently. Numerical experiments demonstrate that the proposed approach satisfies the prescribed variance tolerance with less computational overhead than standard rounding strategies.

Parallelizable Gradient-Based Optimization For Multi-Objective MaxCut

Multi-objective combinatorial optimization arises in a wide range of problems and applications, including the canonical multi-objective MaxCut problem. Differentiable single-instance quadratic methods have recently achieved remarkable performance in single-objective combinatorial optimization. In this paper, we develop a differentiable framework for multi-objective MaxCut by combining an adjacency-based quadratic formulation with linear scalarization, thereby reducing the problem to a preference-conditioned single-objective signed-weight MaxCut problem. Theoretically, we characterize the stationary points of the resulting signed-weight formulation and show how they induce preference-conditioned fixed points on the Pareto front. Computationally, unlike conventional heuristics and branch-and-bound methods, our approach is GPU-parallelizable and can therefore benefit from substantial performance speedups. We term our algorithm Multi-objective QUadratic Combinatorial Optimization (MO-QUCO) and its parallelized variant pMO-QUCO. Empirically, across different multi-layered (and weight distributions) graphs, we show that both our CPU-only and GPU-based algorithms outperform SOTA exact and heuristic methods in terms of wall-clock runtime and objective quality. Despite operating under different computational settings, MO-QUCO also outperforms the SOTA quantum method.

Out-Of-The-Loop Multi-Fidelity Bayesian Optimization

Black-box optimization is a ubiquitous problem in science and engineering, often dealing with expensive objective functions with cheaper lower-fidelity proxies available. Multi-fidelity Bayesian optimization (MF-BO) is a principled approach to this problem, leveraging correlations across different fidelities when querying the objective. However, for many important MF-BO tasks, the true highest-fidelity function is prohibitively expensive to be part of the optimization loop. Nevertheless, practitioners often have gold standard data (observations of the highest-fidelity function) obtained from previous experiments that might provide information for the current task. For instance, in molecular optimization, chemists often pick the top-$k$ candidate molecules using various computer simulations, and later reveal their true objective function values. In this work, we demonstrate the suboptimality of standard MF-BO algorithms in the real-world scenarios above, even under ideal assumptions. Next, we mitigate this problem by incorporating historical high-fidelity data accompanied by task descriptors---which can be explicitly given or extracted from unstructured metadata. We demonstrate the effectiveness of our methods on synthetic functions, as well as real-world problems in chemistry and hyperparameter optimization.