Submodular Functions: Learnability, Structure, and Optimization
Authors:
- Maria-Florina BalcanMBMaria-Florina Balcan
- Nicholas J. A. HarveyNHNicholas J. A. Harvey
- 1 January 2018
- journal article
- research article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 47 (3) , 703-754
Abstract
Submodular functions are discrete functions that model laws of diminishing returns and enjoy numerous algorithmic applications. They have been used in many areas, including combinatorial optimization, machine learning, and economics. In this work we study submodular functions from a learning theoretic angle. We provide algorithms for learning submodular functions, as well as lower bounds on their learnability. In doing so, we uncover several novel structural results revealing ways in which submodular functions can be both surprisingly structured and surprisingly unstructured. We provide several concrete implications of our work in other domains including algorithmic game theory and combinatorial optimization. At a technical level, this research combines ideas from many areas, including learning theory (distributional learning and PAC-style analyses), combinatorics and optimization (matroids and submodular functions), and pseudorandomness (lossless expander graphs).Keywords
All Related Versions
Funding Information
- Air Force Office of Scientific Research (FA9550-09-1-0538)
- Office of Naval Research (N00014-09-1-0751)
- Natural Sciences and Engineering Research Council of Canada
- Microsoft
- National Science Foundation (CCF-0953192, CCF-1101283)
This publication has 69 references indexed in Scilit:
- PseudorandomnessFoundations and Trends® in Theoretical Computer Science, 2012
- Expander graphs and their applicationsBulletin of the American Mathematical Society, 2006
- Combinatorial auctions with decreasing marginal utilitiesGames and Economic Behavior, 2006
- Improved Bounds on the Sample Complexity of LearningJournal of Computer and System Sciences, 2001
- Putting Auction Theory to Work: The Simultaneous Ascending AuctionJournal of Political Economy, 2000
- Expander codesIEEE Transactions on Information Theory, 1996
- Cryptographic limitations on learning Boolean formulae and finite automataJournal of the ACM, 1994
- Constant depth circuits, Fourier transform, and learnabilityJournal of the ACM, 1993
- A theory of the learnableCommunications of the ACM, 1984
- Job Matching, Coalition Formation, and Gross SubstitutesEconometrica, 1982