Submodular functions: learnability, structure, and optimization
From MaRDI portal
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).
Recommendations
Cites work
- A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
- A Stab at Approximating Minimum Subadditive Join
- A theory of the learnable
- A Unified Continuous Greedy Algorithm for Submodular Maximization
- Agnostically Learning Halfspaces
- Algorithmic Game Theory
- An analysis of approximations for maximizing submodular set functions—I
- An analysis of the greedy algorithm for the submodular set covering problem
- Approximability of Combinatorial Problems with Multi-agent Submodular Cost Functions
- Are Bitvectors Optimal?
- Combinatorial auctions with decreasing marginal utilities
- Combinatorial auctions. Foreword by Vernon L. Smith.
- Combinatorial Optimization. Polyhedra and efficiency. CD-ROM
- Communication complexity of combinatorial auctions with submodular valuations
- Complexity of Matroid Property Algorithms
- Concentration of measure and isoperimetric inequalities in product spaces
- Connections in combinatorial optimization
- Constant depth circuits, Fourier transform, and learnability
- Cryptographic limitations on learning Boolean formulae and finite automata
- Decision theoretic generalizations of the PAC model for neural net and other learning applications
- Discrete Convex Analysis
- Expander codes
- Expander graphs and their applications
- Geometric algorithms and combinatorial optimization.
- Graph colouring and the probabilistic method
- Graph cuts with interacting edge weights: examples, approximations, and algorithms
- Hardness of learning halfspaces with noise
- Horn functions and submodular Boolean functions
- scientific article; zbMATH DE number 420868 (Why is no real title available?)
- scientific article; zbMATH DE number 3904328 (Why is no real title available?)
- scientific article; zbMATH DE number 1332320 (Why is no real title available?)
- scientific article; zbMATH DE number 1540669 (Why is no real title available?)
- scientific article; zbMATH DE number 7051222 (Why is no real title available?)
- scientific article; zbMATH DE number 7051294 (Why is no real title available?)
- scientific article; zbMATH DE number 893887 (Why is no real title available?)
- scientific article; zbMATH DE number 3422402 (Why is no real title available?)
- scientific article; zbMATH DE number 3052220 (Why is no real title available?)
- Improved bounds on the sample complexity of learning
- Job Matching, Coalition Formation, and Gross Substitutes
- Learnability and rationality of choice.
- Learning and Smoothed Analysis
- Learning intersections and thresholds of halfspaces
- Learning Pseudo-Boolean k-DNF and Submodular Functions
- Maximizing a monotone submodular function subject to a matroid constraint
- Maximizing Non-monotone Submodular Functions
- Maximizing nonmonotone submodular functions under matroid or knapsack constraints
- Maximizing submodular set functions subject to multiple linear constraints
- Neural Network Learning
- Nonmonotone submodular maximization via a structural continuous greedy algorithm (extended abstract)
- Oblivious routing in directed graphs with random demands
- On concentration of self-bounding functions
- On learning monotone DNF under product distributions
- On the structure of all minimum cuts in a network and applications
- Optimal approximation for the submodular welfare problem in the value oracle model
- Optimal bounds on approximation of submodular and XOS functions by juntas
- Optimal Bundle Pricing
- Optimal value of information in graphical models
- Probability and Computing
- Sketching valuation functions
- Submodular Approximation: Sampling-based Algorithms and Lower Bounds
- Submodular function maximization via the multilinear relaxation and contention resolution schemes
- Submodular function minimization
- Submodular Function Minimization under Covering Constraints
- Submodular functions and optimization.
- Submodular functions are noise stable
- Submodular maximization by simulated annealing
- Submodular maximization over multiple matroids via generalized exchange properties
- Symmetry and Approximability of Submodular Maximization Problems
- The probabilistic method. With an appendix on the life and work of Paul Erdős.
- Truthful randomized mechanisms for combinatorial auctions
- Unbalanced expanders and randomness extractors from Parvaresh-Vardy codes
- Walrasian equilibrium with gross substitutes
Cited in
(13)- Tight bounds on \(\ell_1\) approximation and learning of self-bounding functions
- Submodular functions: from discrete to continuous domains
- A note on the implications of approximate submodularity in discrete optimization
- Optimal bounds on approximation of submodular and XOS functions by juntas
- SFO: a toolbox for submodular function optimization
- Combinatorial problems with discounted price functions in multi-agent systems
- Approximate modularity revisited
- Graph cuts with interacting edge weights: examples, approximations, and algorithms
- Learning with submodular functions: a convex optimization perspective
- Learning submodular functions
- Learning Pseudo-Boolean k-DNF and Submodular Functions
- Submodular functions are noise stable
- Tractability of explaining classifier decisions
This page was built for publication: Submodular functions: learnability, structure, and optimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4564777)
