skip to main content


Title: Bounding the Distance of Closest Approach to Unsafe Sets with Occupation Measures
This paper presents a method to lower-bound the distance of closest approach between points on an unsafe set and points along system trajectories. Such a minimal distance is a quantifiable and interpretable certificate of safety of trajectories, as compared to prior art in barrier and density methods which offers a binary indication of safety/unsafety. The distance estimation problem is converted into a infinitedimensional linear program in occupation measures based on existing work in peak estimation and optimal transport. The moment-SOS hierarchy is used to obtain a sequence of lower bounds obtained through solving semidefinite programs in increasing size, and these lower bounds will converge to the true minimal distance as the degree approaches infinity under mild conditions (e.g. Lipschitz dynamics, compact sets).  more » « less
Award ID(s):
2208182 1808381
NSF-PAR ID:
10447151
Author(s) / Creator(s):
;
Date Published:
Journal Name:
60th IEEE Conf. Decision and Control
Page Range / eLocation ID:
5008- 5013
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. This work proposes an algorithm to bound the minimum distance between points on trajectories of a dynamical system and points on an unsafe set. Prior work on certifying safety of trajectories includes barrier and density methods, which do not provide a margin of proximity to the unsafe set in terms of distance. The distance estimation problem is relaxed to a Monge-Kantorovich-type optimal transport problem based on existing occupation-measure methods of peak estimation. Specialized programs may be developed for polyhedral norm distances (e.g. L1 and Linfinity) and for scenarios where a shape is traveling along trajectories (e.g. rigid body motion). The distance estimation problem will be correlatively sparse when the distance objective is separable. 
    more » « less
  2. We study robust testing and estimation of discrete distributions in the strong contamination model. Our results cover both centralized setting and distributed setting with general local information constraints including communication and LDP constraints. Our technique relates the strength of manipulation attacks to the earth-mover distance using Hamming distance as the metric between messages (samples) from the users. In the centralized setting, we provide optimal error bounds for both learning and testing. Our lower bounds under local information constraints build on the recent lower bound methods in distributed inference. In the communication constrained setting, we develop novel algorithms based on random hashing and an L1-L1 isometry. 
    more » « less
  3. We consider nonparametric estimation of a mixed discrete‐continuous distribution under anisotropic smoothness conditions and a possibly increasing number of support points for the discrete part of the distribution. For these settings, we derive lower bounds on the estimation rates. Next, we consider a nonparametric mixture of normals model that uses continuous latent variables for the discrete part of the observations. We show that the posterior in this model contracts at rates that are equal to the derived lower bounds up to a log factor. Thus, Bayesian mixture of normals models can be used for (up to a log factor) optimal adaptive estimation of mixed discrete‐continuous distributions. The proposed model demonstrates excellent performance in simulations mimicking the first stage in the estimation of structural discrete choice models. 
    more » « less
  4. We study the Rouquier dimension of wrapped Fukaya categories of Liouville manifolds and pairs, and apply this invariant to various problems in algebraic and symplectic geometry. On the algebro-geometric side, we introduce a new method based on symplectic flexibility and mirror symmetry to bound the Rouquier dimension of derived categories of coherent sheaves on certain complex algebraic varieties and stacks. These bounds are sharp in dimension at most $3$ . As an application, we resolve a well-known conjecture of Orlov for new classes of examples (e.g. toric $3$ -folds, certain log Calabi–Yau surfaces). We also discuss applications to non-commutative motives on partially wrapped Fukaya categories. On the symplectic side, we study various quantitative questions including the following. (1) Given a Weinstein manifold, what is the minimal number of intersection points between the skeleton and its image under a generic compactly supported Hamiltonian diffeomorphism? (2) What is the minimal number of critical points of a Lefschetz fibration on a Liouville manifold with Weinstein fibers? We give lower bounds for these quantities which are to the best of the authors’ knowledge the first to go beyond the basic flexible/rigid dichotomy. 
    more » « less
  5. null (Ed.)
    Lightness and sparsity are two natural parameters for Euclidean (1+ε)-spanners. Classical results show that, when the dimension d ∈ ℕ and ε > 0 are constant, every set S of n points in d-space admits an (1+ε)-spanners with O(n) edges and weight proportional to that of the Euclidean MST of S. Tight bounds on the dependence on ε > 0 for constant d ∈ ℕ have been established only recently. Le and Solomon (FOCS 2019) showed that Steiner points can substantially improve the lightness and sparsity of a (1+ε)-spanner. They gave upper bounds of Õ(ε^{-(d+1)/2}) for the minimum lightness in dimensions d ≥ 3, and Õ(ε^{-(d-1))/2}) for the minimum sparsity in d-space for all d ≥ 1. They obtained lower bounds only in the plane (d = 2). Le and Solomon (ESA 2020) also constructed Steiner (1+ε)-spanners of lightness O(ε^{-1}logΔ) in the plane, where Δ ∈ Ω(log n) is the spread of S, defined as the ratio between the maximum and minimum distance between a pair of points. In this work, we improve several bounds on the lightness and sparsity of Euclidean Steiner (1+ε)-spanners. Using a new geometric analysis, we establish lower bounds of Ω(ε^{-d/2}) for the lightness and Ω(ε^{-(d-1)/2}) for the sparsity of such spanners in Euclidean d-space for all d ≥ 2. We use the geometric insight from our lower bound analysis to construct Steiner (1+ε)-spanners of lightness O(ε^{-1}log n) for n points in Euclidean plane. 
    more » « less