This thesis studies the problem of optimization and learning in graphical models via stochastic approximation theory. First, in various multi-agent networked environments, the system can benefit from coordinating actions of two interacting agents at some cost of coordination, where a primary goal is to develop a distributed algorithm maximizing the coordination effect. Such pairwise coordinations and nodewise costs in the network can be captured by graphical model framework, which becomes the problem of finding the optimal graph parameter. We propose various distributed algorithms that require only one-hop message passing, which can be interpreted based on either Lagrange duality theory or game theory framework. Our algorithms are motivated by a stochastic approximation method that runs a Markov chain incompletely over time, but provably guarantees the convergence to the optimal solution. In machine learning field, for the problem of parameter learning in graphical models having latent variables, the standard approach, i.e., EM algorithm, is computationally intractable for high dimensional graphs in both E and M steps. Since the substitution of one step to a faster surrogate for combating against intractability can often cause failure in convergence, we propose a new learning algorithm which is computationally efficient and provably ensures convergence to a correct optimum via multi-time-scale stochastic approximation theory, where its key idea is to run only a few cycles of Markov chain in both steps. We demonstrate our theoretical findings through extensive simulations with synthetic data and/or real-world datasets.
이 논문에서는 그래프 모형을 최적화하거나 학습하는 반복 알고리즘에 대해 연구하였다. 확률론적 근사법 이론에 기반하여, 주변 사용자로부터 얻는 지역적 정보만을 사용하면서도 정확한 해로 수렴하는 알고리즘을 제시하였다. 첫째로, 네트워크 사용자들의 의견 결정 현상을 그래프 모형을 이용해 수학적으로 모델링하고, 이들이 정보를 주고 받으며 의견 조정을 이룸으로써 발생하는 이득을 극대화하기 위한 분산 알고리즘들을 제시하였다. 구체적으로, 이는 유한한 횟수의 불완전한 마르코프 연쇄 샘플링을 사용하며, 확률론적 근사법에 기반하여 최적화 해로의 수렴성을 보장하기 위한 조건을 규명하고, 또한 게임이론에 근거한 새로운 해석을 제시하고 있다. 둘째로, 은닉 요소를 가진 그래프 모형의 변수를 학습하는 문제를 다루며, 정확한 변수로의 수렴성을 보장할 수 없었던 기존 연구들의 한계점을 해결할 수 있는 새로운 학습 알고리즘을 제시하였다. 구체적으로, 유한한 횟수의 마르코프 연쇄 샘플링을 서로 결합된 두 시간 척도에 적용하여 효율적으로 학습하며, 다 시간 척도를 다루는 확률론적 근사법에 기반하여 올바른 변수로의 수렴성을 증명하였다.
