William Guo

Week 0

Prior to the program starting, I did some background reading on asymptotic truth learning in social networks. Most notably, the work by Lu et al. from a previous iteration of this REU noted that ATL can be achieved so long as there exists an agent adjacent to \omega(1) independent neighbors (or technically any agent obtaining a high quality signal) that can then propogate the signal to the rest of the network. Bahar et al. analyzes a uniformly random decision ordering, under which a "celebrity graph" (bipartite graph with vastly uneven groups) can obtain ATL. In essence, the celebrities act as opinion leaders which will both obtain a high quality signal and propogate it to the rest of the network. Arieli et al. extended this by noting any graph in which each vertex has nearly-independent neighbors, known as the local learning requirement, can achieve ATl under a uniformly random decision ordering. I also briefly read up on the repeated learning settings, notably Mossel et al.

[citations to be added later]

Week 1

Entering this week, I was particularly interested in adversarial robustness of different topologies and non-Bayesian decision algorithms (weighted majority voting). I met with Prof. Jie Gao and Edward Xiong in-person for the first time, in which we discussed potential directions to take the project. I was convinced that finding weights for the weighted majority voting algorithm is equivalent to computing the CDF of a generalized Bernoulli distribution, which may be difficult to do efficiently. We then discussed pivoting to an entirely different setting, the naming game. As of writing this, I think we can push the current topic at least a little further, so I have started focused my efforts on robustness by looking at the effects of adversaries in the repeated learning setting.

There are different ways "robustness" can be defined, as seen in Bohren 2014 and Frick et al 2020, though the most similar to our setting that I read this week is perhaps Mueller-Frank 2018 in which at each iteration, an adversary can make an \epsilon-adjustment to the belief of a single agent (i.e. if the agent would have broadcasted opinion a, the adversary can change it to value in [a \pm \epsilon]). Interestingly, for any \epsilon > 0, such an adversary influencing an arbitrary agent can eventually sway a network using a DeGroot learning system to converge to any arbitrary belief, so DeGroot learning is not robust. This suggests repeated learning is surprisingly vulnerable to adversaries, though I'd believe that the adversary's power is significantly diminished in the sequential learning setting. Next week, I'll look into the effects of the graph topology on the robustness of Bayesian learners.

[more citations: Mossel et al, naming game, non-Bayesian voting algs]

Week 2

This week, I began working on sufficient conditions for adversarial robustness in the sequential learning setting. Since there wasn't much literature on this particular direction, I started with simple graphs permitting ATL under random orderings. For the celebrity graph, I noticed that in the presence of adversaries, it would be possible for the celebrities disagree with each other, which is typically impossible under a normal Bayesian setting and would confuse any Bayesian observer unaware of the presence of adversaries. Thus, I continued with the assumption that Bayesian agents are aware of the presence of adversaries, and thus can adjust their beliefs accordingly. With this in mind, and changing from picking k adversarial agents to all agents becoming adversarial independently w.p. k/n to simplify the analysis, it turns out that a variation of the improvement principle still holds in the presence of independent agents. In particular, as long as the distance of any vertex to an opinion leader is small (~o(n/k)), it still achieves a high learning rate. Moving forward, I hope to classify the diameter of random order graphs, or analyze the distance of arbitrary vertices to celebrities more specifically.

Interestingly, this implies there exist instances where agents act differently simply because of the presence of adversaries. For example, given a long chain of agents with a celebrity at one end, for a sufficiently long chain, the members at the end will assume the path to the celebrity is occluded by \geq 1 adversary and end up following their own private signal. In other words, agents near the end of the chain will follow their own independent signal instead of following the celebrity, which may actually induce ATL while the graph without adversaries would not.

In a similar vein, Edward has been working on finding graphs for which the exact value of q actually changes whether ATL is achieved or not. We found an interesting type of network where for high values of q, a large group of commoners can be dissuaded from revealing their private signals and all following a marginally stronger signal, while for low values of q, all commoners can give private signals that can be aggregated into a strong signal. A similar configuration gives a graph where for low values of q, the commoners aren't independent whereas they are for higher values of q. We hope to look into topologies/ordering assumptions that allow Bayesian commoners to be independent in weird edge cases as such.

