Carla Gomes

NeurIPS Conference 2025 Conference Paper

FEAT: Free energy Estimators with Adaptive Transport

• Yuanqi Du
• Jiajun He
• Francisco Vargas
• Yuanqing Wang
• Carla Gomes
• José Miguel Hernández-Lobato
• Eric Vanden-Eijnden

We present Free energy Estimators with Adaptive Transport (FEAT), a novel framework for free energy estimation---a critical challenge across scientific domains. FEAT leverages learned transports implemented via stochastic interpolants and provides consistent, minimum-variance estimators based on escorted Jarzynski equality and controlled Crooks theorem, alongside variational upper and lower bounds on free energy differences. Unifying equilibrium and non-equilibrium methods under a single theoretical framework, FEAT establishes a principled foundation for neural free energy calculations. Experimental validation on toy examples, molecular simulations, and quantum field theory demonstrates promising improvements over existing learning-based methods. Our PyTorch implementation is available at https: //github. com/jiajunhe98/FEAT.

AIJ Journal 2022 Journal Article

Efficient projection algorithms onto the weighted ℓ1 ball

• Guillaume Perez
• Sebastian Ament
• Carla Gomes
• Michel Barlaud

Projected gradient descent has been proved efficient in many optimization and machine learning problems. The weighted ℓ 1 ball has been shown effective in sparse system identification and features selection. In this paper we propose three new efficient algorithms for projecting any vector of finite length onto the weighted ℓ 1 ball. The first two algorithms have a linear worst case complexity. The third one has a highly competitive performances in practice but the worst case has a quadratic complexity. These new algorithms are efficient tools for machine learning methods based on projected gradient descent such as compressed sensing, feature selection. We illustrate this effectiveness by adapting an efficient compressed sensing algorithm to weighted projections. We demonstrate the efficiency of our new algorithms on benchmarks using very large vectors. For instance, it requires only 8 ms, on an Intel I7 3rd generation, for projecting vectors of size 107.

IJCAI Conference 2022 Conference Paper

Monitoring Vegetation From Space at Extremely Fine Resolutions via Coarsely-Supervised Smooth U-Net

• Joshua Fan
• Di Chen
• Jiaming Wen
• Ying Sun
• Carla Gomes

Monitoring vegetation productivity at extremely fine resolutions is valuable for real-world agricultural applications, such as detecting crop stress and providing early warning of food insecurity. Solar-Induced Chlorophyll Fluorescence (SIF) provides a promising way to directly measure plant productivity from space. However, satellite SIF observations are only available at a coarse spatial resolution, making it impossible to monitor how individual crop types or farms are doing. This poses a challenging coarsely-supervised regression (or downscaling) task; at training time, we only have SIF labels at a coarse resolution (3km), but we want to predict SIF at much finer spatial resolutions (e. g. 30m, a 100x increase). We also have additional fine-resolution input features, but the relationship between these features and SIF is unknown. To address this, we propose Coarsely-Supervised Smooth U-Net (CS-SUNet), a novel method for this coarse supervision setting. CS-SUNet combines the expressive power of deep convolutional networks with novel regularization methods based on prior knowledge (such as a smoothness loss) that are crucial for preventing overfitting. Experiments show that CS-SUNet resolves fine-grained variations in SIF more accurately than existing methods.

AAAI Conference 2021 Conference Paper

Accelerating Ecological Sciences from Above: Spatial Contrastive Learning for Remote Sensing

• Johan Bjorck
• Brendan H. Rappazzo
• Qinru Shi
• Carrie Brown-Lima
• Jennifer Dean
• Angela Fuller
• Carla Gomes

The rise of neural networks has opened the door for automatic analysis of remote sensing data. A challenge to using this machinery for computational sustainability is the necessity of massive labeled data sets, which can be cost-prohibitive for many non-profit organizations. The primary motivation for this work is one such problem; the efficient management of invasive species – invading flora and fauna that are estimated to cause damages in the billions of dollars annually. As an ongoing collaboration with the New York Natural Heritage Program, we consider the use of unsupervised deep learning techniques for dimensionality reduction of remote sensing images, which can reduce sample complexity for downstream tasks and decreases the need for large labeled data sets. We consider spatially augmenting contrastive learning by training neural networks to correctly classify two nearby patches of a landscape as such. We demonstrate that this approach improves upon previous methods and naive classification for a large-scale data set of remote sensing images derived from invasive species observations obtained over 30 years. Additionally, we simulate deployment in the field via active learning and evaluate this method on another important challenge in computational sustainability – landcover classification – and again find that it outperforms previous baselines.

AAAI Conference 2021 Conference Paper

Characterizing the Loss Landscape in Non-Negative Matrix Factorization

• Johan Bjorck
• Anmol Kabra
• Kilian Q. Weinberger
• Carla Gomes

Non-negative matrix factorization (NMF) is a highly celebrated algorithm for matrix decomposition that guarantees non-negative factors. The underlying optimization problem is computationally intractable, yet in practice, gradient-descentbased methods often find good solutions. In this paper, we revisit the NMF optimization problem and analyze its loss landscape in non-worst-case settings. We specifically study star-convexity, which implies that the gradients point towards the final minimizer. We show that such a property holds with high probability for NMF, provably in a non-worst case model with a planted solution, and empirically across an extensive suite of real-world NMF problems spanning collaborative filtering, scientific analysis, and image analysis. Our analysis predicts that this property becomes more likely with a growing number of parameters, and experiments suggest that a similar trend might also hold for deep neural networks—turning increasing dataset sizes and model sizes into a blessing from an optimization perspective.

