A class of optimization problems motivated by rank estimators in robust regression

Abstract

A rank estimator in robust regression is a minimizer of a function which depends (in addition to other factors) on the ordering of residuals but not on their values. Here we focus on the optimization aspects of rank estimators. We distinguish two classes of functions: a class with a continuous and convex objective function (CCC), which covers the class of rank estimators known from statistics, and also another class (GEN), which is far more general. We propose efficient algorithms for both classes. For GEN we propose an enumerative algorithm that works in polynomial time as long as the number of regressors is $O\left(1\right)$. The proposed algorithm utilizes the special structure of arrangements of hyperplanes that occur in our problem and is superior to other known algorithms in this area. For the continuous and convex case, we propose an unconditionally polynomial algorithm finding the exact minimizer, unlike the heuristic or approximate methods implemented in statistical packages.

Keywords:

• Discrete optimization
• arrangement of hyperplanes
• continuous optimization
• ellipsoid method
• rank estimators

2010 Mathematics Subject Classifications:

• 90C25
• 90C27

Disclosure statement

No potential conflict of interest was reported by the author(s).

Notes

1 Sometimes it is also required ${\int }_0^1{\varphi }^2\left(t\right)\mathrm{d}t=1$ and even central symmetry of the graph of ϕ around $[1/2,0]$; such properties are essential for asymptotic statistical properties, but do not play a role in this text.

2 On the contrary, algorithms for decision problems give just a single-bit YES/NO output. This is an example where the computation time cannot be related to the size of output.

3 For the sake of simplicity, a reader can always think of ${\mathrm{\Phi }}^{\mathrm{\prime }}$ as a vertex; but generally, an arrangement need not have vertices, so we prefer this more careful formulation.

Additional information

Funding

This work was supported by Grantová Agentura České Republiky (Czech Science Foundation), 19-02773S (M. Černý, J. Antoch, M. Hladík) and 17-13086S (M. Rada).