Week 3

This week, I made a nice finding for adversarial random order networks: given a graph G with learning rate L(G) = 1 - \epsilon, the error rate in the presence of \sim k adversaries (i.e. adversaries chosen w.p. k/n) is O(\sqrt{k\epsilon}). The key combinatorial finding uses that for a random vertex ordering, the shortest path from any s to some reachable t is O(\sqrt{n}) whp. Then, so long as each vertex has in its subnetwork (set of vertices that can reach it) an ancestor with high learning rate, we only incur a (1 - k/\sqrt{n}) factor which is acceptable for k << \sqrt{n}. Indeed, since the small number of agents obtaining low learning rates are unaffected by the adversaries whp for sufficiently small k, the first few high learning rate agents are almost guaranteed to be unaffected by the adversaries, and can propogate their signal to the rest of the network.

This week, Edward and I also began chipping away at more properties of Bayesian learning. We both began working on the effect of removing/adding edges to a network, which unlike removing vertices requires a firm grasp on how Bayesian agents can improve the strength of a signal. This has proven to be quite tricky for a number of reasons, and we haven't been able to formalize much of our shared intuition. One thought I had was that in order to obtain a higher quality signal, an agent would need highly independent neighbors. However, removing an edge can actually reduce independence as follows: if two agents share a common ancestor with a learning rate similar to that of the ancestor, removing edges can weaken the signal of each agent, causing them to rely more on the ancestor's signal & increasing the probability of dependence. But interestingly, removing edges doesn't seem to harm more than 1 neighbor's dependence, which may help us bound the effect of removing random edges on any agent attempting to learn from its independent neighbors.

Independently, our group also began conjecturing properties of networks learning under random order. One interesting thought is whether low degree vertices can be removed; that is, if G learns under random order, then perhaps the k-core of G also learns under random order, k = \omega(1). Like Bayesian learning, it's been difficult to formalize our intuition, but I hope to find some more properties of random order ATL graphs in addition to shortest path lengths.

Week 4

This week, I continued characterizing graphs achieving ATL under random orderings. One would expect that agents with constant learning rates would have small degree, while agents with high learning rates would have large degree with many neighbors sharing similarly high learning rates. Indeed, agents with constant learning rate can only have constant many neighbors with learning rate \geq 1 - o(1), and generally an agent with learning rate 1 - \epsilon has at most O(\epsilon) edges to neighbors with learning rate \geq 1 - \epsilon / O(1). This directly gives us an upper bound on the connectivity of a graph achieving ATL, namely the number of edges/vertices needed to isolate all constant learning rate agents.

Regarding robustness against edge/vertex removal, Edward found a nice property that the learning rate of an agent is monotonic in its index. Using this property, one can show that k modifications (added/removed vertices or edges, potentially chosen strategically, and randomly chosen adversaries) to a graph G learning under random order with learning rate L(G) = 1 - \epsilon will still obtain learning rate at least 1 - 2k\epsilon. This is quite strong, directly improving upon our work from Weeks 2-3. The argument, though nuanced, is simple to intuit as an inherent strength of the random ordering: the first ~n/k agents in a network are w.h.p unaffected by perturbations, and by monotonicity any agent after the first n/k performs as least as well as if it were put early on in the ordering. Though the number of modifications k = o(1/\epsilon) isn't strong enough in combination with the above results, this was a critical insight in addressing the k-core conjecture from last week.

Aside, we still don't know of many graph families obtaining ATL under random orderings apart from the celebrity graphs & "egalitarian" expander graphs, so I showed that Erdos-Renyi random graphs with p \in [\omega(1/n), O(\log n)] should also work, which may be helpful for analyzing perturbations to networks learning under random orders.

Resources

6/3/25 Intro Presentation