Search for: All records

We investigate a simple model for social learning with two agents: a teacher and a student. The teacher’s goal is to teach the student the state of the world Theta, however, the teacher herself is not certain about Theta and needs to simultaneously learn it and teach it to the student. We model the teacher’s and the student’s uncertainty via binary symmetric channels, and employ a simple heuristic decoder at the student’s end. We focus on two teaching strategies: a "low effort" strategy of simply forwarding information, and a "high effort" strategy of communicating the teacher’s current best estimate of Theta at each time instant. Using tools from large deviation theory, we calculate the exact learning rates for these strategies and demonstrate regimes where the low effort strategy outperforms the high effort strategy. Our primary technical contribution is a detailed analysis of the large deviation properties of the sign of a transient Markov random walk on the integers. 

We study the problem of finding the maximum of a function defined on the nodes of a connected graph. The goal is to identify a node where the function obtains its maximum. We focus on local iterative algorithms, which traverse the nodes of the graph along a path, and the next iterate is chosen from the neighbors of the current iterate with probability distribution determined by the function values at the current iterate and its neighbors. We study two algorithms corresponding to a Metropolis-Hastings random walk with different transition kernels: (i) The first algorithm is an exponentially weighted random walk governed by a parameter gamma. (ii) The second algorithm is defined with respect to the graph Laplacian and a smoothness parameter k. We derive convergence rates for the two algorithms in terms of total variation distance and hitting times. We also provide simulations showing the relative convergence rates of our algorithms in comparison to an unbiased random walk, as a function of the smoothness of the graph function. Our algorithms may be categorized as a new class of “descent-based” methods for function maximization on the nodes of a graph.