We consider the problem of estimating a regularization parameter, or shrinkage coefficient α ∈ (0, 1) for regularized Tyler M-estimators (RTME). In particular, we propose a data-dependent approach for estimating an optimal α based on maximizing a suitably chosen leave-one-out cross-validated (LOOCV) likelihood function. Since the LOOCV approach scales linearly with the number of samples n and hence is computationally intensive, we propose a computationally efficient approximation for the LOOCV likelihood function that permits selecting a near-optimal choice for the shrinkage coefficient α. We demonstrate the efficiency and accuracy of our proposed approach on high-dimensional data sampled from heavy-tailed elliptical distributions, and show that it is consistently better than other methods in the literature for shrinkage coefficient estimation.

There is an accumulating evidence in the literature that stability of learning algorithms is a key characteristic that permits a learning algorithm to generalize. Despite various insightful results in this direction, there seems to be an overlooked dichotomy in the type of stability-based generalization bounds we have in the literature. On one hand, the literature seems to suggest that exponential generalization bounds for the estimated risk, which are optimal, can be only obtained through stringent, distribution independent and computationally intractable notions of stability such as uniform stability. On the other hand, it seems that weaker notions of stability such as hypothesis stability, although it is distribution dependent and more amenable to computation, can only yield polynomial generalization bounds for the estimated risk, which are suboptimal. In this paper, we address the gap between these two regimes of results. In particular, the main question we address here is whether it is possible to derive exponential generalization bounds for the estimated risk using a notion of stability that is computationally tractable and distribution dependent, but weaker than uniform stability. Using recent advances in concentration inequalities, and using a notion of stability that is weaker than uniform stability but distribution dependent and amenable to computation, we derive an exponential tail bound for the concentration of the estimated risk of a hypothesis returned by a general learning rule, where the estimated risk is expressed in terms of the deleted estimate. Interestingly, we note that our final bound has similarities to previous exponential generalization bounds for the deleted estimate, in particular, the result of Bousquet and Elisseeff (2002) for the regression case.

There is an accumulating evidence in the literature that *stability of learning algorithms* is a key characteristic that permits a learning algorithm to generalize. Despite various insightful results in this direction, there seems to be an overlooked dichotomy in the type of stability-based generalization bounds we have in the literature. On one hand, the literature seems to suggest that exponential generalization bounds for the estimated risk, which are optimal, can be *only* obtained through *stringent*, *distribution independent* and *computationally intractable* notions of stability such as *uniform stability*. On the other hand, it seems that *weaker* notions of stability such as hypothesis stability, although it is *distribution dependent* and more *amenable* to computation, can *only* yield polynomial generalization bounds for the estimated risk, which are suboptimal. In this paper, we address the gap between these two regimes of results. In particular, the main question we address here is *whether it is possible to derive exponential generalization bounds for the estimated risk using a notion of stability that is computationally tractable and distribution dependent, but weaker than uniform stability*. Using recent advances in concentration inequalities, and using a notion of stability that is weaker than uniform stability but distribution dependent and amenable to computation, we derive an exponential tail bound for the concentration of the estimated risk of a hypothesis returned by a *general* learning rule, where the estimated risk is expressed in terms of either the resubstitution estimate (empirical error), or the deleted (or, leave-one-out) estimate. As an illustration we derive exponential tail bounds for ridge regression with *unbounded responses* – a setting where uniform stability results of Bousquet and Elisseeff (2002) are not applicable.

Manifold learning algorithms rely on a neighbourhood graph to provide an estimate of the data’s local topology. Unfortunately, current methods for estimating local topology assume local Euclidean geometry and locally uniform data density, which often leads to poor data embeddings. We address these shortcomings by proposing a framework that combines local learning with parametric density estimation for local topology estimation. Given a data set \mathcalD ⊂\mathcalX, we first estimate a new metric space (\mathbbX,d_\mathbbX) that characterizes the varying sample density of \mathcalX in \mathbbX, then use (\mathbbX,d_\mathbbX) as a new (pilot) input space for the graph construction step of the manifold learning process. The proposed framework results in significantly improved embeddings, which we demonstrated objectively by assessing clustering accuracy.

Linear Discriminant Analysis (LDA) is a popular tool for multiclass discriminative dimensionality reduction. However, LDA suffers from two major problems: (1) It only optimizes the Bayes error for the case of unimodal Gaussian classes with equal covariances (assuming full rank matrices) and, (2) The multiclass extension maximizes the sum of pairwise distances between the classes, and does not “simultaneously” maximize each pairwise distance between the classes. This typically results in serious overlapping in the projected space between classes that are “close” in the input space. To solve these two problems, this paper proposes Pareto Discriminant Analysis (PARDA). Firstly, PARDA explicitly models each of the classes as a multidimensional Gaussian with a sample covariance. Secondly, PARDA decomposes the multiclass problem to a set of pairwise objective functions representing the pairwise distance between different classes. Unlike existing extensions of Fisher discriminant analysis (FDA) to multiclass problems, that typically maximize the sum of pairwise distances between classes, PARDA simultaneously maximizes each pairwise distance, thus encouraging the case that all classes are equidistant from each other in the lower dimensional space. Solving PARDA is a multiobjective optimization problem - simultaneously optimizing more than one, possibly conflicting, objective functions - and the resulting solution is known to be “Pareto Optimal”. Experimental results on synthetic data, several image data sets and data sets from the UCI repository show positive and encouraging results in favor of PARDA when compared with standard and state-of-the-art multiclass extensions of LDA.

We are interested in learning an adaptive local metric on a lower dimensional manifold for query--based operations.We combine the concept underlying manifold learning algorithms and the minimum volume ellipsoid metric to find the nearest neighbouring points to a query point on the manifold on which the query point is lying. Extensive experiments on various standard benchmark data sets in the context of classification showed very promising results when compared to state of the art metric learning algorithms.

To learn a metric for query-based operations, we combine the concept underlying manifold learning algorithms and the minimum volume ellipsoid metric in a unified algorithm to find the nearest neighbouring points on the manifold on which the query point is lying. Extensive experiments on standard benchmark data sets in the context of classification showed promising and interesting results with regard to our proposed algorithm.

Classification of sequential data using discriminative models such as support vector machines is very hard due to the variable length of this type of data. On the other hand, generative models such as HMMs have become the standard tool for representing sequential data due to their efficiency. This paper proposes a general generative-discriminative framework that uses HMMs to map the variable length sequential data into a fixed size P-dimensional vector (likelihood score) that can be easily classified using any discriminative model. The preliminary experiments of the framework on the MNIST database for handwritten digits have achieved a better recognition rate of 98.02% than that of standard HMMs (94.19%).