AAAI Conference 2021 Conference Paper

HOT-VAE: Learning High-Order Label Correlation for Multi-Label Classification via Attention-Based Variational Autoencoders

• Wenting Zhao
• Shufeng Kong
• Junwen Bai
• Daniel Fink
• Carla Gomes

Understanding how environmental characteristics affect biodiversity patterns, from individual species to communities of species, is critical for mitigating effects of global change. A central goal for conservation planning and monitoring is the ability to accurately predict the occurrence of species communities and how these communities change over space and time. This in turn leads to a challenging and long-standing problem in the field of computer science - how to perform accurate multi-label classification with hundreds of labels? The key challenge of this problem is its exponential-sized output space with regards to the number of labels to be predicted. Therefore, it is essential to facilitate the learning process by exploiting correlations (or dependency) among labels. Previous methods mostly focus on modelling the correlation on label pairs; however, complex relations between real-world objects often go beyond second order. In this paper, we propose a novel framework for multi-label classification, Highorder Tie-in Variational Autoencoder (HOT-VAE), which performs adaptive high-order label correlation learning. We experimentally verify that our model outperforms the existing state-of-the-art approaches on a bird distribution dataset on both conventional F1 scores and a variety of ecological metrics. To show our method is general, we also perform empirical analysis on seven other public real-world datasets in several application domains, and Hot-VAE exhibits superior performance to previous methods.

AAAI Conference 2021 Conference Paper

Learning Augmented Methods for Matching: Improving Invasive Species Management and Urban Mobility

• Johan Bjorck
• Qinru Shi
• Carrie Brown-Lima
• Jennifer Dean
• Angela Fuller
• Carla Gomes

With the success of machine learning, integrating learned models into real-world systems has become a critical challenge. Naively applying predictions to combinatorial optimization problems can incur high costs, which has motivated researchers to consider learning augmented algorithms that can make use of faulty or incomplete predictions. Inspired by two matching problems in computational sustainability where data are abundant, we consider the learning augmented min-cost matching problem where some nodes are revealed online while others are known a priori, e. g. , by being predicted by machine learning. We develop an algorithm that is able to make use of this extra information and provably improves upon pessimistic online algorithms. We evaluate our algorithm on two settings from computational sustainability – the coordination of opportunistic citizen scientists for invasive species management and the matching between taxis and riders under uncertain trip duration predictions. In both cases, we perform extensive experiments on real-world datasets and find that our method outperforms baselines, showing how learning augmented algorithms can reliably improve solutions for problems in computational sustainability.

AAAI Conference 2021 Conference Paper

Understanding Decoupled and Early Weight Decay

• Johan Bjorck
• Kilian Q. Weinberger
• Carla Gomes

Weight decay (WD) is a traditional regularization technique in deep learning, but despite its ubiquity, its behavior is still an area of active research. Golatkar et al. have recently shown that WD only matters at the start of the training in computer vision, upending traditional wisdom. Loshchilov et al. show that for adaptive optimizers, manually decaying weights can outperform adding an l2 penalty to the loss. This technique has become increasingly popular and is referred to as decoupled WD. The goal of this paper is to investigate these two recent empirical observations. We demonstrate that by applying WD only at the start, the network norm stays small throughout training. This has a regularizing effect as the effective gradient updates become larger. However, traditional generalizations metrics fail to capture this effect of WD, and we show how a simple scale-invariant metric can. We also show how the growth of network weights is heavily influenced by the dataset and its generalization properties. For decoupled WD, we perform experiments in NLP and RL where adaptive optimizers are the norm. We demonstrate that the primary issue that decoupled WD alleviates is the mixing of gradients from the objective function and the l2 penalty in the buffers of Adam (which stores the estimates of the first-order moment). Adaptivity itself is not problematic and decoupled WD ensures that the gradients from the l2 term cannot ”drown out” the true objective, facilitating easier hyperparameter tuning.

IJCAI Conference 2020 Conference Paper

Deep Hurdle Networks for Zero-Inflated Multi-Target Regression: Application to Multiple Species Abundance Estimation

• Shufeng Kong
• Junwen Bai
• Jae Hee Lee
• Di Chen
• Andrew Allyn
• Michelle Stuart
• Malin Pinsky
• Katherine Mills

A key problem in computational sustainability is to understand the distribution of species across landscapes over time. This question gives rise to challenging large-scale prediction problems since (i) hundreds of species have to be simultaneously modeled and (ii) the survey data are usually inflated with zeros due to the absence of species for a large number of sites. The problem of tackling both issues simultaneously, which we refer to as the zero-inflated multi-target regression problem, has not been addressed by previous methods in statistics and machine learning. In this paper, we propose a novel deep model for the zero-inflated multi-target regression problem. To this end, we first model the joint distribution of multiple response variables as a multivariate probit model and then couple the positive outcomes with a multivariate log-normal distribution. By penalizing the difference between the two distributions’ covariance matrices, a link between both distributions is established. The whole model is cast as an end-to-end learning framework and we provide an efficient learning algorithm for our model that can be fully implemented on GPUs. We show that our model outperforms the existing state-of-the-art baselines on two challenging real-world species distribution datasets concerning bird and fish populations.

IJCAI Conference 2020 Conference Paper

Disentangled Variational Autoencoder based Multi-Label Classification with Covariance-Aware Multivariate Probit Model

