Multiplicative Weights Update

Thatchaphol Saranurak 강의를 듣고 안 까먹으려고 작성

1. Warmup: Two Action Setting

$n$ 명의 전문가와 함께 주식 시장을 $T$일에 걸쳐 예측하려고 한다. 매일 다음과 같은 일이 일어난다:

• 각각의 전문가가 오늘의 주식 시장이 상승인지 하락인지 예측한다.
• 당신은 이를 보고 오늘 주식 시장이 상승인지 하락인지 결정한다.
• 이후 주식 시장의 결과가 나온다. (주식 시장은 adversarial할 수 있다. 즉 당신의 결정의 반대만 찍는 등의 일이 발생할 수 있음)

Loss를 결과를 못 맞춘 날의 수로 정의하자. 주식 시장이 무조건 내가 찍은 것의 반대만 찍는다면 Loss가 $T$ 가 나오는 것은 어렵지 않다. 고로 목표는 최고의 전문가에 비해서 그렇게 못하지 않는 전략을 찾는 것이다.

주식 시장의 모든 날을 맞출 수 있는 전문가가 존재한다고 가정하면, 다음과 같은 알고리즘을 사용할 수 있다.

• 현재 남은 전문가들 중 다수 의견을 따른다.
• 다수 의견이 정답이라면 아무 문제 없다.
• 다수 의견이 오답이라면 다수 의견을 낸 모든 전문가들을 숙청(!) 하자.

모든 날을 맞추는 전문가는 숙청당하지 않고, 오답을 낼 때마다 전문가의 수가 반으로 줄어드니, Loss가 $\log_2 n$ 이하임이 보장된다.

이제 위 가정을 없애자. 이 때는 다음과 같은 알고리즘을 사용할 수 있다.

• 현재 남은 전문가들 중 다수 의견을 따른다.
• 다수 의견이 정답이라면 아무 문제 없다.
• 다수 의견이 오답이라면 다수 의견을 낸 모든 전문가들을 숙청(!) 하자.
• 모든 전문가들이 숙청당했다면 전부 부활(!)시킨다.

내가 모든 전문가들을 부활시킨 횟수를 $r$ 이라고 하자.

• 최고의 전문가의 Loss는 $r$ 이상이다. 모두 $r$번 숙청당했기 때문이다.
• 나의 Loss는 $(r+1) \log_2 n$ 이하이다. 각 부활 사이에 최대 $\log_2 n$ 번 오답을 냈을 것이기 때문이다.

고로 내가 내는 오답의 수는 최적 전문가의 오답의 수의 $O(\log n)$ 배 이하이다. 더 개선하면 $(2+\epsilon)$배로 줄일 수도 있다고 한다.

한편 $2$ 배보다 잘하는 것은 불가능하다. 전문가 두 명이 있는데 한 명은 항상 상승한다 그러고 한 명은 항상 하락한다고 한다고 하자. 그리고 시장은 내 예측의 반대만 찍는다고 하자 (참 답답하다). 나는 무조건 모든 문제를 틀리게 되어 있으며, 사실 내가 무엇을 대답하는지 자체가 중요하지 않다. 내 대답 중 적게 등장한 답을 고른 전문가가 반 이하의 문제를 틀리게 되기 때문에, 내가 $2$ 배보다 잘하는 것이 불가능하게 하는 adversary가 존재한다.

2. General Setting

$n$ 명의 전문가와 함께 주식 시장을 $T$일에 걸쳐 예측하려고 한다. 매일 다음과 같은 일이 일어난다:

• 당신은 $n$ 명의 전문가 중 한 명의 전문가를 골라서 그 사람의 의견을 따른다.
• 각 전문가의 손실이 $[-1, 1]$ 사이의 수로 공개된다. adversarial할 수 있다. 음수면 이득이다.
• 당신은 앞에서 고른 전문가의 손실만큼의 손실을 얻는다. (음수일 경우 이득을 얻는다.)

이걸 그대로 플레이하면 2-Action Setting과 비슷한 이유로 $n$ 배보다 잘하는 것이 불가능하다. 그래서 당신은 랜덤성 을 사용할 수 있다. 구체적으로, 당신은 어떠한 확률 분포 $p_1, p_2, \ldots, p_n$ 을 골라서, $p_i$ 의 확률로 $i$ 번 전문가의 의견을 고른다. 시장은 당신의 확률 분포를 읽고 adversarial하게 행동할 수 있지만 랜덤이 그 확률에 따라 어떤 의견을 골랐는지는 알 수 없다 (그걸 알면 앞이랑 똑같아짐). 그 때 당신은 손실 기댓값을 최소화해야 한다.

