In this task, you are given a part of an article. Your task is to generate headline (title) for this text. Preferred headlines are under fifteen words.

[EX Q]: Consider a weighted or unweighted k-nearest neighbor graph that has been built on n data points drawn randomly according to some density p on R. We study the convergence of the shortest path distance in such graphs as the sample size tends to infinity. We prove that for unweighted kNN graphs, this distance converges to an unpleasant distance function on the underlying space whose properties are detrimental to machine learning. We also study the behavior of the shortest path distance in weighted kNN graphs.
[EX A]: Shortest path distance in random k-nearest neighbor graphs

[EX Q]: Recently there has been significant activity in developing algorithms with provable guarantees for topic modeling. In standard topic models, a topic (such as sports, business, or politics) is viewed as a probability distribution ai over words, and a document is generated by first selecting a mixture w over topics, and then generating words i.i.d. from the associated mixture Aw. Given a large collection of such documents, the goal is to recover the topic vectors and then to correctly classify new documents according to their topic mixture. In this work we consider a broad generalization of this framework in which words are no longer assumed to be drawn i.i.d. and instead a topic is a complex distribution over sequences of paragraphs. Since one could not hope to even represent such a distribution in general (even if paragraphs are given using some natural feature representation), we aim instead to directly learn a document classifier. That is, we aim to learn a predictor that given a new document, accurately predicts its topic mixture, without learning the distributions explicitly. We present several natural conditions under which one can do this efficiently and discuss issues such as noise tolerance and sample complexity in this model. More generally, our model can be viewed as a generalization of the multi-view or co-training setting in machine learning. ∗Supported in part by National Science Foundation grants CCF-1525971 and CCF-1535967. †Supported in part by National Science Foundation grant CCF-1525971 and by a Microsoft Research Graduate Fellowship and an IBM Ph.D Fellowship. ar X iv :1 61 1. 01 25 9v 1 [ cs .L G ] 4 N ov 2 01 6
[EX A]: Generalized Topic Modeling

[EX Q]: <lb>Many machine learning approaches are characterized by information constraints on how<lb>they interact with the training data. These include memory and sequential access constraints<lb>(e.g. fast first-order methods to solve stochastic optimization problems); communication con-<lb>straints (e.g. distributed learning); partial access to the underlying data (e.g. missing features<lb>and multi-armed bandits) and more. However, currently we have little understanding how such<lb>information constraints fundamentally affect our performance, independent of the learning prob-<lb>lem semantics. For example, are there learning problems where any algorithm which has small<lb>memory footprint (or can use any bounded number of bits from each example, or has certain<lb>communication constraints) will perform worse than what is possible without such constraints?<lb>In this paper, we describe how a single set of results implies positive answers to the above, for<lb>a variety of settings.
[EX A]:
Fundamental Limits of Online and Distributed Algorithms for Statistical Learning and Estimation