Control and Dynamical Systems (Thursday 10:45 - 12:30)

Sunbochen Tang

Learning dissipative chaotic dynamics with boundedness guarantees

Chaotic dynamics, commonly seen in weather systems and fluid turbulence, are characterized by their sensitivity to initial conditions, which makes accurate prediction challenging. Recent approaches have been focused on developing data-driven models that preserve invariant statistics over long horizons since many chaotic systems observe dissipative behaviors and ergodicity. Although these methods have shown empirical success, many of the models are still prone to generating unbounded trajectories, leading to invalid statistics evaluation. In this paper, we propose a novel neural network architecture that simultaneously learns a dissipative dynamics emulator that guarantees to generate bounded trajectories and an energy-like function that governs the dissipative behavior. More specifically, by leveraging control-theoretic ideas, we derive algebraic conditions based on the learned energy-like function that ensure asymptotic convergence to an invariant level set. Using these algebraic conditions, our proposed model enforces dissipativity through a ReLU projection layer, which provides formal trajectory boundedness guarantees. Furthermore, the invariant level set provides an outer estimate for the strange attractor, which is known to be very difficult to characterize due to its complex geometry. We demonstrate the capability of our model in producing bounded long-horizon trajectory forecasts that preserve invariant statistics and characterizing the attractor, for chaotic dynamical systems including Lorenz 96 and a truncated Kuramoto-Sivashinsky equation.

Paper link: https://arxiv.org/abs/2410.00976

Yue Meng

Diverse Controllable Diffusion Policy With Signal Temporal Logic

Generating realistic simulations is critical for autonomous system applications such as self-driving. However, driving simulators nowadays still have difficulty generating controllable, diverse, and rule-compliant behaviors for road participants: Rule-based models cannot produce diverse behaviors and require careful tuning, whereas learning-based methods imitate the policy from data but are not designed to follow the rules explicitly. Besides, the real-world datasets are by nature “single-outcome,” making the learning method hard to generate diverse behaviors. In this letter, we leverage Signal Temporal Logic (STL) and Diffusion Models to learn controllable, diverse, and rule-aware policy. We first calibrate the STL on the real-world data, then generate diverse synthetic data using trajectory optimization, and finally learn the rectified diffusion policy on the augmented dataset. We test on the NuScenes dataset and our approach can achieve the most diverse rule-compliant trajectories compared to other baselines, with a runtime 1/17X to the second-best approach. In closed-loop testing, our approach reaches the highest diversity, rule satisfaction rate, and the lowest collision rate.

Paper link: https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=10638176

Naman Aggarwal

SDP Synthesis of Backward Reachable Trees for Probabilistic Planning: A Coverage Perspective

The talk focuses on multi-query planning for linear stochastic systems. Multi-query planning seeks to create a reusable control framework that works across multiple initial configurations to reach a specified goal. A common approach is to synthesize an abstract graph of controllers, called a roadmap, which simplifies the planning problem into a graph search. We discuss our recent work that defines the backward reachable set of distributions corresponding to a roadmap. Additionally, we will explore various roadmap synthesis algorithms that account for this backward reachable space, enabling efficient multi-query planning with significantly smaller roadmaps as compared to existing methods in the literature.

Kota Kondo

DYNUS: Uncertainty-aware Multiagent Trajectory Planner in Dynamic Unknown Environments

This talk presents DYNUS, a fully decentralized, asynchronous multiagent trajectory planner designed to handle uncertainties and enable efficient navigation without prior assumptions on the environment. DYNUS is capable of operating in both open and confined, static and dynamic unknown spaces. DYNUS introduces three key contributions: (1) a fast and uncertainty-aware global planner, DYNUS Global Planner (DGP), (2) a robust and efficient trajectory optimization approach with an efficient time allocation algorithm, and (3) an uncertainty-aware yaw optimization method. Simulation results show that DYNUS outperforms state-of-the-art methods across various benchmarks. DGP achieves an average computation time of 8.8 ms, significantly outperforming Dynamic A* while achieving superior travel performance. In local trajectory optimization, DYNUS achieves only 31% of the computation time compared to the fastest existing method. Furthermore, DYNUS's yaw optimization enhances obstacle tracking, achieving a 100% success rate with a maximum computation time of just 6.1ms. DYNUS's navigation capabilities have been extensively evaluated across diverse benchmarks, including confined, cluttered, open, static, and dynamic unknown environments such as forests, office spaces, caves, and dynamic obstacle-filled spaces.