다시 말해서, 매 $t$ 일에 대해:

• 당신은 벡터 $p^t_1, p^t_2, \ldots, p^t_n$ 을 고른다. ($p^t_i \geq 0, \sum p^t_i = 1$)
• 시장은 손실 벡터 $l^t_1, l^t_2, \ldots, l^t_n$ 을 반환한다. ($l^t_i \in [-1, 1]$)
• 당신은 $\ell^t = \sum p^t_i l^t_i$ 만큼의 손실을 얻는다.

당신이 최종적으로 얻은 손실은 $L_A = \sum_{t = 1}^{T} \ell^t$ 이고, $i$ 번 전문가가 얻은 손실은 $L_i = \sum_{t=1}^T l_i^t$ 이다. 최고의 전문가가 얻은 손실은 $\min L_i$ 이다. $L_A$ 를 $\min L_i$ 만큼 작게 유지할 수 있을까?

아래 설명할 Multiplicative Weights Update를 사용하면 가능하다.

• 초기 $w_1, w_2, \ldots, w_n = 1$ 로 설정하자. 대략 각 전문가의 신뢰도 에 대응된다.
• 매 $t = 1, \ldots, T$ 에 대해
  • $p_i^t = \frac{w_i}{\sum_j w_j}$ 로 고른다.
  • 시장은 손실 벡터 $l^t_1, l^t_2, \ldots, l^t_n$ 을 반환한다. ($l^t_i \in [-1, 1]$)
  • $w_i := w_i \cdot (1 - \epsilon \cdot l_i^t)$ 로 신뢰도를 업데이트한다. (1의 손실을 봤다면 신뢰도가 $\epsilon$ 배만큼 깎이고, $-1$ 의 손실을 봤다면 신뢰도가 $\epsilon$ 배만큼 증가한다.)

다음 사실을 증명할 수 있다 (증명은 여기에는 생략한다. 위 유튜브 링크 보면 있음)

Theorem 1. 임의의 $\epsilon \in (0, 1/2]$ 에 대해서 위 알고리즘은 $L_A \le L_* + \epsilon T + \frac{\ln n}{ \epsilon}$ 을 보장한다.

$\epsilon = \sqrt{\frac{\ln n}{T}}$ 로 설정하면 $L_A \le L_* + 2\sqrt{T \ln n}$ 가 보장된다. 즉 손실이 증가하는 속도가 $T$ 가 증가하는 속도에 비해 제곱근된 정도로 느리다.

추가로 손실 벡터가 $[0, 1]$ 에 있다고 하면 다음도 성립한다:

Theorem 2. 임의의 $\epsilon \in (0, 1/2]$ 에 대해서 위 알고리즘은 $L_A \le (1 +\epsilon) L_* + \frac{\ln n}{ \epsilon}$ 을 보장한다.

3. Linear Programming with MWU

$\Delta_n = \{x | x \geq 0, \sum x_i = 1\}$ 을 만족하는 벡터의 집합이라고 하자. 즉, 확률 분포이다.

목표는 MWU를 사용해서 다음과 같은 LP를 푸는 것이다:

• Given $A \in [-1, 1]^{m \times n}, b \in \mathbb{R}^m$
• Find $x \in \Delta_n$ such that $Ax \le b + 2 \epsilon \mathbb{1}$ or state that no solution such that $Ax \le b$ exists

Multiplicative Weights Update를 다음과 같이 사용하자.

• 초기 $w_1, w_2, \ldots, w_n = 1$ 로 설정하자.
• 매 $t = 1, \ldots, T$ 에 대해
  • $p_i^t = \frac{w_i}{\sum_j w_j}$ 로 고른다.
  • $Ap^t \le b + 2\epsilon\mathbb{1}$ 인지를 판별한다. 맞다면 $p^t$ 를 반환한다.
  • 아니라면 $A_{i_t} \cdot p^t > b + 2\epsilon$ 인 제약조건 행 $i_t \in [m]$ 이 있을 것이다. (아무거나 잡음)
  • 이 행을 손실 벡터로 선언해서 반환한다.
  • 이에 따라 $w_i := w_i \cdot (1 - \epsilon \cdot A_{i_t, i})$ 로 신뢰도를 업데이트한다.
• $T$ 를 충분히 돌려도 답이 없다면 infeasible하다고 선언

대체 이게 무슨 뜻일까? 일단 Theorem 1의 statement를 다시 살펴보자.

