Seth Gilbert

Muhammad Ayaz Dzulfikar, Seth Gilbert

In Byzantine agreement with predictions each process begins with an input value and some (unreliable) prediction bits. Recently, it has been shown that with \emph{classification predictions} -- where the predictions predict each process to be honest or faulty -- Byzantine agreement can be completed more quickly than without predictions, circumventing the traditional $Ω(f)$ round lower bound. However, existing algorithms either handle limited prediction errors or send too many messages. Moreover, they all exchange $Ω(n^3)$ bits -- enough to allow the processes to approximately agree on the classifications. In fact, it almost seemed necessary to share a significant number of prediction bits if one wanted to tolerate a high number of incorrect predictions. In this paper, we show that this high level of communication (and sharing of predictions) is not inherent by developing an unauthenticated algorithm with $\tilde{O}(n^{2.5})$ communication complexity. Furthermore, with authentication, we give an algorithm with optimal $O(n^2κ)$ communication complexity (where $κ$ is a security parameter). All of our results have optimal round complexity for any number of errors in the predictions.

Shunhao Oh, Anuja Meetoo Appavoo, Seth Gilbert

Bandit-style algorithms have been studied extensively in stochastic and adversarial settings. Such algorithms have been shown to be useful in multiplayer settings, e.g. to solve the wireless network selection problem, which can be formulated as an adversarial bandit problem. A leading bandit algorithm for the adversarial setting is EXP3. However, network behavior is often repetitive, where user density and network behavior follow regular patterns. Bandit algorithms, like EXP3, fail to provide good guarantees for periodic behaviors. A major reason is that these algorithms compete against fixed-action policies, which is ineffective in a periodic setting. In this paper, we define a periodic bandit setting, and periodic regret as a better performance measure for this type of setting. Instead of comparing an algorithm's performance to fixed-action policies, we aim to be competitive with policies that play arms under some set of possible periodic patterns $F$ (for example, all possible periodic functions with periods $1,2,\cdots,P$). We propose Periodic EXP4, a computationally efficient variant of the EXP4 algorithm for periodic settings. With $K$ arms, $T$ time steps, and where each periodic pattern in $F$ is of length at most $P$, we show that the periodic regret obtained by Periodic EXP4 is at most $O\big(\sqrt{PKT \log K + KT \log |F|}\big)$. We also prove a lower bound of $Ω\big(\sqrt{PKT + KT \frac{\log |F|}{\log K}} \big)$ for the periodic setting, showing that this is optimal within log-factors. As an example, we focus on the wireless network selection problem. Through simulation, we show that Periodic EXP4 learns the periodic pattern over time, adapts to changes in a dynamic environment, and far outperforms EXP3.

Seth Gilbert, Xiao Liu, Haifeng Yu

In collaborative recommendation systems, privacy may be compromised, as users' opinions are used to generate recommendations for others. In this paper, we consider an online collaborative recommendation system, and we measure users' privacy in terms of the standard differential privacy. We give the first quantitative analysis of the trade-offs between recommendation quality and users' privacy in such a system by showing a lower bound on the best achievable privacy for any non-trivial algorithm, and proposing a near-optimal algorithm. From our results, we find that there is actually little trade-off between recommendation quality and privacy for any non-trivial algorithm. Our results also identify the key parameters that determine the best achievable privacy.