Explore the latest research from Facebook

All Publications

August 22, 2020 Julian Mestre, Nicolas Stier
Paper

Tight approximation for the minimum bottleneck generalized matching problem

We study a problem arising in statistical analysis called the minimum bottleneck generalized matching problem that involves breaking up a population into blocks in order to carry out generalizable statistical analyses of randomized experiments.
Paper
July 1, 2020 Zhixiang Gu, Jose Moreira, David Edelsohn, Ariful Azad
Paper

Bandwidth-Optimized Parallel Algorithms for Sparse Matrix-Matrix Multiplication using Propagation Blocking

Sparse matrix-matrix multiplication (SpGEMM) is a widely used kernel in various graph, scientific computing and machine learning algorithms. It is well known that SpGEMM is a memory-bound operation, and its peak performance is expected to be bound by the memory bandwidth. Yet, existing algorithms fail to saturate the memory bandwidth, resulting in suboptimal performance under the Roofline model. In this paper, we characterize existing SpGEMM algorithms based on their memory access patterns and develop practical lower and upper bounds for SpGEMM performance.
Paper
June 9, 2020 Julian Runge, Steve Geinitz, Simon Ejdemyr
Paper

Experimentation and Performance in Advertising: An Observational Survey of Firm Practices on Facebook

It is widely assumed that firms experiment with their online advertising to identify more profitable approaches to then increase their investment in more profitable advertising, increasing their overall performance. Generalizable evidence on the actual use of such experiment-based learning by firms is sparse. The study herein addresses this shortcoming – detailing the extent to which large advertisers are utilizing experimentation along with evidence on the benefits of doing so.
Paper
June 1, 2020 Andy Newell, Sergey Pupyrev
Paper

Improved Basic Block Reordering

Basic block reordering is an important step for profile-guided binary optimization. The state-of-the-art for basic block reordering is to maximize the number of fall-through branches. However, we demonstrate that such orderings may impose suboptimal performance on instruction and I-TLB caches. We propose a new algorithm that relies on a model combining the effects of fall-through and caching behavior.
Paper
April 20, 2020 Jack Marriott, Birce Tezel, Zhang Liu, Nicolas Stier
Paper

Trajectory Optimization of Solar-Powered High-Altitude Long Endurance Aircraft

Solar-powered high-altitude long endurance aircraft that harvest and store solar energy can fly indefinitely if they are able to close a 24-hour energy cycle. Perpetual endurance is possible when energy consumption does not exceed energy storage.
Paper
February 12, 2020 Riley Murray, Christian Kroer, Alex Peysakhovich, Parikshit Shah
Paper

Robust Market Equilibria with Uncertain Preferences

In this paper, we show how concepts from classical market equilibrium can be extended to reflect such uncertainty. We show that in linear, divisible Fisher markets a robust market equilibrium (RME) always exists; this also holds in settings where buyers may retain unspent money.
Paper
November 10, 2019 Nicole Immorlica, Karthik Abinav Sankararaman, Robert Schapire, Aleksandrs Slivkins
Paper

Adversarial Bandits with Knapsacks

We consider Bandits with Knapsacks (henceforth, BwK), a general model for multi-armed bandits under supply/budget constraints. In particular, a bandit algorithm needs to solve a well-known knapsack problem: find an optimal packing of items into a limited-size knapsack. The BwK problem is a common generalization of numerous motivating examples, which range from dynamic pricing to repeated auctions to dynamic ad allocation to network routing and scheduling.
Paper
July 1, 2019 Dmitrii Avdiukhin, Sergey Pupyrev, Grigory Yaroslavtsev
Paper

Multi-Dimensional Balanced Graph Partitioning via Projected Gradient Descent

Motivated by performance optimization of large-scale graph processing systems that distribute the graph across multiple machines, we consider the balanced graph partitioning problem. Compared to most of the previous work, we study the multi-dimensional variant in which balance according to multiple weight functions is required.
Paper
June 26, 2019 Vincent Conitzer, Christian Kroer, Debmalya Panigrahi, Okke Schrijvers, Eric Sodomka, Nicolas Stier, Chris Wilkens
Paper

Pacing Equilibrium in First-Price Auction Markets

In the isolated auction of a single item, second price is often preferable to first price in properties of theoretical interest. Unfortunately, single items are rarely sold in true isolation, so considering the broader context is critical when adopting a pricing strategy. In this paper, we show that this context is important in a model centrally relevant to Internet advertising: when items (ad impressions) are individually auctioned within the context of a larger system that is managing budgets, theory offers surprising support for using a first price auction to sell each individual item.
Paper
June 13, 2019 Arjun Seshadri, Alexander Peysakhovich, Johan Ugander
Paper

Discovering Context Effects from Raw Choice Data

Many applications in preference learning assume that decisions come from the maximization of a stable utility function. Yet a large experimental literature shows that individual choices and judgements can be affected by “irrelevant” aspects of the context in which they are made. An important class of such contexts is the composition of the choice set. In this work, our goal is to discover such choice set effects from raw choice data.
Paper