One occasionally encounters computational problems that work just fine on ill-posed inputs, even though they should not. One example is polynomial eigenvalue problems, where standard algorithms such as QZ can find a desired solution to instances with infinite condition number to machine precision, while being completely oblivious to the ill-conditioning of the problem. One explanation is that, intuitively, adversarial perturbations are extremely unlikely, and "for all practical purposes'' the problem might not be ill-conditioned at all. We analyse perturbations of singular polynomial eigenvalue problems and derive methods to bound the likelihood of adversarial perturbations for any given input in different stochastic models.
Joint work with Vanni Noferini