Оптимизация параметров субградиентного метода на основе двухранговой коррекции матриц метрики

Оптимизация параметров субградиентного метода на основе двухранговой коррекции матриц метрики

Крутиков В. Н., Станимирович П. С., Инденко О. Н., Товбис Е. М., Казаковцев Л. А.
Дискретный анализ и исследование операций, 29, 3, 24-44 (2022)
Скачать статью

УДК 519.8 
DOI: 10.33048/daio.2022.29.739

Аннотация:

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

Литература:
  1. Шор Н. З. Применение метода градиентного спуска для решения сетевой транспортной задачи // Мат. науч. семинара по теор. и прикл. вопросам кибернетики и исследования операций. Вып. 1. К.: Науч. совет по кибернетике АН УССР, 1962. С. 9–17.
     
  2. Поляк Б. Т. Один общий метод решения экстремальных задач // Докл. АН СССР. 1967. Т. 174, вып. 1. С. 33–36.
     
  3. Поляк Б. Т. Введение в оптимизацию. М.: Наука, 1983.
     
  4. Wolfe P. Note on a method of conjugate subgradients for minimizing nondifferentiable functions // Math. Program. 1974. V. 7, No. 1. P. 380–383.
     
  5. Гольштейн Е. Г., Немировский А. С., Нестеров Ю. Е. Метод уровней, его обобщения и приложения // Экономика и мат. методы. 1983. Т. 31, вып. 3. С. 164–180.
     
  6. Nesterov Yu. E. Universal gradient methods for convex optimization problems // Math. Program. Ser. A. 2015. V. 152. P. 381–404.
     
  7. Gasnikov A. V., Nesterov Yu. E. Universal method for stochastic composite optimization. Ithaca, NY: Cornell Univ., 2016. (Cornell Univ. Libr. e-Print Archive; arXiv:1604.05275).
     
  8. Ouyang H., Gray A. Stochastic smoothing for nonsmooth minimizations: Accelerating SGD by exploiting structure // Proc. 29th Int. Conf. Machine Learning (Edinburgh, Scotland, June 26–July 1, 2012). Madison, WI: Omnipress, 2012. P. 33–40.
     
  9. Boob D., Deng Q., Lan G. Stochastic first-order methods for convex and nonconvex functional constrained optimization // Math. Program. 2022. [in print]. Available at doi.org/10.1007/s10107-021-01742-y (accessed June 17, 2022).
     
  10. Lan G. First-order and stochastic optimization methods for machine learning. Cham: Springer, 2020.
     
  11. Ghadimi S., Lan G. Accelerated gradient methods for nonconvex nonlinear and stochastic programming // Math. Program. 2016. V. 156, No. 1–2. P. 59–99.
     
  12. Fang C., Li C. J., Lin Z., Zhang T. Spider: Near-optimal non-convex optimization via stochastic path-integrated differential estimator // Advances in Neural Information Processing Systems 31. 32nd Annual Conf. (Montréal, Canada, Dec. 3–8, 2018). Red Hook, NY: Curran Associates, 2018. P. 687–697.
     
  13. Немировский А. С., Юдин Д. Б. Сложность задач и эффективность методов оптимизации. М.: Наука, 1979. 
     
  14. Шор Н. З. Методы минимизации недифференцируемых функций и их приложения. К.: Наук. думка, 1979. 
     
  15. Cao H., Song Y., Khan K. Convergence of subtangent-based relaxations of non-linear programs // Processes. 2019. V. 7, No. 4. P. 221.
     
  16. Поляк Б. Т. Минимизация негладких функционалов // Журн. вычисл. математики и мат. физики. 1969. Т. 9, вып. 3. С. 509–521.
     
  17. Крутиков В. Н., Самойленко Н. С., Мешечкин В. В. О свойствах метода минимизации выпуклых функций, релаксационного по расстоянию до экстремума // Автоматика и телемеханика. 2019. Т. 80, вып. 1. С. 126–137.
     
  18. Демьянов В. Ф., Васильев Л. В. Недифференцируемая оптимизация. М.: Наука, 1981.
     
  19. Lemarechal C. An extension of Davidon methods to non-differentiable problems // Math. Program. Study. 1975. V. 3. P. 95–109.
     
  20. Крутиков В. Н., Петрова Т. В. Релаксационный метод минимизации с растяжением пространства в направлении субградиента // Экономика и мат. методы. 2003. Т. 39, вып. 1. С. 106–119.
     
  21. Крутиков В. Н., Горская Т. А. Семейство релаксационных субградиентных методов с двухранговой коррекцией матриц метрики // Экономика и мат. методы. 2009. Т. 45, вып. 4. С. 37–80.
     
  22. Скоков В. А. Замечание к методам оптимизации, использующим операцию растяжения пространства // Кибернетика и систем. анализ. 1974. № 4. С. 115–117.
     
  23. Крутиков В. Н., Самойленко Н. С. О скорости сходимости субградиентного метода с изменением метрики и его приложения в схемах нейросетевых приближений // Вестн. Томск. гос. ун-та. Сер. Математика и механика. 2018. № 55. С. 22–37.
     
  24. Nocedal J., Wright S. J. Numerical optimization. New York: Springer, 2006.
     
  25. Avriel M. Nonlinear programming: Analysis and methods. Mineola: Dover Publ., 2003.
     
  26. Нурминский Е. А., Тьен Д. Метод сопряжённых субградиентов с ограниченной памятью // Автоматика и телемеханика. 2014. Т. 75, вып. 4. С. 646–656.
     
  27. Цыпкин Я. З. Основы теории обучающихся систем. М.: Наука, 1970.
     
  28. Жуковский Е. Л., Липцер Р. Ш. О рекуррентном способе вычисления нормальных решений линейных алгебраических уравнений // Журн. вычисл. математики и мат. физики. 1972. Т. 12, вып. 4. С. 843–857.
     
  29. Krutikov V. N., Kazakovtsev L. A., Kazakovtsev V. L. Non-smooth regularization in radial artificial neural networks // IOP Conf. Ser.: Materials Science and Engineering. 2018. V. 450, No. 4, ID 042010. 7 p.
     
  30. Krutikov V. N., Kazakovtsev L. A., Shkaberina G. Sh., Kazakovtsev V. L. New method of training two-layer sigmoid neural networks using regularization // IOP Conf. Ser.: Materials Science and Engineering. 2019. V. 537, No. 4, ID 042055. 6 p.
     
  31. Tibshirani R. J. Regression shrinkage and selection via the Lasso // J. Royal Stat. Soc. Ser. B (Methodological). 1996. V. 58. P. 267–288.
     
  32. Frostig R., Ge R., Kakade S. M., Sidford A. Un-regularizing: Approximate proximal point and faster stochastic algorithms for empirical risk minimization // Proc. Mach. Learn. Res. 2015. V. 37. P. 2540–2548.

