Upgrade to Pro — share decks privately, control downloads, hide ads and more …

Regret Ratio Minimization in Multi-objective Su...

Tasuku Soma
February 02, 2017
1.8k

Regret Ratio Minimization in Multi-objective Submodular Function Maximization

AAAI 2017

Tasuku Soma

February 02, 2017
Tweet

Transcript

  1. Regret Ratio Minimization in Multi-objective Submodular Function Maximization P(S) a

    Tasuku Soma (U. Tokyo) with Yuichi Yoshida (NII & PFI) 1 / 15
  2. Submodular Func. Maximization f : 2E → R+ is submodular:

    f(X + e) − f(X) ≥ f(Y + e) − f(Y) (X ⊆ Y, e ∈ E \ Y) “diminishing return” max f(X) s.t. X ∈ C Applications • Influence Maximization • Data Summarization, etc 2 / 15
  3. Multi-objective Optimization? × Exponentially Many Pareto Solutions! “Good” Subsets of

    Pareto Solutions • k-representative skyline queries [Lin et al. 07, Tao et al. 09] • top-k dominating queries [Yiu and Mamoulis 09] • regret minimizing database [Nanongkai et al. 10] 4 / 15
  4. Multi-objective Optimization? × Exponentially Many Pareto Solutions! “Good” Subsets of

    Pareto Solutions • k-representative skyline queries [Lin et al. 07, Tao et al. 09] • top-k dominating queries [Yiu and Mamoulis 09] • regret minimizing database [Nanongkai et al. 10] Issue These assume data points are explicitly given... 4 / 15
  5. Our Results Extend regret ratio framework to submodular maximization Upper

    Bound Given an α-approx algorithm for (weighted) single objective problem, • regret ratio 1 − α/d for any d • regret ratio 1 − α + O(1/k) for any k and d = 2. d = # objectives, k = # of feasible solutions 5 / 15
  6. Our Results Extend regret ratio framework to submodular maximization Upper

    Bound Given an α-approx algorithm for (weighted) single objective problem, • regret ratio 1 − α/d for any d • regret ratio 1 − α + O(1/k) for any k and d = 2. d = # objectives, k = # of feasible solutions Lower Bound • Even if α = 1 and d = 2, it is impossible to achieve regret ratio o(1/k2). 5 / 15
  7. Regret Ratio Single Objective The regret ratio for S ⊆

    C and f is rr(S) = 1 − maxX∈S f(X) maxX∈C f(X) . 6 / 15
  8. Regret Ratio Single Objective The regret ratio for S ⊆

    C and f is rr(S) = 1 − maxX∈S f(X) maxX∈C f(X) . Multi Objective The regret ratio for S ⊆ C and f1 , . . ., fd is rrf1 ,...,fd ,C(S) = max a∈Rd + rrfa ,C(S), where fa := a1 f1 + · · · + ad fd . (linear weighting) 6 / 15
  9. Geometry of Regret Ratio f1 f2 Pareto opt point P(S)

    point in S ε−1P(S) rr(S) ≤ 1 − ε ⇐⇒ f(X) ∈ ε−1P(S) (X ∈ C). 7 / 15
  10. Regret Ratio Minimization Given: f1 , . . ., fd

    : submodular, C ⊆ 2E, k > 0 minimize rr(S) subject to S ⊆ C, |S| ≤ k. 8 / 15
  11. Algorithm 1: Coordinate f1 f2 approx solution to maxX∈C f1

    (X) approx solution to maxX∈C f2 (X) Scoord : α-approx. solutions to maxX∈C fi (X) (i = 1, . . ., d) =⇒ rr(Scoord ) ≤ 1 − α/d. 9 / 15
  12. Algorithm 2: Polytope f1 f2 S: output of Coordinate and

    d = 2, =⇒ rr(S) ≤ 1 − α − O(1/k). 10 / 15
  13. Lower Bound f1 (X) = cos π|X| 2n , f2

    (X) = sin π|X| 2n > π 2k f1 f2 distance = O(1/k2) 11 / 15
  14. Experiment Algorithms • Coordinate • Polytope • Random: Pick k

    random directions a1 , . . ., ak and output the family {X1 , . . ., Xk } of solutions, where Xi is an approx solution to max X∈C fai (X). Machine • Intel Xeon E5-2690 (2.90 GHz) CPU, 256 GB RAM • implemented in C# 12 / 15
  15. Data Summarization Dataset: MovieLens E: set of movies, si,j :

    similarities of movies i and j f1 (X) = i∈E j∈X si,j , coverage f2 (X) = λ i∈E j∈E si,j − λ i∈X j∈X si,j diversity C = 2E (unconstrained), 1 ≤ k ≤ 20, λ > 0, single-objective algorithm: double greedy (1/2-approx) [Buchbinder et al. 12] 13 / 15
  16. Result 0 5 10 15 20 k 10−3 10−2 10−1

    100 101 Estimated regret ratio Polytope Random Coordinate
  17. Result 0 5 10 15 20 k 10−3 10−2 10−1

    100 101 Estimated regret ratio Polytope Random Coordinate regret ratio decreases dramatically 14 / 15
  18. Our Results Extend regret ratio framework to submodular maximization Upper

    Bound Given an α-approx algorithm for (weighted) single objective problem, • regret ratio 1 − α/d for any d • regret ratio 1 − α + O(1/k) for any k and d = 2. d = # objectives, k = # of feasible solutions Lower Bound • Even if α = 1 and d = 2, it is impossible to achieve regret ratio o(1/k2). 15 / 15