article

Isotonic Regression for Multiple Independent Variables

Author:

Quentin F. StoutAuthors Info & Claims

Algorithmica, Volume 71, Issue 2

Pages 450 - 470

https://doi.org/10.1007/s00453-013-9814-z

Published: 01 February 2015 Publication History

Abstract

This paper gives algorithms for determining isotonic regressions for weighted data at a set of points P in multidimensional space with the standard componentwise ordering. The approach is based on an order-preserving embedding of P into a slightly larger directed acyclic graph (dag) G , where the transitive closure of the ordering on P is represented by paths of length 2 in G . Algorithms are given which, compared to previous results, improve the time by a factor of $\tilde{\varTheta}(|P|)$ for the L ₁, L ₂, and L metrics. A yet faster algorithm is given for L ₁ isotonic regression with unweighted data. L isotonic regression is not unique, and algorithms are given for finding L regressions with desirable properties such as minimizing the number of large regression errors.

References

[1]

Angelov, S., Harb, B., Kannan, S., Wang, L.-S.: Weighted isotonic regression under the L1 norm. In: Symposium on Discrete Algorithms (SODA), pp. 783---791 (2006)

Digital Library

[2]

Ayer, M., Brunk, H.D., Ewing, G.M., Reid, W.T., Silverman, E.: An empirical distribution function for sampling with incomplete information. Ann. Math. Stat. 5, 641---647 (1955)

[3]

Barlow, R.E., Bartholomew, D.J., Bremner, J.M., Brunk, H.D.: Statistical Inference Under Order Restrictions: the Theory and Application of Isotonic Regression. Wiley, New York (1972)

[4]

Barlow, R.E., Brunk, H.D.: The isotonic regression problem and its dual. J. Am. Stat. Soc. 67, 140---147 (1972)

[5]

Beran, R., Dümbgen, L.: Least squares and shrinkage estimation under bimonotonicity constraints. Stat. Comput. 20, 177---189 (2010)

Digital Library

[6]

Bril, G., Dykstra, R., Pillars, C., Robertson, T.: Algorithm AS 206: isotonic regression in two independent variables. J. R. Stat. Soc., Ser. C, Appl. Stat. 33, 352---357 (1984)

[7]

Burdakov, O., Grimvall, A., Hussian, M.: A generalized PAV algorithm for monotonic regression in several variables. In: Proceedings of COMPSTAT'2004 (2004)

[8]

Chandrasekaran, R., Rhy, Y.U., Jacob, V.S., Hong, S.: Isotonic separation. INFORMS J. Comput. 17, 462---474 (2005)

Digital Library

[9]

Dembczynski, K., Greco, S., Kotlowski, W., Slowinski, R.: Statistical model for rough set approach to multicriteria classification. In: PKDD 2007: 11th European Conference on Principles and Practice Knowledge Discovery in Databases. Springer Lecture Notes in Computer Science, vol. 4702, pp. 164---175 (2007)

Digital Library

[10]

Dette, H., Scheder, R.: Strictly monotone and smooth nonparametric regression for two or more variables. Can. J. Stat. 34, 535---561 (2006)

[11]

Dykstra, R., Hewett, J., Robertson, T.: Nonparametric, isotonic discriminant procedures. Biometrika 86, 429---438 (1999)

[12]

Dykstra, R.L., Robertson, T.: An algorithm for isotonic regression of two or more independent variables. Ann. Stat. 10, 708---716 (1982)

[13]

Gamarnik, D.: Efficient learning of monotone concepts via quadratic optimization. In: Proceedings of Computational Learning Theory (COLT), pp. 134---143 (1998)

Digital Library

[14]

Gebhardt, F.: An algorithm for monotone regression with one or more independent variables. Biometrika 57, 263---271 (1970)

[15]

Gudmundsson, J., Klein, O., Knauer, C., Smid, M.: Small Manhattan networks and algorithmic applications for the earth mover's distance. In: Proceedings 23rd European Workshop on Computational Geometry, pp. 174---177 (2007)

[16]

Hanson, D.L., Pledger, G., Wright, F.T.: On consistency in monotonic regression. Ann. Stat. 1, 401---421 (1973)

