Report

Learning and Testing Submodular Functions Grigory Yaroslavtsev With Sofya Raskhodnikova (SODA’13) + Work in progress with Rocco Servedio Columbia University October 26, 2012 Submodularity • Discrete analog of convexity/concavity, law of diminishing returns • Applications: optimization, algorithmic game theory Let : 2 → [0, ]: • Discrete derivative: = ∪ {} − , ⊆ , ∉ • Submodular function: ≥ , ∀ ⊆ ⊆ , ∉ Exact learning • Q: Reconstruct a submodular : 2 → with poly(|X|) queries (for all arguments)? • A: Only Θ -approximation (multiplicative) possible [Goemans, Harvey, Iwata, Mirrokni, SODA’09] • Q: Only for 1 − -fraction of points (PAC-style membership queries under uniform distribution)? Pr Pr = ∼(2 ) • A: Almost as hard [Balcan, Harvey, STOC’11]. learning with 1 ≥1− ≥ 2 Approximate learning • PMAC-learning (Multiplicative), with poly(|X|) queries : Pr Pr ∼(2 ) 1 3 Ω ≤ ≤ ≤≤ • PAAC-learning (Additive) Pr Pr ∼(2 ) • Running time: (over arbitrary distributions [BH’11]) 1 | − | ≤ ≥ 1 − ≥ 2 || 2 • Running time: poly Lee, SODA’12] 1 ≥1− ≥ 2 1 log() 2 [Gupta, Hardt, Roth, Ullman, STOC’11] , log 1 [Cheraghchi, Klivans, Kothari, Learning : 2 → [0, ] • For all algorithms = . Learning Time Extra features Goemans, Harvey, Iwata, Mirrokni Balcan, Harvey approximation Everywhere PMAC Multiplicative Poly(|X|) Poly(|X|) = Gupta, Hardt, Roth, Ullman Cheraghchi, Our result with Klivans, Sofya Kothari, Lee PAAC Additive Under arbitrary distribution Tolerant queries || 2 SQqueries, Agnostic PAC : → , … , (bounded integral range ≤ ||) 3 ( ⋅log ) Agnostic Learning: Bigger picture ⊆ Subadditive ⊆ XOS = Fractionally subadditive } [Badanidiyuru, Dobzinski, Fu, Kleinberg, Nisan, Roughgarden,SODA’12] ⊆ Submodular ⊆ Gross substitutes OXS Additive (linear) Value demand Other positive results: • Learning valuation functions [Balcan, Constantin, Iwata, Wang, COLT’12] • PMAC-learning (sketching) valuation functions [BDFKNR’12] • PMAC learning Lipschitz submodular functions [BH’10] (concentration around average via Talagrand) Discrete convexity • Monotone convex : {1, … , } → 0, … , 8 6 4 2 0 1 2 3 … <=R … … … … … … … … n … … n • Convex : {1, … , } → 0, … , 8 6 4 2 0 1 2 3 … <=R … … … …>= n-R… Discrete submodularity : 2 → {0, … , } • Case study: = 1 (Boolean submodular functions : 0,1 → {0,1}) Monotone submodular = 1 ∨ 2 ∨ ⋯ ∨ (monomial) Submodular = (1 ∨ ⋯ ∨ ) ∧ (1 ∨ ⋯ ∨ ) (2-term CNF) • Monotone submodular • Submodular ≥ − ≤ ≤ ∅ ∅ Discrete monotone submodularity • Monotone submodular : 2 → 0, … , ≥ ( , ( )) ≥ ( ) ≥ ( ) ≤ ( ) ( ) Discrete monotone submodularity • Theorem: for monotone submodular : 2 → 0, … , for all : = max () ⊆, ≤ • ≥ max ⊆, ≤ () (by monotonicity) ≤ ⊆ , ≤ Discrete monotone submodularity • ≤ max ⊆, ≤ • S’ = smallest subset of such that = ’ • ∀ ∈ ′ we have ′ ∖ > 0 => Restriction of ′ on 2 is monotone increasing =>|’| ≤ ′ ≤ ′ Representation by a formula • Theorem: for monotone submodular : 2 → 0, … , for all : = max () ⊆, ≤ • Notation switch: → , 2 → (1 , … , ) • (Monotone) Pseudo−Boolean k−DNF ( ∨ → , = 1 → ∈ ℝ): [ ⋅ 1 ∧ 2 ∧ ⋯ ∧ ] (no negations) • (Monotone) submodular 1 , … , → 0, … , can be represented as a (monotone) pseudo-Boolean 2R-DNF with constants ∈ 0, … , . Discrete submodularity • Submodular 1 , … , → 0, … , can be represented as a pseudo-Boolean 2R-DNF with constants ∈ 0, … , . • Hint [Lovasz] (Submodular monotonization): Given submodular , define = ⊆ Then is monotone and submodular. ≥ − ≤ ∅ Learning pB-formulas and k-DNF • , = class of pB-DNF of width with ∈ {0, … , } • i-slice 1 , … , → {0,1} defined as 1 , … , = 1 iff 1 , … , ≥ • If ∈ , its i-slices are -DNF and: 1 , … , = max ( ⋅ 1 , … , ) 1≤≤ • PAC-learning Pr Pr () ∼( 0,1 ) = 1 ≥1− ≥ 2 Learning pB-formulas and k-DNF • Learn every i-slice on 1 − ′ = (1 − / ) fraction of arguments • Learning -DNF ( , ) (let Fourier sparsity = log ) – Kushilevitz-Mansour (Goldreich-Levin): , queries/time. – ``Attribute efficient learning’’: ⋅ queries – Lower bound: Ω(2 ) queries to learn a random -junta (∈ -DNF) up to constant precision. • Optimizations: – Slightly better than KM/GL by looking at the Fourier spectrum of , (see SODA paper: switching lemma => 1 bound) – Do all R iterations of KM/GL in parallel by reusing queries Property testing • Let C be the class of submodular : 0,1 → {0, … , } • How to (approximately) test, whether a given is in C? • Property tester: (Randomized) algorithm for distinguishing: 1. ∈ 2. (-far): min – ≥ 2 ∈ • Key idea: -DNFs have small representations: – [Gopalan, Meka,Reingold CCC’12] (using quasi-sunflowers [Rossman’10]) ∀ > 0, ∀ -DNF formula F there exists: -DNF formula F’ of size ≤ 1 () log such that – ’ ≤ 2 Testing by implicit learning • Good approximation by juntas => efficient property testing [surveys: Ron; Servedio] – -approximation by ()-junta – Good dependence on : = 1 () log • [Blais, Onak] sunflowers for submodular functions 1 [ log + log ](+) – Query complexity: 1 () log (independent of n) – Running time: exponential in (we think can be reduced it to O(()) ) – We have Ω lower bound for testing -DNF (reduction from Gap Set Intersection: distinguishing a random -junta vs + O(log )-junta requires Ω queries) Previous work on testing submodularity : 0,1 → [0, ] [Parnas, Ron, Rubinfeld ‘03, Seshadhri, Vondrak, ICS’11]: • Upper bound (/)( ) . } Gap in query complexity • Lower bound: Special case: coverage functions [Chakrabarty, Huang, ICALP’12]. Thanks!