Isotone Optimization in R: Pool-Adjacent-Violators Algorithm (PAVA) and Active Set Methods

By Jan de Leeuw, Kurt Hornik, Patrick Mair. 2009

317 citations recorded by the source corpus.

In this paper we give a general framework for isotone optimization. First we discuss a generalized version of the Pool-Adjacent-Violators Algorithm (PAVA) to minimize a separable convex function with simple chain constraints. Besides of general convex functions we extend existing PAVA implementations in terms of observation weights, approaches for tie handling, and responses from repeated measurement designs. Since isotone optimization problems can be formulated as convex programming problems with linear constraints we then develop a primal active set method to solve such problem. This methodology is applied on speci�c loss functions relevant in statistics. Both approaches are implemented in the R package isotone.

Subfields: Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/3e9e9891a01adc7975aeb06a88535af2d0268b1b

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Statistics and Probability

1. Weijie Su
2. E.J. Candes
3. Richard Nock
4. Ananda Theertha Suresh
5. Chiara Sabatti
6. Ewout van den Berg
7. Malgorzata Bogdan
8. Laya Ghodrati

Citations in the corpus

• SLOPE—ADAPTIVE VARIABLE SELECTION VIA CONVEX OPTIMIZATION (2014, background): “In closing, we would also like to note that De Leeuw, Hornik and Mair [32] have contributed a nice R package called isotone available at http://cran.”
• A workflow for differentially-private graph synthesis (2012, methodology): “While PAVA [6], and indepen­dently [3], can regress either the CCDF or the degree se­quence to a consistent non-increasing sequence, in [10] we W ITEM develop a regression technique based on shortest paths that 1 (0,0) 2 (A,D),0 1 (0,0) 3 }edges .nds a single sequence optimizing the pair of meas”
• Regression diagnostics meets forecast evaluation: conditional calibration, reliability diagrams, and coefficient of determination (2021, unknown): “Extant asymptotic theory for nonparametric isotonic regression, as implemented by Algorithm 1, is available for quantiles and the mean or expectation functional, as developed and reviewed by Barlow et al. (1972), Casady and Cryer (1976), Wright (1984), Robertson et al. (1988), El Barmi and Mukerjee ”
• Distribution-on-Distribution Regression via Optimal Transport Maps (2021, methodology): “The above problem resembles an isotonic regression problem with multiple measurements, and can be solved via pool-adjacent-violater-algorithm (PAVA) (Mair et al [10]).”
• Differentially private anonymized histograms (2019, methodology): “Isotonic regression in one dimension can be run in time linear in the number of inputs using the pool adjacent violators algorithm (PAVA) or its variants [47, 48].”
• Learning Binary Trees via Sparse Relaxation (2020, methodology): “This initial algorithm has been generalized and incorporated into convex programming frameworks (see Mair et al. (2009) for an excellent summary of the history of isotonic regression and its extensions).”