Lujie Yang

Physics-Driven Data Generation for Contact-Rich Manipulation via Trajectory Optimization

We present a low-cost data generation pipeline that integrates physics-based simulation, human demonstrations, and model-based planning to efficiently generate large-scale, high-quality datasets for contact-rich robotic manipulation tasks. Starting with a small number of embodiment-flexible human demonstrations collected in a virtual reality simulation environment, the pipeline refines these demonstrations using optimization-based kinematic retargeting and trajectory optimization to adapt them across various robot embodiments and physical parameters. This process yields a diverse, physically consistent dataset that enables cross-embodiment data transfer, and offers the potential to reuse legacy datasets collected under different hardware configurations or physical parameters.We validate the pipeline’s effectiveness by training diffusion policies on the generated datasets for challenging contact-rich manipulation tasks across multiple robot embodiments, including a floating Allegro hand and bimanual robot arms. The trained policies are deployed zero-shot on hardware for bimanual iiwa arms, achieving high success rates with minimal human input.

Taylor Elise Baum

Dynamic Cardiovascular State Estimation from Arterial Blood Pressure Recordings for Use in a Closed-Loop Cardiovascular Control System

Cardiovascular management is necessary in the operating room (OR) and intensive care unit (ICU). Ensuring proper end-organ perfusion (i.e., oxygenation of organs) through regulation of arterial blood pressure (ABP) is a primary cardiovascular management goal. To achieve this goal, clinicians must first select the appropriate treatment to recover both ABP and end-organ perfusion. To make this treatment selection, real-time estimation of patient cardiovascular states, including cardiac output (CO) and systemic vascular resistance (R) are necessary. Highly invasive measurements enable reliable estimation of these states but increase patient risk. Prior methods using minimally invasive measurements reduce patient risk but produce unreliable estimates limited due to trade-offs in time resolution and accuracy. We present a state-space method which enables beat-by-beat proportional estimation of cardiac function (i.e., CO) and vascular function (i.e., R) from minimally invasive ABP measurements. We then show, as validated with a swine dataset, that our cardiac and vascular function estimates agree closely with those derived from highly invasive measurements, agree closely with those derived from three separate arterial tree locations, and change predictably in response to standard cardiovascular medications. We finally provide a brief introduction to a closed-loop system for regulation of ABP informed by our estimates. Overall, our approach produces reliable, real-time estimates of cardiovascular states crucial for monitoring and control of the cardiovascular system.

Paper link: https://ieeexplore.ieee.org/document/10552349

Peter Fisher

Adaptive Control with Safety Guarantees: Reducing Conservatism

When looking to enforce state constraints in a dynamical system, the presence of parametric uncertainties will always necessitate some conservatism. But how much is really needed, and when can it be removed? We present a new integration of adaptive control with control barrier functions: an Error-Based Safety Buffer. Many previous approaches to this problem apply a buffer window around the boundary of the safe set whose size depends directly on the parameter estimation error, leading to a conservative buffer window which is either fixed for all time, or which can only be removed via persistent excitation and parameter learning. Other previous approaches are more heuristical in nature, giving good results in simulation but lacking in provable safety. In contrast, we provide a provably-safe algorithm which smoothly varies the size of the buffer window with the state tracking error. This approach leads to conservatism only when tracking performance is bad and shrinks the buffer window to near zero once adaptation has occurred, with no requirements on excitation.

 

Optimization and Robotics (Thursday 1:30 - 2:45)

Omar Bennouna

Addressing misspecification in contextual optimization

We study a linear contextual optimization problem where a decision maker has access to historical data and contextual features to learn a cost prediction model aimed at minimizing decision error. We adopt the predict-then-optimize framework for this analysis. Given that perfect model alignment with reality is often unrealistic in practice, we focus on scenarios where the chosen hypothesis set is misspecified. In this context, it remains unclear whether current contextual optimization approaches can effectively address such model misspecification. In this paper, we present a novel integrated learning and optimization approach designed to tackle model misspecification in contextual optimization. This approach offers theoretical generalizability, tractability, and optimality guarantees, along with strong practical performance. Our method involves minimizing a tractable surrogate loss that aligns with the performance value from cost vector predictions, regardless of whether the model is misspecified, and can be optimized in reasonable time. To our knowledge, no previous work has provided an approach with such guarantees in the context of model misspecification.

Paper link: https://arxiv.org/pdf/2409.10479

Lorenzo Shaikewitz

