FOCS2013読み会

11/2にFOCS2013読み会に参加してきたのでその要約を書いてみます．FOCSは理論計算機科学のトップ会議の1つです．

※なんか理解が浅かったり間違えたまま把握してたりしてテキトーなことを書いてしまっているかもしれませんがご了承ください．

Learning Sums of Independent Integer Random Variables, by Constantinos Daskalakis, Ilias Diakonikolas, Ryan O'Donnell, Rocco A. Servedio and Li-Yang Tan

離散変数に関する中心極限定理の話．

問題設定

$\{0,1,\cdots,k\}$ を取る確率変数 $X_1, \cdots, X_n$ と，$S = X_1 + \cdots + X_n$ があるとする．各 $X_i$ は互いに独立であるが，それぞれ異なる分布に従うかもしれないとする．確率変数 $S$ の値を何回か確率分布に沿ってサンプリングして， $S$ の分布を $\varepsilon$-近似したい．(正確には，見積もった分布と本当の分布の分散が $\varepsilon$ 以下になるようにしたい．) 何回くらいサンプリングが必要か? ここで，$k$ は定数で，$n$ は十分に大きい数であるとみなします．

論文内容

この論文では $O(poly(k, 1/\varepsilon))$ 回のサンプリングで近似できると主張しています．元の値が $0$ から $kn$ と広い値を取るのに対してサンプル回数は $n$ に依存しない回数で済むということを考えると，これは強力な結果であるように見えます．

各 $X_i$ がすべて同じ分布に従うなら中心極限定理で終わり？ですが，そうでないので難しい(はず)．$k=2$ のとき (つまり各変数が0か1しかとらない場合) には2012年に既存研究があって，中心極限定理により正規分布で近似できる(らしいです)．ところが，$k=3$ のときは単なる正規分布ではだめで，たとえば $n=50$ で，$X_1, ..., X_{49}$ は $\{0, 2\}$ を等確率で取り，$X_{50}$ は $\{0, 1\}$ を偏った確率で取るような場合，$S$ の値が偶数を取るときと奇数を取るときで振る舞いが変わってしまう．

f:id:ir5:20131216084126p:plain

このような複雑な振る舞いを解析したのが本論文の結果で，以下の構造定理にまとめられます．

構造定理. ある $c \in \{0, 1, \cdots, k-1 \}$ が存在し，$S$ は "$c \cdot$ (離散の正規分布) $+\{0,1,\cdots,c-1\}$ の任意分布のランダム変数" で近似できる．

つまり，離散変数の和にはなんらかの周期性が必ず出て，周期ごとに分解するとそれぞれは正規分布に従っているとみなせる，というものです．アルゴリズムはこの定理をほとんどそのまま使って導出できる模様です．
証明は，まず周期性が無い場合について考え，次に周期性がある場合について考えるために各 $X_i$ の値域を小さいステップに対応する部分と大きいステップに対応する部分の2つに分割して解析するっぽいです．(このへんはよくわかりませんでした)

今後の発展として，$k$ がconstantでない場合どうなのかとか，$k=2$ の場合は機械学習に応用があるらしいけど $k \ge 3$ の場合どうなのかということが挙げられていました．

Efficient Accelerated Coordinate Descent Methods and Faster Algorithms for Solving Linear Systems, by Yin Tat Lee and Aaron Sidford

(概要だけ)
リプシッツ連続で強凸というクラスに属する関数 $f$ が与えられるので，それを最小化する問題(つまり $\min_x f(x)$ を計算する問題)に関する新しい反復型のアルゴリズムを提案．

この問題では今までに「座標勾配法」と「加速勾配法」というものが知られていた．
それぞれ，

  • 座標勾配法：式を1成分ずつupdateすればいいので扱いやすい
  • 加速勾配法：収束が速い

というメリットがあり，今回はそれらを組み合わせた手法を考案した．

アルゴリズムの性能の評価には，Estimate sequence という1983年くらいの結果を確率変数に拡張したものを使うらしいです．

Improved approximation for 3-dimensional matching via bounded pathwidth local search, by Marek Cygan

著者の Marek Cygan はFPT関係の分野で様々な成果を出しています．またプログラミングコンテストでも強い人として有名なので知ってる人は知っているかもしれません．
この論文では，$k$-set packing という問題に対して既存のものより良い精度の近似アルゴリズムを与えます．

問題設定

集合族 $\mathcal{F} \subseteq 2^U$ が与えられる．$\mathcal{F}$ の内の各集合の大きさはちょうど $k$ である．
$\mathcal{F}$ からできるだけ多くの disjoint な集合を選びたい．最大でいくつ選べるか?

研究背景

set packingは有名なNP完全問題であり，近似もそれなりに難しい問題として知られています．$O(|U|^{1-\varepsilon})$ 近似困難?) 既存研究で知られていたのは以下のとおりです．

  • 貪欲に選ぶ：$k$-近似アルゴリズム
  • サイズ2の交換という操作(後述)によって解を改善していく：$(k+1)/2$-近似アルゴリズム

今回はこの交換という操作を拡張したものを考えます．

  • サイズ $O(\log|F|)$ の交換という操作によって解を改善していく：$(k+1+\varepsilon)/3$-近似アルゴリズム

