Sign up for free to use this document yourself.
  • Data distribution-dependent

  • Data distribution-independent

  • Assumes only realizability
    By assuming realizability, we only look at bounds on generalization error rather than generalization gap

  • Stronger assumptions/dependence on data distribution

  • Data-dependent

  • Data-independent

  • Data-dependent

  • Data-independent

  • Data-dependent

  • Data-independent

  • Bounds on generalization gap

  • Bounds on the generalization error

  • Bound on generalization gap

  • Bound on generalization error
    Not possible to have non-trivial bounds due to No Free Lunch theorem

  • Realizable data-dependent bounds
    Optimality of bound depends on assumptions on data distribution..

  • Realizable VC dimension bound is optimal
    Sometimes is vacuous

  • Bounds on generalization gap

  • Bounds on generalization error

  • Bounds on generalization gap

  • Bounds on generalization error

  • Data-dependent Bound on generalization gap of function found by algorithm

  • Data-dependent uniform convergence generalization gap bound
    Rademacher complexity bound is sometimes optimal?
    For some data distributions
    Do they fail for some data distributions

  • Data-dependent Non-uniform (SRM-like) generalization gap bound
    For some data distributions
    Do they fail for some data distributions

  • Assuming realizability (possible for fully expressive models - e.g. some non-parametric models)
    Realizable data-dependent bounds

  • Agnostic VC dimension bound is optimal
    Sometimes is vacuous

  • Data-dependent Bound on generalization gap of function found by algorithm with assumptions on data distribution

  • Data-dependent uniform convergence generalization gap bound with assumptions on data distribution
    Rademacher complexity bound is sometimes optimal?
    For some data distributions
    Do they fail for some data distributions

  • Data-dependent Non-uniform (SRM-like) generalization gap bound with assumptions on data distribution
    For some data distributions
    Do they fail for some data distributions

  • Assuming realizability
    Realizable data-dependent bounds with extra assumptions on data distribution
    Always possible in principle. But do particular approaches fail for some distributions

  • Other assumptions

  • Assuming realizability
    Realizable data-independent bounds with extra assumptions on data distribution
    Always possible in principle. But do particular approaches fail for some distributions
    Only example I can think of right now are some realizable margin bounds I’ve seen.

  • Other assumptions