A Certifiable Algorithm for Simultaneous Shape Estimation and Object Tracking

Applications from manipulation to autonomous vehicles rely on robust and general object tracking to safely perform tasks in dynamic environments. We propose the first certifiably optimal category-level approach for simultaneous shape estimation and pose tracking of an object of known category (e.g. a car). Our approach uses 3D semantic keypoint measurements extracted from an RGB-D image sequence, and phrases the estimation as a fixed-lag smoothing problem. Temporal constraints enforce the object's rigidity (fixed shape) and smooth motion according to a constant-twist motion model. The solutions to this problem are the estimates of the object's state (poses, velocities) and shape (parameterized according to the active shape model) over the smoothing horizon. Our key contribution is to show that despite the non-convexity of the fixed-lag smoothing problem, we can solve it to certifiable optimality using a small-size semidefinite relaxation. We also present a fast outlier rejection scheme that filters out incorrect keypoint detections with shape and time compatibility tests, and wrap our certifiable solver in a graduated non-convexity scheme. We evaluate the proposed approach on synthetic and real data, showcasing its performance in a table-top manipulation scenario and a drone-based vehicle tracking application.

Paper link: https://arxiv.org/abs/2406.16837

Gagik Magakyan

General framework for online-to-nonconvex conversion: Schedule-free SGD is also effective for nonconvex optimization

This work investigates the effectiveness of schedule-free methods, developed by A. Defazio et al. (NeurIPS 2024), in nonconvex optimization settings, inspired by their remarkable empirical success in training neural networks. Specifically, we show that schedule-free SGD achieves optimal iteration complexity for nonsmooth, nonconvex optimization problems. Our proof begins with the development of a general framework for online-to-nonconvex conversion, which converts a given online learning algorithm into an optimization algorithm for nonconvex losses. Our general framework not only recovers existing conversions but also leads to two novel conversion schemes. Notably, one of these new conversions corresponds directly to schedule-free SGD, allowing us to establish its optimality. Additionally, our analysis provides valuable insights into the parameter choices for schedule-free SGD, addressing a theoretical gap that the convex theory cannot explain.

Paper link: https://arxiv.org/pdf/2411.07061

Thomas Cohn

Non-Euclidean Motion Planning with Graphs of Geodesically-Convex Sets

Computing optimal, collision-free trajectories for high-dimensional systems is a challenging and important problem. Sampling-based planners struggle with the dimensionality, whereas trajectory optimizers may get stuck in local minima due to inherent nonconvexities in the optimization landscape. The use of mixed-integer programming to encapsulate these nonconvexities and find globally optimal trajectories has recently shown great promise, thanks in part to tight convex relaxations and efficient approximation strategies that greatly reduce runtimes. These approaches were previously limited to Euclidean configuration spaces, precluding their use with mobile bases or continuous revolute joints. In this paper, we handle such scenarios by modeling configuration spaces as Riemannian manifolds, and we describe a reduction procedure for the zero-curvature case to a mixed-integer convex optimization problem. We further present a method for obtaining approximate solutions via piecewise-linear approximations that is applicable to manifolds of arbitrary curvature. We demonstrate our results on various robot platforms, including producing efficient collision-free trajectories for a PR2 bimanual mobile manipulator.

Paper link: https://journals.sagepub.com/doi/full/10.1177/02783649241302419

 

Efficient and Fair Learning (Friday 10:30 - 12:30)

Yongchao Chen

Integrating Foundation Models and Symbolic Computing for Augmented Reasoning and Planning

State-of-the-art language models, like GPT-4o and O1, continue to face challenges in solving tasks with intricate constraints involving logic, geometry, iteration, and optimization. While it's common to query LLMs to generate an answer or plan purely through text output, we stress the importance of integrating symbolic computing to enhance general reasoning and planning capabilities. By combining LLMs with symbolic planners and solvers, or guiding LLMs to generate code for solving the tasks, we enable them to address complex decision-making tasks for both real and virtual robots. This approach extends to various applications, including general question answering, task and motion planning for drones and manipulators, travel itinerary planning, and more.

Olawale Salaudeen

Hitting the Wrong Target: On the Prevalence of Underspecified Spurious Correlations Benchmarks

