pwc-archive/papers-with-abstracts huggingface dataset:
Continuous Latent Search for Combinatorial Optimization
Authors: Sergey Bartunov, Vinod Nair, Peter Battaglia, Tim Lillicrap
Date: 2020-10-17 00:00:00
Proceeding: NeurIPS Workshop LMCA 2020 12
Tasks: Combinatorial Optimization

Combinatorial optimization problems are notoriously hard because they often require enumeration of the exponentially large solution space.
  Both classical solving techniques and machine learning-based approaches usually address combinatorial optimization problems by manipulating solutions in their original discrete form.
  In contrast, we propose a framework that consists of reparametrizing the original discrete solution space into a continuous latent space in which the problem can be (approximately) solved by running continuous optimization methods.
  We achieve this by learning a surrogate function that is shaped to correlate with the original objective when the latent solution is decoded back to the original solution space.
  We show that this approach can learn efficient solution strategies and is useful as a primal heuristic inside the widely-used open-source solver SCIP.
Learning Elimination Ordering for Tree Decomposition Problem
Authors: Taras Khakhulin, Roman Schutski, Ivan Oseledets
Date: 2020-10-17 00:00:00
Proceeding: NeurIPS Workshop LMCA 2020 12
Tasks: reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL), Tree Decomposition

We propose a Reinforcement Learning-based approach to approximately solve the Tree Decomposition problem. 
Recently, it was shown that learned heuristics could successfully solve combinatorial problems. 
We establish that our approach successfully generalizes from small graphs, where an optimal Tree Decomposition can be found by exact algorithms, to large instances of practical interest, while still having very low time-to-solution.
On the other hand, the agent-based approach surpasses all classical greedy heuristics by the quality of the solution.
Neural Large Neighborhood Search
Authors: Ravichandra Addanki, Vinod Nair, Mohammad Alizadeh
Date: 2020-10-17 00:00:00
Proceeding: NeurIPS Workshop LMCA 2020 12
Tasks: Combinatorial Optimization, Deep Reinforcement Learning

Large Neighborhood Search (LNS) is a combinatorial optimization technique that works iteratively starting from a poor solution, and at each iteration searches a large set of neighbors of the current solution to find a better one. The choice of the set of neighbors to search at each iteration is crucial for LNS to be effective, and successful applications rely on problem-specific neighborhood definitions that are difficult to develop. In this work we propose NLNS, a Deep Reinforcement Learning approach to automatically learn a strong neighborhood selection policy in LNS for a given input distribution of problems. NLNS works in tandem with an existing solver that searches in each neighborhood, guiding it towards optimal solutions efficiently. We demonstrate our approach on Mixed Integer Programs (MIPs). Results on several datasets show that it is possible to learn a neighbor selection policy that allows LNS to efficiently find good solutions. We also present results for integrating the learned policy in a state-of-the-art MIP solver based on the branch-and-bound algorithm to improve its performance.
Differentiable Top-$k$ with Optimal Transport
Authors: Yujia Xie, Hanjun Dai, Minshuo Chen, Bo Dai, Tuo Zhao, Hongyuan Zha, Wei Wei, Tomas Pfister
Date: 2020-10-17 00:00:00
Proceeding: NeurIPS Workshop LMCA 2020 12
Tasks: Information Retrieval, Retrieval

The top-$k$ operation, i.e., finding the $k$ largest or smallest elements from a collection of scores, is an important model component, which is widely used in information retrieval, machine learning, and data mining.  However, if the top-$k$ operation is implemented in an algorithmic way, e.g., using bubble algorithm, the resulting model cannot be trained in an end-to-end way using prevalent gradient descent algorithms. This is because these implementations typically involve swapping indices, whose gradient cannot be computed. Moreover, the corresponding mapping from the input scores to the indicator vector of whether this element belongs to the top-$k$ set is essentially discontinuous. To address the issue, we propose a smoothed approximation, namely the SOFT (Scalable Optimal transport-based diFferenTiable) top-$k$ operator. Specifically, our SOFT top-$k$ operator approximates the output of the top-$k$ operation as the solution of an Entropic Optimal Transport (EOT) problem. The gradient of the SOFT operator can then be efficiently approximated based on the optimality conditions of EOT problem. We apply the proposed operator to the $k$-nearest neighbors and beam search algorithms, and demonstrate improved performance.
Fragment Relation Networks for Geometric Shape Assembly
Authors: Jinhwi Lee, Jungtaek Kim, Hyunsoo Chung, Jaesik Park, Minsu Cho
Date: 2020-10-17 00:00:00
Proceeding: NeurIPS Workshop LMCA 2020 12
Tasks: Object, Relation

