On an optimization problem in robust statistics

Abstract

In this article, we consider a large class of computational problems in robust statistics that can be formulated as selection of optimal subsets of data based on some criterion function. To solve such problems, there are broadly two classes of algorithms available in the literature. One is based on purely random search, and the other is based on deterministically guided strategies. Though these methods can achieve satisfactory results in some specific examples, none of them can be used satisfactorily for a large class of similar problems either due to their very long expected waiting time to hit the true optimum or due to their failure to come out of a local optimum when they get trapped there. Here, we propose two probabilistic search algorithms, and under some conditions on the parameters of the algorithms, we establish the convergence of our algorithms to the true optimum. We also show some results on the probability of hitting the true optimum if the algorithms are run for a finite number of iterations. Finally, we compare the performance of our algorithms to some commonly available algorithms for computing some popular robust multivariate statistics using real datasets.