# Oshima 2021 - Improved Randomized Algorithm for k-Submodular Function Maximization

## One-paragraph Summary

Day la paper noi ngay sau dong Ward-Zivny / Iwata-Tanigawa-Yoshida trong bai toan unconstrained non-monotone `k`-submodular maximization. Dong gop chinh khong phai la mot framework moi hoan toan, ma la mot phan tich sac hon cho chinh randomized assignment framework quen thuoc: paper chi ra cach chon phan phoi tren cac label tot hon de nang ratio vuot moc `1/2`. Cu the, paper dat `(k^2 + 1) / (2k^2 + 1)` voi moi `k >= 3`, va trong truong hop `k = 3` dat them ratio dep hon `(sqrt(17) - 3) / 2`.

## Classification Rationale

Paper thuoc `k-submodular` vi no lam viec hoan toan tren domain `(k+1)^V` va khai thac truc tiep orthant submodularity cung pairwise monotonicity. Ve lineage, no nam trong nhanh `unconstrained` va `randomized oracle approximation`, la paper can chen vao giua Ward-Zivny 2014 va cac paper constrained / streaming ve sau de thay phan unconstrained non-monotone da duoc lam sac den dau.

## Setup

- Domain / model: ham `f : (k+1)^V -> R_+`, voi nghiem la `k` tap roi nhau hoac tuong duong la vector nhan trong `{0,1,...,k}^V`.
- Oracle / access model: value oracle; tai moi phan tu `e`, thuat toan nhin cac marginal `Delta_(e,i) f` khi dat `e` vao tung label `i`.
- Objective: maximize mot ham `k`-submodular khong am, khong rang buoc them.
- Assumptions: paper nham vao non-monotone case; monotone case chi duoc nhac lai nhu tien de tu ket qua truoc do cua Iwata et al.

## Main Results

1. Paper cai thien ratio randomized cho unconstrained non-monotone `k`-submodular maximization tu moc `1/2` cua Iwata et al. len `(k^2 + 1) / (2k^2 + 1)` cho `k >= 3`.
2. Cho `k = 3`, paper thiet ke mot phan phoi dac biet dat ratio `(sqrt(17) - 3) / 2`, tot hon ratio tong quat khi thay `k = 3`.
3. Cai thien den tu phan tich one-step sac hon, khong can doi sang mot framework thuat toan khac; van la quy trinh duyet tung phan tu va random hoa label theo cac marginal hien tai.

## Core Algorithmic Idea

Paper giu nguyen khung randomized assignment co san: duyet tung phan tu `e(1), ..., e(n)`, o moi buoc tinh cac marginal `y_i = Delta_(e,i) f(s)` cua nghiem dang xay, roi rut tham label theo mot phan phoi `p_1, ..., p_k`. Diem moi nam o viec chon `p_i`.

Trong cac paper truoc, phan tich so sanh expected gain cua nghiem hien tai voi expected loss khi "dong bo" nghiem toi uu da cho ra ratio `1/2`. Oshima nhan ra rang khi so sanh cac so `a_i` tren nghiem toi uu da bien doi, do pairwise monotonicity chi co the co toi da mot chi so am. Khai thac them thong tin nay lam giam do bi quan trong inequality moi buoc, tu do mo duoc cac phan phoi xac suat tot hon.

Voi `k = 3`, paper sap xep `y_1 >= y_2 >= y_3`, dat `beta = y_2 / y_1`, `gamma = y_3 / y_1`, roi chia thanh cac mien cua `(beta, gamma)` de chon mot trong ba dang phan phoi. Voi `k >= 3`, paper dua ra mot flow phan loai theo dau cua marginal nho nhat va muc do tap trung cua hai marginal lon nhat, roi chon phan phoi phu hop cho tung mien.

## Proof / Analysis Strategy