• Junwen Bai
• Shufeng Kong
• Carla Gomes

Multi-label classification is the challenging task of predicting the presence and absence of multiple targets, involving representation learning and label correlation modeling. We propose a novel framework for multi-label classification, Multivariate Probit Variational AutoEncoder (MPVAE), that effectively learns latent embedding spaces as well as label correlations. MPVAE learns and aligns two probabilistic embedding spaces for labels and features respectively. The decoder of MPVAE takes in the samples from the embedding spaces and models the joint distribution of output targets under a Multivariate Probit model by learning a shared covariance matrix. We show that MPVAE outperforms the existing state-of-the-art methods on important computational sustainability applications as well as on other application domains, using public real-world datasets. MPVAE is further shown to remain robust under noisy settings. Lastly, we demonstrate the interpretability of the learned covariance by a case study on a bird observation dataset.

IJCAI Conference 2020 Conference Paper

Solving Hard AI Planning Instances Using Curriculum-Driven Deep Reinforcement Learning

• Dieqiao Feng
• Carla Gomes
• Bart Selman

Despite significant progress in general AI planning, certain domains remain out of reach of current AI planning systems. Sokoban is a PSPACE-complete planning task and represents one of the hardest domains for current AI planners. Even domain-specific specialized search methods fail quickly due to the exponential search complexity on hard instances. Our approach based on deep reinforcement learning augmented with a curriculum-driven method is the first one to solve hard instances within one day of training while other modern solvers cannot solve these instances within any reasonable time limit. In contrast to prior efforts, which use carefully handcrafted pruning techniques, our approach automatically uncovers domain structure. Our results reveal that deep RL provides a promising framework for solving previously unsolved AI planning problems, provided a proper training curriculum can be devised.

IJCAI Conference 2020 Conference Paper

Task-Based Learning via Task-Oriented Prediction Network with Applications in Finance

• Di Chen
• Yada Zhu
• Xiaodong Cui
• Carla Gomes

Real-world applications often involve domain-specific and task-based performance objectives that are not captured by the standard machine learning losses, but are critical for decision making. A key challenge for direct integration of more meaningful domain and task-based evaluation criteria into an end-to-end gradient-based training process is the fact that often such performance objectives are not necessarily differentiable and may even require additional decision-making optimization processing. We propose the Task-Oriented Prediction Network (TOPNet), an end-to-end learning scheme that automatically integrates task-based evaluation criteria into the learning process via a learnable surrogate loss function, which directly guides the model towards the task-based goal. A major benefit of the proposed TOPNet learning scheme lies in its capability of automatically integrating non-differentiable evaluation criteria, which makes it particularly suitable for diversified and customized task-based evaluation criteria in real-world tasks. We validate the performance of TOPNet on two real-world financial prediction tasks, revenue surprise forecasting and credit risk modeling. The experimental results demonstrate that TOPNet significantly outperforms both traditional modeling with standard losses and modeling with hand-crafted heuristic differentiable surrogate losses.

AAAI Conference 2018 Conference Paper

Efficiently Approximating the Pareto Frontier: Hydropower Dam Placement in the Amazon Basin

• Xiaojian Wu
• Jonathan Gomes-Selman
• Qinru Shi
• Yexiang Xue
• Roosevelt Garcia-Villacorta
• Elizabeth Anderson
• Suresh Sethi
• Scott Steinschneider

Real–world problems are often not fully characterized by a single optimal solution, as they frequently involve multiple competing objectives; it is therefore important to identify the so-called Pareto frontier, which captures solution trade-offs. We propose a fully polynomial-time approximation scheme based on Dynamic Programming (DP) for computing a polynomially succinct curve that approximates the Pareto frontier to within an arbitrarily small > 0 on treestructured networks. Given a set of objectives, our approximation scheme runs in time polynomial in the size of the instance and 1/. We also propose a Mixed Integer Programming (MIP) scheme to approximate the Pareto frontier. The DP and MIP Pareto frontier approaches have complementary strengths and are surprisingly effective. We provide empirical results showing that our methods outperform other approaches in efficiency and accuracy. Our work is motivated by a problem in computational sustainability concerning the proliferation of hydropower dams throughout the Amazon basin. Our goal is to support decision-makers in evaluating impacted ecosystem services on the full scale of the Amazon basin. Our work is general and can be applied to approximate the Pareto frontier of a variety of multiobjective problems on tree-structured networks.

AAAI Conference 2018 Conference Paper

Multi-Entity Dependence Learning With Rich Context via Conditional Variational Auto-Encoder

• Luming Tang
• Yexiang Xue
• Di Chen
• Carla Gomes

Multi-Entity Dependence Learning (MEDL) explores conditional correlations among multiple entities. The availability of rich contextual information requires a nimble learning scheme that tightly integrates with deep neural networks and has the ability to capture correlation structures among exponentially many outcomes. We propose MEDL CVAE, which encodes a conditional multivariate distribution as a generating process. As a result, the variational lower bound of the joint likelihood can be optimized via a conditional variational auto-encoder and trained end-to-end on GPUs. Our MEDL CVAE was motivated by two real-world applications in computational sustainability: one studies the spatial correlation among multiple bird species using the eBird data and the other models multi-dimensional landscape composition and human footprint in the Amazon rainforest with satellite images. We show that MEDL CVAE captures rich dependency structures, scales better than previous methods, and further improves on the joint likelihood taking advantage of very large datasets that are beyond the capacity of previous methods.

AAAI Conference 2018 Conference Paper