{"cards":[{"_id":"53f46ea03afa97e09d00001f","treeId":"53f46eb73afa97e09d00001d","seq":19575298,"position":1,"parentId":null,"content":"Data distribution-dependent\n\n<style>\n@import url(\"https://maxcdn.bootstrapcdn.com/font-awesome/4.7.0/css/font-awesome.min.css\");\n@import url(\"https://nagoshiashumari.github.io/Rpg-Awesome/stylesheets/rpg-awesome.min.css\");\n</style>"},{"_id":"53f46cfb3afa97e09d000021","treeId":"53f46eb73afa97e09d00001d","seq":19575389,"position":1,"parentId":"53f46ea03afa97e09d00001f","content":"Assumes only realizability\nBy assuming realizability, we only look at bounds on generalization error rather than generalization gap"},{"_id":"53f43bfc3afa97e09d000030","treeId":"53f46eb73afa97e09d00001d","seq":19575346,"position":1,"parentId":"53f46cfb3afa97e09d000021","content":"Data-dependent"},{"_id":"53f420783afa97e09d000037","treeId":"53f46eb73afa97e09d00001d","seq":19575388,"position":1,"parentId":"53f43bfc3afa97e09d000030","content":"Realizable data-dependent bounds\nOptimality of bound depends on assumptions on data distribution.."},{"_id":"53f43bce3afa97e09d000031","treeId":"53f46eb73afa97e09d00001d","seq":19575349,"position":2,"parentId":"53f46cfb3afa97e09d000021","content":"Data-independent"},{"_id":"53f43ace3afa97e09d000032","treeId":"53f46eb73afa97e09d00001d","seq":19575428,"position":1,"parentId":"53f43bce3afa97e09d000031","content":"Realizable VC dimension bound is optimal\nSometimes is vacuous <i class=\"fa fa-times\"></i> "},{"_id":"53f46b603afa97e09d000022","treeId":"53f46eb73afa97e09d00001d","seq":19575285,"position":2,"parentId":"53f46ea03afa97e09d00001f","content":"Stronger assumptions/dependence on data distribution"},{"_id":"53f46a943afa97e09d000023","treeId":"53f46eb73afa97e09d00001d","seq":19575417,"position":1,"parentId":"53f46b603afa97e09d000022","content":"Data-dependent <i class=\"fa fa-check\"></i> <i class=\"fa fa-question\"></i>"},{"_id":"53f4386a3afa97e09d000033","treeId":"53f46eb73afa97e09d00001d","seq":19575351,"position":4,"parentId":"53f46a943afa97e09d000023","content":"Bounds on generalization gap"},{"_id":"53f44f7d3afa97e09d00002b","treeId":"53f46eb73afa97e09d00001d","seq":19575446,"position":1,"parentId":"53f4386a3afa97e09d000033","content":"Data-dependent Bound on generalization gap of function found by algorithm with assumptions on data distribution\n<i class=\"fa fa-check\"></i>"},{"_id":"53f464c23afa97e09d000029","treeId":"53f46eb73afa97e09d00001d","seq":19575470,"position":2,"parentId":"53f4386a3afa97e09d000033","content":"Data-dependent uniform convergence generalization gap bound with assumptions on data distribution\nRademacher complexity bound is sometimes optimal?\nFor some data distributions <i class=\"fa fa-check\"></i>\nDo they fail for some data distributions <i class=\"fa fa-question\"></i>"},{"_id":"53f4640b3afa97e09d00002a","treeId":"53f46eb73afa97e09d00001d","seq":19575457,"position":3,"parentId":"53f4386a3afa97e09d000033","content":"Data-dependent Non-uniform (SRM-like) generalization gap bound with assumptions on data distribution\nFor some data distributions <i class=\"fa fa-check\"></i>\nDo they fail for some data distributions <i class=\"fa fa-question\"></i>"},{"_id":"53f438283afa97e09d000034","treeId":"53f46eb73afa97e09d00001d","seq":19575361,"position":5,"parentId":"53f46a943afa97e09d000023","content":"Bounds on generalization error"},{"_id":"53f432493afa97e09d000035","treeId":"53f46eb73afa97e09d00001d","seq":19575387,"position":1,"parentId":"53f438283afa97e09d000034","content":"Assuming realizability <i class=\"fa fa-check\"></i>\nRealizable data-dependent bounds with extra assumptions on data distribution\nAlways possible in principle. But do particular approaches fail for some distributions <i class=\"fa fa-question\"></i>"},{"_id":"53f428e13afa97e09d000036","treeId":"53f46eb73afa97e09d00001d","seq":19575379,"position":2,"parentId":"53f438283afa97e09d000034","content":"Other assumptions <i class=\"fa fa-question\"></i>"},{"_id":"53f4699e3afa97e09d000024","treeId":"53f46eb73afa97e09d00001d","seq":19575287,"position":2,"parentId":"53f46b603afa97e09d000022","content":"Data-independent"},{"_id":"53f446bc3afa97e09d00002c","treeId":"53f46eb73afa97e09d00001d","seq":19575333,"position":4,"parentId":"53f4699e3afa97e09d000024","content":"Bounds on generalization gap"},{"_id":"53f4697d3afa97e09d000025","treeId":"53f46eb73afa97e09d00001d","seq":19575334,"position":1,"parentId":"53f446bc3afa97e09d00002c","content":"Bound on generalization gap of function found by algorithm\n<i class=\"fa fa-check\"></i>"},{"_id":"53f4688f3afa97e09d000026","treeId":"53f46eb73afa97e09d00001d","seq":19575489,"position":2,"parentId":"53f446bc3afa97e09d00002c","content":"Uniform convergence generalization gap bound \nRademacher complexity bound is sometimes optimal?\nFor some data distributions <i class=\"fa fa-check\"></i>\nFor some data distributions <i class=\"fa fa-times\"></i> (Nagarajan et al. https://papers.nips.cc/paper/9336-uniform-convergence-may-be-unable-to-explain-generalization-in-deep-learning)"},{"_id":"53f467ec3afa97e09d000027","treeId":"53f46eb73afa97e09d00001d","seq":19575490,"position":3,"parentId":"53f446bc3afa97e09d00002c","content":"Non-uniform (SRM-like) generalization gap bound\nFor some data distributions <i class=\"fa fa-check\"></i>\nFor some data distributions <i class=\"fa fa-times\"></i> (Nagarajan et al. https://papers.nips.cc/paper/9336-uniform-convergence-may-be-unable-to-explain-generalization-in-deep-learning)"},{"_id":"53f446013afa97e09d00002d","treeId":"53f46eb73afa97e09d00001d","seq":19575341,"position":5,"parentId":"53f4699e3afa97e09d000024","content":"Bounds on generalization error"},{"_id":"53f4442a3afa97e09d00002e","treeId":"53f46eb73afa97e09d00001d","seq":19575384,"position":1,"parentId":"53f446013afa97e09d00002d","content":"Assuming realizability <i class=\"fa fa-check\"></i>\nRealizable data-independent bounds with extra assumptions on data distribution\nAlways possible in principle. But do particular approaches fail for some distributions <i class=\"fa fa-question\"></i>\nOnly example I can think of right now are some realizable margin bounds I've seen."},{"_id":"53f4426e3afa97e09d00002f","treeId":"53f46eb73afa97e09d00001d","seq":19575378,"position":2,"parentId":"53f446013afa97e09d00002d","content":"Other assumptions <i class=\"fa fa-question\"></i>"},{"_id":"53f46d9b3afa97e09d000020","treeId":"53f46eb73afa97e09d00001d","seq":19575281,"position":2,"parentId":null,"content":"Data distribution-independent"},{"_id":"53f4165b3afa97e09d000038","treeId":"53f46eb73afa97e09d00001d","seq":19575392,"position":1,"parentId":"53f46d9b3afa97e09d000020","content":"Data-dependent"},{"_id":"53f413553afa97e09d00003d","treeId":"53f46eb73afa97e09d00001d","seq":19575405,"position":1,"parentId":"53f4165b3afa97e09d000038","content":"Bounds on generalization gap"},{"_id":"53f3fb563afa97e09d000041","treeId":"53f46eb73afa97e09d00001d","seq":19575510,"position":2,"parentId":"53f413553afa97e09d00003d","content":"Data-dependent Bound on generalization gap of function found by algorithm\n<i class=\"fa fa-check\"></i>"},{"_id":"53f3f1853afa97e09d000042","treeId":"53f46eb73afa97e09d00001d","seq":19575462,"position":3,"parentId":"53f413553afa97e09d00003d","content":"Data-dependent uniform convergence generalization gap bound\nRademacher complexity bound is sometimes optimal?\nFor some data distributions <i class=\"fa fa-check\"></i>\nDo they fail for some data distributions <i class=\"fa fa-question\"></i>"},{"_id":"53f3eeb43afa97e09d000043","treeId":"53f46eb73afa97e09d00001d","seq":19575463,"position":4,"parentId":"53f413553afa97e09d00003d","content":"Data-dependent Non-uniform (SRM-like) generalization gap bound\nFor some data distributions <i class=\"fa fa-check\"></i>\nDo they fail for some data distributions <i class=\"fa fa-question\"></i>"},{"_id":"53f40c853afa97e09d00003f","treeId":"53f46eb73afa97e09d00001d","seq":19575411,"position":2,"parentId":"53f4165b3afa97e09d000038","content":"Bounds on the generalization error"},{"_id":"53f40c463afa97e09d000040","treeId":"53f46eb73afa97e09d00001d","seq":19575418,"position":1,"parentId":"53f40c853afa97e09d00003f","content":"Assuming realizability (possible for fully expressive models - e.g. some non-parametric models) <i class=\"fa fa-check\"></i> \nRealizable data-dependent bounds "},{"_id":"53f4162a3afa97e09d000039","treeId":"53f46eb73afa97e09d00001d","seq":19575393,"position":2,"parentId":"53f46d9b3afa97e09d000020","content":"Data-independent"},{"_id":"53f416033afa97e09d00003a","treeId":"53f46eb73afa97e09d00001d","seq":19575395,"position":1,"parentId":"53f4162a3afa97e09d000039","content":"Bound on generalization gap"},{"_id":"53f414333afa97e09d00003c","treeId":"53f46eb73afa97e09d00001d","seq":19575426,"position":1,"parentId":"53f416033afa97e09d00003a","content":"Agnostic VC dimension bound is optimal\nSometimes is vacuous <i class=\"fa fa-times\"></i> "},{"_id":"53f415c93afa97e09d00003b","treeId":"53f46eb73afa97e09d00001d","seq":19575399,"position":2,"parentId":"53f4162a3afa97e09d000039","content":"Bound on generalization error \n<i class=\"fa fa-times\"></i> Not possible to have non-trivial bounds due to No Free Lunch theorem"}],"tree":{"_id":"53f46eb73afa97e09d00001d","name":"Taxonomy of generalization error bounds","publicUrl":"taxonomy-of-generalization-error-bounds"}}