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
- 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?)
- A Stab at Approximating Minimum Subadditive Join
- A Unified Continuous Greedy Algorithm for Submodular Maximization
- A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
- A theory of the learnable
- 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 Optimization. Polyhedra and efficiency. CD-ROM
- Combinatorial auctions with decreasing marginal utilities
- Combinatorial auctions. Foreword by Vernon L. Smith.
- 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
- Improved bounds on the sample complexity of learning
- Job Matching, Coalition Formation, and Gross Substitutes
- Learnability and rationality of choice.
- Learning Pseudo-Boolean k-DNF and Submodular Functions
- Learning and Smoothed Analysis
- Learning intersections and thresholds of halfspaces
- Maximizing Non-monotone Submodular Functions
- Maximizing a monotone submodular function subject to a matroid constraint
- 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 Bundle Pricing
- Optimal approximation for the submodular welfare problem in the value oracle model
- Optimal bounds on approximation of submodular and XOS functions by juntas
- Optimal value of information in graphical models
- Probability and Computing
- Sketching valuation functions
- Submodular Approximation: Sampling-based Algorithms and Lower Bounds
- Submodular Function Minimization under Covering Constraints
- Submodular function maximization via the multilinear relaxation and contention resolution schemes
- Submodular function minimization
- 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)- Approximate modularity revisited
- A note on the implications of approximate submodularity in discrete optimization
- SFO: a toolbox for submodular function optimization
- Combinatorial problems with discounted price functions in multi-agent systems
- Tractability of explaining classifier decisions
- Graph cuts with interacting edge weights: examples, approximations, and algorithms
- Learning submodular functions
- Learning with submodular functions: a convex optimization perspective
- Submodular functions: from discrete to continuous domains
- Tight bounds on \(\ell_1\) approximation and learning of self-bounding functions
- Optimal bounds on approximation of submodular and XOS functions by juntas
- Submodular functions are noise stable
- Learning Pseudo-Boolean k-DNF and Submodular Functions
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)
