$\require{mediawiki-texvc}$

연합인증

연합인증 가입 기관의 연구자들은 소속기관의 인증정보(ID와 암호)를 이용해 다른 대학, 연구기관, 서비스 공급자의 다양한 온라인 자원과 연구 데이터를 이용할 수 있습니다.

이는 여행자가 자국에서 발행 받은 여권으로 세계 각국을 자유롭게 여행할 수 있는 것과 같습니다.

연합인증으로 이용이 가능한 서비스는 NTIS, DataON, Edison, Kafe, Webinar 등이 있습니다.

한번의 인증절차만으로 연합인증 가입 서비스에 추가 로그인 없이 이용이 가능합니다.

다만, 연합인증을 위해서는 최초 1회만 인증 절차가 필요합니다. (회원이 아닐 경우 회원 가입이 필요합니다.)

연합인증 절차는 다음과 같습니다.

최초이용시에는
ScienceON에 로그인 → 연합인증 서비스 접속 → 로그인 (본인 확인 또는 회원가입) → 서비스 이용

그 이후에는
ScienceON 로그인 → 연합인증 서비스 접속 → 서비스 이용

연합인증을 활용하시면 KISTI가 제공하는 다양한 서비스를 편리하게 이용하실 수 있습니다.

통계적 기계학습에서의 ADMM 알고리즘의 활용
ADMM algorithms in statistics and machine learning 원문보기

Journal of the Korean Data & Information Science Society = 한국데이터정보과학회지, v.28 no.6, 2017년, pp.1229 - 1244  

최호식 (경기대학교 응용통계학과) ,  최현집 (경기대학교 응용통계학과) ,  박상언 (경기대학교 경영정보학과)

초록
AI-Helper 아이콘AI-Helper

최근 여러 분야에서 데이터에 근거한 분석방법론에 대한 수요가 증대됨에 따라 이를 처리할 수 있는 최적화 방법이 발전되고 있다. 특히 통계학과 기계학습 분야의 문제들에서 요구되는 다양한 제약 조건은 볼록 최적화 (convex optimization) 방법으로 해결할 수 있다. 본 논문에서 리뷰하는 alternating direction method of multipliers (ADMM) 알고리즘은 선형 제약 조건을 효과적으로 처리할 수 있으며, 합의 방식을 통해 병렬연산을 수행할 수 있어서 범용적인 표준 최적화 툴로 자리매김 되고 있다. ADMM은 원래의 문제보다 최적화가 쉬운 부분문제로 분할하고 이를 취합함으로써 복잡한 원 문제를 해결하는 방식의 근사알고리즘이다. 부드럽지 않거나 복합적인 (composite) 목적 함수를 최적화할 때 유용하며, 쌍대이론과 proximal 작용소 이론을 토대로 체계적으로 알고리즘을 구성할 수 있기 때문에 통계 및 기계학습 분야에서 폭 넓게 활용되고 있다. 본 논문에서는 최근 통계와 관련된 여러 분야에서 ADMM알고리즘의 활용도를 살펴보고자 하며 주요한 두 가지 주제에 중점을 두고자 한다. (1) 목적식의 분할 전략과 증강 라그랑지안 방법 및 쌍대문제의 설명과 (2) proximal 작용소의 역할이다. 알고리즘이 적용된 사례로, 별점화 함수 추정 등의 조정화 (regularization)를 활용한 방법론들을 소개한다. 모의 자료를 활용하여 lasso 문제의 최적화에 대한 실증결과를 제시한다.

Abstract AI-Helper 아이콘AI-Helper

In recent years, as demand for data-based analytical methodologies increases in various fields, optimization methods have been developed to handle them. In particular, various constraints required for problems in statistics and machine learning can be solved by convex optimization. Alternating direc...

주제어

