17 accepted papers
We propose a novel method for learning time-varying graphs from time-series data by leveraging techniques from directed acyclic graph (DAG) learning. The unknown graphs are parameterized with a time-varying structural vector autoregression model (SVAR), which we view as a linear structural equation…
We introduce SpinSVAR, a novel method for estimating a (linear) structural vector autoregression (SVAR) from time-series data under a sparse input assumption. Unlike prior approaches using Gaussian noise, we model the input as independent and identically distributed (i.i.d.) Laplacian variables, enf
We propose a novel and general method to learn Bregman divergences from raw high-dimensional data that measure similarity between images in pixel space. As a prototypical application, we learn divergences that consider real-world corruptions of images (e.g., blur) as close to the original and noisy…
In this paper we port assumptions and techniques from DAG (directed acyclic graph) learning and causal inference to time-series graph data. In particular, we view such data as indexed by a DAG obtained by unrolling the graph in time and generated by a causal linear structural equation model (SEM) fr…
We present a novel perspective and algorithm for learning directed acyclic graphs (DAGs) from data generated by a linear structural equation model (SEM). First, we show that a linear SEM can be viewed as a linear transform that, in prior work, computes the data from a dense input vector of random va…
We propose a novel definition of total variation (TV) specifically defined for directed acyclic graphs (DAGs). It is a generalization of the classical definition for discrete-time signals (noting that discrete-time is a DAG) and obtained by inverting an integration operator on DAGs, leveraging the t…
Recent advances in Fourier analysis have brought new tools to efficiently represent and learn set functions. In this paper, we bring the power of Fourier analysis to the design of combinatorial auctions (CAs). The key idea is to approximate bidders' value functions using Fourier-sparse set functions…
Many applications of machine learning on discrete domains, such as learning preference functions in recommender systems or auctions, can be reduced to estimating a set function that is sparse in the Fourier domain. In this work, we present a new family of algorithms for learning Fourier-sparse set f…
Recent work introduced a framework for signal processing (SP) on meet/join lattices. Such a lattice is partially ordered and supports a meet (or join) operation that returns the greatest lower bound and the smallest upper bound of two elements, respectively. Lattices appear in various domains and ca…
Graph signal processing on directed graphs poses theoretical challenges since an eigendecomposition of filters is in general not available. Instead, Fourier analysis requires a Jordan decomposition and the frequency response is given by the Jordan normal form, whose computation is numerically unstab…
We introduce a novel discrete signal processing framework, called discrete-lattice SP, for signals indexed by a finite lattice. A lattice is a partially ordered set that supports a meet (or join) operation that returns the greatest element below two given elements. Discrete-lattice SP chooses the me…
We propose a new parametric framework, called k-ReLU, for computing precise and scalable convex relaxations used to certify neural networks. The key idea is to approximate the output of multiple ReLUs in a layer jointly instead of separately. This joint relaxation captures dependencies between the i…
We present a novel approach for the certification of neural networks against adversarial perturbations which combines scalable overapproximation methods with precise (mixed integer) linear programming. This results in significantly better precision than state-of-the-art verifiers on challenging feed…
The Walsh-Hadamard transform (WHT) is computed using a network of butterflies, similar to the fast Fourier transform. The network is not unique but can be modified in exponentially many ways by properly changing the permutations between butterfly stages. Our first contribution is the exact char-acte…
We present a novel class of convolutional neural networks (CNNs) for set functions, i.e., data indexed with the powerset of a finite set. The convolutions are derived as linear, shift-equivariant functions for various notions of shifts on set functions. The framework is fundamentally different fro…
A set function associates a real (or complex) value with every subset of a given finite set S. In this paper, we derive a novel discrete signal processing (DSP) framework for such functions. This means we define and derive suitable notions of basic DSP concepts including shift, filtering, frequency…
We present a new method and system, called DeepZ, for certifying neural network robustness based on abstract interpretation. Compared to state-of-the-art automated verifiers for neural networks, DeepZ: (i) handles ReLU, Tanh and Sigmoid activation functions, (ii) supports feedforward and convolution…