Are the negative impacts of spurious correlations on out-of-distribution (OOD/domain) generalization overstated? Empirical evidence increasingly suggests so, as the naive empirical risk minimizer of training distributions achieves the best out-of-distribution accuracy across a multitude of domain generalization benchmarks. In light of these counterintuitive results, we propose a different perspective: many state-of-the-art benchmarks for evaluating the mitigation of spurious correlations usage in machine learning predictions are fundamentally underspecified and may not accurately measure robustness to spurious correlations under distribution shifts. Through theoretical analysis, we show that only datasets with adversarially constructed out-of-domain spurious correlations can reliably evaluate a model's ability to eliminate these correlations. Moreover, we evaluate state-of-the-art domain generalization benchmarks and find that the majority do not exhibit such adversarial shifts. These findings reveal an ambiguity in the state of current state-of-the-art domain generalization algorithms and emphasize the need to rethink how benchmarks are designed for this critical task.

A. Anas Chentouf

Training Dynamics to Detect Noisy Labels in Deep Classifiers

Noisy labels in real-world training datasets are a ubiquitous challenge that can degrade model performance, generalization, and usability. Recent work has proposed various approaches to address this issue, including data filtering methods that aim to detect and remove mislabeled samples from training datasets. In this context, we report on recent work that investigates noisy labels through the lens of training dynamics in over-parameterized and over-trained deep neural classifiers. We also establish connections to other data filtering and model selection strategies.

Aparna Balagopalan

Operationalizing a Pipeline Perspective on Fair and Reliable Machine Learning

While there has been significant research in the space of reliability in machine learning systems, a majority of work has been in the modeling phase, with substantially less focus on other critical model design choices during data collection, and model deployment. Our work instead aims to build fair and reliable machine learning-based systems, by operationalizing a pipeline perspective on fairness in practice, considering the interplay of human processes from training data collection to model presentation. In this scope, I'll talk about our recent work in this space on: (1) developing methods for to filter data used to train vision-language models, (2) developing user attention-distribution based fair ranking systems.

Mansi Sood

Balancing Sparsity and Connectivity in Distributed Network Design

In several applications in distributed systems, an important design criterion is ensuring that the network is sparse, i.e., does not contain too many edges, while achieving reliable connectivity (e.g., to facilitate reliable communication or performance guarantees for distributed algorithms). A class of network models known as ‘random K-out graphs’ widely appear as a heuristic to balance connectivity and sparsity, especially in distributed settings with limited trust. However, the implications of operational constraints, such as node heterogeneity and failures on the connectivity of random K-out graphs, remain underexplored. To address this gap, we present deployable theorems to inform the choice of network parameters that guarantee reliable connectivity in regimes where nodes can be finite, heterogeneous, or unreliable. Our results underscore the usefulness of random K-out graphs as a tool for balancing sparsity and connectivity in distributed network design.

 

Inference and Information (Friday 2:45 - 4:30)

Melihcan Erol

Noise Contrastive Estimation: An Information Geometric Perspective

Noise Contrastive Estimation (NCE) makes it possible to estimate the parameters of unnormalized models directly from data. However, the influence of the noise distribution on estimation efficiency is not yet fully understood. In this work, we reveal how geometric considerations play a pivotal role in selecting an effective noise distribution.

Abhinav Kumar

Disentangling Mixtures of Unknown Causal Interventions

The ability to conduct interventions plays a pivotal role in learning causal relationships among variables, thus facilitating applications across diverse scientific disciplines such as genomics, economics, and machine learning. However, in many instances within these applications, the process of generating interventional data is subject to noise: rather than data being sampled directly from the intended interventional distribution, interventions often yield data sampled from a blend of both intended and unintended interventional distributions. We consider the fundamental challenge of disentangling mixed interventional and observational data within linear Structural Equation Models (SEMs) with Gaussian additive noise without the knowledge of the true causal graph. We demonstrate that conducting interventions, whether do or soft, yields distributions with sufficient diversity and properties conducive to efficiently recovering each component within the mixture. Furthermore, we establish that the sample complexity required to disentangle mixed data inversely correlates with the extent of change induced by an intervention in the equations governing the affected variable values. As a result, the causal graph can be identified up to its interventional Markov Equivalence Class, similar to scenarios where no noise influences the generation of interventional data. We further support our theoretical findings by conducting simulations wherein we perform causal discovery from such mixed data.

Paper link: https://arxiv.org/abs/2411.00213

Eric Xia

Instrumental variables: A non-asymptotic viewpoint