참고문헌 (43)

  1. Beck, A. and Teboulle, M. (2009). A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM Journal on Imaging Sciences, 2, 183-202. 

  2. Bertsekas, D. P. (2003). Nonlinear Programming. 2nd edition, Athena Scientific. 

  3. Boyd, S., Parikh, N., Chu, E., Peleato, B., and Eckstein, J. (2010). Distributed optimization and statistical learning via the alternating direction method of multipliers. Foundations and Trends in Optimization, 3, 1-122. 

  4. Boyd, S. and Vandenberghe, L. (2004). Convex optimization. Cambridge University Press. 

  5. Chen, X., Lin, Q., Kim, S., Carbonell, J. G., and Xing, E. P. (2012). Smoothing proximal gradient method for general structured sparse regression. Annals of Applied Statistics, 12, 719-752. 

  6. Chi, E. C. and Lange, K. (2015). Splitting methods for convex clustering. Journal of Computational and Graphical Statistics, 24, 994-1013. 

  7. Choi, H., Koo, J.-Y., and Park, C. (2015). Fused least absolute shrinkage and selection operator for credit scoring. Journal of Statistical Computation and Simulation, 85, 2135-2147. 

  8. Choi, H. and Lee, S. (2017). Convex clustering for binary data. Technical Report. 

  9. Choi, H. and Park, C. (2016). Clustering analysis of particulate matter data using shrinkage boxplot. Journal of the Korean Data Analysis Society, 18, 2435-2443. 

  10. Choi, H., Park, H., and Park, C. (2013). Support vector machines for big data analysis. Journal of the Korean data & Information Science Society, 24, 989-998. 

  11. Davis, D. and Wotao, Y. (2016). Convergence rate analysis of several splitting schemes, Splitting methods in communication, imaging, science, and engineering, Springer International Publishing, 115-163. 

  12. Fang, E. X., He, B., Liu, H., and Yuan, X. (2015). Generalized alteranting direction method of multipliers: new theoretical insights and applications. Mathematical Programming Computation, 7, 149-187. 

  13. Forero, P. A., Cano, A., and Giannakis, G. B. (2010). Consensus-based distributed support vector machines. Journal of Machine Learning Research, 6, 2873-2898. 

  14. Hastie, T., Tibshirani, and R. Wainwright, M. (2016). Statistical learning with sparsity: The lasso and generalizations, CRC Press. 

  15. Hallac, D., Leskovec, J., and Boyd, S. (2015). Network lasso: Clustering and optimization in large graphs. Proceeding KDD '15 Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 387-396. 

  16. Hwang, C. and Shim, J. (2017). Geographically weighted least squares-support vector machine. Journal of the Korean Data & Information Science Society, 28, 227-235. 

  17. He, B. and Yuan, X. (2012). On the o(1/n) convergence rate of teh Douglas-Rachford alternating direction method. SIAM Journal on Numerical Analysis, 50, 700-709. 

  18. Jeon, J. and Choi, H. (2016). The sparse Luce model. Applied Intelligence, https://doi.org/10.1007/s10489-016-0861-4, In press. 

  19. Jeon, J., Kwon, S., and Choi, H. (2017). Homogeneity detection for the high-dimensional generalized linear model. Computational Statistics and Data Analysis, 114, 61-74. 

  20. Kim, S. and Xing, E. P. (2012). Tree-guided group lasso for multi-response regression with structured sparsity, with an application to eQTL mapping. The Annals of Applied Statistics, 6, 1095-1117. 

  21. Lange, K. (2016). MM optimization algorithms. SIAM-Society for Industrial and Applied Mathematics. 

  22. Parekh, A. and Selesnick, I. W. (2017). Improved sparse low-rank matrix estimation. arXiv:1605.00042v2. 

  23. Parikh, N. and Boyd, S. (2013). Proximal algorithms. Foundations and Trends in Optimization. 1, 123-231. 

  24. Park, C., Kim, Y., Kim, J., Song, J., and Choi, H. (2015). Data mining using R. 2nd edition, Kyowoosa. 

  25. Polson, N. G., Scott, J. G., and Willard, B. T. (2015). Proximal algorithms in statistics and machine learning. Statistical Science, 30, 559-581. 

  26. Ramdas, A. and Tibshirani, R. (2016). Fast and flexible admm algorithms for trend filtering. Journal of Computational and Graphical Statistics, 25, 839-858. 

  27. Taylor, G., Burmeister, R., Xu, Z., Singh, B., Patel, A., Goldstein, T. (2016). Training neural networks without gradients: A scalable ADMM approach. CoRR, arXiv1605.02026. 

  28. Tibshirani, R. J., Hoefling, H., and Tibshirani, R. (2011). Nearly-Isotonic regression. Technometrics, 53, 54-61. 

  29. Tibshirani, R., Saunders, M., Rosset, S., Zhu, J., and Knight, K. (2005). Sparsity and smoothness via the fused lasso. Journal of the Royal Statistical Society Series B, 67, 91-108. 

  30. Tibshirani, R. J. and Taylor, J. (2011). The solution path of the generalized lasso. The Annals of Statistics, 39, 1335-1371. 

  31. Tibshirani, R. (2014). Adaptive piecewise polynomial estimation via trend filtering. The Annals of Statistics, 42, 285-323. 

  32. Wen, W., Wu, C., Wang, Y., Chen, Y., and Li, H. (2016). Learning structured sparsity in deep neural networks. In Neural Information Processing Systems, 2074-2082. 

  33. Xu, Z., Taylor, G., Li, H., Figueiredo, M., Yuan, X., and Goldstein, T. (2017). Adaptive consensus ADMM for distributed optimization. arXiv:1706.02869v2. 

  34. Xu, Y., Yin, W., Wen, Z., and Zhang, Y. (2012). An alternating direction algorithm for matrix completion with nonnegative factors. Frontiers of Mathematics in China, 7, 365-384. 

  35. Yang, Y., Sun, J., Li, H., and Xu, Z. (2017). ADMM-Net: A deep learning approach for compressive sensing MRI. CoRR, arXiv:1705.06869. 

  36. Yin, W., Osher, S., Goldfarb, D., and Darbon, J. (2008). Bregman iterative algorithms for l1-minimization with applications to compressed sensing. SIAM Journal on Imaging Sciences, 1, 143-168. 

  37. Yuan, M. and Lin, Y. (2006). Model selection and estimation in regression with grouped variables. Journal of the Royal Statistical Society Series B, 68, 49-67. 

  38. Yan, X. and Bien, J. (2015). Hierarchical sparse modeling: A choice of two group lasso formulations. Technical Report. 

  39. Yu, G. and Liu, Y. (2016). Sparse regression incorporating graphical structure among predictors. Journal of the American Statistical Association, 111, 707-720. 

  40. Zhang, X., Burger, M., Bresson, X., and Osher, S. (2010). Bregmanized nonlocal regularization for deconvolution and sparse reconstruction. SIAM Journal of Imaging Science, 3, 253-276. 

  41. Zhang, X., Burger, M., and Osher, S. (2011). A unified primal-dual algorithm framework based on Bregman iteration. Journal of Scientific Computing, 46, 20-46. 

  42. Zhao, P., Rocha, G., and Yu, B. (2009). The composite absolute penalties family for grouped and hierarchical variable selection. The Annals of Statistics, 37, 3468-3497. 

  43. Zhu, Y. (2017). An augmented ADMM algorithm with application to the generalized lasso Problem. Journal of Computational and Graphical Statistics, 26, 195-204. 

관련 콘텐츠

오픈액세스(OA) 유형

GOLD

오픈액세스 학술지에 출판된 논문

이 논문과 함께 이용한 콘텐츠

저작권 관리 안내
섹션별 컨텐츠 바로가기

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

AI-Helper 아이콘
AI-Helper
안녕하세요, AI-Helper입니다. 좌측 "선택된 텍스트"에서 텍스트를 선택하여 요약, 번역, 용어설명을 실행하세요.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.

선택된 텍스트

맨위로