麻辣坊主

運動して美味しいものを食べて時々勉強

2022 年振り返り（研究）

およそ１年ぶりにブログの管理画面を開きました． 開いたら今年初めに書いていた新年の目標記事の下書きが残ってました．当然達成できてません．

当初の目標はさておき，今年は NeurIPS に投稿した主著 2 本，共著 1 本が全部採択されて，非常にラッキーな年でした． 研究室で同僚氏と議論できるようになったおかげで色々と捗りました．圧倒的感謝 🙏🙏🙏

せっかくなので今年取り組んだ＆気になった研究トピックについて書きたいと思います．

Data-driven Algorithm Design

多くのアルゴリズムは調整可能なパラメータを持っていて，それらを現実の問題の傾向に適合させることで経験的には性能は向上します． しかし，そのような経験的な調整の理論的側面は従来の最悪ケースの理論解析でカバーしにくいので，機械学習でモデルを学習するのと同様に，アルゴリズムのパラメータも手元の問題のサンプルから学習していると思って，どれくらい問題のサンプルがあれば学習可能か（サンプル複雑度）を調べてみよう，という分野です．

Gupta & Roughgarden が提案した枠組みで，おそらく Roughgarden はこれをきっかけに Beyond the Worst-Case Analysis of Algorithms を推し始めたんだと思います．

その後は CMU の Nina Balcan のグループが積極的に研究していて，branch-and-bound, branch-and-cut, tree search, linkage clustering などに適用した論文を出しています． また上記の beyond the worst case 本に Balcan によるサーベイが収録されていて，arXiv でも公開されています． とりあえず入門するにはおすすめです．

テクニカルには，区分的に構造を持った関数のクラス（アルゴリズムを問題の関数と思って，パラメータを動かして得られるクラス）の複雑度を評価することになり，Sauer の補題 などを使ってそのクラスの Pseudo dimension（VC dimension の実関数版）を抑えるということをよくやります．割と離散幾何っぽいツールが登場します． この方針の general な結果も Balcan グループが出していて，上でリストアップした論文の解析のアイデアは基本的にこの結果から来ているようです．

もう一つの方針として，アルゴリズムの計算手続きを表現する algebraic computation tree を経由して Pseudo dimension を評価するやり方もあり，このアイデアを使ってスケッチング行列の学習のサンプル複雑度を解析した論文もあります．個人的に今年読んだ中で結構好きな論文です．

ちなみに今年我々が取り組んだ研究では，1 つ目の方針を使って A* 探索のヒューリスティック関数の学習の解析をしたり，2 つ目のスケッチング行列の学習の解析を改善＆拡張したりしました．

注意点として，基本的には「どれだけ問題サンプルがあれば良いパラメータを学習可能か？」しか考えていないので，具体的な学習の方法は議論されないことが多いです（非連続関数の最適化なので真面目に扱うのは大変）． しかしこの問題に対しても，Balcan グループが計算幾何的な道具を使った方法を研究していたりします．

Algorithms with Predictions

こちらも アルゴリズム × 機械学習 なトピックで，同様に beyond the worst case 本にサーベイが収録されていて，arXiv にも公開されています． このサーベイにあるスキーレンタル問題の例を紹介します．

Aさんは最近よくスキーに行くので，スキー板を買ってしまおうか迷っています． スキー板の値段は $b>1$ 円で，板のレンタル料は 1 回 $1$ 円です． 今後 $b$ 回以上スキーに行くのであれば今すぐ板を買って良いのですが，ある時には飽きてしまってその後行かなくなるかもしれません． もし $a < b$ 回で飽きるとしたら，今後も買わずにレンタルした方が良いです． Aさんは自分がいつスキーに飽きるか全くわからないので，何回目に板を買えば良いか戦略を立てる必要があります． そこで，「今後 $b-1$ 回目までレンタルして，$b$ 回目に板を買う」という戦略にすれば，

  1. $a < b$ 回以内に飽きたら支払い料金は $a$ 円．これはオフライン最適戦略（何回目に飽きるか知ってた場合の最適戦略）と同じ．
  2. $a \ge b$ 回目に飽きたら支払い料金は $2b-1$ 円．この場合オフライン最適戦略は最初に $b$ 円で板を買うので，最適支払額は $b$ 円．

となり，実際に支払う金額 $/$ オフライン最適戦略で支払う金額（競合比）が漸近的に高々 2 で済みます．deterministic な戦略の中ではこれが最悪ケースに対する最適な競合比です．

