RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB
Общая информация
Последний выпуск
Архив
Импакт-фактор
Правила для авторов

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Пробл. передачи информ.:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Пробл. передачи информ., 2005, том 41, выпуск 4, страницы 78–96 (Mi ppi116)  

Эта публикация цитируется в 35 научных статьях (всего в 35 статьях)

Методы обработки сигналов

Рекуррентное агрегирование оценок методом зеркального спуска с усреднением

А. Б. Юдицкийa, А. В. Назинb, А. Б. Цыбаковcd, Н. Ваятисd

a Laboratoire Techniques de l'Ingénierie Médicale et de la Complexité — Informatique, Mathématiques et Applications de Grenoble
b Институт проблем управления им. В. А. Трапезникова РАН
c Институт проблем передачи информации РАН
d Université Pierre & Marie Curie, Paris VI

Аннотация: Рассматривается рекуррентный метод построения агрегированной оценки на конечном классе базовых решающих правил в задаче классификации. Оценка приближенно минимизирует выпуклый функционал риска при $\ell_1$-ограничении. Она задается стохастическим вариантом метода зеркального спуска, осуществляющего спуск градиентного типа в двойственном пространстве с дополнительным усреднением. Основной результат настоящей статьи – верхняя граница для средней точности предложенного алгоритма, имеющая порядок $C\sqrt{(\ln M)/t}$, с явным выражением малого постоянного множителя $C$, где $M$ – размерность задачи, $t$ – число наблюдений. Аналогичная граница получена и для более общей постановки, охватывающей, в частности, модель регрессии при квадратичных потерях.

Полный текст: PDF файл (1907 kB)
Список литературы: PDF файл   HTML файл

Англоязычная версия:
Problems of Information Transmission, 2005, 41:4, 368–384

Реферативные базы данных:

УДК: 621.391.1:519.2
Поступила в редакцию: 16.03.2005
После переработки: 26.07.2005

Образец цитирования: А. Б. Юдицкий, А. В. Назин, А. Б. Цыбаков, Н. Ваятис, “Рекуррентное агрегирование оценок методом зеркального спуска с усреднением”, Пробл. передачи информ., 41:4 (2005), 78–96; Problems Inform. Transmission, 41:4 (2005), 368–384

