Publication

Beyond Time-Average Convergence: Near-Optimal Uncoupled Online Learning via Clairvoyant Multiplicative Weights Update

Related publications (21)

Analysis of a Canonical Labeling Algorithm for the Alignment of Correlated Erdős-Rényi Graphs

Matthias Grossglauser, Negar Kiyavash, Osman Emre Dai

Graph alignment in two correlated random graphs refers to the task of identifying the correspondence between vertex sets of the graphs. Recent results have characterized the exact information-theoretic threshold for graph alignment in correlated Erdös-Rény ...

Association for Computing Machinery (ACM)2019

Walrasian Dynamics in Multi-unit Markets

Aris Filos Ratsikas

In a multi-unit market, a seller brings multiple units of a good and tries to sell them to a set of buyers that have monetary endowments. While a Walrasian equilibrium does not always exist in this model, natural relaxations of the concept that retain its ...

AAAI Press2019

On Risk Reduction in Kelly Betting Using the Conservative Expected Value

Daniel Kuhn, Napat Rujeerapaiboon

The celebrated Kelly betting strategy guarantees, with probability one, higher long-run wealth than any other causal investment strategy. However, on the way to its long-term supremacy, this strategy has a notable downfall: it typically displays high varia ...

2018

Robust Multidimensional Pricing: Separation without Regret

Daniel Kuhn, Napat Rujeerapaiboon, Cagil Kocyigit

We study a robust monopoly pricing problem with a minimax regret objective, where a seller endeavors to sell multiple goods to a single buyer, only knowing that the buyer's values for the goods range over a rectangular uncertainty set. We interpret this pr ...

2022

When Stuck, Flip a Coin : New Algorithms for Large-Scale Tasks

Slobodan Mitrovic

Many modern services need to routinely perform tasks on a large scale. This prompts us to consider the following question: How can we design efficient algorithms for large-scale computation? In this thesis, we focus on devising a general strategy to addr ...

EPFL2018

Efficient Learning from Comparisons

Lucas Maystre

Humans are comparison machines: comparing and choosing an item among a set of alternatives (such as objects or concepts) is arguably one of the most natural ways for us to express our preferences and opinions. In many applications, the analysis of data con ...

EPFL2018

Training DNNs with Hybrid Block Floating Point

Babak Falsafi, Martin Jaggi, Tao Lin, Mario Paulo Drumond Lages De Oliveira

The wide adoption of DNNs has given birth to unrelenting computing requirements, forcing datacenter operators to adopt domain-specific accelerators to train them. These accelerators typically employ densely packed full-precision floating-point arithmetic t ...

NEURAL INFORMATION PROCESSING SYSTEMS (NIPS)2018

Finding Mixed Nash Equilibria of Generative Adversarial Networks

Volkan Cevher, Ya-Ping Hsieh, Chen Liu

We reconsider the training objective of Generative Adversarial Networks (GANs) from the mixed Nash Equilibria (NE) perspective. Inspired by the classical prox methods, we develop a novel algorithmic framework for GANs via an infinite-dimensional two-player ...

2018

Partial Truthfulness in Minimal Peer Prediction Mechanisms with Limited Knowledge

Boi Faltings, Goran Radanovic

We study minimal single-task peer prediction mechanisms that have limited knowledge about agents' beliefs. Without knowing what agents' beliefs are or eliciting additional information, it is not possible to design a truthful mechanism in a Bayesian-Nash se ...

ASSOC ADVANCEMENT ARTIFICIAL INTELLIGENCE2018

New Algorithmic Paradigms for Discrete Problems using Dynamical Systems and Polynomials

Damian Mateusz Straszak

Optimization is a fundamental tool in modern science. Numerous important tasks in biology, economy, physics and computer science can be cast as optimization problems. Consider the example of machine learning: recent advances have shown that even the most s ...

EPFL2018