ここで占い師が現れて「あなたはあと $p$ 回スキーをしたら飽きる」と教えてくれます． この予測は正しいとは限らず，実際は $a$ 回スキーをしたら飽きるとします． 仮に占い師を完全に信じる（$p = a$ と思う）なら「$p > b$ なら今すぐ板を買い，$p \le b$ ならレンタルを続ける」戦略をとれば良いですが，実は占い師はスキー業界の回し者で $p > b \gg a$ かもしれません．そうなると，レンタルし続ければ $a$ 円で済むところを $b$ 円払うことになり，競合比 $b/a$ で大損です．

そこで，占い師の怪しさを $\lambda \in [0,1]$ として，予測が正しい場合とそうでない場合のトレードオフを $\lambda$ を介して調整できるような方法を考えてみます． 先ほどの占い師を完全に信じる戦略の $\lambda$ を使った自然な修正版として 「$p > b$ なら $\lceil \lambda b \rceil$ 回目に板を買い，$p \le b$ なら $\lfloor b/\lambda \rfloor$ 回目に板を買う」 という戦略が考えられます． 実はこの戦略とオフライン最適戦略との競合比は $$ 1 + \min \left( \frac{1}{\lambda}, \lambda + \frac{|p - a|}{(1 - \lambda) \text{OPT}} \right) $$ となることが示せます．$\text{OPT}$ はオフライン最適戦略の支払額です． 占い師が完全に怪しい場合が $\lambda = 1$ で，この場合の競合比は $2$ となり，上記の deterministic な戦略の競合比を再現できます． 占い師が完全に信頼できるなら $\lambda = 0$ で，競合比は $1 + \frac{|p - a|}{\text{OPT}}$ です． 実際に予測の誤差 $|p - a|$ が小さければ競合比は $2$ よりも良くなり得ます（$p = a$ なら競合比 $1$）． 予測が完全に正確でないにしても，「ある程度正確な予測をうまく利用できれば，最悪ケースで最適な理論保証よりも良い保証が付き得る」ということになります．

このように何らかの予測が使えるときに「予測がある程度正確なら最悪ケースで最適な理論保証を超えつつ，不正確な予測に対してもロバストな方法を設計したい」というのが Algorithms with Predictions の考え方です． スタンスとしては「機械学習を何か予測を出してくれるブラックボックスと捉えて，それ使ってアルゴリズムの理論保証の意味で何か得をしたい」という感じで，上記の data-driven algorithm design の「パラメータを持ったアルゴリズムをモデルと思って，どれくらい問題のサンプルがあれば学習可能か調べる」という考え方とは微妙に異なります．

これまで色々なオンラインアルゴリズムに対して「予測が使えたらどんな理論保証が付くか？」が研究されてきました． 代表的なのは Lykouris & Vassilvitskii (ICML '18, J. ACM '21)です． 離散アルゴリズムの研究者の間でも流行りつつある話題なようで，SODA 等でも時々このトピックの論文を見かけます． この分野の論文は有志が論文リストを作って公開してくれているので，とてもサーベイしやすいです．

Warm-starts with Predictions

調子に乗ってスキーレンタルの話を長々と書いてしまいましたが，今年我々が取り組んだのは少し毛色の違う派生トピックで，予測を使ってアルゴリズムをウォームスタートするという内容です． きっかけは NeurIPS '21 の Oral で発表されていた論文 を読んだことで，ざっくり以下のような内容です：

  1. 最大重み二部グラフ完全マッチングに対するハンガリアン法は最悪 $O(mn)$ 時間かかるが，双対最適解の予測 $\hat p$ を使ってウォームスタートすると $O(m\sqrt{n} \| \hat p - p^\ast \|_1)$ 時間で済む（$p^\ast$ は双対最適解）．
  2. $\| \hat p - p^\ast \|_1$ の期待値は $\Omega(n^3)$ 個の過去の双対最適解のサンプルがあれば高確率で近似的に最小化できるので，十分なサイズのサンプルから双対解の予測 $\hat p$ を学習してウォームスタートすると，最悪時計算量よりも少ない計算量で問題が解ける得ると言える．

１つ目は同僚氏のような離散凸解析プロの視点で見ると「L凸関数最小化の最急降下法は最適解の近くからスタートすれば早く停止する」という自然な結果で，素直に拡張＆改良できます． という経緯で，”離散凸解析 × 機械学習” 論文が書けました．

そのほかのトピック

他にも気になっているトピックについて書くつもりでしたが，書き始めると思ったより疲れました． キーワードだけ並べると，

などが気になっていて，時々論文を眺めています（があまり真面目には追えてはいません．．．）

さいごに

興味の近そうな方ぜひ共同研究しましょう！よいお年を！