BEGIN:VCALENDAR VERSION:2.0 PRODID:-//wp-events-plugin.com//7.2.3.1//EN BEGIN:VEVENT UID:371@lincs.fr DTSTART;TZID=Europe/Paris:20180514T143000 DTEND;TZID=Europe/Paris:20180514T150000 DTSTAMP:20180515T060443Z URL:https://www.lincs.fr/events/on-graph-reconstruction-via-empirical-risk -minimization/ SUMMARY:On graph reconstruction via empirical risk minimization DESCRIPTION:The problem of predicting connections between a set of data points finds many applications\, in systems biology and social network analysis among others. We focus on the graph reconstruction problem\, where the prediction rule is obtained by minimizing the average error over all n(n-1)/2 possible pairs of the n nodes of a training graph. Our first contribution is to derive learning rates of order O(log n / n) for this problem\, significantly improving upon the slow rates of order O(1/?n) established in the seminal work of Biau &\; Bleakley (2006). Strikingly\, these fast rates are universal\, in contrast to similar results known for other statistical learning problems (e.g.\, classification\, density level set estimation\, ranking\, clustering) which require strong assumptions on the distribution of the data. Motivated by applications to large graphs\, our second contribution deals with the computational complexity of graph reconstruction. Specifically\, we investigate to which extent the learning rates can be preserved when replacing the empirical reconstruction risk by a computationally cheaper Monte-Carlo version\, obtained by sampling with replacement B <\;<\; n2 pairs of nodes. Finally\, we illustrate our theoretical results by numerical experiments on synthetic and real graphs. CATEGORIES:Seminars,Youtube LOCATION:LINCS / EIT Digital\, 23 avenue d'Italie\, 75013 Paris\, France X-APPLE-STRUCTURED-LOCATION;VALUE=URI;X-ADDRESS=23 avenue d'Italie\, 75013 Paris\, France;X-APPLE-RADIUS=100;X-TITLE=LINCS / EIT Digital:geo:0,0 END:VEVENT BEGIN:VTIMEZONE TZID:Europe/Paris X-LIC-LOCATION:Europe/Paris BEGIN:DAYLIGHT DTSTART:20180325T030000 TZOFFSETFROM:+0100 TZOFFSETTO:+0200 TZNAME:CEST END:DAYLIGHT END:VTIMEZONE END:VCALENDAR