- Buoc 1: dat lai khung phan tich chuan voi `s^(t)` la nghiem thuat toan sau `t` buoc, `o^(t)` la nghiem toi uu da duoc "sua" de khop voi cac quyet dinh da chot, va hai day marginal `y_i`, `a_i`.
- Buoc 2: cai thien lemma then chot cua literature cu. Thay vi chan truc tiep `sum_i (a_(i*) - a_i) p_i`, paper tach rieng truong hop co mot `a_i < 0` va dung su that chi co toi da mot chi so am. Day la cho paper tiet kiem duoc he so trong expected-loss bound.
- Buoc 3: tim phan phoi `p` sao cho `f(p) <= c g(p)`, trong do `g(p)` la expected gain cua nghiem dang xay, con `f(p)` la upper bound cho expected loss cua optimum da bien doi.
- Buoc 4: tong hop bat dang thuc qua tat ca phan tu bang telescoping / amortized comparison. Neu moi buoc co `f(p) <= c g(p)` thi tong the cho ratio `1 / (1 + c)`.
- Buoc 5: cho `k = 3`, giai bai toan toi uu hoa local bang tay tren ba mien. Cho `k >= 3`, chia thanh hai nhanh lon: khi co marginal am thi giong tinh than monotone tren `k - 1` label duong; khi tat ca marginals duong thi dung mot quy tac phan phoi phu thuoc vao tham so `l` va mot `epsilon` noi bo de duy tri `c = 1 - 1 / k^2`.

## Key Techniques

- sequential randomized assignment tren assignment-domain
- refined local-ratio style analysis cho mot buoc
- orthant submodularity va pairwise monotonicity
- khai thac "at most one negative `a_i`"
- chia mien theo thu tu va dau cua marginal
- tailor probability distributions theo profile cua `y_i`

## Key Lemmas Or Structural Claims

- Lemma trung tam cua paper thay the phien ban cu bang mot bat dang thuc sac hon, trong do expected loss cua optimum duoc bound boi `(1 - p_(i*)) a_(i*)` cong them mot hieu chinh chi khi ton tai mot chi so am `i_-`.
- Cho `k = 3`, sau khi viet upper bounds cua `f(p)` theo tung cap `(i*, i_-)`, paper chi can toi uu hoa hai tham so ti le `beta`, `gamma`; day la nguon goc cua con so `(sqrt(17) - 3) / 2`.
- Cho `k >= 3`, neu marginal nho nhat am thi bo nhan am ra va ap dung phan bo giong monotone tren `k - 1` label con lai; neu tat ca marginals duong thi dung quy tac phan phoi phan doan cho ra `c = 1 - 1 / k^2`, tuong ung ratio `(k^2 + 1) / (2k^2 + 1)`.

## Delicate Points / Caveats

- Paper khong dua ra lower-bound optimality cho ratio moi; no la cai thien trong nhanh analysis, khong phai ket luan cuoi cung cua bai toan.
- Phan `k >= 3` co flowchart va chia case kha ky thuat; neu doc lai sau nay, diem can nam that chac la y tuong "at most one negative comparison marginal", khong phai tung cong thuc xac suat.
- Bai bao journal nam 2021, nhung file intake la preprint arXiv ngay 27-07-2019; minh da map canonical theo nam venue journal.
- Cai thien ratio chi cho non-monotone unconstrained case; khong dong nghia rang proof nay se chuyen nguyen van sang knapsack, matroid, hay streaming.

## Extraction To Concepts

- Bo sung vao `concepts/k-submodularity.md` dong unconstrained non-monotone: randomized assignment framework co the duoc lam sac boi local inequality manh hon, khong chi boi doi framework.
- Reusable ingredient: khi pairwise monotonicity ep tong hai comparison marginals khong am, so luong chi so am trong vector `a` rat bi han che; day la mot manh thong tin phan tich co gia tri tai dung.
- Technique note nen nho: sap xep marginals giam dan roi thiet ke probability theo profile cua ratios `y_2 / y_1`, `y_3 / y_1`, ... la mot mau lap lai trong cac proof unconstrained.

## Extraction To Syntheses

- Chen paper nay vao `syntheses/k-submodular.md` giua Ward-Zivny 2014 va cac paper constrainted de phan unconstrained non-monotone co du lich su lien tuc.
- Trong synthesis can nhan manh mot nhanh rieng: "giu framework randomized greedy, nhung cai thien local comparison inequality."

## Weaknesses / Limits

- Trinh bay rat ky thuat va nhieu case, nen kha kho truy hoi nhanh neu khong tach duoc thong diep chinh cua proof.
- Cai thien ve ratio la tu phan tich hon la tu y tuong thuat toan de implement don gian hon; do do gia tri retrieval cua note nay nam nhieu o proof spine.
- Paper khong giai quyet bai toan constrained; no chu yeu la cot moc cho unconstrained non-monotone line.

## Research Ideas Triggered

- Tao mot note so sanh rieng giua Ward-Zivny, Iwata et al., va Oshima de xem muc cai thien nao den tu probability design, muc nao den tu inequality trung gian.
- Kiem tra xem "at most one negative comparison marginal" co analog huu ich nao khi sang thresholding / multi-budget hay khong.