Стохастические градиентные методы с неточным оракулом

Стохастические градиентные методы с неточным оракулом

Автор: Гасников А.В., Двуреченский П.Е., Нестеров Ю.Е.

Журнал: Труды Московского физико-технического института @trudy-mipt

Рубрика: Информатика, вычислительная техника и упровление

Статья в выпуске: 1 (29) т.8, 2016 года.

Бесплатный доступ

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

Стохастическая оптимизация, рандомизация, неточный оракул, безградиентные методы, покомпонентные методы

Короткий адрес: https://sciup.org/142186120

IDR: 142186120

Список литературы Стохастические градиентные методы с неточным оракулом

  • Поляк Б.Т. Градиентные методы минимизации функционалов, решения уравнений и неравенств: диссертация на соискание ученой степени кандидата физикоматематических наук. МГУ, механико-математический факультет, 1963
  • Поляк Б.Т. Введение в оптимизацию. М.: Наука, 1983; М.: УРСС, 2014
  • Хачиян Л.Г. Избранные труды/сост. С. П. Тарасов. М.: МЦНМО, 2009
  • Немировский А.С., Юдин Д.Б. Сложность задач и эффективность методов оптимизации. М.: Наука, 1979
  • Поляк Б.T., Цыпкин Я.З. Оптимальные псевдоградиентные алгоритмы адаптации//Автоматика и телемеханика. 1980. № 8. С. 74-84
  • Цыпкин Я.З., Позняк А.С. Оптимальные поисковые алгоритмы стохастической оптимизации//Докл. АН СССР. 1981. Т. 260, № 3. С. 550-553
  • Нестеров Ю.Е. Эффективные методы в нелинейном программировании. М.: Радио и связь, 1989
  • Nesterov Y., Nemirovsky A. Interior-point polynomial methods in convex programming. Studies in applied mathematics. V. 13. SIAM, Philadelphia, 1994
  • Nemirovski A. Lectures on modern convex optimization algorithms, and engineering applications. Philadelphia: SIAM, http://www2.isye.gatech.edu/˜nemirovs/Lect_ModConvOpt.pdf
  • Нестеров Ю.Е. Введение в выпуклую оптимизацию. М.: МЦНМО, 2010
  • Bubeck S. Convex optimization: algorithms and complexity//In Foundations and Trends in Machine Learning. 2015. V. 8, N 3-4. P. 231-357. arXiv:1405.4980
  • http://cvxr.com/cvx/
  • http://www.cvxpy.org/en/latest/; https://github.com/cvxgrp/scs
  • Нестеров Ю.Е. Алгоритмическая выпуклая оптимизация: диссертация на соискание степени д.ф.-м.н. по специальности 01.01.07 -вычислительная математика. Долгопрудный, МФТИ 26 декабря 2013 г. 367 c. http://www.mathnet.ru/php/seminars.phtml?option_lang=rus&presentid=8313
  • Левитин Е.С., Поляк Б.Т. Методы минимизации при наличии ограничений//ЖВМ и МФ. 1966. Т. 6, № 5. С. 787-823
  • Васильев Ф.П. Методы оптимизации. М.: МЦНМО, 2011
  • Jaggi M. Revisiting Frank-Wolfe: Projection-free sparse convex optimization//Proceedings of the 30th International Conference on Machine Learning, Atlanta, Georgia, USA, 2013. https://sites.google.com/site/frankwolfegreedytutorial/
  • Nesterov Yu. Complexity bounds for primal-dual methods minimizing the model of objective function//CORE Discussion Papers. 2015/03. 2015
  • Tseng P. On accelerated proximal gradient methods for convex-concave optimization//SIAM J. Optim. 2008. (submitted) http://www.mit.edu/˜dimitrib/PTseng/papers.html
  • Neumaier A. OSGA: A fast subgradient algorithm with optimal complexity//e-print, 2014. arXiv:1402.1125
  • Allen-Zhu Z., Orecchia L. Linear coupling: An ultimate unification of gradient and mirror descent//e-print, 2014. arXiv:1407.1537
  • Ермольев Ю.М. Методы стохастического программирования. М.: Наука, 1976
  • Нурминский Е.А. Численные методы решения детерминированных и стохастических минимаксных задач. Киев: Наукова думка, 1979
  • Shapiro A., Dentcheva D., Ruszczynski A. Lecture on stochastic programming. Modeling and theory. MPS-SIAM series on Optimization, 2014
  • Nesterov Y. Minimizing functions with bounded variation of subgradients//CORE Discussion Papers. 2005/79. 2005
  • Гасников А.В., Нестеров Ю.Е., Спокойный В.Г. Об эффективности одного метода рандомизации зеркального спуска в задачах онлайн-оптимизации//ЖВМ и МФ. Т. 55, № 4. 2015. С. 55-71. arXiv:1410.3118
  • Nesterov Y. Primal-dual subgradient methods for convex problems//Math. Program. Ser. B. 2009. V. 120(1). P. 261-283
  • Поляк Б.Т. Новый метод типа стохастической аппроксимации//Автоматика и телемеханика. 1990. № 7. C. 98-107
  • Polyak B.T., Juditsky A.B. Acceleration of stochastic approximation by averaging//SIAM J. Control Optim. 1992. V. 30. P. 838-855
  • Juditsky A., Lan G., Nemirovski A., Shapiro A. Stochastic approximation approach to stochastic programming//SIAM Journal on Optimization. 2009. V. 19, N 4. P. 1574-1609
  • Juditsky A., Nemirovski A. First order methods for nonsmooth convex large-scale optimization, I, II. In: Optimization for Machine Learning. Eds. S. Sra, S. Nowozin, S. Wright. MIT Press, 2012
  • Sridharan K. Learning from an optimization viewpoint. PhD Thesis, Toyota Technological Institute at Chicago, 2011. http://ttic.uchicago.edu/˜karthik/thesis.pdf
  • Граничин О.Н., Поляк Б.Т. Рандомизированные алгоритмы оценивания и оптимизации при почти произвольных помехах. М.: Наука, 2003
  • Spokoiny V. Parametric estimation. Finite sample theory//The Annals of Statistics. 2012. V. 40, N 6. P. 2877-2909. arXiv:1111.3029v5
  • Ибрагимов И.А., Хасьминский Р.З. Асимптотическая теория оценивания. М.: Наука, 1977
  • Lacost-Julien S., Schmidt M., Bach F. A simpler approach to obtaining 𝑂 (1/𝑡) convergence rate for the projected stochastic subgradient method//e-print, 2012. arXiv:1212.2002
  • Rakhlin A., Shamir O., Sridharan K. Making gradient descent optimal for strongly convex stochastic optimization//ICML, 2012. arXiv:1109.5647
  • Juditsky A., Nesterov Yu. Deterministic and stochastic primal-dual subgradient algorithms for uniformly convex minimization//Stoch. System. 2014. V. 4, N 1. P. 44-80. arXiv:1401.1792
  • Hazan E., Kale S. Beyond the regret minimization barrier: Optimal algorithms for stochastic strongly-convex optimization//JMLR. 2014. V. 15. P. 2489-2512
  • Боровков А.А., Боровков К.А. Асимптотический анализ случайных блужданий. Т. 1. Медленно убывающие распределения скачков. М.: Физматлит, 2008
  • Ким К., Нестеров Ю., Скоков В., Черкасский Б. Эффективные алгоритмы для дифференцирования и задачи экстремали//Экономика и математические методы. 1984. Т. 20. С. 309-318
  • Евтушенко Ю.Г. Оптимизация и быстрое автоматическое дифференцирование. М.: ВЦ РАН, 2013
  • Гасников А.В., Двуреченский П.Е., Усманова И.Н. О нетривиальности быстрых (ускоренных) рандомизированных методов//Труды МФТИ. 2016. Т. 8. (в печати) arXiv:1508.02182
  • Аникин А.С., Гасников А.В., Горнов А.Ю. Рандомизация и разреженность в задачах huge-scale оптимизации на примере работы метода зеркального спуска//Труды МФТИ. 2016. Т. 8. (в печати) arXiv:1602.00594
  • Bubeck S., Cesa-Bianchi N. Regret analysis of stochastic and nonstochastic multi-armed bandit problems//Foundation and Trends in Machine Learning. 2012. V. 5, № 1. P. 1-122. http://www.princeton.edu/˜sbubeck/SurveyBCB12.pdf
  • Гасников А.В., Лагуновская А.А., Морозова Л.Э. О связи имитационной логитдинамики в популяционной теории игр и метода зеркального спуска в онлайноптимизации на примере задачи выбора кратчайшего маршрута//Труды МФТИ. 2015. Т. 7, № 4. С. 104-113. arXiv:1511.02398
  • Agarwal A., Bartlett P.L., Ravikumar P., Wainwright M.J. Information-theoretic lower bounds on the oracle complexity of stochastic convex optimization//IEEE Transaction of Information. 2012. V. 58, N 5. P. 3235-3249. arXiv:1009.0571
  • Аникин А.С., Гасников А.В., Горнов А.Ю., Камзолов Д.И., Максимов Ю.В., Нестеров Ю.Е. Эффективные численные методы решения задачи PageRank для дважды разреженных матриц//Труды МФТИ. 2015. Т. 7, № 4. С. 74-94. arXiv:1508.07607
  • Назин А.В., Поляк Б.Т. Рандомизированный алгоритм нахождения собственного вектора стохастической матрицы с приложением к задаче PageRank//ДАН РАН. 2009. Т. 426, № 6. С. 734-737
  • Nesterov Y.E. Efficiency of coordinate descent methods on large scale optimization problem//SIAM Journal on Optimization. 2012. V. 22, N 2. P. 341-362
  • Nesterov Y.E. Subgradient methods for huge-scale optimization problems//CORE Discussion Paper 2012/2. 2012
  • Гасников А.В., Дмитриев Д.Ю. Об эффективных рандомизированных алгоритмах поиска вектора PageRank//ЖВМ и МФ. 2015. Т. 55, № 3. С. 355-371. arXiv:1410.3120
  • Fercoq O., Richtarik P. Accelerated, parallel and proximal coordinate descent//SIAM Journal on Optimization. 2015. V. 25, N 4. 1997-2023. arXiv:1312.5799
  • Qu Z., Richtarik P. Coordinate Descent with Arbitrary Sampling I: Algorithms and Complexity//e-print, 2014. arXiv:1412.8060
  • Anikin A., Dvurechensky P., Gasnikov A., Golov A., Gornov A., Maximov Yu., Mendel M., Spokoiny V. Modern efficient numerical approaches to regularized regression problems in application to traffic demands matrix calculation from link loads//Proceedings of International conference ITAS-2015. Russia, Sochi, September, 2015. arXiv:1508.00858
  • Аникин А.С., Гасников А.В., Горнов А.Ю. О неускоренных эффективных методах решения разреженных задач квадратичной оптимизации//Труды МФТИ. 2016. Т. 8. (в печати). arXiv:1602.01124
  • Nesterov Yu., Nemirovski A. On first order algorithms for 𝑙1/nuclear norm minimization//Acta Numerica. 2013. V. 22. P. 509-575
  • Гасников А.В., Дорн Ю.В., Нестеров Ю.Е, Шпирко С.В. О трехстадийной версии модели стационарной динамики транспортных потоков//Математическое моделирование. 2014. Т. 26:6. C. 34-70. arXiv:1405.7630
  • Гасников А.В., Гасникова Е.В., Ершов Е.И., Двуреченский П.Е., Лагуновская А.А. Поиск стохастических равновесий в транспортных моделях равновесного распределения потоков//Труды МФТИ. 2015. Т. 7, № 4. С. 114-128. arXiv:1505.07492
  • Гасников А.В., Двуреченский П.Е., Дорн Ю.В., Максимов Ю.В. Численные методы поиска равновесного распределения потоков в модели Бэкмана и модели стабильной динамики//Математическое моделирование. 2016. Т. 28. (в печати). arXiv:1506.00293
  • Гасников А.В., Двуреченский П.Е., Камзолов Д.И., Нестеров Ю.Е., Спокойный В.Г., Стецюк П.И., Суворикова А.Л., Чернов А.В. Поиск равновесий в многостадийныйх транспортных моделях//Труды МФТИ. 2015. Т. 7, № 4. С. 143-155. https://mipt.ru/upload/medialibrary/ffe/143-155.pdf
  • Гасников А.В., Двуреченский П.Е., Спокойный В.Г., Стецюк П.И., Суворикова А.Л. Суперпозиция метода балансировки и универсального градиентного метода для поиска энтропийно-сглаженного барицентра Вассерштейна и равновесий в многостадийных моделях транспортных потоков//Труды МФТИ. 2016. Т. 8. (в печати). arXiv:1506.00292
  • Richtarik P. http://www.maths.ed.ac.uk/˜richtarik/
  • Shalev-Shwartz S. http://www.cs.huji.ac.il/˜shais/
  • Zhang T. http://www.stat.rutgers.edu/home/tzhang/
  • Le Roux N., Schmidt M., Bach F. A stochastic gradient method with an exponential convergence rate for strongly-convex optimization with finite training sets//In Advances in Neural Information Processing Systems (NIPS). 2012. arXiv:1202.6258
  • Johnson B., Zhang T. Accelerating stochastic gradient descent using predictive variance reduction//In Advances in Neural Information Processing Systems (NIPS). 2013.http://www.stat.rutgers.edu/home/tzhang/pubs.html
  • Konecny J., Richtarik P. Semi-Stochastic gradient descent methods//e-print, 2013. arXiv:1312.1666
  • Konecny J., Liu J., Richtarik P., Takac M. Mini-batch semi-stochastic gradient descent in the proximal setting//e-print, 2015. arXiv:1504.04407
  • Lan G., Zhou Y. An optimal randomized incremental gradient methods//Technical Report, Department of Industrial and Systems Engineering, University of Florida, July 7, 2015, updated in October, 2015.http://www.ise.ufl.edu/glan/files/2015/10/OptRandom10-18.pdf
  • Lin Q., Lu Z., Xiao L. An Accelerated Randomized Proximal Coordinate Gradient Method and its Application to Regularized Empirical Risk Minimization//SIAM J. Optim. 2015. V. 25, N 4. P. 2244-2273.http://research.microsoft.com/pubs/228730/spdc_paper.pdf, http://research.microsoft.com/pubs/258430/APCG_ERM_2015.pdf
  • Agarwal A., Bottou L. A lower bound for the optimization of finite sums//e-print, 2014. arXiv:1410.0723
  • Shalev-Shwartz S., Zhang T. Accelerated proximal stochastic dual coordinate ascent for regularized loss minimization//In Proceedings of the 31th International Conference on Machine Learning, ICML 2014, Beijing, China, 21-26 June 2014. P. 64-72. arXiv:1309.2375
  • Zheng Q., Richtarik P., Zhang T. Randomized dual coordinate ascent with arbitrary sampling//e-print, 2014. arXiv:1411.5873
  • Bartlett P.L., Mendelson S. Empirical minimization//Probability theory and related fields. 2006. V. 135(3). P. 311-334
  • Nesterov Yu., Spokoiny V.Random gradient-free minimization of convex functions//Foundations of Computational Mathematics, 2015; CORE Discussion Paper 2011/1. 2011
  • Nesterov Y. Smooth minimization of non-smooth function//Math. Program. Ser. A. 2005. V. 103, N 1. P. 127-152
  • Devolder O., Glineur F., Nesterov Yu. First order methods of smooth convex optimization with inexact oracle//Math. Progr. Ser. A. 2014. V. 146(1-2). P. 37-75
  • Devolder O. Exactness, inexactness and stochasticity in first-order methods for large-scale convex optimization. CORE UCL, PhD thesis, March 2013
  • D'Aspermont A. Smooth optimization with approximate gradient//SIAM Journal of Optimization. 2008. V. 19(3). P. 1171-1183
  • Baes M. Estimate sequence methods: extensions and approximations. IFOR Internal report. ETH Zurich, Switzerland, 2009
  • Devolder O., Glineur F., Nesterov Yu. First order methods with inexact oracle: the smooth strongly convex case//CORE Discussion Paper 2013/16. 2013
  • Devolder O., Glineur F., Nesterov Yu. Intermediate gradient methods for smooth convex problems with inexact oracle//CORE Discussion Paper 2013/17. 2013
  • Ghadimi S., Lan G. Optimal stochastic approximation algorithms for strongly convex stochastic composite optimization I: A generic algorithmic framework//SIAM J. Optim. 2012. V. 22(4). P. 1469-1492
  • Ghadimi S., Lan G. Optimal stochastic approximation algorithms for strongly convex stochastic composite optimization II: Shrinking procedures and optimal algorithms//SIAM J. Optim. 2013. V. 23(4). P. 2061-2089
  • Гасников А.В., Двуреченский П.Е. Стохастический промежуточный метод для задач выпуклой оптимизации//ДАН РАН. 2016. Т. 467, № 2. С. 131-134
  • Dvurechensky P., Gasnikov A. Stochastic Intermediate Gradient Method for Convex Problems with Inexact Stochastic Oracle//Journal Optimization Theory and Applications. 2016. (подана) arXiv:1411.2876
  • Ортега Дж., Рейнболдт В. Итерационные методы решения нелинейных систем уравнений со многими неизвестными. М.: Мир, 1975
  • Евтушенко Ю.Г. Методы решения экстремальных задач и их применение в системах оптимизации. М.: Наука, 1982
  • Wu S., Boyd S., Candes E. A differential equation for modeling Nesterov's accelerated gradient method: Theory and insight//NIPS, December 2014. http://stanford.edu/˜boyd/papers/ode_nest_grad.html
  • Wibisono A., Wilson A.C. On accelerated methods in optimization//e-print, 2015. arXiv:1509.03616
  • Аникин А.С., Гасников А.В., Двуреченский П.Е., Тюрин А.И., Чернов А.В. Двойственные подходы к задачам минимизации сильно выпуклых функционалов простой структуры при аффинных ограничениях//ЖВМ и МФ. 2016. Т. 56. (подана). arXiv:1602.01686
  • Nesterov Yu., Shikhman V. Convergent subgradient methods for nonsmooth convex minimization//CORE Discussion Paper 2014/5. 2014. https://www.uclouvain.be/cps/ucl/doc/core/documents/coredp2014_5web.pdf
  • Lin H., Mairal J., Harchaoui Z. A universal catalyst for first-order optimization//Advances in Neural Information Processing Systems (NIPS), 2015. https://hal.inria.fr/hal01160728
  • Lan G. Gradient sliding for composite optimization//Math. Progr. 2014. (submitted). http://pwp.gatech.edu/guanghui-lan/wp-content/uploads/sites/330/2016/02/GSnonsmooth-stochastic6-11-submit.pdf
  • Lan G. http://www.ise.ufl.edu/glan/publications/
  • Гасников А.В., Гасникова Е.В., Нестеров Ю.Е., Чернов А.В. Об эффективных численных методах решения задач энтропийно-линейного программирования//ЖВМ и МФ. 2016. Т. 56, № 4. С. 523-534. arXiv:1410.7719
  • Spielman D. Algorithms, graph theory, and linear equations in Laplacian matrices//Proc. of the International Congress of Mathematicians. Hyderabad, India, 2010. P. 1-23
  • Никайдо Х. Выпуклые структуры и математическая экономика. М.: Мир, 1972
  • Nesterov Yu. Excessive gap technique in nonsmooth convex minimization//SIAM Journal of Optimization. 2005. V. 16, N 1. P. 235-249
  • Nemirovski A. http://www2.isye.gatech.edu/˜nemirovs/
  • Juditsky A. http://ljk.imag.fr/membres/Anatoli.Iouditski/
  • Cox B., Juditsky A., Nemirovski A. Decomposition techniques for bilinear saddle point problems and variational inequalities with affine monotone operators on domains given by linear minimization oracles//e-print, 2015. arXiv:1506.02444
  • Nesterov Y., de Palma A. Stationary dynamic solutions in congested transportation Networks: Summary and Perspectives//Networks Spatial Econ. 2003. N 3(3). P. 371-395
  • Nesterov Yu., Shikhman V. Algorithmic models of market equilibrium//CORE Discussion Paper 2013/66. 2013
  • Ващенко М.П., Гасников А.В., Молчанов Е.Г., Поспелова Л.Я., Шананин А.А. Вычислимые модели и численные методы для анализа тарифной политики железнодорожных грузоперевозок. М.: ВЦ РАН, 2014. arXiv:1501.02205
  • Гасников А.В. Заметка об эффективной вычислимости конкурентных равновесий в транспортно-экономических моделях//Математическое моделирование. 2015. Т. 27, № 12. С. 121-136. arXiv:1410.3123
  • Бабичева Т.С., Гасников А.В., Лагуновская А.А., Мендель М.А. Двухстадийная модель равновесного распределения транспортных потоков//Труды МФТИ. 2015. Т. 7, № 3. С. 31-41. https://mipt.ru/upload/medialibrary/971/31-41.pdf
  • Гасников А.В., Гасникова Е.В., Мациевский С.В., Усик И.В. О связи моделей дискретного выбора с разномасштабными по времени популяционными играми загрузок//Труды МФТИ. 2015. Т. 7, № 4. С. 129-142. arXiv:1511.02390
  • Nemirovski A., Onn S., Rothblum U.G. Accuracy certificates for computational problems with convex structure//Mathematics of Operation Research. 2010. V. 35, № 1. P. 52-78
  • Nesterov Yu. New primal-dual subgradient methods for convex optimization problems with functional constraints//International Workshop «Optimization and Statistical Learning». January 11-16. France, Les Houches, 2015. http://lear.inrialpes.fr/workshop/osl2015/program.html
  • Магарил-Ильяев Г.Г., Тихомиров В.М. Выпуклый анализ и его приложения. М.: УРСС, 2011
  • Guzman C., Nemirovski A. On lower complexity bounds for large-scale smooth convex optimization//Journal of Complexity. 2015. V. 31. P. 1-14. arXiv:1307.5001
  • Немировский А.С., Нестеров Ю.Е. Оптимальные методы гладкой выпуклой оптимизации//ЖВМ и МФ. 1985. Т. 25, № 3. С. 356-369
  • Harchaoui Z., Juditsky A., Nemirovski A. Conditional gradient algorithms for norm-regularized smooth convex optimization//Math. Program. Ser. B. 2015. V. 152. P. 75-112. http://www2.isye.gatech.edu/˜nemirovs/ccg_revised_apr02.pdf
  • Nesterov Yu. Universal gradient methods for convex optimization problems//Math. Prog. 2015, V. 152, N 1. P. 381-404; CORE Discussion Paper 2013/63. 2013
  • Гасников А.В., Двуреченский П.Е., Камзолов Д.И. Градиентные и прямые методы с неточным оракулом для задач стохастической оптимизации//Динамика систем и процессы управления. Труды Международной конференции, посвященой 90летию со дня рождения академика Н.Н. Красовского. Екатеринбург, 15-20 сентября 2014. Издательство: Институт математики и механики УрО РАН им. Н.Н. Красовского (Екатеринбург), 2015. С. 111-117. arXiv:1502.06259
  • Nesterov Yu. How to make the gradients small//OPTIMA 88. 2012. P. 10-11. http://www.mathopt.org/Optima-Issues/optima88.pdf
  • Nesterov Yu. Gradient methods for minimizing composite functions//Math. Prog. 2013. V. 140, N 1. P. 125-161
  • Горнов А.Ю. Вычислительные технологии решения задач оптимального управления. Новосибирск: Наука, 2009
  • Lugosi G., Cesa-Bianchi N. Prediction, learning and games. New York: Cambridge University Press, 2006
  • Shalev-Shwartz S. Online learning and online convex optimization//Foundation and Trends in Machine Learning. 2011. V. 4, N 2. P. 107-194. http://www.cs.huji.ac.il/˜shais/papers/OLsurvey.pdf
  • Rakhlin A., Sridharan K. Statistical Learning Theory and Sequential Prediction//e-print, 2015. http://stat.wharton.upenn.edu/˜rakhlin/book_draft.pdf
  • Hazan E. Introduction to online convex optimization//e-print, 2015. http://ocobook.cs.princeton.edu/OCObook.pdf
  • Гасников А.В., Лагуновская А.А., Усманова И.Н., Федоренко Ф.А. Безградиентные прокс-методы с неточным оракулом для негладких задач выпуклой стохастической оптимизации на симплексе//Автоматика и телемеханика. 2016 (в печати). arXiv:1412.3890
  • Гасников А.В., Крымова Е.А., Лагуновская А.А., Усманова И.Н., Федоренко Ф.А. Стохастическая онлайн-оптимизация. Одноточечные и двухточечные нелинейные многорукие бандиты. Выпуклый и сильно выпуклый случаи//Автоматика и Телемеханика. 2016 (подана). arXiv:1509.01679
  • Duchi J.C., Jordan M.I., Wainwright M.J., Wibisono A. Optimal rates for zero-order convex optimization: the power of two function evaluations//IEEE Transaction of Information. 2015. V. 61, N 5. P. 2788-2806. http://www.eecs.berkeley.edu/˜wainwrig/Papers/DucZero15.pdf
  • Поляк Б.Т., Цыбаков А.Б. Оптимальные порядки точности поисковых алгоритмов стохастической оптимизации//Проб. перед. информ. 1990. Т. 26, № 2. С. 45-53
  • Spall J.C. Introduction to stochastic search and optimization: estimation, simulation and control. Wiley, 2003
  • Agarwal A., Dekel O., Xiao L. Optimal algorithms for online convex optimization with multi-point bandit feedback//Proceedings of 23 Annual Conference on Learning Theory. 2010. P. 28-40
  • Граничин О.Н. Об одной стохастической рекуррентной процедуре при зависимых помехах в наблюдении, использующей на входе пробные возмущения//Вестник Ленинградского университета. 1989. Cер. 1. Bып. 1. С. 19-21
  • Shamir O. An Optimal Algorithm for Bandit and Zero-Order Convex Optimization with Two-Point Feedback//e-print, 2015. arXiv:1507.08752
  • Ledoux M. Concentration of measure phenomenon. Providence, RI, Amer. Math. Soc., 2001 (Math. Surveys Monogr. V. 89)
  • Wright S.J. Coordinate descent algorithms//e-print, 2015. arXiv:1502.04759
  • Dempe S. Foundations of bilevel programming. Dordrecht: Kluwer Academic Publishers, 2002
  • Bogolubsky L., Dvurechensky P., Gasnikov A., Gusev G., Nesterov Yu., Raigorodskii A., Tikhonov A., Zhukovskii M. Learning supervised PageRank with gradient-free optimization methods//e-print, 2014. arXiv:1411.4282
  • Bogolubsky L., Dvurechensky P., Gasnikov A., Gusev G., Nesterov Yu., Raigorodskii A., Tikhonov A., Zhukovskii M. Learning Supervised PageRank with Gradient-Based and Gradient-Free Optimization Methods//e-print, 2016. arXiv:1603.00717
  • Nesterov Yu. Structural Optimization: New Perspectives for Increasing Efficiency of Numerical Schemes//International conference «Optimization and Applications in Control and Data Science» on the occasion of Boris Polyak's 80th birthday, Moscow, May, 2015. http://www.mathnet.ru/php/presentation.phtml?option_lang=rus&presentid=11909
  • http://www.mathnet.ru/php/conference.phtml?option_lang=rus&eventID=1&confid=699
  • Гасников А.В. «Алгебра» над эффективными методами выпуклой оптимизации (элементарное введение)//Математический кружок. ФУПМ МФТИ. 8 февраля 2014 г. http://www.mathnet.ru/php/seminars.phtml?option_lang=rus&presentid=8395
  • Гасников А.В., Камзолов Д.И., Мендель М.С. Основные конструкции над алгоритмами выпуклой оптимизации и их приложения к получению новых оценок для сильно выпуклых задач//Труды МФТИ. 2016. Т. 8 (в печати). arXiv:1603.07701
Еще
Статья научная
SciUp 2024 © 2024 ©