A geometric shape is often made of multiple fragments or parts. Assembling the fragments into the target object can be viewed as an interesting combinatorial problem with a variety of applications in science and engineering. Previous related work, however, focuses on tackling limited cases, e.g., primitive fragments of identical shapes or jigsaw-style fragments of textured shapes, which greatly mitigate the combinatorial challenge. In this work we introduce a challenging problem of shape assembly with textureless fragments of arbitrary shapes and propose a learning-based approach to solving it. Given a target object and a set of candidate fragments, the proposed model learns to select one of the fragments and place it into a right place. Our model processes the candidate fragments in a permutation-equivariant manner and can generalize to cases with an arbitrary number of fragments and even with a different target object. We demonstrate our method on shape assembly tasks with different shapes and assembling scenarios.
K-plex Cover Pooling for Graph Neural Networks
Authors: Davide Bacciu, Alessio Conte, Roberto Grossi, Francesco Landolfi, Andrea Marino
Date: 2020-10-17 00:00:00
Proceeding: NeurIPS Workshop LMCA 2020 12
Tasks: Graph Classification

We introduce a novel pooling technique which borrows from classical results in graph theory that is non-parametric and generalizes well to graphs of different nature and connectivity pattern. 
Our pooling method, named KPlexPool, builds on the concepts of graph covers and $k$-plexes, i.e. pseudo-cliques where each node can miss up to $k$ links.
The experimental evaluation on molecular and social graph classification shows that KPlexPool achieves state of the art performances, supporting the intuition that well-founded graph-theoretic approaches can be effectively integrated in learning models for graphs.
Virtual Savant: learning for optimization
Authors: Renzo Massobrio, Sergio Nesmachnow, Bernabé Dorronsoro
Date: 2020-10-17 00:00:00
Proceeding: NeurIPS Workshop LMCA 2020 12
Tasks: BIG-bench Machine Learning, Combinatorial Optimization

This article describes Virtual Savant, a novel paradigm that applies machine learning to derive knowledge from previously-solved optimization problem instances in order to solve new ones in a massively-parallel fashion. Applications of Virtual Savant to two classic combinatorial optimization problems and to one real-world problem are presented and experimental results are discussed.
Neural-Driven Multi-criteria Tree Search for Paraphrase Generation
Authors: Betty Fabre, Tanguy Urvoy, Jonathan Chevelu, Damien Lolive
Date: 2020-10-17 00:00:00
Proceeding: NeurIPS Workshop LMCA 2020 12
Tasks: Diversity, Paraphrase Generation, Sentence, Text Generation

A good paraphrase is semantically similar to the original sentence but it must be also well formed, and syntactically different to ensure diversity. To deal with this trade-off, we propose to cast the paraphrase generation task as a multi-objectives search problem on the lattice of text transformations. We use BERT and GPT2 to measure respectively the semantic distance and the correctness of the candidates. We study two search algorithms: Monte-Carlo Tree Search For Paraphrase Generation (MCPG) and Pareto Tree Search (PTS) that we use to explore the huge sets of candidates generated by applying the PPDB-2.0 edition rules.  We evaluate this approach on 5 datasets and show that it performs reasonably well and that it outperforms a state-of-the-art edition-based text generation method.
Scalable Evolution Strategies Pipeline for Solving the Vehicle Routing Problem
Authors: Anonymous
Date: 2020-10-17 00:00:00
Proceeding: NeurIPS Workshop LMCA 2020 12
Tasks: Deep Reinforcement Learning, GPU, Reinforcement Learning (RL)