Scalable Relaxations of Sparse Packing Constraints: Optimal Biocontrol in Predator-Prey Networks

• Johan Bjorck
• Yiwei Bai
• Xiaojian Wu
• Yexiang Xue
• Mark Whitmore
• Carla Gomes

Cascades represent rapid changes in networks. A cascading phenomenon of ecological and economic impact is the spread of invasive species in geographic landscapes. The most promising management strategy is often biocontrol, which entails introducing a natural predator able to control the invading population, a setting that can be treated as two interacting cascades of predator and prey populations. We formulate and study a nonlinear problem of optimal biocontrol: optimally seeding the predator cascade over time to minimize the harmful prey population. Recurring budgets, which typically face conservation organizations, naturally leads to sparse constraints which make the problem amenable to approximation algorithms. Available methods based on continuous relaxations scale poorly, to remedy this we develop a novel and scalable randomized algorithm based on a width relaxation, applicable to a broad class of combinatorial optimization problems. We evaluate our contributions in the context of biocontrol for the insect pest Hemlock Wolly Adelgid (HWA) in eastern North America. Our algorithm outperforms competing methods in terms of scalability and solution quality and finds near-optimal strategies for the control of the HWA for fine-grained networks – an important problem in computational sustainability.

NeurIPS Conference 2018 Conference Paper

Understanding Batch Normalization

• Nils Bjorck
• Carla Gomes
• Bart Selman
• Kilian Weinberger

Batch normalization (BN) is a technique to normalize activations in intermediate layers of deep neural networks. Its tendency to improve accuracy and speed up training have established BN as a favorite technique in deep learning. Yet, despite its enormous success, there remains little consensus on the exact reason and mechanism behind these improvements. In this paper we take a step towards a better understanding of BN, following an empirical approach. We conduct several experiments, and show that BN primarily enables training with larger learning rates, which is the cause for faster convergence and better generalization. For networks without BN we demonstrate how large gradient updates can result in diverging loss and activations growing uncontrollably with network depth, which limits possible learning rates. BN avoids this problem by constantly correcting activations to be zero-mean and of unit standard deviation, which enables larger gradient steps, yields faster convergence and may help bypass sharp local minima. We further show various ways in which gradients and activations of deep unnormalized networks are ill-behaved. We contrast our results against recent findings in random matrix theory, shedding new light on classical initialization schemes and their consequences.

AAAI Conference 2017 Conference Paper

Dynamic Optimization of Landscape Connectivity Embedding Spatial-Capture-Recapture Information

• Yexiang Xue
• Xiaojian Wu
• Dana Morin
• Bistra Dilkina
• Angela Fuller
• J. Royle
• Carla Gomes

Maintaining landscape connectivity is increasingly important in wildlife conservation, especially for species experiencing the effects of habitat loss and fragmentation. We propose a novel approach to dynamically optimize landscape connectivity. Our approach is based on a mixed integer program formulation, embedding a spatial capture-recapture model that estimates the density, space usage, and landscape connectivity for a given species. Our method takes into account the fact that local animal density and connectivity change dynamically and non-linearly with different habitat protection plans. In order to scale up our encoding, we propose a sampling scheme via random partitioning of the search space using parity functions. We show that our method scales to realworld size problems and dramatically outperforms the solution quality of an expectation maximization approach and a sample average approximation approach.

NeurIPS Conference 2016 Conference Paper

Solving Marginal MAP Problems with NP Oracles and Parity Constraints

• Yexiang Xue
• Zhiyuan Li
• Stefano Ermon
• Carla Gomes
• Bart Selman

Arising from many applications at the intersection of decision-making and machine learning, Marginal Maximum A Posteriori (Marginal MAP) problems unify the two main classes of inference, namely maximization (optimization) and marginal inference (counting), and are believed to have higher complexity than both of them. We propose XOR MMAP, a novel approach to solve the Marginal MAP problem, which represents the intractable counting subproblem with queries to NP oracles, subject to additional parity constraints. XOR MMAP provides a constant factor approximation to the Marginal MAP problem, by encoding it as a single optimization in a polynomial size of the original problem. We evaluate our approach in several machine learning and decision-making applications, and show that our approach outperforms several state-of-the-art Marginal MAP solvers.

AAAI Conference 2015 Conference Paper

Learning Large-Scale Dynamic Discrete Choice Models of Spatio-Temporal Preferences with Application to Migratory Pastoralism in East Africa

• Stefano Ermon
• Yexiang Xue
• Russell Toth
• Bistra Dilkina
• Richard Bernstein
• Theodoros Damoulas
• Patrick Clark
• Steve DeGloria

Understanding spatio-temporal resource preferences is paramount in the design of policies for sustainable development. Unfortunately, resource preferences are often unknown to policy-makers and have to be inferred from data. In this paper we consider the problem of inferring agents’ preferences from observed movement trajectories, and formulate it as an Inverse Reinforcement Learning (IRL) problem. With the goal of informing policy-making, we take a probabilistic approach and consider generative models that can be used to simulate behavior under new circumstances such as changes in resource availability, access policies, or climate. We study the Dynamic Discrete Choice (DDC) models from econometrics and prove that they generalize the Max-Entropy IRL model, a widely used probabilistic approach from the machine learning literature. Furthermore, we develop SPL-GD, a new learning algorithm for DDC models that is considerably faster than the state of the art and scales to very large datasets. We consider an application in the context of pastoralism in the arid and semi-arid regions of Africa, where migratory pastoralists face regular risks due to resource availability, droughts, and resource degradation from climate change and development. We show how our approach based on satellite and survey data can accurately model migratory pastoralism in East Africa and that it considerably outperforms other approaches on a largescale real-world dataset of pastoralists’ movements in Ethiopia collected over 3 years.

