Source author record

Mark Sellke

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Data Structures and Algorithms Machine Learning math.PR cond-mat.dis-nn math.OC Computational Complexity Computer Science and Game Theory Discrete Mathematics math-ph math.MG math.MP Multiagent Systems

Catalog footprint

Research overview

9works

12topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Cutoff for the Asymmetric Riffle Shuffle

In the Gilbert-Shannon-Reeds shuffle, a deck of $N$ cards is cut into two approximately equal parts which are then riffled uniformly at random. Bayer and Diaconis famously showed that this Markov chain undergoes cutoff in total variation after $\frac{3\log(N)}{2 \log(2)}$ shuffles. We establish cutoff for the more general asymmetric riffle shuffles in which one cuts the deck into differently sized parts before riffling. The value of the cutoff point confirms a conjecture of Lalley from 2000. Some appealing consequences are that asymmetry always slows mixing and that total variation mixing is strictly faster than separation and $L^{\infty}$ mixing.

preprint2022arXiv

First-Order Bayesian Regret Analysis of Thompson Sampling

We address online combinatorial optimization when the player has a prior over the adversary's sequence of losses. In this framework, Russo and Van Roy proposed an information-theoretic analysis of Thompson Sampling based on the information ratio, resulting in optimal worst-case regret bounds. In this paper we introduce three novel ideas to this line of work. First we propose a new quantity, the scale-sensitive information ratio, which allows us to obtain more refined first-order regret bounds (i.e., bounds of the form $\sqrt{L^*}$ where $L^*$ is the loss of the best combinatorial action). Second we replace the entropy over combinatorial actions by a coordinate entropy, which allows us to obtain the first optimal worst-case bound for Thompson Sampling in the combinatorial setting. Finally, we introduce a novel link between Bayesian agents and frequentist confidence intervals. Combining these ideas we show that the classical multi-armed bandit first-order regret bound $\tilde{O}(\sqrt{d L^*})$ still holds true in the more challenging and more general semi-bandit scenario. This latter result improves the previous state of the art bound $\tilde{O}(\sqrt{(d+m^3)L^*})$ by Lykouris, Sridharan and Tardos. Moreover we sharpen these results with two technical ingredients. The first leverages a recent insight of Zimmert and Lattimore to replace Shannon entropy with more refined potential functions in the analysis. The second is a \emph{Thresholded} Thompson sampling algorithm, which slightly modifies the original algorithm by never playing low-probability actions. This thresholding results in fully $T$ -independent regret bounds when $L^*$ is almost surely upper-bounded, which we show does not hold for ordinary Thompson sampling.

preprint2022arXiv

The Pareto Frontier of Instance-Dependent Guarantees in Multi-Player Multi-Armed Bandits with no Communication

We study the stochastic multi-player multi-armed bandit problem. In this problem, $m$ players cooperate to maximize their total reward from $K > m$ arms. However the players cannot communicate and are penalized (e.g. receive no reward) if they pull the same arm at the same time. We ask whether it is possible to obtain optimal instance-dependent regret $\tilde{O}(1/Δ)$ where $Δ$ is the gap between the $m$ -th and $m+1$ -st best arms. Such guarantees were recently achieved in a model allowing the players to implicitly communicate through intentional collisions. Surprisingly, we show that with no communication at all, such guarantees are not achievable. In fact, obtaining the optimal $\tilde{O}(1/Δ)$ regret for some values of $Δ$ necessarily implies strictly sub-optimal regret in other regimes. Our main result is a complete characterization of the Pareto optimal instance-dependent trade-offs that are possible with no communication. Our algorithm generalizes that of Bubeck, Budzinski, and the second author. As there, our algorithm succeeds even when feedback upon collision can be corrupted by an adaptive adversary, thanks to a strong no-collision property. Our lower bound is based on topological obstructions at multiple scales and is completely new.

preprint2022arXiv

