130 citations · 209 across the 59 of their papers we have counts for
10 papers · 1 filter
Cooperative and Stochastic Multi-Player Multi-Armed Bandit: Optimal Regret With Neither Communication Nor Collisions
Sébastien Bubeck, Thomas Budzinski, Mark Sellke
We consider the cooperative multi-player version of the stochastic multi-armed bandit problem. We study the regime where the players cannot communicate but have access to shared ra…
Metric Transforms and Low Rank Matrices via Representation Theory of the Real Hyperrectangle
Josh Alman, Timothy Chu, Gary Miller +3
In this paper, we develop a new technique which we call representation theory of the real hyperrectangle, which describes how to compute the eigenvectors and eigenvalues of certain…
Algorithmic pure states for the negative spherical perceptron
Ahmed El Alaoui, Mark Sellke
We consider the spherical perceptron with Gaussian disorder. This is the set of points on the sphere of radius satisfying $\langle g_a , σ\rangle…
Metrical Service Systems with Transformations
Sébastien Bubeck, Niv Buchbinder, Christian Coester +1
We consider a generalization of the fundamental online metrical service systems (MSS) problem where the feasible region can be transformed between requests. In this problem, which…
Approximate Ground States of Hypercube Spin Glasses are Near Corners
Mark Sellke
We show that with probability exponentially close to , all near-maximizers of any mean-field mixed -spin glass Hamiltonian on the hypercube are near a corner. This…
Vertex Sparsification for Edge Connectivity
Parinya Chalermsook, Syamantak Das, Bundit Laekhanukit +5
Graph compression or sparsification is a basic information-theoretic and computational question. A major open problem in this research area is whether -approximate cut-prese…
Online Multiserver Convex Chasing and Optimization
Sébastien Bubeck, Yuval Rabani, Mark Sellke
We introduce the problem of -chasing of convex functions, a simultaneous generalization of both the famous k-server problem in , and of the problem of chasing convex bodies…
Covering With Tensor Products and Powers
Mark Sellke
We study when a tensor product of irreducible representations of the symmetric group contains all irreducibles as subrepresentations; we say such a tensor product covers $\ma…
The Price of Incentivizing Exploration: A Characterization via Thompson Sampling and Sample Complexity
Mark Sellke, Aleksandrs Slivkins
We consider incentivized exploration: a version of multi-armed bandits where the choice of arms is controlled by self-interested agents, and the algorithm can only issue recommenda…
Optimization of Mean-field Spin Glasses
Ahmed El Alaoui, Andrea Montanari, Mark Sellke
Mean-field spin glasses are families of random energy functions (Hamiltonians) on high-dimensional product spaces. In this paper we consider the case of Ising mixed -spin models…