AAAI Conference 2015 Conference Paper

Pattern Decomposition with Complex Combinatorial Constraints: Application to Materials Discovery

• Stefano Ermon
• Ronan Le Bras
• Santosh Suram
• John Gregoire
• Carla Gomes
• Bart Selman
• Robert van Dover

Identifying important components or factors in large amounts of noisy data is a key problem in machine learning and data mining. Motivated by a pattern decomposition problem in materials discovery, aimed at discovering new materials for renewable energy, e. g. for fuel and solar cells, we introduce CombiFD, a framework for factor based pattern decomposition that allows the incorporation of a-priori knowledge as constraints, including complex combinatorial constraints. In addition, we propose a new pattern decomposition algorithm, called AMIQO, based on solving a sequence of (mixed-integer) quadratic programs. Our approach considerably outperforms the state of the art on the materials discovery problem, scaling to larger datasets and recovering more precise and physically meaningful decompositions. We also show the effectiveness of our approach for enforcing background knowledge on other application domains.

AAAI Conference 2014 Conference Paper

Challenges in Materials Discovery – Synthetic Generator and Real Datasets

• Ronan Le Bras
• Richard Bernstein
• John Gregoire
• Santosh Suram
• Carla Gomes
• Bart Selman
• R. Bruce van Dover

Newly-discovered materials have been central to recent technological advances. They have contributed significantly to breakthroughs in electronics, renewable energy and green buildings, and overall, have promoted the advancement of global human welfare. Yet, only a fraction of all possible materials have been explored. Accelerating the pace of discovery of materials would foster technological innovations, and would potentially address pressing issues in sustainability, such as energy production or consumption. The bottleneck of this discovery cycle lies, however, in the analysis of the materials data. As materials scientists have recently devised techniques to efficiently create thousands of materials and experimentalists have developed new methods and tools to characterize these materials, the limiting factor has become the data analysis itself. Hence, the goal of this paper is to stimulate the development of new computational techniques for the analysis of materials data, by bringing together the complimentary expertise of materials scientists and computer scientists. In collaboration with two major research laboratories in materials science, we provide the first publicly available dataset for the phase map identification problem. In addition, we provide a parameterized synthetic data generator to assess the quality of proposed approaches, as well as tools for data visualization and solution evaluation.

AAAI Conference 2014 Conference Paper

Designing Fast Absorbing Markov Chains

• Stefano Ermon
• Carla Gomes
• Ashish Sabharwal
• Bart Selman

Markov Chains are a fundamental tool for the analysis of real world phenomena and randomized algorithms. Given a graph with some specified sink nodes and an initial probability distribution, we consider the problem of designing an absorbing Markov Chain that minimizes the time required to reach a sink node, by selecting transition probabilities subject to some natural regularity constraints. By exploiting the Markovian structure, we obtain closed form expressions for the objective function as well as its gradient, which can be thus evaluated efficiently without any simulation of the underlying process and fed to a gradient-based optimization package. For the special case of designing reversible Markov Chains, we show that global optimum can be efficiently computed by exploiting convexity. We demonstrate how our method can be used for the evaluation and design of local search methods tailored for certain domains.

AAAI Conference 2014 Conference Paper

Uncovering Hidden Structure through Parallel Problem Decomposition

• Yexiang Xue
• Stefano Ermon
• Carla Gomes
• Bart Selman

A key strategy for speeding up computation is to run in parallel on multiple cores. However, on hard combinatorial problems, exploiting parallelism has been surprisingly challenging. It appears that traditional divide-and-conquer strategies do not work well, due to the intricate non-local nature of the interactions between the problem variables. In this paper, we introduce a novel way in which parallelism can be used to exploit hidden structure of hard combinatorial problems. We demonstrate the success of this approach on minimal set basis problem, which has a wide range of applications in machine learning and system security, etc. We also show the effectiveness on a related application problem from materials discovery. In our approach, a large number of smaller sub-problems are identified and solved concurrently. We then aggregate the information from those solutions, and use this to initialize the search of a global, complete solver. We show that this strategy leads to a significant speed-up over a sequential approach. The strategy also greatly outperforms state-of-the-art incomplete solvers in terms of solution quality. Our work opens up a novel angle for using parallelism to solve hard combinatorial problems.

NeurIPS Conference 2013 Conference Paper

Embed and Project: Discrete Sampling with Universal Hashing

• Stefano Ermon
• Carla Gomes
• Ashish Sabharwal
• Bart Selman

We consider the problem of sampling from a probability distribution defined over a high-dimensional discrete set, specified for instance by a graphical model. We propose a sampling algorithm, called PAWS, based on embedding the set into a higher-dimensional space which is then randomly projected using universal hash functions to a lower-dimensional subspace and explored using combinatorial search methods. Our scheme can leverage fast combinatorial optimization tools as a blackbox and, unlike MCMC methods, samples produced are guaranteed to be within an (arbitrarily small) constant factor of the true probability distribution. We demonstrate that by using state-of-the-art combinatorial search tools, PAWS can efficiently sample from Ising grids with strong interactions and from software verification instances, while MCMC and variational methods fail in both cases.

AAAI Conference 2013 Conference Paper

