# Adversarial Sign-Corrupted Isotonic Regression

arXiv: https://arxiv.org/abs/2207.07075 · HTML: https://mlsanity.com/paper/2207.07075/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 4 of its 36 references that are in the map.
- First posted on arXiv 14 Jul 2022.

## Builds on (most cited first, 4 of 4)

- [Statistical guarantees for the EM algorithm: From population to sample-based analysis](https://mlsanity.com/paper/1408.2156/) (2014)
- [On the folded normal distribution](https://mlsanity.com/paper/1402.3559/) (2014)
- [Partial recovery bounds for clustering with the relaxed Kmeans](https://mlsanity.com/paper/1807.07547/) (2018)
- [Nonparametric Shape-restricted Regression](https://mlsanity.com/paper/1709.05707/) (2017)

## Abstract (arXiv)

Classical univariate isotonic regression involves nonparametric estimation under a monotonicity constraint of the true signal. We consider a variation of this generating process, which we term adversarial sign-corrupted isotonic (textttASCI) regression. Under this textttASCI setting, the adversary has full access to the true isotonic responses, and is free to sign-corrupt them. Estimating the true monotonic signal given these sign-corrupted responses is a highly challenging task. Notably, the sign-corruptions are designed to violate monotonicity, and possibly induce heavy dependence between the corrupted response terms. In this sense, textttASCI regression may be viewed as an adversarial stress test for isotonic regression. Our motivation is driven by understanding whether efficient robust estimation of the monotone signal is feasible under this adversarial setting. We develop textttASCIFIT, a three-step estimation procedure under the textttASCI setting. The textttASCIFIT procedure is conceptually simple, easy to implement with existing software, and consists of applying the textttPAVA with crucial pre- and post-processing corrections. We formalize this procedure, and demonstrate its theoretical guarantees in the form of sharp high probability upper bounds and minimax lower bounds. We illustrate our findings with detailed simulations.