Asymptotics of boosting, greedy learning algorithms, and wireless networks

With advances in computer and information technology that generate data with increasing volume and complexity, learning from data has become a key challenge. The evolving technology also impacts the way communication networks are designed by enabling all-wireless communication between millimeter-sized sensors. Motivated by these challenges, this thesis considers problems in the areas of statistical learning and wireless communication, with a focus on fundamental limits that provide guideline for practical applications.; The first part of this work concentrates on learning algorithms based on greedy minimization of loss functions (e.g., boosting). Our first contribution is the introduction of recursive greedy algorithms. While the standard batch method as the sample size increases is to re-initialize the greedy algorithm with an arbitrary rule, the proposed procedures proceed with a composite classifier obtained earlier for smaller sample size. We prove that the recursive methods are Bayes-consistent. Experiments demonstrate the practical benefits of these methods for the practitioner who continually receives new batches of training examples or has to cope with large data sets.; Another principal finding is to generalize consistency results for boosting methods originally obtained under the assumption of independent observations to the much less restrictive case of weakly dependent observations. Our investigation is motivated by the fact that in practice observations are rarely independent; ignoring dependence can seriously undermine performance. We obtain a consistency result in which the less restricted nature of sampling is manifested through a generalized condition on the growth of a regularization parameter.; The last part of the thesis concerns fundamental limits of all-wireless networks. We concentrate on the scaling of the throughput capacity. Previous results indicate that with an increasing number of nodes, the throughput collapses to zero for immobile nodes, while it can be kept constant if the nodes move freely in the communication domain. We analyze the impact of restricting mobility on throughput scaling, and obtain a general throughput result which is a function of simple properties of the network. It is shown to capture every order of growth for the throughput, encompassing the results for immobile and fully mobile nodes as extremes.