Transcript Geometry of Online Packing Linear Programs

Geometry of Online Packing
Linear Programs
Marco Molinaro and R. Ravi
Carnegie Mellon University
Packing Integer Programs (PIPs)
• Non-negative c, A, b
• Max 𝑐𝑥
n
st
A
𝑥 ∈ {0,1}𝑛
• A has entries in [0,1]
x
≤
b
m
Online Packing Integer Programs
•
•
•
•
Adversary chooses values for c, A, b
…but columns are presented in random order
…when column comes, set variable to 0/1 irrevocably
b and n are known upfront
A
c
A
n
1
0
x
≤
b
Online Packing Integer Programs
• Goal: Find feasible solution that maximizes
expected value
• 1 − 𝜖 -competitive:
E ALG ≥ 1 − 𝜖 OfflineIP
Previous Results
• First online problem: secretary problem [Dynkin 63]
• B-secretary problem (m=1, b=B, A is all 1’s) [Kleinberg 05]
(1 − 𝜖)-competitive for 𝐵 = Ω
do not depend
on n
1
𝜖2
• PIPs (B=min bi) [FHKMS 10, AWY]
(1 − 𝜖)-competitive for 𝐵 = Ω
need 𝐵 = Ω
depends on n
𝑚
log
2
𝜖
1
log
2
𝜖
𝑛
𝑚
Main Question and Result
• Q: Do general PIPs become more difficult for
larger n?
• A: No!
Main result
Algorithm 1 − 𝜖 -competitive when 𝐵 = Ω
𝑚2
log
𝜖2
𝑚
High-level Idea
1. Online PIP as learning
2. Improving learning error using tailored covering
bounds
3. Geometry of PIPs that allow good covering bounds
4. Reduce general PIP to above
For this talk:
• 𝒄=1
• Every right-hand side 𝑏𝑖 = 𝐵
• Show weaker bound 𝐵 = Ω
𝑚2
log
𝜖3
𝑚
Online PIP as Learning
1) Reduction to learning a classifier [DH 09]
Linear classifier: given (dual) vector 𝑝 ∈ 𝑅𝑚 ,
𝑥(𝑝)𝑡 = 1 iff 𝑝𝐴𝑡 − 1 < 0
𝑨𝒕
0
0
1
1
1
0
𝒙(𝒑)𝒕
1
𝒑
Online PIP as Learning
1) Reduction to learning a classifier [DH 09]
Linear classifier: given (dual) vector 𝑝 ∈ 𝑅𝑚 ,
𝑥(𝑝)𝑡 = 1 iff 𝑝𝐴𝑡 − 1 < 0
Claim: If the classification 𝑥(𝑝) given by 𝑝 satisfies
1) [Feasible]
𝑡 𝐴𝑡𝑖 𝑥(𝑝)𝑡
≤𝐵
2) [Packs tightly] If 𝑝𝑖 > 0, then
𝑡 𝐴𝑡𝑖 𝑥(𝑝)𝑡
≥ 1−𝜖 𝐵
then 𝑥(𝑝) is (1−𝜖) optimal.
Moreover, such classification always exists.
Online PIP as Learning
1) Reduction to learning [DH 09]
Linear classifier: given (dual) vector 𝑝 ∈ 𝑅𝑚 , set
𝑥(𝑝)𝑡 = 1 iff 𝑝𝐴𝑡 − 1 < 0
Claim: If the classification 𝑥(𝑝) given by 𝑝 satisfies
1) [Feasible]
𝑡 𝐴𝑡𝑖 𝑥(𝑝)𝑡
≤𝐵
2) [Packs tightly] If 𝑝𝑖 > 0, then
𝑡 𝐴𝑡𝑖 𝑥(𝑝)𝑡
≥ 1−𝜖 𝐵
then 𝑥(𝑝) is (1−𝜖) optimal.
Moreover, such classification always exists.
Online PIP as Learning
2) Solving PIP via learning
a) See first 𝜖 fraction of columns
b) Compute appropriate 𝑝 for sampled IP
[𝑝𝑖 > 0],
𝑡≤𝜖𝑛 𝐴𝑡𝑖 𝑥(𝑝)𝑡
≤ 𝜖𝐵 −𝜖 2 𝐵
𝑡≤𝜖𝑛 𝐴𝑡𝑖 𝑥(𝑝)𝑡
≥ 1 − 𝜖 𝜖𝐵 +𝜖 2 𝐵
c) Use 𝑝 to classify remaining columns
Online PIP as Learning
2) Solving PIP via learning
𝒑
a) See first 𝜖 fraction of columns
b) Compute appropriate 𝑝 for sampled IP
[𝑝𝑖 > 0],
𝑡≤𝜖𝑛 𝐴𝑡𝑖 𝑥(𝑝)𝑡
≤ 𝜖𝐵 −𝜖 2 𝐵
𝑡≤𝜖𝑛 𝐴𝑡𝑖 𝑥(𝑝)𝑡
≥ 1 − 𝜖 𝜖𝐵 +𝜖 2 𝐵
c) Use 𝑝 to classify remaining columns
Probability of learning good classifier:
• Consider a classifier 𝑝 that overfills some budget:
𝑡 𝐴𝑡𝑖 𝑥(𝑝)𝑡 > 𝐵
• Can only learn 𝑝 if sample is skewed. Happens with probability at most exp(−𝜖 3 𝐵)
• At most ~ 𝑛𝑚 distinct bad classifiers
• Union bounding over all bad classifiers, learn bad classifier with prob. at most
𝑛𝑚 exp(−𝜖 3 𝐵)
𝑚
• When 𝐵 = Ω 3 log 𝑛 to get good classifier with high probability
𝜖
Online PIP as Learning
2) Solving PIP via learning
Improve this…
Probability of learning good classification:
• Consider a classification 𝑝 that overfills some budget:
• Can only learn 𝑝 if sample is skewed. Happens with probability at most exp(−𝜖 3 𝐵)
• At most ~ 𝑛𝑚 distinct bad classifications
• Union bounding over all bad classifications, learn desired good classification with
prob. at least 1 − 𝑛𝑚 exp(𝜖 3 𝐵)
• When
to get good classification with high probability
Improved Learning Error
• Idea 1: Covering bounds via witnesses
(handling multiple bad classifiers at a time)
+-witness: 𝑝 is a +-witness of 𝑝’ for constraint 𝑖 if
1) Columns picked by 𝑝 ⊆ columns picked by 𝑝’
2) Total occupation of constraint 𝑖 by columns picked by 𝑝 is > 𝐵
−-witness: similar…
Lemma: Suppose there is a witness set of size 𝑀.
Then probability of learning a bad classifier is ~𝑀. exp(−𝜖 3 𝐵)
Total weight > 𝐵
Geometry of PIPs with Small Witness Set
• For some PIPs, size of witness set is at least 𝑀 > Ω(𝑛)
• Idea 2: Consider PIPs whose columns lie on few (𝐾) 1-d
subspaces
Geometry of PIPs with Small Witness Set
• For some PIPs, size of witness set is at least 𝑀 > Ω(𝑛)
• Idea 2: Consider PIPs whose columns lie on few (𝐾) 1-d
subspaces
𝑲=2
Lemma: For such PIPs, can find witness set of size 𝑂
𝐾 𝑚
𝜖
Geometry of PIPs with Small Witness Set
• Covering bound + witness size: it suffices 𝐵 ≥
• Final step: Convert any PIP into one with 𝐾 =
𝑚
Ω 3 log 𝐾
𝜖
𝑚 𝑚
𝜖
Algorithm 1 − 𝜖 -competitive when 𝐵 = Ω
, loses 𝜖 value
𝑚2
log
𝜖3
𝑚
Conclusion
• Guarantee for online PIPs independent of number of columns 𝑛
• Asymptotically matches that for single constraint version [Kleinberg 05]
• Ideas
1) Tailored covering bound based on witnesses
2) Analyze geometry of columns to obtain small witness set
⇒ Make the learning problem more robust
Open problems
1) Obtain optimal 𝐵 ≥ Ω
replacement [DJSW 11]
1
log 𝑚
𝜖2
? Can do if sample columns with
2) Generalize to AdWords-type problem
3) Better online models: infinite horizon? less randomness?
Thank you!