As a general framework for applying deep learning methods to solve a problem, Deep Reinforcement Learning (RL)  has  many  applications.  In this  paper we study Deep  RL  as  it  applies  to  the Vehicle Routing Problem (VRP). Specifically, we focus on the capacitated variant of the VRP (CVRP), in which vehicles have a maximum carrying capacity and customers have varied demands. Currently in the literature, there are quite a few papers in which researchers have applied Deep RL to the CVRP. While the methods developed are able to produce solutions to problems fairly quickly, so far, they all use GPUs to train the models, which reduces scalability. Recently, OpenAI released a study on comparing Evolution Strategies (ES) with classic Deep RL training methods, such as Policy Gradient (PG), and found that ES uses less resources and performs similarly to state-of-the-art Deep RL training methods. The main benefit of this is that ES can be trained on CPUs in parallel, which costs less than training on a GPU. In light of this, we are motivated to replace traditional RL training methods in the research  with ES for comparison.
CoCo: Learning Strategies for Online Mixed-Integer Control
Authors: Abhishek Cauligi, Preston Culbertson, Mac Schwager, Bartolomeo Stellato, Marco Pavone
Date: 2020-10-17 00:00:00
Proceeding: NeurIPS Workshop LMCA 2020 12
Tasks: Combinatorial Optimization

Mixed-integer convex programming (MICP) is a popular modeling framework for solving discrete and combinatorial optimization problems arising in various settings. Despite advances in efficient solvers for numerical optimization problems, MICPs remain challenging to solve for real-time control in applications requiring solution rates of 10-100Hz. Seeking to bridge this gap, we present an approach that leverages results from supervised learning and parametric programming to quickly solve for feasible solutions to MICPs. This approach consists of (1) an offline phase where a classifier is trained on a codebook consisting of solved MICPs and (2) an online step where the network yields candidate strategies given a new set of problem parameters. Unlike other data-driven approaches for solving MICPs, we show that our approach can tackle a broad category of problems that can be modeled as MICPs and how our framework can handle problems with a different number of discrete decision variables than the problems in the training set. Finally, we demonstrate the efficacy of our proposed approach through numerical experiments showing improved solution times and optimality compared to existing approaches for solving MICPs.
Learning Lower Bounds for Graph Exploration With Reinforcement Learning
Authors: Jorel Elmiger, Lukas Faber, Pankaj Khanchandani, Oliver Paul Richter, Roger Wattenhofer
Date: 2020-10-17 00:00:00
Proceeding: NeurIPS Workshop LMCA 2020 12
Tasks: reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL)

We explore the usage of reinforcement learning for theoretical computer science. Reinforcement learning has shown to find solutions in challenging domains such as Chess or Go. Theoretical problems, such as finding the worst possible input for an algorithm come with even more vast, combinatorial search spaces. In this paper, we look at the example of online graph exploration. Here we want to find graphs that yield a high competitive ratio for a greedy explorer. The search space consists of having every edge being either present or absent. Given there are quadratically many possible edges in a graph and each subset of edges is a possible solution, this yields unfeasibly large search spaces even for few nodes. We show experimentally how clever constraints can keep such search spaces manageable. As a result, we can learn graphs that resemble those known from literature and even improve them to yield higher competitive ratios.
Dreaming with ARC
Authors: Andrzej Banburski, Anshula Gandhi, Simon Alford, Sylee Dandekar, Sang Chin, tomaso a poggio
Date: 2020-10-17 00:00:00
Proceeding: NeurIPS Workshop LMCA 2020 12
Tasks: ARC, Object Recognition, Program Synthesis

Current machine learning algorithms are highly specialized to whatever it is they are meant to do –– e.g. playing chess, picking up objects, or object recognition.  How can we extend this to a system that could solve a wide range of problems?  We argue that this can be achieved by a modular system –– one that can adapt to solving different problems by changing only the modules chosen and the order in which those modules are applied to the problem. The recently introduced ARC (Abstraction and Reasoning Corpus) dataset serves as an excellent test of abstract reasoning. Suited to the modular approach, the tasks depend on a set of human Core Knowledge inbuilt priors. In this paper we implement these priors as the modules of our system. We combine these modules using a neural-guided program synthesis.
Towards transferring algorithm configurations across problems
Authors: Alberto Franzin, Thomas Stützle
Date: 2020-10-17 00:00:00
Proceeding: NeurIPS Workshop LMCA 2020 12

