On the convergence of a greedy algorithm for the solution of the problem for the construction of monotone regression

A. A. Gudkov ; S. V. Mironov ; A. R. Faizliev

Izvestiya of Saratov University. Mathematics. Mechanics. Informatics, Tome 17 (2017) no. 4, pp. 431-440.

Résumé

The paper presents greedy algorithms that use the Frank–Woolf-type approach for finding a sparse monotonic regression. The problem of finding monotonic regression arises in smoothing an empirical data, in problems of dynamic programming, mathematical statistics and in many other applied problems. The problem is to find a non-decreasing sequence of points with the lowest error of approximation to the given set of points on the plane. The problem of constructing monotonic regression can be formulated as a convex programming problem with linear constraints and is NP-hard problem. The paper also contains estimates of the rate of convergence for the presented greedy algorithms.

Bibliographie

[1] Chen Y., Aspects of Shape-constrained Estimation in Statistics, PhD Thesis, University of Cambridge, 2013, 143 pp. | MR

[2] Robertson T., Wright F., Dykstra R., Order Restricted Statistical Inference, John Wiley Sons, N. Y., 1988, 544 pp. | MR | Zbl

[3] Barlow R., Brunk H., “The Isotonic Regression Problem and Its Dual”, Journal of the American Statistical Association, 67:1 (1972), 140–147 | DOI | MR | Zbl

[4] Dykstra R., “An Isotonic Regression Algorithm”, Journal of Statistical Planning and Inference, 5:1 (1981), 355–363 | DOI | MR | Zbl

[5] Best M. J., Chakravarti N., “Active set algorithms for isotonic regression: a unifying framework”, Math. Program., 47:3 (1990), 425–439 | DOI | MR | Zbl

[6] Best M., Chakravarti N., Ubhaya V., “Minimizing Separable Convex Functions Subject to Simple Chain Constraints”, SIAM Journal on Optimization, 10:3 (2000), 658–672 | DOI | MR | Zbl

[7] Stromberg U., “An Algorithm for Isotonic Regression with Arbitrary Convex Distance Function”, Computational Statistics Data Analysis, 11:1 (1991), 205–219 | DOI | MR | Zbl

[8] Ahuja R., Orlin J., “A Fast Scaling Algorithm for Minimizing Separable Convex Functions Subject to Chain Constraints”, Operations Research, 49:1 (2001), 784–789 | DOI | MR | Zbl

[9] Hansohm J., “Algorithms and Error Estimations for Monotone Regression on Partially Preordered Sets”, Journal of Multivariate Analysis, 98:1 (2007), 1043–1050 | DOI | MR | Zbl

[10] Dykstra R., Robertson T., “An Algorithm for Isotonic Regression for Two or More Independent Variables”, Ann. Statist., 10:1 (1982), 708–719 | DOI | MR

[11] Burdakov O., Grimvall A., Hussian M., “A Generalised PAV Algorithm for Monotonic Regression in Several Variables”, Proc. 16th Symposium in Computational Statistics, COMPSTAT (Prague, Czech Republic, 2004), 761–767 | MR

[12] Bach F., Efficient Algorithms for Non-convex Isotonic Regression through Submodular Optimization, 2017, arXiv: (accessed 10, September, 2017) 1707.09157 [cs.LG]

[13] Diggle P., Morris S., Morton-Jones T., “Case-control isotonic regression for investigation of elevation in risk around a point source”, Statistics in medicine, 18:13 (1999), 1605–1613 | 3.0.CO;2-V class='badge bg-secondary rounded-pill ref-badge extid-badge'>DOI

[14] Cai Y., Judd K. L., “Shape-preserving dynamic programming”, Math. Meth. Oper. Res., 77 (2013), 407–421 | DOI | MR | Zbl

[15] Frank M., Wolfe Ph., “An algorithm for quadratic programming”, Naval Research Logistics Quarterly, 3:1–2 (1956), 95–110 | DOI | MR

[16] Levitin E. S., Polyak B. T., “Constrained minimization methods”, USSR Comp. Math. M. Phys., 6:5 (1966), 1–50 | DOI

[17] Clarkson K. L., “Coresets, sparse greedy approximation, and the Frank–Wolfe algorithm”, ACM Transactions on Algorithms, 6:4 (2010), 1–30 | DOI | MR

[18] Freund R. M., Grigas P., “New analysis and results for the Frank–Wolfe method”, Math. Program., 155:1–2 (2016), 199–230 | DOI | MR | Zbl

[19] Jaggi M., “Revisiting Frank–Wolfe: Projection-free sparse convex optimization”, Proc. 30th International Conference on Machine Learning, ICML'13 (Atlanta, GA, USA, 2013), 427–435

[20] Friedman J., “Greedy Function Approximation: A Gradient Boosting Machine”, Ann. Statist., 29:5 (2001), 1189–1232 | DOI | MR | Zbl

[21] Davis G., Mallat S., Avellaneda M., “Adaptive greedy approximation”, Constr. Approx., 13 (1997), 57–98 | DOI | MR | Zbl

[22] Jones L., “On a conjecture of Huber concerning the convergence of projection pursuit regression”, Ann. Statist., 15:2 (1987), 880–882 | DOI | MR | Zbl

[23] Barron A. R., Cohen A., Dahmen W., DeVore R. A., “Approximation and Learning by Greedy Algorithms”, Ann. Statist., 36:1 (2008), 64–94 | DOI | MR | Zbl

[24] DeVore R. A., Temlyakov V. N., “Some remarks on greedy algorithms”, Advances in Computational Mathematics, 5 (1996), 173–187 | DOI | MR | Zbl

[25] Konyagin S. V., Temlyakov V. N., “A remark on greedy approximation in Banach spaces”, East J. Approx., 5:3 (1999), 365–379 | MR | Zbl

[26] Nguyen H., Petrova G., “Greedy Strategies for Convex Optimization”, Calcolo, 54:1 (2017), 207–224 | DOI | MR | Zbl

[27] Temlyakov V. N., “Dictionary descent in optimization”, Analysis Mathematica, 42:1 (2016), 69–89 | DOI | MR | Zbl

[28] DeVore R. A., Temlyakov V. N., “Convex optimization on Banach spaces”, Found. Comput. Math., 16:2 (2016), 369–394 | DOI | MR | Zbl

[29] Sidorov S., Mironov S., Pleshakov M., “Dual Greedy Algorithm for Conic Optimization Problem”, CEUR-WS, 1623, 2016, 276–283

[30] Temlyakov V. N., “Greedy approximation in convex optimization”, Constr. Approx., 41:2 (2015), 269–296 | DOI | MR | Zbl

[31] De Leeuw J., Hornik K., Mair P., “Isotone Optimization in R: Pool-Adjacent-Violators Algorithm (PAVA) and Active Set Methods”, Journal of Statistical Software, 32:5 (2009), 1–24 | DOI

[32] Chepoi V., Cogneau D., Fichet B., “Polynomial algorithms for isotonic regression”, Lecture Notes–Monograph Series, 31 (1997), 147–160 | DOI | MR | Zbl