| Name: | Edward Xiong |
|---|---|
| Email: | eyxiong (at) mit.edu |
| Home Institution: | Massachusetts Institute of Technology |
| Project: | Truth Learning in a Social Network |
| Mentor: | Jie Gao |
| Collaborators: | William Guo |
Individuals gather information by both independent observations and communication with others in a social environment. Social Learning studies how dispersed and self-interested agents aggregate information. In this project we study whether social learning can enable truth learning. It is well known that learning can fail due to herding, where agents collectively focus on an early false consensus and ignore subsequent observations. Therefore, a general goal in social learning is to get around the issue of herding and enable truth learning. In this project we study the computational aspect of social learning with different observation models, the knowledge landscape, the environment of learning and social processes such as peer pressure, social influence, network effect as well as the existence of adversarial players.
I met with William and Professor Gao to discuss research ideas that we could explore. William and I agreed to work on sequential learning specifically, and I read some of the more important papers on the topic. William is focusing on analyzing how adversaries can impact asymptotic learning, and I'm working on further characterizing configurations which give asymptotic learning. I have been working specifically on networks described by directed acyclic graphs, or equivalently, graphs with a fixed order of signals.
Specifically, I spent some time considering how different equilibrium strategies may affect social learning. If every agent is fully rational, they can choose any strategy in the case of a tie between the two possible values of the truth; we can characterize some such strategies with a probability $p \in [0,1]$, where each agent goes with their own private signal with probability $p$. It is straightforward to construct a family of graphs which achieves asymptotic learning for any $p > 0$, but fails for $p = 0$. I believe that, given a family $\mathcal{F}$ of graphs which achieves learning for some $p \in (0, 1]$, it also achieves learning for any other value of $p \in (0, 1]$.
I also thought about how the strength of the private signals can affect learning. After reviewing the known classes of graphs which have asymptotic learning, I saw that none of these classes depended on the value of $q$, the probability that any private signal is correct. That is, all the constructed classes achieved learning for all $q > \frac[1}{2}$. Thus I conjectured that asymptotic learning is also a property independent of $q$. I spent some time working on this problem, but I didn't make too much progress.
On Tuesday, June 3, every student was required to do a short presentation on their project. Our presentation was fairly straightforward, explaining the problem and our current ideas on how to proceed.
I continued working on the same questions for most of this week. I gained a better intuition for how agents perform Bayesian inference, and we found a small graph which has different behaviors for small and large values of $q$. Working with William, I was able to construct a network which exploited this behavior to achieve learning for small $q$ but not large $q$, which is a pretty counterintuitive result.
I also spent some time working to characterize graphs which achieve random truth learning. Since we were able to find networks which exhibited very "fragile" behavior, we had the idea that adding some elements of randomness might make networks more robust against such behaviors. I reviewed some of the previous literature more carefully, and I started looking at how graphs which achieve random learning behave after making small changes; for example, I think that removing a single vertex or edge from a network might not stop asymptotic learning.
For most of the week, I was thinking about how learning networks behave under small changes. I was able to obtain a nice result showing that you can remove any vertex from a network, and it will still achieve learning. I have been working on other possible changes, such as adding or deleting edges, where it is easy to see that these deformations should almost always work. However, I'm having trouble finding a direction that will allow us to get stronger results. This is partially because it is difficult to describe agents which do Bayesian inference in a general way.
William also proved a new result about adversaries in arbitrary random networks. In this general topic regarding the robustness of learning networks, I think we could continue to make progress. Together with Professor Gao, we came up with some conjectures that seem interesting, such as whether removing bounded-degree vertices affects learning. I have been looking at the role of such vertices in networks that achieve learning, and I have also been trying to analyze how rational agents act.
Note the shortened week because of Juneteenth (observed on June 20th). We continued to work on understanding characteristics of graphs that achieve random learning. I realized that networks have a nice property in that the learning rate of a specific agent is monotonic with respect to its position in an ordering. This is a very natural argument, and I'm honestly surprised I missed it for so many weeks. It easily allowed us to improve our bound from last week about modifying a graph, and also we were able to extend this to modifying vertices in many other ways.
The intuitive reason why this argument is so useful is because on a given network, we can compare random learning under different probability distributions of orderings. For example, if we modify the behavior of a vertex, for any other vertex we can argue that its learning rate given it arrives after the modified vertex is no worse then its learning rate given that it arrives before the modified vertex.
Thus we can obtain better bounds for a variety of cases, such as adding or removing a constant number of vertices and adding or removing a constant number of edges. While this approach still runs into the same issue of not truly analyzing the rational behavior of agents, I hope to use it to gain insight onto removing small-degree vertices.
We found a counterexample that shows that small-degree vertices can be important to the learning rate of a network. In retrospect, this example is quite obvious: we can 'boost' any vertex in a given network by adding a superconstant number of edges from that vertex to new independent vertices. For example, on a complete graph $K_n$ we can do this on $\omega(1)$ vertices to achieve learning.
We realized that this idea can be used to transform any network into a learning network, so we spent a lot of time thinking about modifying graphs by adding edges. We were able to come up with a few basic lower bounds on the number of edges required to do this. For example, for sparse graphs and very dense graphs we obtained tight bounds. In the next week we'll try to figure out if there are any properties of networks that we could infer stronger bounds from. One promising idea is to try to use something related to the degree or inverse degree of vertices. I also looked into the problem of varying $q$, but made very little progress on that.
We continued working on adding edges to arbitrary networks to achieve random learning. We decided to focus on the boosting idea, since it was pretty accessible. Ultimately, Professor Gao suggested comparing this approach to the influence maximization problem, since we are essentially trying to choose a small set of vertices which are connected to most other vertices under random ordering. Since we can formulate this as a submodular function, the same argument holds where we should be able to obtain roughly a $\log n$ approximation with a greedy algorithm.
Other than that, we struggled to make much progress on the problem this week. I spent some time trying to further characterize graphs that achieve random learning, and while I have some conjectures I'm not sure if they're accessible problems (or even true!). We also tried to develop some general algorithms for boosting graphs either under random orderings or under specific orderings, but we didn't obtain anything other than the greedy approximation.
We continued working along the same lines as in the previous week. We realized that the boosting idea should indeed be near optimal (with some additional $\omega(1)$ cost), so we can use this to get a polynomial-time approximation algorithm. However, this algorithm needs access to an oracle to calculate the learning rates of individual vertices; we suspect this is likely an NP-hard problem, since previous papers on the fixed ordering problem had some hardness results.
After spending some time checking our approximation algorithm for correctness, and constructing an adversarial problem where we indeed need a learning oracle to achieve the bounds, we spent some time thinking about hardness. After reading through the paper that illustrated that a fixed ordering problem is hard, we confirmed that the same proof works for some similar results that are more relevant to our problem.
We had our final presentations this week, so I did not spend much time researching. A relatively simple result we noticed is that the induced DAG given by an ordering needs a superconstant number of vertices to learn; otherwise, there is a constant chance that all the sources do a wrong prediction and we have herding. Since the sources in the DAG are all independent, this also implies that the maximum independent set of a learning network must be large.
I also worked on hardness results this week. The randomness makes it quite tricky to come up with reductions from common NP-complete problems, such as 3SAT or vertex cover. In general, these problems require 'selecting' the values of some variables and checking whether they meet some threshold. This is hard to represent with random networks, since behaviors are averaged out and also its hard to construct gadgets with the desired correlations. I also tried an approach to calculate fixed-order learning using a random-order oracle, which seems relatively feasible.
This was the last week of the REU, so we were required to write a paper summarizing our work this summer. This took some time, so not much research was done this week. William and I are both willing to continue working on the project for the next few months, so we may solve some more problems.
After thinking about our previous condition that vertices almost always required a large number of sources in their subnetwork to learn, I start to consider possible sufficiency conditions along the same lines. I believed for some time that such vertices will necessarily learn, but William constructed a pretty clear counterxample to this conjecture. However, I still think it's possible to extract some nontrivial properties of learning networks by considering the structure of their subnetworks, and will continue working on this.
We also would like to prove some hardness results about random learning, which would tie in nicely with some of our other results. This is probably the other important direction we would like to continue working on.