Author name cluster

Thibaut Horel

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

6 papers

2 author rows

JMLR Journal 2021 Journal Article

Optimal Bounds between f-Divergences and Integral Probability Metrics

Rohit Agrawal
Thibaut Horel

The families of $f$-divergences (e.g. the Kullback-Leibler divergence) and Integral Probability Metrics (e.g. total variation distance or maximum mean discrepancies) are widely used to quantify the similarity between probability distributions. In this work, we systematically study the relationship between these two families from the perspective of convex duality. Starting from a tight variational representation of the $f$-divergence, we derive a generalization of the moment-generating function, which we show exactly characterizes the best lower bound of the $f$-divergence as a function of a given IPM. Using this characterization, we obtain new bounds while also recovering in a unified manner well-known results, such as Hoeffding's lemma, Pinsker's inequality and its extension to subgaussian functions, and the Hammersley-Chapman-Robbins bound. This characterization also allows us to prove new results on topological properties of the divergence which may be of independent interest. [abs] [ pdf ][ bib ] &copy JMLR 2021. ( edit, beta )

PDF Details

NeurIPS Conference 2021 Conference Paper

The CPD Data Set: Personnel, Use of Force, and Complaints in the Chicago Police Department

Thibaut Horel
Lorenzo Masoero
Raj Agrawal
Daria Roithmayr
Trevor Campbell

The lack of accessibility to data on policing has severely limited researchers’ ability to conduct thorough quantitative analyses on police activity and behavior, particularly with regard to predicting and explaining police violence. In the present work, we provide a new dataset that contains information on the personnel, activities, use of force, and complaints in the Chicago Police Department (CPD). The raw data, obtained from the CPD via a series of requests under the Freedom of Information Act (FOIA), consists of 35 unlinked, inconsistent, and undocumented spreadsheets. Our paper provides a cleaned, linked, and documented version of this data that can be reproducibly generated via open source code. We provide a detailed description of the dataset contents, the procedures for cleaning the data, and summary statistics. The data have a rich variety of uses, such as prediction (e. g. , predicting misconduct from officer traits, experience, and assigned units), network analysis (e. g. , detecting communities within the social network of officers co-listed on complaints), spatiotemporal data analysis (e. g. , investigating patterns of officer shooting events), causal inference (e. g. , tracking the effects of new disciplinary practices, new training techniques, and new oversight on complaints and use of force), and much more. Access to this dataset will enable the machine learning community to meaningfully engage with the problem of police violence.

PDF Details

STOC Conference 2020 Conference Paper

Data structures meet cryptography: 3SUM with preprocessing

Alexander Golovnev
Siyao Guo 0001
Thibaut Horel
Sunoo Park
Vinod Vaikuntanathan

This paper shows several connections between data structure problems and cryptography against preprocessing attacks. Our results span data structure upper bounds, cryptographic applications, and data structure lower bounds, as summarized next. First, we apply Fiat-Naor inversion, a technique with cryptographic origins, to obtain a data structure upper bound. In particular, our technique yields a suite of algorithms with space S and (online) time T for a preprocessing version of the N -input 3SUM problem where S 3 · T = O ( N 6 ). This disproves a strong conjecture (Goldstein et al., WADS 2017) that there is no data structure that solves this problem for S = N 2−δ and T = N 1−δ for any constant δ>0. Secondly, we show equivalence between lower bounds for a broad class of (static) data structure problems and one-way functions in the random oracle model that resist a very strong form of preprocessing attack. Concretely, given a random function F : [ N ] → [ N ] (accessed as an oracle) we show how to compile it into a function G F : [ N 2 ] → [ N 2 ] which resists S -bit preprocessing attacks that run in query time T where ST = O ( N 2−ε ) (assuming a corresponding data structure lower bound on 3SUM). In contrast, a classical result of Hellman tells us that F itself can be more easily inverted, say with N 2/3 -bit preprocessing in N 2/3 time. We also show that much stronger lower bounds follow from the hardness of kSUM. Our results can be equivalently interpreted as security against adversaries that are very non-uniform, or have large auxiliary input, or as security in the face of a powerfully backdoored random oracle. Thirdly, we give non-adaptive lower bounds for 3SUM which match the best known lower bounds for static data structure problems. Moreover, we show that our lower bound generalizes to a range of geometric problems, such as three points on a line, polygon containment, and others.

Details

ICML Conference 2020 Conference Paper

Optimal Bounds between f-Divergences and Integral Probability Metrics

Rohit Agrawal 0002
Thibaut Horel

The families of f-divergences (e. g. the Kullback-Leibler divergence) and Integral Probability Metrics (e. g. total variation distance or maximum mean discrepancies) are commonly used in optimization and estimation. In this work, we systematically study the relationship between these two families from the perspective of convex duality. Starting from a tight variational representation of the f-divergence, we derive a generalization of the moment generating function, which we show exactly characterizes the best lower bound of the f-divergence as a function of a given IPM. Using this characterization, we obtain new bounds on IPMs defined by classes of unbounded functions, while also recovering in a unified manner well-known results for bounded and subgaussian functions (e. g. Pinsker’s inequality and Hoeffding’s lemma).

Details

NeurIPS Conference 2016 Conference Paper

Maximization of Approximately Submodular Functions

Thibaut Horel
Yaron Singer

We study the problem of maximizing a function that is approximately submodular under a cardinality constraint. Approximate submodularity implicitly appears in a wide range of applications as in many cases errors in evaluation of a submodular function break submodularity. Say that $F$ is $\eps$-approximately submodular if there exists a submodular function $f$ such that $(1-\eps)f(S) \leq F(S)\leq (1+\eps)f(S)$ for all subsets $S$. We are interested in characterizing the query-complexity of maximizing $F$ subject to a cardinality constraint $k$ as a function of the error level $\eps > 0$. We provide both lower and upper bounds: for $\eps > n^{-1/2}$ we show an exponential query-complexity lower bound. In contrast, when $\eps < {1}/{k}$ or under a stronger bounded curvature assumption, we give constant approximation algorithms.

PDF Details

ICML Conference 2015 Conference Paper

Inferring Graphs from Cascades: A Sparse Recovery Framework

Jean Pouget-Abadie
Thibaut Horel

In the Graph Inference problem, one seeks to recover the edges of an unknown graph from the observations of cascades propagating over this graph. In this paper, we approach this problem from the sparse recovery perspective. We introduce a general model of cascades, including the voter model and the independent cascade model, for which we provide the first algorithm which recovers the graph’s edges with high probability and O(s log m) measurements where s is the maximum degree of the graph and m is the number of nodes. Furthermore, we show that our algorithm also recovers the edge weights (the parameters of the diffusion process) and is robust in the context of approximate sparsity. Finally we prove an almost matching lower bound of Ω(s \log m/s) and validate our approach empirically on synthetic graphs.

Details