Theorem 1. 임의의 $\epsilon \in (0, 1/2]$ 에 대해서 위 알고리즘은 $L_A \le L_* + \epsilon T + \frac{\ln n}{ \epsilon}$ 을 보장한다.
Corollary 3. 임의의 $\epsilon \in (0, 1/2]$ 와 $x \in \Delta_n$ 에 대해서 위 알고리즘은 $L_A \le L \cdot x + \epsilon T + \frac{\ln n}{\epsilon}$ 을 보장한다.

Corollary 3은 당연하다. $L_* = \min L_i$ 이기 때문에 $L_* \le L \cdot x$ 가 성립한다. 대충 직관적으로는 "최고의 전문가를 따라갈 수 있으면 각 전문가의 weighted average도 당연히 따라갈 수 있다" 는 뜻으로 해석하면 된다.

킥은 최적해가 존재하기 때문에 어떤 전문가의 조합은 손실을 꽤 잘 조절할 것이라는 데에 있다. 구체적으로, $x^*$ 를 $Ax^* \le b$ 를 만족하는 어떠한 해라고 정의하면, Corollary 3에 의해

$L_A \le L \cdot x^* + \epsilon T + \frac{\ln n}{\epsilon}$

근데 우리가 매 시간 얻는 손실 벡터는 $L \cdot x^*$ 와 $L_A$ 의 거리를 계속 증가시킨다. 구체적으로

$l^t p^t > b_{i_t} + 2 \epsilon$
$l^t x^* \le b_{i_t}$

니까 알고리즘이 $T$ 번 돌고 나면

$L_A > L \cdot x^* + 2 \epsilon T$

이고 이에 따라서 $T = \frac{2 \ln n}{\epsilon^2}$ 번 이후에 알고리즘이 돈다는 것은 $x^*$ 가 존재한다는 것과 모순이 된다. 고로 $O(\frac{2 \ln n}{\epsilon^2})$ 번의 iteration 이후 알고리즘은 근사해를 찾거나 아니면 $x^*$ 가 존재하지 않음을 올바르게 판별한다. 각 iteration은 벡터/행렬 곱이니, 행렬의 nonzero entry가 $k$개면 $O(n+m+k)$ 시간에 구현할 수 있다.

마지막으로, 이 알고리즘의 두 가지 한계점을 살펴보자. Feasible한 벡터를 찾을 수 있으면 목표 최대화는 이분 탐색으로 할 수 있다. ($\max c^T x$ 대신 $c^T x \geq \lambda$ 로 설정하고 $\lambda$ 이분탐색). 그래서 그건 큰 문제는 아니고, 진짜 문제는:

• $A, x$ 의 절댓값 범위
• $2 \epsilon \mathbb{1}$ 의 error term

첫 번째는 $\epsilon$ 을 크게 줄인 후 scaling하는 식으로 없앨 수 있는데 단점은 아주 느리다는 것이다. 일부 LP에 대해서 width-independent MWU라고 불리는 테크닉이 존재한다. 아마 $A, b$ 에 음수 항이 없어야 하는듯. 두 번째는 완전히 없애는 방법이 있는지 모른다. 아마 없지 않을까...

4. Minimax Theorem via MWU

두 플레이어 $X, Y$ 가 게임판 $A \in [-1, 1]^{m \times n}$ 에서 게임을 한다. $X$ 는 게임판에서 행을 고르고, $Y$ 는 게임판에서 열을 고른다. $X, Y$ 가 고른 행과 열에 있는 값이 payoff이다. $X$ 는 이 payoff를 최대화하려고 하고 $Y$ 는 이 payoff를 최소화하려고 한다. (일단 여기서는 $A \in [-1, 1]^{m \times n}$ 에 대해서만 고려하지만, 위에서 얘기한 scaling을 쓰면 상관없다.)

이 문제의 답은 $X$ 가 선공이면 $\max_i \min_j A_{i, j}$ 이거나 그럴 것이다. 위에서 얘기한 것과 비슷하게 랜덤성을 도입하자. 이 경우 $X$ 는 확률 분포 $x \in \mathbb{R}_{\geq 0}^m$ 을 고르고, $Y$ 는 확률 분포 $y \in \mathbb{R}_{\geq 0}^{n}$ 을 고른다. ($\sum x_i = \sum y_j = 1$ 이다.) $X$ 가 선공이면 답은 $\max_x \min_y (x^T A y)$ 이고 $Y$ 가 선공이면 답은 $\min_y \max_x (x^T A y)$ 가 된다. 이 두 값이 똑같다는 유명한 정리인 Minimax Theorem가 있다. LP Duality의 special case로 기억하는데, LP Duality든 Minimax Theorem이든 증명을 알지 못한다.

