본문 바로가기
KERD
논문KCI 등재

A memory efficient incremental gradient method for regularized minimization

Sangwoon Yun
대한수학회 (The Korean Mathematical Society)|2016.03|대한수학회보 (Bulletin of the KMS)|제53권 제2호|pp. 589-600

2

조회

0

다운로드

0

인용

0

참고문헌

키워드

regularizationincremental gradient methodnonsmoothrunning average
주제분류수학

초록

In this paper, we propose a new incremental gradient method for solving a regularized minimization problem whose objective is the sum of $m$ smooth functions and a (possibly nonsmooth) convex function. This method uses an adaptive stepsize. Recently proposed incremental gradient methods for a regularized minimization problem need $O(mn)$ storage, where $n$ is the number of variables. This is the drawback of them. But, the proposed new incremental gradient method requires only $O(n)$ storage.

Abstract

In this paper, we propose a new incremental gradient method for solving a regularized minimization problem whose objective is the sum of $m$ smooth functions and a (possibly nonsmooth) convex function. This method uses an adaptive stepsize. Recently proposed incremental gradient methods for a regularized minimization problem need $O(mn)$ storage, where $n$ is the number of variables. This is the drawback of them. But, the proposed new incremental gradient method requires only $O(n)$ storage.

참고문헌 (31)

  1. D. P. Bertsekas, "A new class of incremental gradient methods for least squares problems", SIAM J. Optim, 7(4), pp.913~926 (1997)
  2. D. P. Bertsekas, "Nonlinear Programming, 2" (1999), Athena Scientific
  3. D. P. Bertsekas, "Parallel and Distributed Computation: Numerical Methods" (1989), Prentice-Hall
  4. D. Blatt, "A convergent incremental gradient method with a constant step size", SIAM J. Optim, 18(1), pp.29~51 (2007)
  5. P. S. Bradley, "Mathematical programming for data mining: formulations and challenges", INFORMS J. Comput, 11(3), pp.217~238 (1999)
  6. S. Chen, "Atomic decomposition by basis pursuit", SIAM J. Sci. Comput, 20(1), pp.33~61 (1998)
  7. N. Cristianini, "An Introduction to Support Vector Machines and Other Kernel-Based Learning Methods" (2000), Cambridge University Press
  8. I. Daubechies, "An iterative thresholding algorithm for linear inverse problems with a sparsity constraint", Comm. Pure Appl. Math, 57(11), pp.1413~1457 (2004)
  9. Regularization paths for generalized lienar models via coordinate descent, "J. Friedman", Department of Statistics, Stanford University, ~ (2009)
  10. A. A. Gaivoronski, "Convergence properties of back-propagation for neural nets via theory of stochastic gradient methods. Part I", Optim. Methods Softw, 4, pp.117~134 (1994)
  11. L. Grippo, "A class of unconstrained minimization methods for neural network training", Optim. Methods Softw, 4, pp.135~150 (1994)
  12. C.-H. Ho, "Large-scale linear support vector regression", J. Mach. Learn. Res, 13, pp.3323~3348 (2012)
  13. A. Juditsky, "Stochastic approximation approach to stochastic programming", SIAM J. Optim, 19, pp.1574~1609 (2009)
  14. K. Koh, "An interior-point method for large-scale ℓ1-regularized logistic regression", J. Mach. Learn. Res, 8, pp.1519~1555 (2007)
  15. S. Lee, "Efficient ℓ1-regularized logistic regression", Proceedings of the 21st National Conference on Artificial Intelligence (2006)
  16. Z.-Q. Luo, "Analysis of an approximate gradient projection method with applications to the backpropagation algorithm", Optim. Methods Softw, 4, pp.85~101 (1994)
  17. O. L. Mangasarian, "Large scale kernel regression via linear pro-gramming", Mach. Learn, 46, pp.255~269 (2002)
  18. O. L. Mangasarian, "Serial and parallel backpropagation convergence via nonmonotone perturbed minimization", Optim. Methods Softw, 4, pp.103~116 (1994)
  19. Y. Nesterov, "Primal-dual subgradient methods for convex problems", Math. Program, 120(1), pp.221~259 (2009)
  20. R. T. Rockafellar, "Convex Analysis" (1970), Princeton University Press
  21. D. E. Rumelhart, "Parallel Distributed Processing–Explorations in the Microstructure of Cognition", pp.318~362 (1986), MIT press
  22. S. Sardy, "AMlet, RAMlet, and GAMlet: automatic nonlinear fitting of additive models, robust and generalized, with wavelets", J. Comput. Graph. Statist, 13(2), pp.283~309 (2004)
  23. R. Tibshirani, "Regression shrinkage and selection via the lasso", J. Roy. Statist. Soc. Ser. B, 58(1), pp.267~288 (1996)
  24. P. Tseng, "On the rate of convergence of a partially asynchronous gradient projection algorithm", SIAM J. Optim, 1(4), pp.603~619 (1991)
  25. P. Tseng, "A coordinate gradient descent method for nonsmooth separable minimization", Math. Program, 117(1-2), pp.387~423 (2009)
  26. P. Tseng, "Incrementally updated gradient methods for constrained and regularized opti-mization", J. Optim. Theory Appl, 160(3), pp.832~853 (2014)
  27. V. Vapnik, "The Nature of Statistical Learning Theory" (2000), Springer-Verlag
  28. L. Wang, "Efficient regularized solution path algorithms with applications in machine learning and data mining", Ph.D, pp.2008
  29. H. White, "Learning in artificial neural networks: a statistical perspective", Neural Com-put, 1, pp.425~464 (1989)
  30. H. White, "Some asymptotic results for learning in single hidden–layer feedforward network models", J. Amer. Statist. Assoc, 84(408), pp.1003~1013 (1989)
  31. L. Xiao, "Dual averaging methods for regularized stochastic learning and online opti-mization", J. Mach. Learn. Res, 11, pp.2543~2596 (2010)

