# Divide and Conquer in Non-standard Problems and the Super-efficiency Phenomenon

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 May 2016.

## Built on by (most cited first, 5 of 5)

- [Distributed Bootstrap for Simultaneous Inference Under High Dimensionality](https://mlsanity.com/paper/2102.10080/) (2021)
- [How Much is Left? LLMs Linearly Encode Their Remaining Output Length](https://mlsanity.com/paper/2607.05316/) (2026)
- [Divide-and-conquer methods for big data analysis](https://mlsanity.com/paper/2102.10771/) (2021)
- [MANDERA: Malicious Node Detection in Federated Learning via Ranking](https://mlsanity.com/paper/2110.11736/) (2021)
- [Distributed Estimation and Inference for Semi-parametric Binary Response Models](https://mlsanity.com/paper/2210.08393/) (2022)

## Abstract (arXiv)

We study how the divide and conquer principle --- partition the available data into subsamples, compute an estimate from each subsample and combine these appropriately to form the final estimator --- works in non-standard problems where rates of convergence are typically slower than √n and limit distributions are non-Gaussian, with a special emphasis on the least squares estimator (and its inverse) of a monotone regression function. We find that the pooled estimator, obtained by averaging non-standard estimates across the mutually exclusive subsamples, outperforms the non-standard estimator based on the entire sample in the sense of pointwise inference. We also show that, under appropriate conditions, if the number of subsamples is allowed to increase at appropriate rates, the pooled estimator is asymptotically normally distributed with a variance that is empirically estimable from the subsample-level estimates. Further, in the context of monotone function estimation we show that this gain in pointwise efficiency comes at a price --- the pooled estimator's performance, in a uniform sense (maximal risk) over a class of models worsens as the number of subsamples increases, leading to a version of the super-efficiency phenomenon. In the process, we develop analytical results for the order of the bias in isotonic regression, which are of independent interest.