MWU를 사용하면 Minimax Theorem을 알고리즘적으로 증명할 수 있다. 정확하게는 둘이 arbitrary close함만 보일 수 있고 같다고 할 수는 없지만.. 나는 신경 안 쓴다. 그 증명을 알아보자.

Multiplicative Weights Update를 다음과 같이 사용하자. Adversary (loss maximizer)가 $X$ 고 당신이 (loss minimizer) $Y$ 라고 생각하면 좋다.

• 초기 $w_1, w_2, \ldots, w_n = 1$ 로 설정하자.
• 매 $t = 1, \ldots, T = \frac{\ln n}{\epsilon^2}$ 에 대해
  • $y_i^t = \frac{w_i}{\sum_j w_j}$ 로 고른다.
  • $A_{i, *} \cdot y^t$ 의 값을 최대화하는 인덱스를 $i_t \in [m]$ 이라고 하자.
  • 이 행을 손실 벡터로 선언해서 반환한다.
  • 이에 따라 $w_i := w_i \cdot (1 - \epsilon \cdot A_{i_t, i})$ 로 신뢰도를 업데이트한다.
• $x = \frac{1}{T} \sum_{t = 1}^T e_{i_t}, y = \frac{1}{T} \sum_{t = 1} y^t$ 로 선언한다.
  • $e_{i_t}$ 는 $i_t$ 번 항만 $1$ 이고 나머지는 $0$ 인 길이 $m$ 의 벡터이다.

Theorem 4. 위 알고리즘이 반환한 $x, y$ 에 대해서 $\max_i (A y)_{i, 1} \le \min_j (x^T A)_{1, j} + 2\epsilon$ 이 성립한다.
Proof. Theorem 1에 의해 MWU 알고리즘은 $L_A \le L_* + 2 \epsilon T$ 을 보장한다. 이제 $L_A$ 와 $L_*$ 가 각각 무슨 의미인지 알아보자.

매 $t$ 에 대해서 알고리즘이 얻은 손실은 $\max_i (A y^t)_{i, 1}$ 이다. 이를 합하면 $L_A = \sum_{t = 1}^T \max_i (A y^t)_{i, 1}$ 이다.

$L_A = \sum_{t = 1}^T \max_i (A y^t)_{i, 1} \geq \max_i \sum_{t = 1}^T (A y^t)_{i,1 } = T \max_i (A y)_{i, 1}$

이다. 부등식은 $i$ 를 어떻게 바꿔도 각 항이 늘어날 수 없기 때문에 성립한다.

MWU 알고리즘에서 $j$ 번째 전문가는 $(\sum_{t = 1}^T A_{i_t})_{1, j}$ 만큼의 손해를 볼 것이다. 이는 $(T x^T A)_{1, j}$ 와 동일하다. 즉 $L_* = \min_j (T x^T A)_{1, j}$ 이다. 정리하면

$T \max_i (A y)_{i, 1} \le \min_j (T x^T A)_{1, j} + 2 \epsilon T$
$\max_i (A y)_{i, 1} \le \min_j (x^T A)_{1, j} + 2 \epsilon$

이 성립한다.

Theorem 5. $\max_x \min_y (x^T A y) \le \min_y \max_x (x^T A y) \le \max_x \min_y (x^T A y) + 2 \epsilon$ 이 성립한다.
Proof.

• 첫 부등식을 증명하자. $\max_x \min_y (x^T A y) > \min_y \max_x (x^T A y)$ 라고 하고, 좌변의 최적해를 $(x_1, y_1)$, 우변의 최적해를 $(x_2, y_2)$ 라고 하자. $x_1^T A y_1 \le x_1^T A y_2$ 이다. 고정된 $x_1$ 에 대해서 $y_1$ 이 최솟값이었기 때문이다. 비슷하게 $x_1^T A y_2 \le x_2^T A y_2$ 이다. 고정된 $y_2$ 에 대해서 $x_2$ 가 최댓값이었기 때문이다. 고로 가정에 모순이다.
• $\max_i (Ay)_{i, 1} = \max_x (x^T A y)$ 이다. 모든 확률 분포 $x$ 에 대해서 저게 최적이기 때문이다. 비슷하게 $\min_j (x^T A)_{1, j} = \min_y (x^T A y)$ 이다.
• 따라서 Theorem 4는 $\max_x (x^T A y) \le \min_y (x^T A y) + 2\epsilon$를 의미한다. 이는 $\min_y \max_x (x^T A y) \le \max_x (x^T A y) \le \min_y (x^T A y) + 2\epsilon \le \max_x \min_y (x^T A y) + 2 \epsilon$ 역시 의미한다. 이에 따라 두 번째 부등식 역시 증명된다.