[17]

Hershberger, J., Suri, S.: Applications of a semi-dynamic convex hull algorithm. BIT Numer. Math. 32, 249---267 (1992)

Digital Library

[18]

Jackson, D.: Note on the median of a set of numbers. Bull. Am. Math. Soc., pp. 160---164 (1921)

[19]

Kalai, A.T., Sastry, R.: The isotron algorithm: high-dimensional isotonic regression. In: Proceedings of Computational Learning Theory (COLT) (2009)

[20]

Kaufman, Y., Tamir, A.: Locating service centers with precedence constraints. Discrete Appl. Math. 47, 251---261 (1993)

Digital Library

[21]

Legg, D., Townsend, D.: Best monotone approximation in L'{0, 1}. J. Approx. Theory 42, 30---35 (1984)

[22]

Luss, R., Rosset, S., Shahar, M.: Decomposing isotonic regression for efficiently solving large problems, In: Proceedings of Neural Information Processing Systems (2010)

[23]

Maxwell, W.L., Muckstadt, J.A.: Establishing consistent and realistic reorder intervals in production-distribution systems. Oper. Res. 33, 1316---1341 (1985)

Digital Library

[24]

Megido, N.: Linear-time algorithms for linear programming in ¿3 and related problems. SIAM J. Comput. 12, 759---776 (1983)

[25]

Meyer, M.: Inference for multiple isotonic regression (2010). www.stat.colostate.edu/research/TechnicalReports/2010/2010_2.pdf

[26]

Moon, T., Smola, A., Chang, Y., Zheng, Z.: IntervalRank--isotonic regression with listwise and pairwise constraints. In: Proceedings Web Search and Data Mining, pp. 151---160 (2010)

Digital Library

[27]

Mukarjee, H., Stern, S.: Feasible nonparametric estimation of multiargument monotone functions. J. Am. Stat. Assoc. 89, 77---80 (1994)

[28]

Pólya, G.: Sur une algorithme toujours convergent pour obtenir les polynomes de meillure approximation de Tchebycheff pour un fonction continue quelconque. Comptes Rendus 157, 840---843 (1913)

[29]

Punera, K., Ghosh, J.: Enhanced hierarchical classification via isotonic smoothing. In: Proceedings International Conference on the World Wide Web, pp. 151---160 (2008)

Digital Library

[30]

Qian, S., Eddy, W.F.: An algorithm for isotonic regression on ordered rectangular grids. J. Comput. Graph. Stat. 5, 225---235 (1996)

[31]

Robertson, T., Wright, F.T.: Multiple isotonic median regression. Ann. Stat. 1, 422---432 (1973)

[32]

Robertson, T., Wright, F.T., Dykstra, R.L.: Order Restricted Statistical Inference. Wiley, New York (1988)

[33]

Saarela, O., Arjas, E.: A method for Bayesian monotonic multiple regression. Scand. J. Stat. 38, 499---513 (2011)

[34]

Salanti, G., Ulm, K.: Multidimensional isotonic regression and estimation of the threshold value. Discussion paper 234. Institute für Statistik, Ludwig-Maximilians Universität, Munchen (2001)

[35]

Sasabuchi, S., Inutsuka, M., Kulatungaz, D.D.S.: A multivariate version of isotonic regression. Biometrika 70, 465---472 (1983)

[36]

Spouge, J., Wan, H., Wilber, W.J.: Least squares isotonic regression in two dimensions. J. Optim. Theory Appl. 117, 585---605 (2003)

[37]

Stout, Q.F.: Strict L' isotonic regression. J. Optim. Theory Appl. 152, 121---135 (2012)

[38]

Stout, Q.F.: Weighted L' isotonic regression, submitted (2012). Available at. www.eecs.umich.edu/~qstout/pap/LinfinityIso.pdf

[39]

Stout, Q.F.: Isotonic regression via partitioning. Algorithmica 66, 93---112 (2013)

[40]

Sysoev, O., Burdakov, O., Grimvall, A.: A segmentation-based algorithm for large-scale partially ordered monotonic regression. Comput. Stat. Data Anal. 55, 2463---2476 (2011)