We provide a non-asymptotic analysis of the linear instrumental variable estimator allowing for the presence of exogeneous covariates. In addition, we introduce a novel measure of the strength of an instrument that can be used to derive non-asymptotic confidence intervals. For strong instruments, these non-asymptotic intervals match the asymptotic ones exactly up to higher order corrections; for weaker instruments, our intervals involve adaptive adjustments to the instrument strength, and thus remain valid even when asymptotic predictions break down. We illustrate our results via an analysis of the effect of PM2.5 pollution on various health conditions, using wildfire smoke exposure as an instrument. Our analysis shows that exposure to PM2.5 pollution leads to statistically significant increases in incidence of health conditions such as asthma, heart disease, and strokes. Based on joint work w/ Martin Wainwright and Whitney Newey.

Paper link: https://arxiv.org/abs/2410.02015

Yassir Jedra

Exploiting Observation Bias to Improve Matrix Completion

We consider a variant of matrix completion where entries are revealed in a biased manner. We wish to understand the extent to which such bias can be exploited in improving predictions. Towards that, we propose a natural model where the observation pattern and outcome of interest are driven by the same set of underlying latent (or unobserved) factors. We devise Mask Nearest Neighbor (MNN), a novel two-stage matrix completion algorithm: first, it recovers (distances between) the latent factors by utilizing matrix estimation for the fully observed noisy binary matrix, corresponding to the observation pattern; second, it utilizes the recovered latent factors as features and sparsely observed noisy outcomes as labels to perform non-parametric supervised learning. Our analysis reveals that MNN enjoys entry-wise finite-sample error rates that are competitive with corresponding supervised learning parametric rates. Despite not having access to the latent factors and dealing with biased observations, MNN exhibits such competitive performance via only exploiting the shared information between the bias and outcomes. Finally, through empirical evaluation using a real-world dataset, we find that with MNN, the estimates have 28x smaller mean squared error compared to traditional matrix completion methods, suggesting the utility of the model and method proposed in this work. This is based on Joint work with Sean Mann , Charlotte Park, and Devavrat Shah.

Paper link: https://arxiv.org/abs/2306.04775

Anjali Parashar

Failure prediction with few demonstrations

Prediction of failures in real-world robotic systems either requires accurate model information or extensive testing. Partial knowledge of the system model makes simulation-based failure prediction unreliable. Moreover, obtaining such demonstrations is expensive, and could potentially be risky for the robotic system to repeatedly fail during data collection. This work presents a novel three-step methodology for discovering failures that occur in the true system by using a combination of a limited number of demonstrations from the true system and the failure information processed through sampling-based testing of a model dynamical system. To illustrate the efficacy of the proposed methodology, we consider: a) the failure discovery for the task of pushing a T block to a fixed target region with UR3E collaborative robot arm using a diffusion policy; and b) the failure discovery for an F1-Tenth racing car tracking a given raceline under an LQR control policy.

Paper link: https://arxiv.org/abs/2410.09249

Vishwak Srinivasan

High-accuracy sampling from constrained spaces with the Metropolis-adjusted Preconditioned Langevin Algorithm

We propose a first-order sampling method called the Metropolis-adjusted Preconditioned Langevin Algorithm for approximate sampling from a target distribution whose support is a proper convex subset of a Euclidean domain. Our proposed method is the result of applying a Metropolis-Hastings filter to the Markov chain formed by a single step of the preconditioned Langevin algorithm with a metric G, and is motivated by the natural gradient descent algorithm for optimisation. The method can be viewed as an interpolation between DikinWalk (a geometric random walk algorithm), and ManifoldMALA (an extension of the classical MALA for manifolds). We derive non-asymptotic upper bounds for the mixing time of this method for sampling from target distributions under a variety of assumptions. We also provide numerical experiments that demonstrate the practicality of our proposed method on certain tasks.

Paper link: https://arxiv.org/abs/2412.18701

Kaveh Alimohammadi

Differentially Private Synthetic Data Generation for Relational Databases

Generating differentially private (DP) synthetic data is essential for enabling privacy-preserving data analysis, yet most existing methods are limited to single-source tables, overlooking the complexities of relational databases. We introduce the first-of-its-kind algorithm that can be combined with any existing DP mechanism to generate synthetic relational databases. Our algorithm iteratively refines the relationship between individual synthetic tables to minimize their approximation errors in terms of low-order marginal distributions while maintaining referential integrity. This approach eliminates the need to flatten a relational database into a master table (saving space), operates efficiently (saving time), and scales effectively to high-dimensional data.

Paper link: https://arxiv.org/abs/2405.18670