Large Landscape Conservation — Synthetic and Real-World Datasets

• Bistra Dilkina
• Katherine Lai
• Ronan Le Bras
• Yexiang Xue
• Carla Gomes
• Ashish Sabharwal
• Jordan Suter
• Kevin McKelvey

Biodiversity underpins ecosystem goods and services and hence protecting it is key to achieving sustainability. However, the persistence of many species is threatened by habitat loss and fragmentation due to human land use and climate change. Conservation efforts are implemented under very limited economic resources, and therefore designing scalable, cost-efficient and systematic approaches for conservation planning is an important and challenging computational task. In particular, preserving landscape connectivity between good habitat has become a key conservation priority in recent years. We give an overview of landscape connectivity conservation and some of the underlying graph-theoretic optimization problems. We present a synthetic generator capable of creating families of randomized structured problems, capturing the essential features of real-world instances but allowing for a thorough typical-case performance evaluation of different solution methods. We also present two large-scale real-world datasets, including economic data on land cost, and species data for grizzly bears, wolverines and lynx.

AAAI Conference 2013 Conference Paper

Robust Network Design For Multispecies Conservation

• Ronan Le Bras
• Bistra Dilkina
• Yexiang Xue
• Carla Gomes
• Kevin McKelvey
• Michael Schwartz
• Claire Montgomery

Our work is motivated by an important network design application in computational sustainability concerning wildlife conservation. In the face of human development and climate change, it is important that conservation plans for protecting landscape connectivity exhibit certain level of robustness. While previous work has focused on conservation strategies that result in a connected network of habitat reserves, the robustness of the proposed solutions has not been taken into account. In order to address this important aspect, we formalize the problem as a node-weighted bi-criteria network design problem with connectivity requirements on the number of disjoint paths between pairs of nodes. While in most previous work on survivable network design the objective is to minimize the cost of the selected network, our goal is to optimize the quality of the selected paths within a specified budget, while meeting the connectivity requirements. We characterize the complexity of the problem under different restrictions. We provide a mixed-integer programming encoding that allows for finding solutions with optimality guarantees, as well as a hybrid local search method with better scaling behavior but no guarantees. We evaluate the typical-case performance of our approaches using a synthetic benchmark, and apply them to a large-scale real-world network design problem concerning the conservation of wolverine and lynx populations in the U. S. Rocky Mountains (Montana).

NeurIPS Conference 2012 Conference Paper

Density Propagation and Improved Bounds on the Partition Function

• Stefano Ermon
• Ashish Sabharwal
• Bart Selman
• Carla Gomes

Given a probabilistic graphical model, its density of states is a function that, for any likelihood value, gives the number of configurations with that probability. We introduce a novel message-passing algorithm called Density Propagation (DP) for estimating this function. We show that DP is exact for tree-structured graphical models and is, in general, a strict generalization of both sum-product and max-product algorithms. Further, we use density of states and tree decomposition to introduce a new family of upper and lower bounds on the partition function. For any tree decompostion, the new upper bound based on finer-grained density of state information is provably at least as tight as previously known bounds based on convexity of the log-partition function, and strictly stronger if a general condition holds. We conclude with empirical evidence of improvement over convex relaxations and mean-field based bounds.

AAAI Conference 2012 Conference Paper

From Streamlined Combinatorial Search to Efficient Constructive Procedures

• Ronan Le Bras
• Carla Gomes
• Bart Selman

In recent years, significant progress in the area of search, constraint satisfaction, and automated reasoning has been driven in part by the study of challenge problems from combinatorics and finite algebra. This work has led to the discovery of interesting discrete structures with intricate mathematical properties. While some of those results have resolved open questions and conjectures, a shortcoming is that they generally do not provide further mathematical insights, from which one could derive more general observations. We propose an approach that integrates specialized combinatorial search, using so-called streamlining, with a human computation component. We use this approach to discover efficient constructive procedures for generating certain classes of combinatorial objects of any size. More specifically, using our framework, we discovered two complementary efficient constructions for generating so-called Spatially Balanced Latin squares (SBLS) of any order N, such that 2N+1 is prime. Previously constructions for SBLSs were not known. Our approach also enabled us to derive a new lower bound for socalled weak Schur numbers, improving on a series of earlier results for Schur numbers.

AAMAS Conference 2012 Conference Paper

Probabilistic Planning with Non-Linear Utility Functions and Worst-Case Guarantees

• Stefano Ermon
• Carla Gomes
• Bart Selman
• Alexander Vladimirsky

Markov Decision Processes are one of the most widely used frameworks to formulate probabilistic planning problems. Since planners are often risk-sensitive in high-stake situations, non-linear utility functions are often introduced to describe their preferences among all possible outcomes. Alternatively, risk-sensitive decision makers often require their plans to satisfy certain worst-case guarantees. We show how to combine these two approaches by considering problems where we maximize the expected utility of the total reward subject to worst-case constraints. We generalize several existing results on the structure of optimal policies to the constrained case, both for finite and infinite horizon problems. We provide a Dynamic Programming algorithm to compute the optimal policy, and we introduce an admissible heuristic to effectively prune the search space. Finally, we use a stochastic shortest path problem on large real-world road networks to demonstrate the practical applicability of our method.

IJCAI Conference 2011 Conference Paper

A Flat Histogram Method for Computing the Density of States of Combinatorial Problems

• Stefano Ermon
• Carla Gomes
• Bart Selman

