Tailoring nearest neighbors algorithms to boosting is an important problem. Recent papers study an approach, UNN, which provably minimizes particular convex surrogates under weak assumptions. However, numerical issues make it necessary to experimentally tweak parts of the UNN algorithm, at the possible expense of the algorithm's convergence and performance. In this paper, we propose a lightweight Newton-Raphson alternative optimizing proper scoring rules from a very broad set, and establish formal convergence rates under the boosting framework that compete with those known for UNN. To the best of our knowledge, no such boosting-compliant convergence rates were previously known in the popular Gentle Adaboost's lineage. We provide experiments on a dozen domains, including Caltech and SUN computer vision databases, comparing our approach to major families including support vector machines, (Ada)boosting and stochastic gradient descent. They support three major conclusions: (i) GNNB significantly outperforms UNN, in terms of convergence rate and quality of the outputs, (ii) GNNB performs on par with or better than computationally intensive large margin approaches, (iii) on large domains that rule out those latter approaches for computational reasons, GNNB provides a simple and competitive contender to stochastic gradient descent. Experiments include a divide-and-conquer improvement of GNNB exploiting the link with proper scoring rules optimization.

Efficient Bigdata classification requires low cost learning methods. A standard approach involves Stochastic Gradient Descent algorithm (SGD) for the minimization of the Hinge Loss in the primal space. Although complexity of Stochastic Gradient Descent is linear with the number of samples these method suffers from slow convergence. In order to cope with this issue, we propose here a Boosting Stochastic Newton Descent (BSND) method for minimization of any calibrated loss in the primal space. BSND approximates the inverse Hessian by the best low-rank approximation. We validate BSND by benchmarking it against several variants of the state-of-the-art SGD algorithm on the the large scale ImageNet and Higgs dataset. We provide further core optimization for fast convergence. The results on big data set: ImageNet and Higgs display that BSND improves significantly accuracy of the SGD baseline while being faster by orders of magnitude.

Computer-based medical systems play a very important role in medical applications because they can strongly support the physicians in the decision making process. The large amount of data nowadays available, although collected from high quality sources, usually contain irrelevant, redundant, or noisy information, suggesting that not all the training instances are useful for the classification task. To address this issue, we present here an instance selection method that, different from the existing approaches, selects in ``real-time" a subset of instances from the original training set on the basis of the information derived from each test instance to be classified. We apply our method to seven public benchmark datasets, achieving larger performances than a baseline classifier.

Several medical and biological applications face with multiclass recognition problems. Such polychotomies can be addressed by decomposition techniques, which reduce the polychotomy into a series of dichotomies and then provide the final multiclass label using a reconstruction rule. Within this framework, we present a reconstruction rule based on softmax regression, where the features of the new classification task are the crisp labels and the reliabilities of dichotomizers' classifications. The approach has been tested on six medical and biological datasets, decomposing the polychotomies via the Error-Correcting Output Code. Its performances favorably compare with those provided by other two well-known reconstruction rules both in terms of global accuracy and accuracy per class.