Automatic approaches for algorithm configuration and design
have received significant attention in the last years, thanks to
both the potential to obtain high performing algorithms, and
the ease for algorithm designers and practitioners.
One limitation of current methods is the need to repeat the task
for every new scenario encountered. We show how the observation of
problem-independent features of the solution landscape can enable
the use of past experiments to infer good configurations for unseen
scenarios, both in case of new instances and new problems.
As a proof of concept, we report preliminary experiments obtained when
configuring a metaheuristic with two parameters.
GalaxyTSP: A New Billion-Node Benchmark for TSP
Authors: Iddo Drori, Brandon J Kates, William R. Sickinger, Anant Girish Kharkar, Brenda Dietrich, Avi Shporer, Madeleine Udell
Date: 2020-10-17 00:00:00
Proceeding: NeurIPS Workshop LMCA 2020 12
Tasks: Scheduling, Traveling Salesman Problem

We approximate a Traveling Salesman Problem (TSP) three orders of magnitude larger than the largest known benchmark, increasing the number of nodes from millions to billions. Previously, the World TSP dataset served as the largest benchmark for TSP approximation with 1.9 million cities. The dataset we use is currently the largest catalog of stars in the Milky Way, which we call Galaxy TSP, consisting of 1.69 billion stars. We use a divide and conquer approach for approximating the TSP by splitting the problem into tiles, approximating each tile, and merging the approximations. We learn to split tiles for efficient computation. We demonstrate our approach on optimization of space telescope target scheduling.
Learning to Select Nodes in Bounded Suboptimal Conflict-Based Search for Multi-Agent Path Finding
Authors: Taoan Huang, Bistra Dilkina, Sven Koenig
Date: 2020-10-17 00:00:00
Proceeding: NeurIPS Workshop LMCA 2020 12
Tasks: Imitation Learning, Multi-Agent Path Finding

Multi-Agent Path Finding is an NP-hard problem that is difficult for current approaches to solve optimally. Research has shown that bounded suboptimal solvers, such as Enhanced Conflict-Based Search (ECBS), are more efficient than optimal solvers in finding a feasible solution with suboptimality guarantees. ECBS is a tree search algorithm that repeatedly selects  nodes from a focal list to expand the tree. In this work, we propose to use imitation learning and curriculum learning to learn node-selection strategies for different grid maps and agent sizes. We then deploy the learned models in ECBS and test their solving performance on unseen instances drawn from the same distribution as the one used in training. Our approach shows substantial improvement over the baselines on different grid maps.
Discrete Planning with Neuro-algorithmic Policies
Authors: Marin Vlastelica Pogančić, Michal Rolinek, Georg Martius
Date: 2020-10-17 00:00:00
Proceeding: NeurIPS Workshop LMCA 2020 12

Although model-based and model-free approaches to learning the control of systems have achieved impressive results on standard benchmarks, most have been shown to be lacking in their generalization capabilities. These methods usually require sampling an exhaustive amount of data from different environment configurations.

We introduce a neuro-algorithmic policy architecture with the ability to plan consisting of a model working in unison with a shortest path solver to predict trajectories with low way-costs. These policies can be trained end-to-end by blackbox differentiation. We show that this type of architecture generalizes well to unseen environment configurations.
A Seq2Seq approach to Symbolic Regression
Authors: Luca Biggio, Tommaso Bendinelli, Aurelien Lucchi, Giambattista Parascandolo
Date: 2020-10-17 00:00:00
Proceeding: NeurIPS Workshop LMCA 2020 12
Tasks: Benchmarking, regression, Symbolic Regression

Deep neural networks have proved to be powerful function approximators. The
large hypothesis space they implicitly model allows them to fit very complicated
black-box functions to the training data. However, often the data generating
process is characterized by a concise and relatively simple functional form. This
is especially true in natural sciences, where elegant physical laws govern the
behaviour of the quantities of interest. In this work, we address this dichotomy
from the perspective of Symbolic Regression (SR). In particular, we apply a
fully-convolutional seq2seq model to map numerical data to the corresponding
symbolic equations. We demonstrate the effectiveness of our approach on a large
set of mathematical expressions by providing both a qualitative and a quantitative
analysis of our results. Additionally, we release our new equation-generator Python
library in order to facilitate benchmarking and stimulate new research on SR.
Fit The Right NP-Hard Problem: End-to-end Learning of Integer Programming Constraints
Authors: Anselm Paulus, Michal Rolinek, Vít Musil, Brandon Amos, Georg Martius
Date: 2020-10-17 00:00:00
Proceeding: NeurIPS Workshop LMCA 2020 12

