196 citations · 319 across the 19 of their papers we have counts for
24 papers
Regret Bounds for Batched Bandits
Hossein Esfandiari, Amin Karbasi, Abbas Mehrabian +1
We present simple and efficient algorithms for the batched stochastic multi-armed bandit and batched stochastic linear bandit problems. We prove bounds for their expected regrets t…
Old Dog Learns New Tricks: Randomized UCB for Bandit Problems
Sharan Vaswani, Abbas Mehrabian, Audrey Durand +1
We propose , a bandit strategy that builds on theoretically derived confidence intervals similar to upper confidence bound (UCB) algorithms, but akin to Thompson sampl…
A Practical Algorithm for Multiplayer Bandits when Arm Means Vary Among Players
Etienne Boursier, Emilie Kaufmann, Abbas Mehrabian +1
We study a multiplayer stochastic multi-armed bandit problem in which players cannot communicate, and if two or more players pull the same arm, a collision occurs and the involved…
The total variation distance between high-dimensional Gaussians with the same mean
Luc Devroye, Abbas Mehrabian, Tommy Reddad
Given two high-dimensional Gaussians with the same mean, we prove a lower and an upper bound for their total variation distance, which are within a constant factor of one another.
Multiplayer bandits without observing collision information
Gabor Lugosi, Abbas Mehrabian
We study multiplayer stochastic multi-armed bandit problems in which the players cannot communicate and if two or more players pull the same arm, a collision occurs and the involve…
The Minimax Learning Rates of Normal and Ising Undirected Graphical Models
Luc Devroye, Abbas Mehrabian, Tommy Reddad
Let be an undirected graph with edges and vertices. We show that -dimensional Ising models on can be learned from i.i.d. samples within expected total variat…
Some techniques in density estimation
Hassan Ashtiani, Abbas Mehrabian
Density estimation is an interdisciplinary topic at the intersection of statistics, theoretical computer science and machine learning. We review some old and new techniques for bou…
Tight Load Balancing via Randomized Local Search
Petra Berenbrink, Peter Kling, Christopher Liaw +1
We consider the following balls-into-bins process with bins and balls: each ball is equipped with a mutually independent exponential clock of rate 1. Whenever a ball's cloc…
Sample-Efficient Learning of Mixtures
Hassan Ashtiani, Shai Ben-David, Abbas Mehrabian
We consider PAC learning of probability distributions (a.k.a. density estimation), where we are given an i.i.d. sample generated from an unknown target distribution, and want to ou…
The string of diamonds is nearly tight for rumour spreading
Omer Angel, Abbas Mehrabian, Yuval Peres
For a rumour spreading protocol, the spread time is defined as the first time that everyone learns the rumour. We compare the synchronous push&pull rumour spreading protocol with i…
Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networks
Peter L. Bartlett, Nick Harvey, Chris Liaw +1
We prove new upper and lower bounds on the VC-dimension of deep neural networks with the ReLU activation function. These bounds are tight for almost the entire range of parameters.…
Rumours spread slowly in a small world spatial network
Jeannette Janssen, Abbas Mehrabian
Rumour spreading is a protocol for modelling the spread of information through a network via user-to-user interaction. The Spatial Preferred Attachment (SPA) model is a random grap…
A simple tool for bounding the deviation of random matrices on geometric sets
Christopher Liaw, Abbas Mehrabian, Yaniv Plan +1
Let be an isotropic, sub-gaussian matrix. We prove that the process has sub-gaussian increments. Using this, we show that for a…
On the push&pull protocol for rumour spreading
Huseyin Acan, Andrea Collevecchio, Abbas Mehrabian +1
The asynchronous push&pull protocol, a randomized distributed algorithm for spreading a rumour in a graph , works as follows. Independent Poisson clocks of rate 1 are associated…
Randomized Rumor Spreading in Poorly Connected Small-World Networks
Abbas Mehrabian, Ali Pourmiri
Push-Pull is a well-studied round-robin rumor spreading protocol defined as follows: initially a node knows a rumor and wants to spread it to all nodes in a network quickly. In eac…
Justifying the small-world phenomenon via random recursive trees
Abbas Mehrabian
We present a new technique for proving logarithmic upper bounds for diameters of evolving random graph models, which is based on defining a coupling between random graphs and varia…
It's a Small World for Random Surfers
Abbas Mehrabian, Nick Wormald
We prove logarithmic upper bounds for the diameters of the random-surfer Webgraph model and the PageRank-based selection Webgraph model, confirming the small world phenomenon holds…
Longest paths in random Apollonian networks and largest -ary subtrees of random -ary recursive trees
Andrea Collevecchio, Abbas Mehrabian, Nick Wormald
Let and be positive integers with . Consider a random -ary tree constructed as follows. Start with a single vertex, and in each time-step choose a uniformly random…
On the Stretch Factor of Randomly Embedded Random Graphs
Abbas Mehrabian, Nick Wormald
We consider a random graph G(n,p) whose vertex set V has been randomly embedded in the unit square and whose edges are given weight equal to the geometric distance between their en…
On a Bounded Budget Network Creation Game
Shayan Ehsani, Saber Shokat Fadaee, MohammadAmin Fazli +4
We consider a network creation game in which each player (vertex) has a fixed budget to establish links to other players. In our model, each link has unit price and each agent trie…
On the density of nearly regular graphs with a good edge-labelling
Abbas Mehrabian
A good edge-labelling of a simple graph is a labelling of its edges with real numbers such that, for any ordered pair of vertices (u,v), there is at most one nondecreasing path fro…
Cops and Robber Game with a Fast Robber on Expander Graphs and Random Graphs
Abbas Mehrabian
We consider a variant of the Cops and Robber game, in which the robber has unbounded speed, i.e. can take any path from her vertex in her turn, but she is not allowed to pass throu…
The capture time of grids
Abbas Mehrabian
We consider the game of Cops and Robber played on the Cartesian product of two trees. Assuming the players play perfectly, it is shown that if there are two cops in the game, then…
Lower Bounds for the Cop Number When the Robber is Fast
Abbas Mehrabian
We consider a variant of the Cops and Robbers game where the robber can move t edges at a time, and show that in this variant, the cop number of a d-regular graph with girth larger…