Известия Саратовского университета. Новая серия.

Серия Математика. Механика. Информатика

ISSN 1816-9791 (Print)
ISSN 2541-9005 (Online)

Для цитирования:

Гудков А. А., Миронов С. В., Файзлиев А. Р. О сходимости жадного алгоритма для решения задачи построения монотонной регрессии // Известия Саратовского университета. Новая серия. Серия: Математика. Механика. Информатика. 2017. Т. 17, вып. 4. С. 431-440. DOI: 10.18500/1816-9791-2017-17-4-431-440, EDN: ZXJPNJ

Статья опубликована на условиях лицензии Creative Commons Attribution 4.0 International (CC-BY 4.0).
Опубликована онлайн: 
28.11.2017
Полный текст:
скачать
(downloads: 196)
Язык публикации: 
русский
Рубрика: 
Информатика
УДК: 
519.6
DOI: 
10.18500/1816-9791-2017-17-4-431-440
EDN: 
ZXJPNJ

О сходимости жадного алгоритма для решения задачи построения монотонной регрессии

Авторы: 
Гудков Александр Александрович, Саратовский национальный исследовательский государственный университет имени Н. Г. Чернышевского
Миронов Сергей Владимирович, Саратовский национальный исследовательский государственный университет имени Н. Г. Чернышевского
Файзлиев Алексей Раисович, Саратовский национальный исследовательский государственный университет имени Н. Г. Чернышевского
Аннотация: 

В статье представлены жадные алгоритмы, которые используют подход типа Франка - Вульфа для нахождения разреженной монотонной регрессии.  Проблема нахождения монотонной регрессии возникает при сглаживании эмпирических данных, в задачах динамического программирования, математической статистике и во многих других прикладных задачах.  Для решения данной задачи требуется найти неубывающую последовательность точек, имеющую наименьшую ошибку приближения к заданному множеству точек на плоскости. Задача построения монотонной регрессии может быть сформулирована в виде задачи выпуклого программирования с линейными ограничениями и имеет неполиномиальную сложность. В статье также находятся оценки скорости сходимости представленных жадных алгоритмов.

Ключевые слова: 
жадные алгоритмы
алгоритм Франка
Вульфа
монотонная регрессия
Список источников: 
  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
Поступила в редакцию: 
20.07.2017
Принята к публикации: 
10.11.2017
Опубликована: 
05.12.2017
Краткое содержание:
скачать
(downloads: 99)
  • 1309 просмотров