관련 논문AI추천

A CLASS OF NONMONOTONE SPECTRAL MEMORY GRADIENT METHODJingzhao Liu, Jinsong Zang, Zhensheng Yu대한수학회 · 대한수학회지2010 · 제47권 제1호MODIFIED LIMITED MEMORY BFGS METHOD WITH NONMONOTONE LINE SEARCH FOR UNCONSTRAINED OPTIMIZATIONGonglin Yuan, Yanlin Wu, Zengxin Wei대한수학회 · 대한수학회지2010 · 제47권 제4호An Iterative Method for Equilibrium and Constrained Convex Minimization ProblemsMaryam Yazdi, Mohammad Mehdi Shabani, Saeed Hashemi Sababe경북대학교 자연과학대학 수학과 · Kyungpook Mathematical Journal2022 · 제62권 제1호Weak and strong convergence of subgradient extragradient methods for pseudomonotone equilibrium problemsDang Van Hieu대한수학회 · 대한수학회논문집2016 · 제31권 제4호A PROXIMAL POINT-TYPE ALGORITHM FOR PSEUDOMONOTONE EQUILIBRIUM PROBLEMSHo Geun Hyun, Jong Kyu Kim, Pham Ngoc Anh대한수학회 · 대한수학회보2012 · 제49권 제4호A stochastic variance reduction method for PCA by an exact penalty approach윤상운, 이재화, 정윤모대한수학회 · 대한수학회보2018 · 제55권 제4호

이 간행물의 다른 논문 (24건)

Inequalities for the angular derivatives of certain classes of holomorphic functions in the unit discB\"{u}lent Nafi \"{O}rnekpp. 325-334Existence results for anti-periodic boundary value problems of nonlinear second-order impulsive $q_k$-difference equationsJessada Tariboon, Sotiris K. Ntouyas, Phollakrit Thiramanuspp. 335-350Entropy-based goodness of fit test for a composite hypothesisSangyeolLeepp. 351-363A note on the value distribution of $f^2(f')^n$ for $n\geq 2$Yan Jiangpp. 365-371On difference quotients of Chebyshev polynomialsJung Hee Lee, 김선홍pp. 373-386
원문 보기