### Learning and Testing Submodular Functions with Bounded Range

Learning and Testing
Submodular Functions
Grigory Yaroslavtsev
(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
Ω
≤   ≤
≤≤
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

Under arbitrary
distribution

Tolerant
queries

|| 2

SQqueries,
Agnostic
PAC
:  → , … ,
(bounded integral
range  ≤ ||)

3

(  ⋅log  )
Agnostic
Learning: Bigger picture
⊆
⊆
}
Fu, Kleinberg, Nisan,
Roughgarden,SODA’12]
⊆
Submodular
⊆
Gross substitutes
OXS
(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!