Partial Function Extension with Applications in Mathematics
Explore the concept of partial function extension in mathematics with real-world applications. Examples include extending convex and monotone functions, and algorithms for efficient function extension. Discover how to determine if a function can be defined to extend a given partial function based on specified points and constraints.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Partial Function Extension with Applications Umang Bhaskar Gunjan Kumar Tata Institute of Fundamental Research
2 Partial Function Extension ?1, ?2, , ?? from domain D values ?1, ?2, , ?? and family F of functions, Given points at the given points Does there exist function ? F defined on D that satisfies ? ?? = ?? for ? = 1 ? ? (i.e., extends the given partial function)
3 Example: Convex Functions Domain D = ? Family F : convex functions Partial function: Partial function: 2 0,1 , 2,2 ,(4,2) 1 Not Extendible 0 2 4
4 Example: Convex Functions Domain D = ? Family F : convex functions Partial function: Partial function: 2 0,1 , 2,1 ,(4,2) 1 0 2 4
5 Example: Convex Functions Domain D = ? Family F : convex functions Partial function: Partial function: 2 0,1 , 2,1 ,(4,2) 1 Extendible 0 2 4
6 Example: Monotone Functions Domain D = 2{?,?,?} Family F : monotone functions ??? 5 Partial function: Partial function: ?? ?? ?? ?,?,? ,5 ,0 , {?},6 ,( ? ,5), ? 5 ? ? 6 Not Extendible 0
7 Example: Monotone Functions Domain D = 2{?,?,?} Family F : monotone functions ??? 5 Partial function: Partial function: ?? ?? ?? ?,?,? ,5 ,0 , {?},6 ,( ? ,5), ? 5 ? ? 1 0
8 Example: Monotone Functions Domain D = 2{?,?,?} Family F : monotone functions ??? 5 Partial function: Partial function: 5 1 5 ?? ?? ?? ?,?,? ,5 ,0 , {?},6 ,( ? ,5), ? 5 ? 0 ? 1 Extendible 0
9 Partial Function Extension Given partial function ? = from domain D = ??or 2?, and family F of functions, ?1,?1, ?2,?2, , (??,??} Does there exist function ? F defined on D that extends ?? Want efficient algorithms: ????(?,?)
10 Approximate Extension Given partial function ? = from domain D = ??or 2?, and family F of functions, ?1,?1, ?2,?2, , (??,??} Minimize ? such that, for some ? F , ?? ? ?? ? ?? for ? = 1 ?
11 Application I: Lower Bounds for PAC Learning
12 Application I: Lower Bounds for PAC Learning For family F of functions, domain D = 2?, F is ? PAC learnable if , for any? F, distribution ?over 2?, ? can be learned within a factor of ?w.h.p., from ????(?) samples
13 Application I: Lower Bounds for PAC Learning For family F of functions, domain D = 2?, F is ? PAC learnable if , for any? F, distribution ?over 2?, ? can be learned within a factor of ?w.h.p., from ????(?) samples ?1,? ?1 ?2,? ?2 ??,? ?? , , , Learning Algorithm ? ? each ?? ~ ? iid, ? = ???? ? ? ? ? ? ? ? ? w.h.p. for ? ~ ?
14 Application I: Lower Bounds for PAC Learning Suppose for family F of functions, domain D = 2?, ?1,?2, ,?? D such that: there exist values ? > 1, ? is superpolynomial in ?, for any?1,?2, ,?? [1,?], partial function ?1,?1, ?2,?2, ??,?? is extendible, then family F cannot be PAC-learned with factor < ?. Let ? be uniform distribution over ?1,?2, ,??. Learning algorithm only sees poly samples, next set ? not seen before w.h.p., must guess value 1.
15 Application II: Property Testing
16 Application II: Property Testing For family F of functions, domain D = 2?, ?1,?2, ,?? Testing Algorithm ? ? ?1,? ?2, ,? (??) determine with ?(2?) queries if ? F, or if far from F ? is ?-far from F if (? 2?) values must be changed to be in F
17 Application II: Property Testing For family F of functions, domain D = 2?, ?1,?2, ,?? Testing Algorithm ? ? ?1,? ?2, ,? (??) determine with ?(2?) queries if ? F, or if far from F can be extended to F, algo must say ? F If partial fn ?1,? ?1 , , ??,? ??
18 Relevant Families F Domain 2[?] Subadditive functions ? ? + ? ? ? ? ? (complement-free)
19 Relevant Families F Domain 2[?] Subadditive functions ? ? + ? ? ? ? ? (complement-free) e.g., ? ? = ?( ? ), where 3 3 2 2 ?( ? ) ?( ? ) 1 1 0 2 3 4 0 2 3 4 1 1 ? ?
20 Relevant Families F Domain 2[?] Subadditive functions ? ? + ? ? ? ? ? (complement-free) Submodular functions ? ? + ? ? ? ? ? + ? ? ? or ? ? ? ? ? ? ? ? ? ? ? ? (diminishing marginal returns)
21 Relevant Families F Domain 2[?] Subadditive functions ? ? + ? ? ? ? ? (complement-free) Submodular functions ? ? + ? ? ? ? ? + ? ? ? or ? ? ? ? ? ? ? ? ? ? ? ? (diminishing marginal returns) 3 3 2 2 ?( ? ) ?( ? ) 1 1 0 2 3 4 1 0 2 3 4 1 ? ?
22 Relevant Families F Domain 2[?] Subadditive functions ? ? + ? ? ? ? ? (complement-free) Submodular functions ? ? + ? ? ? ? ? + ? ? ? or ? ? ? ? ? ? ? ? ? ? ? ? (diminishing marginal returns) Domain ?? Convex functions ?1? ?1 + + ??? ?? ? ?1?1+ + ???? ?? 0, ???= 1
23 Previous Work ? ? Subadditive functions: bounds of ?( ? log ?) and bounds of ?( ? log ?) and log ?on learning log ?on learning [Balcan et al., 2012] bounds of ?( ?) and ?1/3on learning nonnegative, monotone submodular fns Submodular functions: [Balcan, Harvey, 2011] tester that makes ? ? ? log ? queries [Seshadhri, Vondrak, 2014] Convex functions: partial function extension studied in convex analysis
24 Our Results Subadditive functions (domain ??): Partial Fn Extn: coNP-complete tight bound of (log ?) on approximate extension improved lower bound of ( ?) Learning: ? 2+? Testing: ? log 1/? queries tester that makes 2 first nontrivial tester, makes ? 2?queries
25 Our Results Submodular functions (general, domain ??): always extendible if points ??s form an antichain (?? ?? ?,?) Partial Fn Extn: Learning: cannot be learned within any factor
26 Our Results Submodular functions (general, domain ??): always extendible if points ??s form an antichain (?? ?? ?,?) Partial Fn Extn: Learning: cannot be learned within any factor 3 2 Convex functions (domain ??): 1 Extension problem is in ? Partial Fn Extn: 2 1 0 but given ? ??, finding value of canonical extension at ? is NP-hard
27 Our Results Submodular functions (general, domain ??): always extendible if points ??s form an antichain (?? ?? ?,?) Partial Fn Extn: Learning: cannot be learned within any factor ? 3 2 Convex functions (domain ??): 1 Extension problem is in ? Partial Fn Extn: ? 2 1 0 but given ? ??, finding value of canonical extension at ? is NP-hard
28 This Talk Subadditive functions (extension, learning, testing) Convex functions (extension)
29 This Talk Subadditive functions (extension, learning, testing) Convex functions (extension)
30 Subadditive Functions Domain 2[?] subadditive functions ? ? + ? ? ? ? ? (complement-free) e.g., ? ? = ?( ? ), where 3 3 2 2 ?( ? ) ?( ? ) 1 1 0 2 3 4 0 2 3 4 1 1 ? ?
31 Subadditive Functions: Extension Theorem: Subadditive extension is coNP-hard Tight bound of (log ?) on approximate subadditive extension Partial fn { ?1,?1, , ??,??} cannot be extended to a subadditive fn iff there exist sets ?1,?2, ,??,??+1 such that: Lemma: ??+1 ?1 ?2 ??, and ??+1 > ?1+?2+ + ??
32 Subadditive Functions: Extension Theorem: Subadditive extension is coNP-hard Tight bound of (log ?) on approximate subadditive extension Partial fn { ?1,?1, , ??,??} cannot be extended to a subadditive fn iff there exist sets ?1,?2, ,??,??+1 such that: Lemma: ??? ??+1 ?1 ?2 ??, and 1 1 3 ?? ?? ?? ??+1 > ?1+?2+ + ?? ? ? ? (lower bound in theorem from set cover, proof skipped) not extendible
33 Subadditive Functions: Learning Theorem: Subadditive functions cannot be learned by any ?( ?) factor We use the existence of large ?-cover free families of sets A 2? is an ?-cover free family if any set in the family is not contained in the union of ? other sets. i.e., if ?,?1, ,?? A and ? ?1 ?2 ??, then ? > ?
34 Subadditive Functions: Learning A 2? is an ?-cover free family if any set in the family is not contained in the union of ? other sets. i.e., if ?,?1, ,?? A and ? ?1 ?2 ??, then ? > ? If ?1, ,?? is an ?-cover free family, then the partial fn can be extended to a subadditive function for any?? 1,? , ? = 1 ? ?1,?1, ,(??,??} Lemma: Suppose not extendible. Then there exist sets ?1,?2, ,??,??+1 s.t.: ??+1 ?1 ?2 ??, and Proof: ??+1 > ?1+?2+ + ?? Since ?-cover free, ? > ?, hence ??+1> ? + 1. Contradiction.
35 Subadditive Functions: Learning If ?1, ,?? is an ?-cover free family, then the partial fn can be extended to a subadditive function for any?? 1,? , ? = 1 ? ?1,?1, ,(??,??} Lemma: Theorem: For ? = ?( ?) , there exists an ?-cover free family of size superpolynomial (in ?) [Dyachkov et al., 2014] Thus there exists a superpolynomial-sized family of sets ?1, ,?? that for any values in [1,? ? ], can be extended to a subadditive function. By earlier argument, using uniform distribution over ?1, ,?? , subadditive functions cannot be learned by any ?( ?) factor.
36 Subadditive Functions: Testing ? 2+? ? log 1/? queries Theorem: There is a tester for subadditive functions that makes 2 Recall: Partial fn { ?1,?1, , ??,??} cannot be extended to a subadditive fn iff there exist sets ?1,?2, ,??,??+1 such that: Lemma: ??+1 ?1 ?2 ??, and ??+1 > ?1+?2+ + ??
37 Subadditive Functions: Testing ? 2+? ? log 1/? queries Theorem: There is a tester for subadditive functions that makes 2 [?] Tester: [?] ?/2
38 Subadditive Functions: Testing ? 2+? ? log 1/? queries Theorem: There is a tester for subadditive functions that makes 2 [?] Tester: Do 1/? times: Choose ? ? ? 2+ ? uniformly [?] Let ? ? be all subsets of ? . Query all sets in ? ? . ( ? ? ? 2+ ? 2?). ?2 ?1 If partial fn { ? ? ,? ? ? characterization, reject violates ?(?2) ?(?1) Accept
39 Subadditive Functions: Testing ? 2+? ? log 1/? queries Theorem: There is a tester for subadditive functions that makes 2 [?] Tester: Do 1/? times: Choose ? ? ? 2+ ? uniformly [?] Let ? ? be all subsets of ? . Query all sets in ? ? . ( ? ? ? 2+ ? 2?). ?2 ?1 If partial fn { ? ? ,? ? ? ) violates characterization, reject ?(?2) ?(?1) Accept
40 This Talk Subadditive functions (extension, learning, testing) Convex functions (extension)
41 Our Results Convex functions (domain ??): Given partial function ? = ?1,?1, ?2,?2, , (??,??} does there exist a convex fn that extends ?? ? 3 Extension problem is in ? 2 but given ? ??, finding value of canonical extension at ? is NP-hard 1 ? 2 1 0
42 3 2 1 2 1 ? 0
43 ? ? ? = min ?? ?? ?=1 ? ?? ?? = ? 3 ?=1 ? 2 ?? = 1, ?? 0 1 ?=1 2 1 ? 0
44 ? will show ?( ) is convex extension, if ? extendible ? ? = min ?? ?? ?=1 ? ?? ?? = ? 3 ?=1 ? 2 ?? = 1, ?? 0 1 ?=1 2 1 ? 0 ? ?? ?? If ?( ) is a convex extn of partial fn, then ? ? ?(?) for feasible ? Thus if there exists a convex extn ? , then ??= ? ?? ? ?? ??, and ? is extn Then:
45 ? ? ? = min ?? ?? ?=1 ? ?? ?? = ? ?=1 ? ?? = 1, ?? 0 ?=1 If there exists a convex extn ? , then ? is extn
46 ? ? ? ? = min ?? ?? max ? + ???? ?=1 ?=1 ? ? ?? ?? = ? ?? 1? ?? ?? for all ? = 1 ?, ?=1 ?=1 ? ?? = 1, ?? 0 Let ?1, ?1, , ??, ?? be vertices of dual polyhedron ?=1 ? ? ? [?] ??+ ? ? =max ???? ?=1 If there exists a convex extn ? , then ? is extn ? is convex Thus ? is convex extn, if partial fn is extendible
47 ? ? ? ? = min ?? ?? max ? + ???? ?=1 ?=1 ? ? ?? ?? = ? ?? 1? ?? ?? for all ? = 1 ?, ?=1 ?=1 ? ?? = 1, ?? 0 Let ?1, ?1, , ??, ?? be vertices of dual polyhedron ?=1 ? ? ? [?] ??+ ? ? =max ???? ?=1 ? in convex hull of ?1, ,??: primal feasible, obtain ? ? by solving primal ? NOT in convex hull of ?1, ,??: obtaining ? ? is NP-hard
48 Further Results This talk: Subadditive functions Submodular functions Convex functions Further work on: XOS, matroid rank, coverage functions Further work on submodular functions
49 Open Questions Hardness of submodular extension? Is submodular extension in NP / coNP? Close gap in learning subadditive functions ( ? ? log ? , ? ) Better testers for subadditive functions? Further applications for partial function extension? Thank You!