交換というのは次のようなものです：
confliction graph を，$\mathcal{F}$ 内の各集合を頂点とし，もし2つの集合が disjoint でないなら枝を張ってできるグラフとします．($\mathcal{F}$で独立な部分集合族はこのグラフ上の独立頂点集合に対応することに注意)
いま，$\mathcal{F}$ の中からいくつかの集合を選んでいる状況を想定します．$X$ を今選んでる頂点集合とします．
improving set を，conflict graph 内の独立頂点集合 $Y$ で，$|X \cap N(Y)| < |Y|$ となるものとします．このとき，いま選んでる集合の中から $Y$ と隣接するものを捨て，代わりに $Y$ を足すと解が改善されることに注意します．

論文内容

できるだけ大きい improving set が見つけることができれば解を改善できて嬉しいです．交換する集合のサイズ $|Y|$ が大きいほどなんとなく良いような気がする(?) んですが，問題はこの交換という操作は普通にやると計算時間が多項式にならないということにあります．
そこで，この論文ではpathwidthというグラフの指標を使い，うまく近似解を得ます．

  • conflict graph の，今選んでいる頂点で誘導される部分の pathwidth が小さいなら，improving set を十分高速な時間で探せる．(FPT系の問題に帰着するとかだった気がする)
  • conflict graph の，今選んでいる頂点で誘導される部分の pathwidth が大きいなら，それは $(k+1+\varepsilon)/3$-近似解になっている．

Approximating Minimum-Cost k-Node Connected Subgraphs via Independence-Free Graphs, by Joseph Cheriyan and Laszlo A. Vegh

問題設定

重みのついた無向グラフが与えられる．点連結度が $k$ になるような部分グラフで，コスト最小のものを取りたい．

研究背景&論文内容

制約が枝連結度なら近似度2で解けるらしいが，点連結度だと難しいらしい．既存研究では以下のことが知られていた．

  • $k$ が $n$ に比べて小さいときは $O(\log{k})$ 近似可能
  • $k$ が大きい時，$n > 3k-3$ のならば $O(k)$ 近似可能

今回は，$n \ge k^3$ ならば6近似可能ということを示したようです．(近似度の改善)

手法はiterative rounding という手法を用いる模様．

An LMP O(log n)-Approximation Algorithm for Node Weighted Prize Collecting Steiner Tree, by Jochen Koenemann, Sina Sadeghian and Laura Sanita

頂点重みのシュタイナー木を考えます．シュタイナー木 $T$ のコストを $w(V(T)) + p(V \setminus V(T))$ で評価するとします．(シュタイナー木に入っていない頂点にもコストがかかる) この問題は集合被覆を含んでいるので近似アルゴリズムを考えることになります．普通，この問題に対する $\alpha$-近似解 といったら，次のようなものです．

$w(V(T)) + p(V \setminus V(T)) \le \alpha w(V(T^*)) + \alpha p(V \setminus V(T^*))$

この論文では LMP (Lagrangean-multiplier-preserving) というものを扱います．次のようなものです．

$w(V(T)) + \alpha p(V \setminus V(T)) \le \alpha w(V(T^*)) + \alpha p(V \setminus V(T^*))$

(左辺の第二項に $\alpha$ がかかっていることに注意．)
これだけ見ると何やってるんだかよく分かりませんが，LMPが解けると quota problem, budget problem 等，他の問題が$\alpha$-近似で解けるようになって嬉しいようです．
で，既存研究で，既に LMP で $O(\log{n})$-近似するアルゴリズム (STOC'01) があったのですが，今回はなんとその結果にミスがあったことを指摘し，新しいアルゴリズムを提案しました．テクニック的にはかなり高度なことをしているっぽいです．

Online Node-weighted Steiner Forest and Extensions via Disk Paintings, by Mohammad Taghi Hajiaghayi, Vahid Liaghat, and Debmalya Panigrahi

オンラインで頂点重みシュタイナー森を計算する問題です．またしても頂点重みシュタイナーなんちゃらで，しかも今度はオンラインというタフな設定です．(発表者の福永さん曰く今は頂点重みがキテいる!! とのこと．)
競合比 $O(\log n)$ で解けるらしいです．

Approximating Bin Packing within O(log OPT*loglog OPT) bins, by Thomas Rothvoss

ビンパッキング問題という有名な問題に対する近似アルゴリズムの提案．
問題設定はとてもシンプルです：$n$ 個のアイテムがあり，それぞれの大きさは $x_1,\cdots,x_n$ $(0\le x_i \le 1)$ である．大きさがちょうど 1 のビンを何個か用意して全てのアイテムをビンに詰めるとき，何個ビンが必要になるか計算せよ．
この問題はNP困難問題であり，近似アルゴリズムの研究がされてきました．最も新しかった結果は1982年の $APPROX \le OPT + O(\log^2 OPT)$ で，それ以降更新がありませんでした．
で，今回の論文は，これを更新し， $APPROX \le OPT + O(\log OPT \log\log OPT)$ にした，というものです．(全然更新できてないやんって感じだけど，有名な問題で30年以来改善されていなかったものを改善したのでこれはすごいことなのである．)
手法はLPのrounding的なテクニックを使うらしいですが，道中で Discrepancy theory でできたツールを使うようです．

その他

あとがき

この会が終わった直後くらいにこの記事書いて公開しようと思ってたのだけど色々やることがあって放置していたら1ヶ月半も経ってしまっていた．