
The Best of Many Worlds: Dual Mirror Descent for Online Allocation Problems
Online allocation problems with resource constraints are central problem...
read it

Optimal Approximation – Smoothness Tradeoffs for SoftMax Functions
A softmax function has two main efficiency measures: (1) approximation ...
read it

Limiting Behaviors of NonconvexNonconcave Minimax Optimization via ContinuousTime Systems
Unlike nonconvex optimization, where gradient descent is guaranteed to c...
read it

Causal Inference with Bipartite Designs
Bipartite experiments are a recent object of study in causal inference, ...
read it

Parallel Graph Algorithms in Constant Adaptive Rounds: Theory meets Practice
We study fundamental graph problems such as graph connectivity, minimum ...
read it

Regularized Online Allocation Problems: Fairness and Beyond
Online allocation problems with resource constraints have a rich history...
read it

The Landscape of NonconvexNonconcave Minimax Optimization
Minimax optimization has become a central tool for modern machine learni...
read it

Bandits with adversarial scaling
We study "adversarial scaling", a multiarmed bandit model where rewards...
read it

Dynamic Incentiveaware Learning: Robust Pricing in Contextual Auctions
Motivated by pricing in ad exchange markets, we consider the problem of ...
read it

Contextual Reserve Price Optimization in Auctions
We study the problem of learning a linear model to set the reserve price...
read it

Adaptivity in Adaptive Submodularity
Adaptive sequential decision making is one of the central challenges in ...
read it

Fully Dynamic Matching: Beating 2Approximation in Δ^ε Update Time
In fully dynamic graphs, we know how to maintain a 2approximation of ma...
read it

NearOptimal Massively Parallel Graph Connectivity
Identifying the connected components of a graph, apart from being a fund...
read it

Batched MultiArmed Bandits with Optimal Regret
We present a simple and efficient algorithm for the batched stochastic m...
read it

Streaming Balanced Clustering
Clustering of data points in metric space is among the most fundamental ...
read it

Dynamic First Price Auctions Robust to Heterogeneous Buyers
We study dynamic mechanisms for optimizing revenue in repeated auctions,...
read it

Distributed Weighted Matching via Randomized Composable Coresets
Maximum weight matching is one of the most fundamental combinatorial opt...
read it

Massively Parallel Computation via Remote Memory Access
We introduce the Adaptive Massively Parallel Computation (AMPC) model, w...
read it

Accelerating Gradient Boosting Machine
Gradient Boosting Machine (GBM) is an extremely powerful supervised lear...
read it

Optimal Dynamic Auctions are Virtual Welfare Maximizers
We are interested in the setting where a seller sells sequentially arriv...
read it

Approximate LeaveOneOut for HighDimensional NonDifferentiable Learning Problems
Consider the following class of learning schemes: β̂ := β∈C ∑_j=1^n ℓ(x_...
read it

Contextual Bandits with Crosslearning
In the classical contextual bandits problem, in each round t, a learner ...
read it

Massively Parallel Dynamic Programming on Trees
Dynamic programming is a powerful technique that is, unfortunately, ofte...
read it

Nonmonotone Submodular Maximization with Nearly Optimal Adaptivity Complexity
As a generalization of many classic problems in combinatorial optimizati...
read it

Parallel and Streaming Algorithms for KCore Decomposition
The kcore decomposition is a fundamental primitive in many machine lear...
read it

Connected Components at Scale via Local Contractions
As a fundamental tool in hierarchical graph clustering, computing connec...
read it

Submodular Maximization with Optimal Approximation, Adaptivity and Query Complexity
As a generalization of many classic problems in combinatorial optimizati...
read it

Approximate LeaveOneOut for Fast Parameter Tuning in High Dimensions
Consider the following class of learning schemes: β̂ := _β ∑_j=1^n ℓ(x_j...
read it

Stochastic bandits robust to adversarial corruptions
We introduce a new model of stochastic bandits with adversarial corrupti...
read it

Optimizing clusterbased randomized experiments under a monotonicity assumption
Clusterbased randomized experiments are popular designs for mitigating ...
read it

Robust Repeated Auctions under Heterogeneous Buyer Behavior
We study revenue optimization in a repeated auction between a single sel...
read it

ASYMP: Faulttolerant Mining of Massive Graphs
We present ASYMP, a distributed graph processing system developed for th...
read it

Online Submodular Welfare Maximization: Greedy Beats 1/2 in Random Order
In the Submodular Welfare Maximization (SWM) problem, the input consists...
read it

Online Allocation with Traffic Spikes: Mixing Adversarial and Stochastic Models
Motivated by Internet advertising applications, online allocation proble...
read it

Coresets Meet EDCS: Algorithms for Matching and Vertex Cover on Massive Graphs
Randomized composable coresets were introduced recently as an effective ...
read it

Matroids Hitting Sets and Unsupervised Dependency Grammar Induction
This paper formulates a novel problem on graphs: find the minimal subset...
read it

Local Graph Clustering Beyond Cheeger's Inequality
Motivated by applications of largescale graph clustering, we study rand...
read it
Vahab Mirrokni
is this you? claim profile