Digital Library

[41]

Ubhaya, V.A.: Isotone optimization, I, II. J. Approx. Theory 12, 146---159, 315---331 (1974)

[42]

Velikova, M., Daniels, H.: Monotone Prediction Models in Data Mining. VDM Verlag (2008)

Digital Library

Cited By

Haider Cde França FKronberger GBurlacu BWagner M(2022)Comparing optimistic and pessimistic constraint evaluation in shape-constrained symbolic regressionProceedings of the Genetic and Evolutionary Computation Conference10.1145/3512290.3528714(938-945)Online publication date: 8-Jul-2022
https://dl.acm.org/doi/10.1145/3512290.3528714
Iwanaga JNishimura NSukegawa NTakano Y(2019)Estimating product-choice probabilities from recency and frequency of page viewsKnowledge-Based Systems10.1016/j.knosys.2016.02.00699:C(157-167)Online publication date: 1-Jan-2019
https://dl.acm.org/doi/10.1016/j.knosys.2016.02.006
Espinosa JHennig C(2019)A constrained regression model for an ordinal response with ordinal predictorsStatistics and Computing10.1007/s11222-018-9842-229:5(869-890)Online publication date: 1-Sep-2019
https://dl.acm.org/doi/10.1007/s11222-018-9842-2
Show More Cited By

Isotonic Regression for Multiple Independent Variables
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory

Recommendations

Linear time isotonic and unimodal regression in the L1 and L∞ norms

We consider L"1-isotonic regression and L"~ isotonic and unimodal regression. For L"1-isotonic regression, we present a linear time algorithm when the number of outputs are bounded. We extend the algorithm to construct an approximate isotonic regression ...
Isotonic Median Regression: A Linear Programming Approach

The isotonic median regression problem arises in statistics. It is known that the isotonic median regression problem, with respect to a complete order, may be solved by a “Pool Adjacent Violators” algorithm. In this paper we show that this algorithm is ...
Unimodal regression via prefix isotonic regression

This paper gives algorithms for determining real-valued univariate unimodal regressions, that is, for determining the optimal regression which is increasing and then decreasing. Such regressions arise in a wide variety of applications. They are shape-...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Algorithmica

Algorithmica Volume 71, Issue 2

February 2015

306 pages

ISSN:0178-4617

Issue’s Table of Contents

Copyright © Copyright © 2015 Springer Science+Business Media New York.

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 01 February 2015

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 07 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Haider Cde França FKronberger GBurlacu BWagner M(2022)Comparing optimistic and pessimistic constraint evaluation in shape-constrained symbolic regressionProceedings of the Genetic and Evolutionary Computation Conference10.1145/3512290.3528714(938-945)Online publication date: 8-Jul-2022
https://dl.acm.org/doi/10.1145/3512290.3528714
Iwanaga JNishimura NSukegawa NTakano Y(2019)Estimating product-choice probabilities from recency and frequency of page viewsKnowledge-Based Systems10.1016/j.knosys.2016.02.00699:C(157-167)Online publication date: 1-Jan-2019
https://dl.acm.org/doi/10.1016/j.knosys.2016.02.006
Espinosa JHennig C(2019)A constrained regression model for an ordinal response with ordinal predictorsStatistics and Computing10.1007/s11222-018-9842-229:5(869-890)Online publication date: 1-Sep-2019
https://dl.acm.org/doi/10.1007/s11222-018-9842-2
Burdakov OSysoev O(2017)A Dual Active-Set Algorithm for Regularized Monotonic RegressionJournal of Optimization Theory and Applications10.1007/s10957-017-1060-0172:3(929-949)Online publication date: 1-Mar-2017
https://dl.acm.org/doi/10.1007/s10957-017-1060-0
Kyng RRao ASachdeva S(2015)Fast, provable algorithms for Isotonic regression in all ℓ--normsProceedings of the 29th International Conference on Neural Information Processing Systems - Volume 210.5555/2969442.2969543(2719-2727)Online publication date: 7-Dec-2015
https://dl.acm.org/doi/10.5555/2969442.2969543

View Options

View options

Figures

Tables

Media

View Issue’s Table of Contents