Friedrich Eisenbrand

Friedrich Eisenbrand, Thomas Rothvoss, Matteo Russo et al.

We investigate the convex-body containment problem $\max\{s >0 : s Z \subseteq Q\}$, where the outer body $Q \subseteq \mathbb R^d$ is described by a membership oracle and the inner body $Z \subseteq \mathbb R^d$ is a zonotope. Our main result is a sampling-based $O(\sqrt{d})$-approximation algorithm for this problem that almost matches the lower bound of $Ω(\sqrt{d/\log d})$ by Khot and Naor in the oracle model. Assuming zonotopes can be sparsified by a linear number of generators, which is referred to as Talagrand conjecture, our approach attains the optimal approximation factor of $Θ(\sqrt{d/\log d})$. Our second main result is a proof of Talagrand's conjecture for $Δ$-modular zonotopes whenever $Δ$ is constant. Those zonotopes are of the form $Z = \{ Wx \colon \| x\|_\infty \leq 1\}$ where the non-zero $d \times d$ sub-determinants of $W$ are between $1$ and $Δ$. This result establishes a connection between zonoid sparsification and spectral sparsification of Batson, Spielman and Srivastava. We complement these results with a universal $Ω(\sqrt{d/\log d})$ lower bound holding for all zonotopes. Finally, we consider containment problems $\max\{s >0 : s K \subseteq Q\}$, for general convex bodies $K \subseteq \mathbb R^d$. A result of Naszódi on approximating $K \subseteq \mathbb R^d$ by a polytope implies a $Θ(d/\log d)$ approximation algorithm in polynomial time. We show the tightness of this approximation factor in the oracle model via a reduction to the circumradius computation. Our lower bound holds for centrally symmetric convex sets, implying that Barvinok's optimal $O(\sqrt{d})$-approximation of a centrally symmetric convex body by a polytope with a polynomial number of vertices cannot be computed in polynomial time.

Matthieu Haeberle, Puck van Gerwen, Ruben Laplaza et al.

Integer linear programming (ILP) is an elegant approach to solve linear optimization problems, naturally described using integer decision variables. Within the context of physics-inspired machine learning applied to chemistry, we demonstrate the relevance of an ILP formulation to select molecular training sets for predictions of size-extensive properties. We show that our algorithm outperforms existing unsupervised training set selection approaches, especially when predicting properties of molecules larger than those present in the training set. We argue that the reason for the improved performance is due to the selection that is based on the notion of local similarity (i.e., per-atom) and a unique ILP approach that finds optimal solutions efficiently. Altogether, this work provides a practical algorithm to improve the performance of physics-inspired machine learning models and offers insights into the conceptual differences with existing training set selection approaches.