Цитирование в формате AMSBIB
\RBibitem{YudNazTsy05}
\by А.~Б.~Юдицкий, А.~В.~Назин, А.~Б.~Цыбаков, Н.~Ваятис
\paper Рекуррентное агрегирование
оценок методом зеркального спуска с~усреднением
\jour Пробл. передачи информ.
\yr 2005
\vol 41
\issue 4
\pages 78--96
\mathnet{http://mi.mathnet.ru/ppi116}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=2198228}
\zmath{https://zbmath.org/?q=an:1123.62044}
\transl
\jour Problems Inform. Transmission
\yr 2005
\vol 41
\issue 4
\pages 368--384
\crossref{https://doi.org/10.1007/s11122-006-0005-2}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/ppi116
  • http://mi.mathnet.ru/rus/ppi/v41/i4/p78

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
    Замечания
    • Письмо в редакцию
      А. Б. Юдицкий, А. В. Назин, А. Б. Цыбаков, Н. Ваятис
      Пробл. передачи информ., 2006, 42:3, 109


    Эта публикация цитируется в следующих статьяx:
    1. Tsybakov A.B., “Discussion: Local Rademacher complexities and oracle inequalities in risk minimization”, Ann. Statist., 34:6 (2006), 2681–2687  crossref  mathscinet  isi
    2. Bickel P.J., Li Bo, Tsybakov A.B., van de Geer S.A., Yu Bin, Valdés T., Rivero C., Fan Jianqing, van der Vaart A., “Regularization in statistics”, Test, 15:2 (2006), 271–344  crossref  zmath  isi  isi
    3. Bunea F., Tsybakov A.B., Wegkamp M.H., “Aggregation for Gaussian regression”, Ann. Statist., 35:4 (2007), 1674–1697  crossref  mathscinet  zmath  isi  elib
    4. Lecué G., “Simultaneous adaptation to the margin and to complexity in classification”, Ann. Statist., 35:4 (2007), 1698–1721  crossref  mathscinet  zmath  isi  elib
    5. Gaïffas S., Lecué G., “Optimal rates and adaptation in the single-index model using aggregation”, Electron. J. Stat., 1 (2007), 538–573  crossref  mathscinet  zmath  isi
    6. Dalalyan A.S., Tsybakov A.B., “Aggregation by exponential weighting and sharp oracle inequalities”, Learning Theory, Proceedings, Lecture Notes in Computer Science, 4539, 2007, 97–111  crossref  mathscinet  zmath  isi
    7. Nemirovski A., Juditsky A., Lan G., Shapiro A., “Robust stochastic approximation approach to stochastic programming”, SIAM J. Optim., 19:4 (2008), 1574–1609  crossref  mathscinet  isi  elib
    8. Juditsky A., Rigollet P., Tsybakov A.B., “Learning by mirror averaging”, Ann. Statist., 36:5 (2008), 2183–2206  crossref  mathscinet  zmath  isi  elib
    9. Alquier P., “Iterative feature selection in least square regression estimation”, Ann. Inst. Henri Poincaré Probab. Stat., 44:1 (2008), 47–88  crossref  mathscinet  zmath  adsnasa  isi
    10. Bunea F., Nobel A., “Sequential procedures for aggregating arbitrary estimators of a conditional mean”, IEEE Trans. Inform. Theory, 54:4 (2008), 1725–1735  crossref  mathscinet  zmath  isi  elib
    11. Dalalyan A., Tsybakov A.B., “Aggregation by exponential weighting, sharp PAC-Bayesian bounds and sparsity”, Machine Learning, 72:1–2 (2008), 39–61  crossref  isi  elib
    12. Назин А.В., Поляк Б.Т., “Рандомизированный алгоритм нахождения собственного вектора стохастической матрицы с приложением к PageRank”, Докл. РАН, 426:6 (2009), 734–737  mathnet  mathscinet  zmath  elib; Nazin A.V., Polyak B.T., “The randomized algorithm for finding an eigenvector of the stochastic matrix with application to PageRank”, Dokl. Math., 79:3 (2009), 424–427  crossref  mathscinet  zmath  isi  elib
    13. Mitchell Ch., van de Geer S., “General oracle inequalities for model selection”, Electron. J. Stat., 3 (2009), 176–204  crossref  mathscinet  zmath  isi
    14. Salmon J., Le Pennec E., “Nl-Means and Aggregation Procedures”, 2009 16th IEEE International Conference on Image Processing, 2009, 2941–2944  isi
    15. Nazin A., Polyak B., “A Randomized Algorithm for Finding Eigenvector of Stochastic Matrix with Application to PageRank Problem”, 2009 IEEE Control Applications CCA & Intelligent Control (Isic), IEEE International Conference on Control Applications, 2009, 412–416  crossref  isi
    16. Amato U., Antoniadis A., Samarov A., Tsybakov A.B., “Noisy independent factor analysis model for density estimation and classification”, Electron. J. Stat., 4 (2010), 707–736  crossref  mathscinet  zmath  isi
    17. Xiao Lin, “Dual Averaging Methods for Regularized Stochastic Learning and Online Optimization”, J. Mach. Learn. Res., 11 (2010), 2543–2596  mathscinet  zmath  isi  elib
    18. Nazin A., “Estimating the Principal Eigenvector of a Stochastic Matrix: Mirror Descent Algorithms via Game Approach with Application to PageRank Problem”, 49th IEEE Conference on Decision and Control (Cdc), 2010, 792–797  crossref  isi
    19. А. В. Назин, Б. Т. Поляк, “Рандомизированный алгоритм нахождения собственного вектора стохастической матрицы с применением к задаче PageRank”, Автомат. и телемех., 2011, № 2, 131–141  mathnet  mathscinet  zmath; A. V. Nazin, B. T. Polyak, “Randomized algorithm to determine the eigenvector of a stochastic matrix with application to the PageRank problem”, Autom. Remote Control, 72:2 (2011), 342–352  crossref  isi
    20. Gaiffas S., Lecue G., “Hyper-Sparse Optimal Aggregation”, Journal of Machine Learning Research, 12 (2011), 1813–1833  mathscinet  zmath  isi
    21. Nazin A.V., Miller B., “The Mirror Descent Control Algorithm for Weakly Regular Homogeneous Finite Markov Chains with Unknown Mean Losses”, 2011 50th IEEE Conference on Decision and Control and European Control Conference (CDC-Ecc), IEEE, 2011, 1779–1783  crossref  isi
    22. Rigollet Ph., Tsybakov A.B., “Sparse Estimation by Exponential Weighting”, Stat. Sci., 27:4 (2012), 558–575  crossref  mathscinet  zmath  isi  elib
    23. Dalalyan A.S., Tsybakov A.B., “Mirror Averaging with Sparsity Priors”, Bernoulli, 18:3 (2012), 914–944  crossref  mathscinet  zmath  isi  elib
    24. Lan G., “An Optimal Method for Stochastic Composite Optimization”, Math. Program., 133:1-2 (2012), 365–397  crossref  mathscinet  zmath  isi
    25. Ghadimi S., Lan G., “Optimal Stochastic Approximation Algorithms for Strongly Convex Stochastic Composite Optimization I: a Generic Algorithmic Framework”, SIAM J. Optim., 22:4 (2012), 1469–1492  crossref  mathscinet  zmath  isi
    26. А. В. Назин, С. В. Анулова, А. А. Тремба, “Алгоритм зеркального спуска для минимизации средних потерь, поступающих пуассоновским потоком”, Автомат. и телемех., 2014, № 6, 30–38  mathnet; A. V. Nazin, S. V. Anulova, A. A. Tremba, “A mirror descent algorithm for minimization of mean Poisson flow driven losses”, Autom. Remote Control, 75:6 (2014), 1010–1016  crossref  isi
    27. Nazin A., Anulova S., Tremba A., “Application of the Mirror Descent Method To Minimize Average Losses Coming By a Poisson Flow”, 2014 European Control Conference (Ecc), IEEE, 2014, 2194–2197  crossref  isi
    28. Nedic A., Lee S., “on Stochastic Subgradient Mirror-Descent Algorithm With Weighted Averaging”, SIAM J. Optim., 24:1 (2014), 84–107  crossref  mathscinet  zmath  isi  elib
    29. А. В. Гасников, Д. Ю. Дмитриев, “Об эффективных рандомизированных алгоритмах поиска вектора PageRank”, Ж. вычисл. матем. и матем. физ., 55:3 (2015), 355–371  mathnet  crossref  mathscinet  zmath  elib; A. V. Gasnikov, D. Yu. Dmitriev, “On efficient randomized algorithms for finding the PageRank vector”, Comput. Math. Math. Phys., 55:3 (2015), 349–365  crossref  isi  elib
    30. А. В. Гасников, Ю. Е. Нестеров, В. Г. Спокойный, “Об эффективности одного метода рандомизации зеркального спуска в задачах онлайн оптимизации”, Ж. вычисл. матем. и матем. физ., 55:4 (2015), 582–598  mathnet  crossref  mathscinet  zmath  elib; A. V. Gasnikov, Yu. E. Nesterov, V. G. Spokoiny, “On the efficiency of a randomized mirror descent algorithm in online optimization problems”, Comput. Math. Math. Phys., 55:4 (2015), 580–596  crossref  isi  elib
    31. А. В. Назин, А. А. Тремба, “Игровой алгоритм зеркального спуска в задаче робастного PageRank”, Автомат. и телемех., 2016, № 8, 105–124  mathnet  elib; A. V. Nazin, A. A. Tremba, “Saddle point mirror descent algorithm for the robust PageRank problem”, Autom. Remote Control, 77:8 (2016), 1403–1418  crossref  isi  elib
    32. А. В. Гасников, А. А. Лагуновская, И. Н. Усманова, Ф. A. Федоренко, “Безградиентные прокc-методы с неточным оракулом для негладких задач выпуклой стохастической оптимизации на симплексе”, Автомат. и телемех., 2016, № 10, 57–77  mathnet  elib; A. V. Gasnikov, A. A. Lagunovskaya, I. N. Usmanova, F. A. Fedorenko, “Gradient-free proximal methods with inexact oracle for convex stochastic nonsmooth optimization problems on the simplex”, Autom. Remote Control, 77:11 (2016), 2018–2034  crossref  isi
    33. Wang X., Ma Sh., Goldfarb D., Liu W., “Stochastic Quasi-Newton Method For Nonconvex Stochastic Optimization”, SIAM J. Optim., 27:2 (2017), 927–956  crossref  mathscinet  zmath  isi  scopus
    34. А. В. Назин, “Алгоритмы инерционного зеркального спуска в выпуклых задачах стохастической оптимизации”, Автомат. и телемех., 2018, № 1, 100–112  mathnet  elib; A. V. Nazin, “Algorithms of inertial mirror descent in convex problems of stochastic optimization”, Autom. Remote Control, 79:1 (2018), 78–88  crossref  isi
    35. Dalalyan A.S., Grappin E., Paris Q., “On the Exponentially Weighted Aggregate With the Laplace Prior”, Ann. Stat., 46:5 (2018), 2452–2478  crossref  mathscinet  zmath  isi  scopus
  • Проблемы передачи информации Problems of Information Transmission
    Просмотров:
    Эта страница:644
    Полный текст:246
    Литература:37
    Первая стр.:1
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020