The Price of Incentivizing Exploration: A Characterization via Thompson Sampling and Sample Complexity

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 recommendations. The algorithm controls the flow of information, and the information asymmetry can incentivize the agents to explore. Prior work achieves optimal regret rates up to multiplicative factors that become arbitrarily large depending on the Bayesian priors, and scale exponentially in the number of arms. A more basic problem of sampling each arm once runs into similar factors. We focus on the price of incentives: the loss in performance, broadly construed, incurred for the sake of incentive-compatibility. We prove that Thompson Sampling, a standard bandit algorithm, is incentive-compatible if initialized with sufficiently many data points. The performance loss due to incentives is therefore limited to the initial rounds when these data points are collected. The problem is largely reduced to that of sample complexity: how many rounds are needed? We address this question, providing matching upper and lower bounds and instantiating them in various corollaries. Typically, the optimal sample complexity is polynomial in the number of arms and exponential in the "strength of beliefs".

preprint2022arXiv

Tight Lipschitz Hardness for Optimizing Mean Field Spin Glasses

We study the problem of algorithmically optimizing the Hamiltonian $H_N$ of a spherical or Ising mixed $p$ -spin glass. The maximum asymptotic value $\mathsf{OPT}$ of $H_N/N$ is characterized by a variational principle known as the Parisi formula, proved first by Talagrand and in more generality by Panchenko. Recently developed approximate message passing algorithms efficiently optimize $H_N/N$ up to a value $\mathsf{ALG}$ given by an extended Parisi formula, which minimizes over a larger space of functional order parameters. These two objectives are equal for spin glasses exhibiting a no overlap gap property. However, $\mathsf{ALG} < \mathsf{OPT}$ can also occur, and no efficient algorithm producing an objective value exceeding $\mathsf{ALG}$ is known. We prove that for mixed even $p$ -spin models, no algorithm satisfying an overlap concentration property can produce an objective larger than $\mathsf{ALG}$ with non-negligible probability. This property holds for all algorithms with suitably Lipschitz dependence on the disorder coefficients of $H_N$ . It encompasses natural formulations of gradient descent, approximate message passing, and Langevin dynamics run for bounded time and in particular includes the algorithms achieving $\mathsf{ALG}$ mentioned above. To prove this result, we substantially generalize the overlap gap property framework introduced by Gamarnik and Sudan to arbitrary ultrametric forbidden structures of solutions.

preprint2020arXiv

Metrical Service Systems with Transformations

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 we call T-MSS, an algorithm maintains a point in a metric space and has to serve a sequence of requests. Each request is a map (transformation) $f_t\colon A_t\to B_t$ between subsets $A_t$ and $B_t$ of the metric space. To serve it, the algorithm has to go to a point $a_t\in A_t$ , paying the distance from its previous position. Then, the transformation is applied, modifying the algorithm's state to $f_t(a_t)$ . Such transformations can model, e.g., changes to the environment that are outside of an algorithm's control, and we therefore do not charge any additional cost to the algorithm when the transformation is applied. The transformations also allow to model requests occurring in the $k$ -taxi problem. We show that for $α$ -Lipschitz transformations, the competitive ratio is $Θ(α)^{n-2}$ on $n$ -point metrics. Here, the upper bound is achieved by a deterministic algorithm and the lower bound holds even for randomized algorithms. For the $k$ -taxi problem, we prove a competitive ratio of $\tilde O((n\log k)^2)$ . For chasing convex bodies, we show that even with contracting transformations no competitive algorithm exists. The problem T-MSS has a striking connection to the following deep mathematical question: Given a finite metric space $M$ , what is the required cardinality of an extension $\hat M\supseteq M$ where each partial isometry on $M$ extends to an automorphism? We give partial answers for special cases.

preprint2020arXiv

Online Multiserver Convex Chasing and Optimization