Consider a combinatorial state space S, such as the set of all truth assignments to N Boolean variables. Given a partition of S, we consider the problem of estimating the size of all the subsets in which S is divided. This problem, also known as computing the density of states, is quite general and has many applications. For instance, if we consider a Boolean formula in CNF and we partition according to the number of violated constraints, computing the density of states is a generalization of both SAT, MAXSAT and model counting. We propose a novel Markov Chain Monte Carlo algorithm to compute the density of states of Boolean formulas that is based on a flat histogram approach. Our method represents a new approach to a variety of inference, learning, and counting problems. We demonstrate its practical effectiveness by showing that the method converges quickly to an accurate solution on a range of synthetic and real-world instances.

AAMAS Conference 2011 Conference Paper

A Message Passing Approach To Multiagent Gaussian Inference for Dynamic Processes

• Stefano Ermon
• Carla Gomes
• Bart Selman

In [1], we introduced a novel distributed inference algorithm for the multiagent Gaussian inference problem, based on the framework of graphical models and message passing algorithms. We compare it to current state of the art techniques and we demonstrate that it is the most efficient one in terms of communication resources used. Moreover, we show experimentally that it outperforms the other methods in terms of estimation error on a general class of problems, even in presence of data loss.

NeurIPS Conference 2011 Conference Paper

Accelerated Adaptive Markov Chain for Partition Function Computation

• Stefano Ermon
• Carla Gomes
• Ashish Sabharwal
• Bart Selman

We propose a novel Adaptive Markov Chain Monte Carlo algorithm to compute the partition function. In particular, we show how to accelerate a flat histogram sampling technique by significantly reducing the number of ``null moves'' in the chain, while maintaining asymptotic convergence properties. Our experiments show that our method converges quickly to highly accurate solutions on a range of benchmark instances, outperforming other state-of-the-art methods such as IJGP, TRW, and Gibbs sampling both in run-time and accuracy. We also show how obtaining a so-called density of states distribution allows for efficient weight learning in Markov Logic theories.

IJCAI Conference 2011 Conference Paper

Embedding System Dynamics in Agent Based Models for Complex Adaptive Systems

• Maarika Teose
• Kiyan Ahmadizadeh
• Eoin O'Mahony
• Rebecca L. Smith
• Zhao Lu
• Stephen P. Ellner
• Carla Gomes
• Yrjo Grohn

Complex adaptive systems (CAS) are composed of interacting agents, exhibit nonlinear properties such as positive and negative feedback, and tend to produce emergent behavior that cannot be wholly explained by deconstructing the system into its constituent parts. Both system dynamics (equation-based) approaches and agent-based approaches have been used to model such systems, and each has its benefits and drawbacks. In this paper, we introduce a class of agent-based models with an embedded system dynamics model, and detail the semantics of a simulation framework for these models. This model definition, along with the simulation framework, combines agent-based and system dynamics approaches in a way that retains the strengths of both paradigms. We show the applicability of our model by instantiating it for two example complex adaptive systems in the field of Computational Sustainability, drawn from ecology and epidemiology. We then present a more detailed application in epidemiology, in which we compare a previously unstudied intervention strategy to established ones. Our experimental results, unattainable using previous methods, yield insight into the effectiveness of these intervention strategies.

TIST Journal 2011 Journal Article

Introduction to special issue on computational sustainability

• Carla Gomes
• Qiang Yang

IJCAI Conference 2011 Conference Paper

Risk-Sensitive Policies for Sustainable Renewable Resource Allocation

• Stefano Ermon
• Jon Conrad
• Carla Gomes
• Bart Selman

Markov Decision Processes arise as a natural model for many renewable resources allocation problems. In many such problems, high stakes decisions with potentially catastrophic outcomes (such as the collapse of an entire ecosystem) need to be taken by carefully balancing social, economic, and ecologic goals. We introduce a broad class of such MDP models with a risk averse attitude of the decision maker, in order to obtain policies that are more balanced with respect to the welfare of future generations. We prove that they admit a closed form solution that can be efficiently computed. We show an application of the proposed framework to the Pacific Halibut marine fishery, obtaining new and more cautious policies. Our results strengthen findings of related policies from the literature by providing new evidence that a policy based on periodic closures of the fishery should be employed, in place of the one traditionally used that harvests a constant proportion of the stock every year.

AAAI Conference 2011 Conference Paper

The Steiner Multigraph Problem: Wildlife Corridor Design for Multiple Species

• Katherine Lai
• Carla Gomes
• Michael Schwartz
• Kevin McKelvey
• David Calkin
• Claire Montgomery

The conservation of wildlife corridors between existing habitat preserves is important for combating the effects of habitat loss and fragmentation facing species of concern. We introduce the Steiner Multigraph Problem to model the problem of minimum-cost wildlife corridor design for multiple species with different landscape requirements. This problem can also model other analogous settings in wireless and social networks. As a generalization of Steiner forest, the goal is to find a minimum-cost subgraph that connects multiple sets of terminals. In contrast to Steiner forest, each set of terminals can only be connected via a subset of the nodes. Generalizing Steiner forest in this way makes the problem NP-hard even when restricted to two pairs of terminals. However, we show that if the node subsets have a nested structure, the problem admits a fixed-parameter tractable algorithm in the number of terminals. We successfully test exact and heuristic solution approaches on a wildlife corridor instance for wolverines and lynx in western Montana, showing that though the problem is computationally hard, heuristics perform well, and provably optimal solutions can still be obtained.

AAMAS Conference 2010 Conference Paper