저 알고리즘을 Profit maximization으로 해석해서 $X$ 의 역할에서 게임을 해도 동일한 결과를 얻을 수 있다. LP Duality같은 상황에서 primal / dual 중 하나만 풀 수 있어도 approximate primal / dual 솔루션을 모두 얻을 수 있다는 게 takeaway인거 같다.

5. Approximate Unit Max Flow via MWU

모든 간선의 용량이 $1$일 때 $s - t$ approximate max flow를 빠르게 구하는 방법을 생각해 보자. 매칭일 때는 간단한 방법이 있는데 (디닉으로 $O(\epsilon^{-1})$ 길이의 augmenting path를 다 소진하면 됨) unit max flow에서는 잘 안되나 보다.

Unit Max Flow는 다음과 같은 지수적 크기의 LP로 표현할 수 있다:

• 모든 $s - t$ 경로 $\mathcal{P}$ 에 적당한 값을 배정해서
• 각 간선에 대해서, 해당 간선을 지나는 가중치 합이 $1$ 이하가 되게 하고
• 배정한 값 합을 최대화

행렬 $A \in [0, 1]^{E \times \mathcal{P}}$ 를, 각 간선이 특정 경로에 속하면 $1$ 이고 아니면 $0$ 인 행렬이라고 하자. $y$ 를 내가 배정한 값이라고 했을 때, 이 해가 올바르다는 것은 $\max_i (A y) \le 1$ 이라는 것과 동일하다. 이제 $y$ 를 확률 분포로 scaling할 경우, 우리가 해결하는 문제는 $\min_y \max_i (Ay)$ 이다. 이 값이 $c$ 라고 하면, $1$ 의 flow로 각 간선의 congestion을 $c$ 로 설정해 줄 수 있으니, $1/c$ 의 unit flow를 찾는 것이다. (사실 구체적으로 왜 이렇게 하는지는 모르겠다. 그냥 위에 있는 LP식으로 해도 똑같은 알고리즘이 나오지 않을까? 아무튼 강의 자료가 이렇게 하길래 그냥 해 봤다.)

즉, $A$ 에 대해서 zero-sum game을 해결하면 Approximate Unit Max Flow를 해결할 수 있다. 해야 할 것은, 모든 경로에 대해서 expert를 배정하고 $A_{i, *} \cdot y$ 를 최대화하는 $i$ 를 고르는 것이다. 즉, 현재 flow에 대해서 congestion이 최대인 간선이 손실 벡터가 된다.

이 MWU는 구현이 어려워보이니, 반대로 $x$ 를 고정하고 $x^T \cdot A_{*, j}$ 를 최소화하는 $j$를 골라보자. $x$ 에 대해서 $x^T \cdot A_{*, j}$ 를 최소화하는 $j$ 가 무슨 뜻일까? 바로 $x$ 를 간선 가중치로 했을 때 $s - t$ 최단 경로라는 뜻이다. 고로 이건 Dijkstra를 사용하여 해결할 수 있다.

마지막으로, MWU를 몇 번 돌려야 할까? $1 - \delta$ approximate solution을 얻고 싶다면:

$\frac{1}{X + 2\epsilon} \geq (1 - \delta)\frac{1}{X}$
$1 \ge (1 - \delta)(1 + \frac{2\epsilon}{X})$
$\epsilon \le O(\delta X) \le O(\delta / m)$
$\epsilon^{-1} \geq m / \delta$

고로 $\frac{\ln n}{\epsilon^2} = m^2 \delta^{-2} \ln n$ 번 돌려야 한다. 다익스트라 한 번을 $O(m\log n)$ 이라 치면 이 알고리즘은 $O(m^3 \delta^{-2} \log^2 n)$ 의 시간 복잡도를 가진다. Theorem 2를 보면 $A$ 가 non-negative entry로 구성되어 있으면 더 빠르게 수렴한다는 얘기가 있다. 이를 사용하면 $\tilde{O}(m^2)$ 정도까지는 줄일 수 있는 것 같다. Decremental SSSP 자료구조를 "잘 쓰면" $O(m^{1 + o(1)})$ 도 되는 것 같다 (BGS'21). Decremental SSSP를 그냥 쓰는 것은 충분치 않고 (최단 경로를 구하는 것을 떠나서 최단 경로를 떠나서 가중치 업데이트를 해야 함을 기억하자). 아주 잘 써야 한다.