Исследование выполнено при финансовой поддержке Министерства науки и высшего образования России (гос. контракт № FEFE–2020–0013). Работа второго автора выполнена при поддержке Научного фонда Республики Сербия (грант № 7750185) и Министерства образования, науки и технологического развития Республики Сербия (контракт № 451–03–68/2020–14/200124).

Крутиков Владимир Николаевич
  1. Кемеровский гос. университет,
    ул. Красная, 6, 650043 Кемерово, Россия

E-mail: krutikovvn@rambler.ru

Станимирович Предраг
  1. Факультет естественных наук и математики, Нишский университет,
    ул. Вышеградска, 33, 18000 Ниш, Сербия

E-mail: pecko@pmf.ni.ac.rs

Инденко Оксана Николаевна
  1. Кемеровский гос. университет,
    ул. Красная, 6, 650043 Кемерово, Россия

E-mail: oksana230805@mail.ru

Товбис Елена Михайловна
  1. Сибирский гос. университет науки и технологий им. акад. Решетнёва,
    пр. Красноярский рабочий, 31, 660031 Красноярск, Россия

E-mail: sibstu2006@rambler.ru

Казаковцев Лев Александрович
  1. Сибирский гос. университет науки и технологий им. акад. Решетнёва,
    пр. Красноярский рабочий, 31, 660031 Красноярск, Россия

