This paper investigates the sublinear regret gu rantees of two \textit{non}-no-regret algorithms in zero-sum games:Fictitious Play, and Online Gradient Descent with \textit{constant} stepsizes. In general adversarial online learning settings, both algorithms may exhibit instability and linear regret due to no regularization (Fictitious Play) or small amounts of regularization (Gradient Descent). However, their ability to obtain tighter regret bounds in two-player zero-sum games is less understood. In this work, we obtain strong new regret guarantees for both algorithms on a class of symmetric zero-sum games that generalize the classic three-strategy Rock-Paper-Scissors to a weighted, $n$-dimensional regime. Under \textit{symmetric initializations} of the players’ strategies, we prove that Fictitious Play with \textit{any tiebreaking rule} has $O(\sqrt{T})$ regret, establishing a new class of games for which Karlin’s Fictitious Play conjecture holds. Moreover, by leveraging a connection between the geometry of the iterates of Fictitious Play and Gradient Descent in the dual space of payoff vectors, we prove that Gradient Descent, for \textit{almost all} symmetric initializations, obtains a similar $O(\sqrt{T})$ regret bound when its stepsize is a \textit{sufficiently large} constant. For Gradient Descent, this establishes the first “fast and furious” behavior (i.e., sublinear regret \textit{without} time-vanishing stepsizes) for zero-sum games larger than $2\times2$.

This paper studies the *optimistic* variant of Fictitious Play for learning in two-player zero-sum games. While it is known that Optimistic FTRL -- a *regularized* algorithm with a bounded stepsize parameter -- obtains constant regret in this setting, we show for the first time that similar, optimal rates are also achievable *without* regularization: we prove for two-strategy games that Optimistic Fictitious Play (using *any* tiebreaking rule) obtains only *constant regret*, providing surprising new evidence on the ability of *non*-no-regret algorithms for fast learning in games. Our proof technique leverages a geometric view of Optimistic Fictitious Play in the dual space of payoff vectors, where we show a certain energy function of the iterates remains bounded over time. Additionally, we also prove a regret *lower bound* of $\Omega(\sqrt{T})$ for *Alternating* Fictitious Play. In the unregularized regime, this separates the ability of optimism and alternation in achieving $o(\sqrt{T})$ regret.

We initiate the study of game dynamics in the population protocol model: n agents each maintain a current local strategy and interact in pairs uniformly at random. Upon each interaction, the agents play a two-person game and receive a payoff from an underlying utility function, and they can subsequently update their strategies according to a fixed local algorithm. In this setting, we ask how the distribution over agent strategies evolves over a sequence of interactions, and we introduce a new distributional equilibrium concept to quantify the quality of such distributions. As an initial example, we study a class of repeated prisoner's dilemma games, and we consider a family of simple local update algorithms that yield non-trivial dynamics over the distribution of agent strategies. We show that these dynamics are related to a new class of high-dimensional Ehrenfest random walks, and we derive exact characterizations of their stationary distributions, bounds on their mixing times, and prove their convergence to approximate distributional equilibria. Our results highlight trade-offs between the local state space of each agent, and the convergence rate and approximation factor of the underlying dynamics. Our approach opens the door towards the further characterization of equilibrium computation for other classes of games and dynamics in the population setting.

We analyze the convergence of the k-opinion Undecided State Dynamics (USD) in the population protocol model. For k=2 opinions it is well known that the USD reaches consensus with high probability within O(n log n) interactions. Proving that the process also quickly solves the consensus problem for k > 2 opinions has remained open, despite analogous results for larger k in the related parallel gossip model. In this paper we prove such convergence: under mild assumptions on k and on the initial number of undecided agents we prove that the USD achieves plurality consensus within O(kn log n) interactions with high probability, regardless of the initial bias. Moreover, if there is an initial additive bias of at least Ω (√n log n) we prove that the initial plurality opinion wins with high probability, and if there is a multiplicative bias the convergence time is further improved. Note that this is the first result for k > 2 for the USD in the population protocol model. Furthermore, it is the first result for the unsynchronized variant of the USD with k > 2 which does not need any initial bias.

The Maximal Information Coefficient (MIC) is a powerful statistic to identify dependencies between variables. However, it may be applied to sensitive data, and publishing it could leak private information. As a solution, we present algorithms to approximate MIC in a way that provides differential privacy. We show that the natural application of the classic Laplace mechanism yields insufficient accuracy. We therefore introduce the MICr statistic, which is a new MIC approximation that is more compatible with differential privacy. We prove MICr is a consistent estimator for MIC, and we provide two differentially private versions of it. We perform experiments on a variety of real and synthetic datasets. The results show that the private MICr statistics significantly outperform direct application of the Laplace mechanism. Moreover, experiments on real-world datasets show accuracy that is usable when the sample size is at least moderately large.

A method to improve protein function prediction for sparsely annotated PPI networks is introduced. The method extends the DSD majority vote algorithm introduced by Cao et al. to give confidence scores on predicted labels and to use predictions of high confidence to predict the labels of other nodes in subsequent rounds. We call this a majority vote cascade. Several cascade variants are tested in a stringent cross-validation experiment on PPI networks from S. cerevisiae and D. melanogaster, and we show that for many different settings with several alternative confidence functions, cascading improves the accuracy of the predictions. A list of the most confident new label predictions in the two networks is also reported. Code and networks for the cross-validation experiments appear at http://bcb.cs.tufts.edu/cascade.

Population protocols are a class of algorithms for modeling distributed computation in networks of finite-state agents communicating through pairwise interactions. Their suitability for analyzing numerous chemical processes has motivated the adaptation of the original population protocol framework to better model these chemical systems. In this paper, we further the study of two such adaptations in the context of solving approximate majority: persistent-state agents (or catalysts) and spontaneous state changes (or leaks). Based on models considered in recent protocols for populations with persistent-state agents, we assume a population with $n$ catalytic input agents and $m$ worker agents, and the goal of the worker agents is to compute some predicate over the states of the catalytic inputs. We call this model the Catalytic Input (CI) model. For $m = Θ(n)$, we show that computing the exact majority of the input population with high probability requires at least $Ω(n^2)$ total interactions, demonstrating a strong separation between the CI model and the standard population protocol model. On the other hand, we show that the simple third-state dynamics of Angluin et al. for approximate majority in the standard model can be naturally adapted to the CI model: we present such a constant-state protocol for the CI model that solves approximate majority in $O(n \log n)$ total steps w.h.p. when the input margin is $Ω(\sqrt{n \log n})$. We then show the robustness of third-state dynamics protocols to the transient leaks events introduced by Alistarh et al. In both the original and CI models, these protocols successfully compute approximate majority with high probability in the presence of leaks occurring at each step with probability $β\leq O\left(\sqrt{n \log n}/n\right)$, exhibiting a resilience to leaks similar to that of Byzantine agents in previous works.