More Like this

1. Bounding the Distance to Unsafe Sets With Convex Optimization

   https://doi.org/10.1109/TAC.2023.3285862  

   Miller, Jared; Sznaier, Mario (August 2023, IEEE Transactions on Automatic Control)

   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. Robust Testing and Estimation under Manipulation Attacks

   Acharya, Jayadev; Sun, Ziteng; Zhang, Huanyu (July 2021, Proceedings of Machine Learning Research)

   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. Nearly Optimal Algorithms for Level Set Estimation

   Mason, Blake; Jain, Lalit; Mukherjee, Subhojyoti; Camilleri, Romain; Jamieson, Kevin; Nowak, Robert (March 2022, International Conference on Artificial Intelligence and Statistics)

   The level set estimation problem seeks to find all points in a domain  where the value of an unknown function 𝑓:→ℝ exceeds a threshold 𝛼 . The estimation is based on noisy function evaluations that may be acquired at sequentially and adaptively chosen locations in  . The threshold value 𝛼 can either be explicit and provided a priori, or implicit and defined relative to the optimal function value, i.e. 𝛼=(1−𝜖)𝑓(𝐱∗) for a given 𝜖>0 where 𝑓(𝐱∗) is the maximal function value and is unknown. In this work we provide a new approach to the level set estimation problem by relating it to recent adaptive experimental design methods for linear bandits in the Reproducing Kernel Hilbert Space (RKHS) setting. We assume that 𝑓 can be approximated by a function in the RKHS up to an unknown misspecification and provide novel algorithms for both the implicit and explicit cases in this setting with strong theoretical guarantees. Moreover, in the linear (kernel) setting, we show that our bounds are nearly optimal, namely, our upper bounds match existing lower bounds for threshold linear bandits. To our knowledge this work provides the first instance-dependent, non-asymptotic upper bounds on sample complexity of level-set estimation that match information theoretic lower bounds. 

   more » « less
4. Adaptive Bayesian Estimation of Discrete‐Continuous Distributions Under Smoothness and Sparsity

   https://doi.org/10.3982/ECTA17884  

   Norets, Andriy; Pelenis, Justinas (January 2022, Econometrica)

   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
5. Stabilization distance bounds from link Floer homology

   https://doi.org/10.1112/topo.12338  

   Juhász, András; Zemke, Ian (June 2024, Journal of Topology)

   Abstract We consider the set of connected surfaces in the 4‐ball with boundary a fixed knot in the 3‐sphere. We define the stabilization distance between two surfaces as the minimal such that we can get from one to the other using stabilizations and destabilizations through surfaces of genus at most . Similarly, we consider a double‐point distance between two surfaces of the same genus that is the minimum over all regular homotopies connecting the two surfaces of the maximal number of double points appearing in the homotopy. To many of the concordance invariants defined using Heegaard Floer homology, we construct an analogous invariant for a pair of surfaces. We show that these give lower bounds on the stabilization distance and the double‐point distance. We compute our invariants for some pairs of deform‐spun slice disks by proving a trace formula on the full infinity knot Floer complex, and by determining the action on knot Floer homology of an automorphism of the connected sum of a knot with itself that swaps the two summands. We use our invariants to find pairs of slice disks with arbitrarily large distance with respect to many of the metrics we consider in this paper. We also answer a slice‐disk analog of Problem 1.105 (B) from Kirby's problem list by showing the existence of non‐0‐cobordant slice disks. 

   more » « less