[YPNG] YPNG, Friday 22 July 2016

Sekhar Tatikonda sekhar.tatikonda at yale.edu
Mon Jul 18 20:59:43 EDT 2016

Hi Folks,

Sabyasachi will talk in the YPNG seminar this Friday:

On Estimation in Tournaments and Graphs under monotonicity constraints

Abstract: We consider the problem of estimating the probability matrix
governing a tournament or linkage in graphs. We assume that the probability
matrix satisfies natural monotonicity constraints after being permuted in
both rows and columns by the same latent permutation. The minimax rates of
estimation for this problem under a mean squared error loss turns out to be
O(1/n) upto logarithmic factors. This minimax rate is achieved by the
overall least squares estimate which is perhaps impractical to compute
because of the need to optimize over the set of all permutations.
Therefore, we investigate in detail a simple two stage estimator which is
computationally tractable. We prove that the maximum squared error risk of
our estimator scales like O(1/√n) up to log factors. In addition, we prove
an automatic adaptation property of our estimator, meaning that the risk of
our estimator scales like O(1/n) upto log factors for several sub classes
of our parameter space which are of natural interest. These sub classes
include probability matrices satisfying appropriate notions of smoothness,
and subsume the popular Bradley Terry Model in the tournament case and the
β model and Stochastic Block Models with monotonicity, in the graph case.

See you Friday in the Stat's classroom.

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.yale.edu/pipermail/ypng/attachments/20160718/1bc741a0/attachment.html 

More information about the YPNG mailing list