We introduce the problem of $k$ -chasing of convex functions, a simultaneous generalization of both the famous k-server problem in $R^d$ , and of the problem of chasing convex bodies and functions. Aside from fundamental interest in this general form, it has natural applications to online $k$ -clustering problems with objectives such as $k$ -median or $k$ -means. We show that this problem exhibits a rich landscape of behavior. In general, if both $k > 1$ and $d > 1$ there does not exist any online algorithm with bounded competitiveness. By contrast, we exhibit a class of nicely behaved functions (which include in particular the above-mentioned clustering problems), for which we show that competitive online algorithms exist, and moreover with dimension-free competitive ratio. We also introduce a parallel question of top- $k$ action regret minimization in the realm of online convex optimization. There, too, a much rougher landscape emerges for $k > 1$ . While it is possible to achieve vanishing regret, unlike the top-one action case the rate of vanishing does not speed up for strongly convex functions. Moreover, vanishing regret necessitates both intractable computations and randomness. Finally we leave open whether almost dimension-free regret is achievable for $k > 1$ and general convex losses. As evidence that it might be possible, we prove dimension-free regret for linear losses via an information-theoretic argument.

preprint2020arXiv

Optimization of Mean-field Spin Glasses

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 $p$ -spin models, namely Hamiltonians $H_N:Σ_N\to {\mathbb R}$ on the Hamming hypercube $Σ_N = \{\pm 1\}^N$ , which are defined by the property that $\{H_N({\boldsymbol σ})\}_{{\boldsymbol σ}\in Σ_N}$ is a centered Gaussian process with covariance ${\mathbb E}\{H_N({\boldsymbol σ}_1)H_N({\boldsymbol σ}_2)\}$ depending only on the scalar product $\langle {\boldsymbol σ}_1,{\boldsymbol σ}_2\rangle$ . The asymptotic value of the optimum $\max_{{\boldsymbol σ}\in Σ_N}H_N({\boldsymbol σ})$ was characterized in terms of a variational principle known as the Parisi formula, first proved by Talagrand and, in a more general setting, by Panchenko. The structure of superlevel sets is extremely rich and has been studied by a number of authors. Here we ask whether a near optimal configuration ${\boldsymbol σ}$ can be computed in polynomial time. We develop a message passing algorithm whose complexity per-iteration is of the same order as the complexity of evaluating the gradient of $H_N$ , and characterize the typical energy value it achieves. When the $p$ -spin model $H_N$ satisfies a certain no-overlap gap assumption, for any $\varepsilon>0$ , the algorithm outputs ${\boldsymbol σ}\inΣ_N$ such that $H_N({\boldsymbol σ})\ge (1-\varepsilon)\max_{{\boldsymbol σ}'} H_N({\boldsymbol σ}')$ , with high probability. The number of iterations is bounded in $N$ and depends uniquely on $\varepsilon$ . More generally, regardless of whether the no-overlap gap assumption holds, the energy achieved is given by an extended variational principle, which generalizes the Parisi formula.

preprint2020arXiv

Vertex Sparsification for Edge Connectivity

Graph compression or sparsification is a basic information-theoretic and computational question. A major open problem in this research area is whether $(1+ε)$ -approximate cut-preserving vertex sparsifiers with size close to the number of terminals exist. As a step towards this goal, we study a thresholded version of the problem: for a given parameter $c$ , find a smaller graph, which we call connectivity- $c$ mimicking network, which preserves connectivity among $k$ terminals exactly up to the value of $c$ . We show that connectivity- $c$ mimicking networks with $O(kc^4)$ edges exist and can be found in time $m(c\log n)^{O(c)}$ . We also give a separate algorithm that constructs such graphs with $k \cdot O(c)^{2c}$ edges in time $mc^{O(c)}\log^{O(1)}n$ . These results lead to the first data structures for answering fully dynamic offline $c$ -edge-connectivity queries for $c \ge 4$ in polylogarithmic time per query, as well as more efficient algorithms for survivable network design on bounded treewidth graphs.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Mark Sellke

Research overview

Is this your work?

9 publications

Cutoff for the Asymmetric Riffle Shuffle

First-Order Bayesian Regret Analysis of Thompson Sampling

The Pareto Frontier of Instance-Dependent Guarantees in Multi-Player Multi-Armed Bandits with no Communication

The Price of Incentivizing Exploration: A Characterization via Thompson Sampling and Sample Complexity

Tight Lipschitz Hardness for Optimizing Mean Field Spin Glasses

Metrical Service Systems with Transformations

Online Multiserver Convex Chasing and Optimization

Optimization of Mean-field Spin Glasses

Vertex Sparsification for Edge Connectivity

See the researcher in context

Building this map preview