E-mail: levk@bk.ru

Статья поступила 10 мая 2022 г. 
После доработки — 10 мая 2022 г. 
Принята к публикации 12 мая 2022 г.

Abstract:

We establish a relaxation subgradient method (RSM) that includes parameter optimization utilizing metric rank-two correction matrices with a structure analogous to quasi-Newtonian (QN) methods. The metric matrix transformation consists of suppressing orthogonal and amplifying collinear components of the minimal length subgradient vector. The problem of constructing a metric matrix is formulated as a problem of solving an involved system of inequalities. Solving such system is based on a new learning algorithm. An estimate for its convergence rate is obtained depending on the parameters of the subgradient set. A new RSM has been developed and investigated on this basis. Computational experiments on complex large-scale functions confirm the effectiveness of the proposed algorithm. 
Tab. 4, bibliogr. 32.

References:
  1. N. Z. Shor, Application of the gradient descent method for solving network transportation problems, in Proc. Scientific Seminar on Theoretic and Applied Problems of Cybernetics and Operations Research, Issue 1 (Nauch. sovet po kibernetike AN USSR, Kyev, 1962), pp. 9–17 [Russian].
     
  2. B. T. Polyak, A general method for solving extremal problems, Dokl. Akad. Nauk SSSR 174 (1), 33–36 (1967) [Russian].
     
  3. B. T. Polyak, Introduction to Optimization (Nauka, Moscow, 1983) [Russian].
     
  4. P. Wolfe, Note on a method of conjugate subgradients for minimizing nondifferentiable functions, Math. Program. 7 (1), 380–383 (1974).
     
  5. E. G. Gol’shtein, A. S. Nemirovskii, and Yu. E. Nesterov, Level method, its generalizations and applications, Ekon. Mat. Metody 31 (3), 164–180 (1983) [Russian].
     
  6. Yu. E. Nesterov, Universal gradient methods for convex optimization problems, Math. Program., Ser. A, 152, 381–404 (2015).
     
  7. A. V. Gasnikov and Yu. E. Nesterov, Universal method for stochastic composite optimization (Cornell Univ., Ithaca, NY, 2016) (Cornell Univ. Libr. ePrint Archive, arXiv:1604.05275).
     
  8. H. Ouyang and A. Gray, Stochastic smoothing for nonsmooth minimizations: Accelerating SGD by exploiting structure, in Proc. 29th Int. Conf. Machine Learning, Edinburgh, Scotland, June 26–July 1, 2012 (Omnipress, Madison, WI, 2012), pp. 33–40.
     
  9. D. Boob, Q. Deng, and G. Lan, Stochastic first-order methods for convex and nonconvex functional constrained optimization // Math. Program. 2022. [in print]. Available at doi.org/10.1007/s10107-021-01742-y (accessed June 17, 2022).
     
  10. G. Lan, First-Order and Stochastic Optimization Methods for Machine Learning (Springer, Cham, 2020).
     
  11. S. Ghadimi and G. Lan, Accelerated gradient methods for nonconvex nonlinear and stochastic programming, Math. Program. 156 (1–2), 59–99 (2016).
     
  12. C. Fang, C. J. Li, Z. Lin, and T. Zhang, Spider: Near-optimal non-convex optimization via stochastic path-integrated differential estimator, in Advances in Neural Information Processing Systems 31 (32nd Annual Conf., Montréal, Canada, Dec. 3–8, 2018) (Curran Associates, Red Hook, NY, 2018), pp. 687–697.
     
  13. A. S. Nemirovskii and D. B. Yudin, Complexity of Problems and Efficiency of Methods in Optimization (Nauka, Moscow, 1979) [Russian].
     
  14. N. Z. Shor, Minimization Methods for Non-differentiable Functions and Their Applications (Nauk. Dumka, Kyev, 1979) [Russian].
     
  15. H. Cao, Y. Song, and K. Khan, Convergence of subtangent-based relaxations of non-linear programs, Processes 7 (4), 221 (2019).
     
  16. B. T. Polyak, Minimization of nonsmooth functionals, Zh. Vychisl. Mat. Mat. Fiz. 9 (3), 509–521 (1969) [Russian] [Comput. Math. Math. Phys. 9 (3), 14–29 (1969)].
     
  17. V. N. Krutikov, N. S. Samoilenko, and V. V. Meshechkin, On the properties of the method of minimization for convex functions with relaxation on the distance to extremum, Avtom. Telemekh., No. 1, 126–137 (2019) [Russian] [Autom. Remote Control 80 (1), 102–111 (2019)].
     
  18. V. F. Demyanov and L. V. Vasilyev, Non-differentiable Optimization (Nauka, Moscow, 1981) [Russian].
     
  19. C. Lemarechal, An extension of Davidon methods to non-differentiable problems, Math. Program. Study 3, 95–109 (1975).
     
  20. V. N. Krutikov and T. V. Petrova, Relaxation method of minimization with space extension in the subgradient direction, Ekon. Mat. Metody 39 (1), 106–119 (2003) [Russian].
     
  21. V. N. Krutikov and T. A. Gorskaya, A family of subgradient relaxation methods with rank 2 correction of metric matrices, Ekon. Mat. Metody 45 (4), 37–80 (2009) [Russian].
     
  22. V. A. Skokov, Note on minimization methods employing space stretching, Kibern. Sist. Anal., No. 4, 115–117 (1974) [Russian] [Cybern. Syst. Anal. 10 (4), 689–692 (1974)].
     
  23. V. N. Krutikov and N. S. Samoilenko, On the convergence rate of the subgradient method with metric variation and its applications in neural network approximation schemes, Vestn. Tomsk. Gos. Univ., Ser. Mat. Mekh., No. 55, 22–37 (2018) [Russian].
     
  24. J. Nocedal and S. J. Wright, Numerical Optimization (Springer, New York, 2006).
     
  25. M. Avriel, Nonlinear Programming: Analysis and Methods (Dover Publ., Mineola, 2003).
     
  26. E. A. Nurminskii and D. Tien, Method of conjugate subgradients with constrained memory, Avtom. Telemekh., No. 4, 67–80 (2014) [Russian] [Autom. Remote Control 75 (4), 646–656 (2014)].
     
  27. Ya. Z. Tsypkin, Basics of Theory of Learning Systems (Nauka, Moscow, 1970) [Russian].
     
  28. E. L. Zhukovskii and R. Sh. Liptser, A recurrence method for computing the normal solutions of linear algebraic equations, Zh. Vychisl. Mat. Mat. Fiz. 12 (4), 843–857 (1972) [Russian] [Comput. Math. Math. Phys. 12 (4), 1–18 (1972)].
     
  29. V. N. Krutikov, L. A. Kazakovtsev, and V. L. Kazakovtsev, Nonsmooth regularization in radial artificial neural networks, IOP Conf. Ser.: Materials Science and Engineering 450 (4), ID 042010. 7 p. (2018).
     
  30. V. N. Krutikov, L. A. Kazakovtsev, G. Sh. Shkaberina, and V. L. Kazakovtsev, New method of training two-layer sigmoid neural networks using regularization, IOP Conf. Ser.: Materials Science and Engineering 537 (4), ID 042055. 6 p. (2019).
     
  31. R. J. Tibshirani, Regression shrinkage and selection via the Lasso, J. Royal Stat. Soc., Ser. B (Methodological) 58, 267–288 (1996).
     
  32. R. Frostig, R. Ge, S. M. Kakade, and A. Sidford, Un-regularizing: Approximate proximal point and faster stochastic algorithms for empirical risk minimization, Proc. Mach. Learn. Res. 37, 2540–2548 (2015).