Collaborative Multiagent Gaussian Inference in a Dynamic Environment Using Belief Propagation

• Stefano Ermon
• Carla Gomes
• Bart Selman

The problem of multiagent Gaussian inference in a dynamicenvironment, also known as distributed Kalman filtering, is formulated into the framework of message passing algorithms. Upon generalizing the derivation of the standardKalman filter to the distributed case, we propose novel solutions that outperform current state of the art techniques.

IJCAI Conference 2009 Conference Paper

• Yunsong Guo
• Carla Gomes

We propose an approach for automatically ranking structured documents applied to patent prior art search. Our model, SVM Patent Ranking (SVMPR) incorporates margin constraints that directly capture the specificities of patent citation ranking. Our approach combines patent domain knowledge features with meta-score features from several different general Information Retrieval methods. The training algorithm is an extension of the Pegasos algorithm with performance guarantees, effectively handling hundreds of thousands of patent-pair judgements in a high dimensional feature space. Experiments on a homogeneous essential wireless patent dataset show that SVMPR performs on average 30%-40% better than many other state-of-the-art general-purpose Information Retrieval methods in terms of the NDCG measure at different cut-off positions.

IJCAI Conference 2009 Conference Paper

• Yunsong Guo
• Carla Gomes

We study the problem of learning an optimal subset from a larger ground set of items, where the optimality criterion is defined by an unknown preference function. We model the problem as a discriminative structural learning problem and solve it using a Structural Support Vector Machine (SSVM) that optimizes a “set accuracy” performance measure representing set similarities. Our approach departs from previous approaches since we do not explicitly learn a pre-defined preference function. Experimental results on both a synthetic problem domain and a real-world face image subset selection problem show that our method significantly outperforms previous learning approaches for such problems.

IJCAI Conference 2007 Conference Paper

• J
• ouml; rg Hoffmann
• Carla Gomes
• Bart Selman
• Henry Kautz

Translation to Boolean satisfiability is an important approach for solving state-space reachability problems that arise in planning and verification. Many important problems, however, involve numeric variables; for example, C programs or planning with resources. Focussing on planning, we propose a method for translating such problems into propositional SAT, based on an approximation of reachable variable domains. We compare to a more direct translation into "SAT modulo theory" (SMT), that is, SAT extended with numeric variables and arithmetic constraints. Though translation to SAT generates much larger formulas, we show that it typically outperforms translation to SMT almost up to the point where the formulas don't fit into memory any longer. We also show that, even though our planner is optimal, it tends to outperform state-of-the-art sub-optimal heuristic planners in domains with tightly constrained resources. Finally we present encouraging initial results on applying the approach to model checking.

NeurIPS Conference 2006 Conference Paper

Near-Uniform Sampling of Combinatorial Spaces Using XOR Constraints

• Carla Gomes
• Ashish Sabharwal
• Bart Selman

We propose a new technique for sampling the solutions of combinatorial problems in a near-uniform manner. We focus on problems specified as a Boolean formula, i. e. , on SAT instances. Sampling for SAT problems has been shown to have interesting connections with probabilistic reasoning, making practical sampling algorithms for SAT highly desirable. The best current approaches are based on Markov Chain Monte Carlo methods, which have some practical limitations. Our approach exploits combinatorial properties of random parity (X O R) constraints to prune away solutions near-uniformly. The final sample is identified amongst the remaining ones using a state-of-the-art SAT solver. The resulting sampling distribution is provably arbitrarily close to uniform. Our experiments show that our technique achieves a significantly better sampling quality than the best alternative.

AIJ Journal 2005 Journal Article

Sensor networks and distributed CSP: communication, computation and complexity

• Ramón Béjar
• Carmel Domshlak
• Cèsar Fernández
• Carla Gomes
• Bhaskar Krishnamachari
• Bart Selman
• Magda Valls

We introduce SensorDCSP, a naturally distributed benchmark based on a real-world application that arises in the context of networked distributed systems. In order to study the performance of Distributed CSP (DisCSP) algorithms in a truly distributed setting, we use a discrete-event network simulator, which allows us to model the impact of different network traffic conditions on the performance of the algorithms. We consider two complete DisCSP algorithms: asynchronous backtracking (ABT) and asynchronous weak commitment search (AWC), and perform performance comparison for these algorithms on both satisfiable and unsatisfiable instances of SensorDCSP. We found that random delays (due to network traffic or in some cases actively introduced by the agents) combined with a dynamic decentralized restart strategy can improve the performance of DisCSP algorithms. In addition, we introduce GSensorDCSP, a plain-embedded version of SensorDCSP that is closely related to various real-life dynamic tracking systems. We perform both analytical and empirical study of this benchmark domain. In particular, this benchmark allows us to study the attractiveness of solution repairing for solving a sequence of DisCSPs that represent the dynamic tracking of a set of moving objects.

IJCAI Conference 2005 Conference Paper

Streamlining Local Search for Spatially Balanced Latin Squares

• Casey Smith
• Carla Gomes
• Cesar

Streamlined constrained reasoning powerfully boosts the performance of backtrack search methods for finding hard combinatorial objects. We use so-called spatially balanced Latin squares to show how streamlining can also be very effective for local search: Our approach is much faster and generates considerably larger spatially balanced Latin squares than previously reported approaches (up to order 35; the previous best results could only generate solutions up to order 18). We also provide a detailed characterization of our streamliner and solution topology for small orders. We believe that streamlined local search is a general technique suitable for solving a wide range of hard combinatorial design problems.