Образец для цитирования:
Гудков А. А., Миронов С. В., Файзлиев А. Р. О сходимости жадного алгоритма для решения задачи построения монотонной регрессии // Изв. Сарат. ун-та. Нов. сер. Сер. Математика. Механика. Информатика. 2017. Т. 17, вып. 4. С. 431-440. DOI: https://doi.org/10.18500/1816-9791-2017-17-4-431-440
О сходимости жадного алгоритма для решения задачи построения монотонной регрессии
В статье представлены жадные алгоритмы, которые используют подход типа Франка - Вульфа для нахождения разреженной монотонной регрессии. Проблема нахождения монотонной регрессии возникает при сглаживании эмпирических данных, в задачах динамического программирования, математической статистике и во многих других прикладных задачах. Для решения данной задачи требуется найти неубывающую последовательность точек, имеющую наименьшую ошибку приближения к заданному множеству точек на плоскости. Задача построения монотонной регрессии может быть сформулирована в виде задачи выпуклого программирования с линейными ограничениями и имеет неполиномиальную сложность. В статье также находятся оценки скорости сходимости представленных жадных алгоритмов.
1. Chen Y. Aspects of Shape-constrained Estimation in Statistics : PhD Thesis. University of Cambridge, 2013. 143 p.
2. Robertson T., Wright F., Dykstra R. Order Restricted Statistical Inference. N.Y. : John Wiley & Sons, 1988. 544 p.
3. Barlow R., Brunk H. The Isotonic Regression Problem and Its Dual // Jurnal of the American Statistical Association. 1972. Vol. 67, № 1. P. 140–147. DOI: https://doi.org/10.2307/2284712.
4. Dykstra R. An Isotonic Regression Algorithm // Journal of Statistical Planning and Inference. 1981. Vol. 5, № 1. P. 355–363. DOI: https://doi.org/10.1214/aos/1176345866.
5. Best M. J., Chakravarti N. Active set algorithms for isotonic regression: a unifying framework // Math. Program. 1990. Vol. 47, № 3. P. 425–439. DOI: https://doi.org/10.1007/BF01580873.
6. Best M., Chakravarti N., Ubhaya V. Minimizing Separable Convex Functions Subject to Simple Chain Constraints // SIAM Journal on Optimization. 2000. Vol. 10, № 3. P. 658–672. DOI: https://doi.org/10.1137/S1052623497314970.
7. Stromberg U. An Algorithm for Isotonic Regression with Arbitrary Convex Distance Function // Computational Statistics & Data Analysis. 1991. Vol. 11, № 1. P. 205–219.
8. Ahuja R., Orlin J. A Fast Scaling Algorithm for Minimizing Separable Convex Functions Subject to Chain Constraints // Operations Research. 2001. Vol. 49, № 1. P. 784–789. DOI: https://doi.org/10.1287/opre.49.5.784.10601
9. Hansohm J. Algorithms and Error Estimations for Monotone Regression on Partially Preordered Sets // Journal of Multivariate Analysis. 2007. Vol. 98, № 1. P. 1043–1050. DOI: https://doi.org/10.1016/j.jmva.2006.11.001.
10. Dykstra R., Robertson T. An Algorithm for Isotonic Regression for Two or More Independent Variables // Ann. Statist. 1982. Vol. 10, № 1. P. 708–719. DOI: 101214/aos/1176345866. 11. Burdakov O., Grimvall A., Hussian M. A Generalised PAV Algorithm for Monotonic Regression in Several Variables // COMPSTAT: Proc. 16th Symposium in Computational Statistics. Prague, Czech Republic, 2004. P. 761–767.
12. Bach F. Efficient Algorithms for Non-convex Isotonic Regression through Submodular Optimization // Online Journal CoRR. 2017. Vol. abs/1707.09157. URL: http://arxiv.org/abs/1707.09157 (accessed 10, September, 2017).
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. 1999. Vol. 18, № 13. P. 1605–1613. DOI: https://doi.org/10.1002/(SICI)1097-0258(19990715)18:13<1605::AID SIM146>3.0.CO;2-V.
14. Cai Y., Judd K. L. Shape-preserving dynamic programming // Math. Meth. Oper. Res.2013. Vol. 77. P. 407–421. DOI: https://doi.org/10.1007/s00186-012-0406-5.
15. Frank M., Wolfe Ph. An algorithm for quadratic programming // Naval Research Logistics Quarterly. 1956. Vol. 3, № 1–2. P. 95–110. DOI: https://doi.org/10.1002/nav.3800030109.
16. Levitin E. S., Polyak B. T. Constrained minimization methods // USSR Comp. Math. & M. Phys. 1966. Vol. 6, № 5. P. 1–50.
17. Clarkson K. L. Coresets, sparse greedy approximation, and the Frank–Wolfe algorithm //ACM Transactions on Algorithms. 2010. Vol. 6, № 4. P. 1–30. DOI: https://doi.org/10.1145/1824777.1824783.
18. Freund R. M., Grigas P. New analysis and results for the Frank-Wolfe method // Math. Program. 2016. Vol. 155, № 1–2. P. 199–230. DOI: https://doi.org/10.1007/s10107-014-0841-6.
19. Jaggi M. Revisiting Frank–Wolfe: Projection-free sparse convex optimization // ICML’13 : Proc. 30th International Conference on Machine Learning. Atlanta, GA, USA, 2013. P. 427–435.
20. Friedman J. Greedy Function Approximation: A Gradient Boosting Machine // Ann. Statist. 2001. Vol. 29, № 5. P. 1189–1232. DOI: https://doi.org/10.1214/aos/1013203451.
21. Davis G., Mallat S., Avellaneda M. Adaptive greedy approximation // Constr. Approx. 1997. Vol. 13. P. 57–98. DOI: https://doi.org/10.1007/BF02678430.
22. Jones L. On a conjecture of Huber concerning the convergence of projection pursuit regression // Ann. Statist. 1987. Vol. 15, № 2. P. 880–882. DOI: https://doi.org/10.1214/aos/1176350382.
23. Barron A. R., Cohen A., Dahmen W., DeVore R. A. Approximation and Learning byGreedy Algorithms // Ann. Statist. 2008. Vol. 36, № 1. P. 64–94. DOI: https://doi.org/10.1214/009053607000000631.
24. DeVore R. A., Temlyakov V. N. Some remarks on greedy algorithms // Advances in Computational Mathematics. 1996. Vol. 5. P. 173–187. DOI: https://doi.org/10.1007/BF02124742.
25. Konyagin S. V., Temlyakov V. N. A remark on greedy approximation in Banach spaces // East J. Approx. 1999. Vol. 5, № 3. P. 365–379.
26. Nguyen H., Petrova G. Greedy Strategies for Convex Optimization // Calcolo. 2017. Vol. 54, № 1. P. 207–224. DOI: https://doi.org/10.1007/s10092-016-0183-2.
27. Temlyakov V. N. Dictionary descent in optimization // Analysis Mathematica. 2016. Vol. 42, № 1. P. 69–89. DOI: https://doi.org/10.1007/s10476-016-0106-0.
28. DeVore R. A., Temlyakov V. N. Convex optimization on Banach spaces // Found. Comput. Math. 2016. Vol. 16, № 2. P. 369–394. DOI: https://doi.org/10.1007/s10208-015-9248-x.
29. Sidorov S., Mironov S., Pleshakov M. Dual Greedy Algorithm for Conic Optimization Problem // CEUR-WS. 2016. Vol. 1623. P. 276–283.
30. Temlyakov V. N. Greedy approximation in convex optimization // Constr. Approx. 2015. Vol. 41, № 2. P. 269–296. DOI: https://doi.org/10.1007/s00365-014-9272-0.
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. 2009. Vol. 32, № 5. P. 1–24. DOI: https://doi.org/10.18637/jss.v032.i05.
32. Chepoi V., Cogneau D., Fichet B. Polynomial algorithms for isotonic regression // Lecture Notes–Monograph Series. 1997. Vol. 31. P. 147–160. DOI: https://doi.org/10.1214/lnms/1215454134