Bridging logical and algorithmic reasoning with modern machine learning
techniques is a fundamental challenge with potentially transformative impact.
On the algorithmic side, many NP-Hard problems can be expressed as integer
programs, in which the constraints play the role of their ``combinatorial
specification''. In this work, we aim to integrate integer programming solvers
into neural network architectures by providing loss functions for \emph{both}
the objective and the constraints. The resulting end-to-end trainable
architectures have the power of jointly extracting features from raw data and
of solving a suitable (learned) combinatorial problem with state-of-the-art
integer programming solvers. We experimentally validate our approach on
artificial datasets created from random constraints, and on solving
\textsc{Knapsack} instances from their description in natural language.
Neural Algorithms for Graph Navigation
Authors: Aaron Zweig, Nesreen Ahmed, Theodore L. Willke, Guixiang Ma
Date: 2020-10-17 00:00:00
Proceeding: NeurIPS Workshop LMCA 2020 12
Tasks: Deep Reinforcement Learning, Graph Learning, Meta-Learning, reinforcement-learning, Reinforcement Learning (RL)

The application of deep reinforcement learning (RL) to graph learning and meta-learning admits challenges from both topics.  We consider the task of one-shot, partially observed graph navigation, acknowledging and addressing the difficulties of partially observed graph environments.  In this work, we present a framework for graph meta-learning, and we propose an agent equipped with external memory and local action priors adapted to the underlying graphs.  We demonstrate the efficacy of our framework through partially-observed navigation on synthetic graphs, as well as application to partially-observed navigation on 3D meshes, showing substantially improvement in one-shot performance over baseline agents.
Combinatorial privacy: Packing splinters in polytopes at scale for private bit sums via SecureHull
Authors: Anonymous
Date: 2020-10-17 00:00:00
Proceeding: NeurIPS Workshop LMCA 2020 12

We present a scheme to obtain counts of 0’s and 1’s at a server based on private
bit streams hosted by multiple clients. The goal is to obtain this solution at the
server while maintaining privacy of client data. The bit sums need to be obtained
with respect to data from all clients; and not at a per client granularity. In our
scheme called SecureHull, we hide the private data encoded as permutations
amidst publicly shareable permutation matrices and form a secret doubly stochastic
matrix via a convex combination with secret coefficients. We exploit the nonuniqueness of the Birkhoff-von Neumann decomposition and use some remnants
of the splintering scheme to provide an unconventional secure computation method
to this private bitsum problem. This scheme does not require any private datadependent communication with the server as is ideal. We also provide lower bounds
to quantify the probability of a successful attack. We show that the lower bound can
be quadratically reduced with a linear increase in communication upto a constant.
Our solution also involves a cryptographic shuffling routine that scales linearly with
number of clients as against to the size of the datasets. The rest of the operations do
not require a cryptographic approach and are secured through our scheme thereby
benefiting its scalability.
Differentiable Optimal Adversaries for Learning Fair Representations
Authors: Anonymous
Date: 2020-10-21 00:00:00
Proceeding: NeurIPS Workshop LMCA 2020 12
Tasks: Fairness, regression, Representation Learning

Fair representation learning is an important task in many real-world domains, with the goal of finding a performant model that obeys fairness requirements. We present an adversarial representation learning algorithm that learns an informative representation while not exposing sensitive features. Our goal is to train an embedding such that it has good performance on a target task while not exposing sensitive information as measured by the performance of an optimally trained adversary. Our approach directly trains the embedding with these dual objectives in mind by implicitly differentiating through the optimal adversary's training procedure. To this end, we derive implicit gradients of the optimal logistic regression parameters with respect to the input training embeddings, and use the fully-trained logistic regression as an adversary. As a result, we are able to train a model without alternating min max optimization, leading to better training stability and improved performance. Given the flexibility of our module for differentiable programming, we evaluate the impact of using implicit gradients in two adversarial fairness-centric formulations. We present quantitative results on the trade-offs of target and fairness tasks in several real-world domains.