The Limitations of Optimization from Samples

DOI10.1145/3511018OpenAlexW2264490347MaRDI QIDQ5889795

Eric Balkanski, Aviad Rubinstein, Yaron Singer

Publication date: 27 April 2023

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/3511018

zbMATH Keywords

PAC-learningsubmodular maximizationmaximum coverageoptimization from samples

Mathematics Subject Classification ID

Computer science (68-XX)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Random matrices and codes for the erasure channel
• Statistical active learning algorithms for noise tolerance and differential privacy
• Combinatorial auctions with decreasing marginal utilities
• Limitations of randomized mechanisms for combinatorial auctions
• Optimal Bounds on Approximation of Submodular and XOS Functions by Juntas
• Symmetry and Approximability of Submodular Maximization Problems
• Testing Coverage Functions
• Privately Releasing Conjunctions and the Statistical Query Barrier
• Sampling and Representation Complexity of Revenue Maximization
• Online Submodular Welfare Maximization
• A threshold of ln n for approximating set cover
• Learning juntas
• An improved approximation algorithm for combinatorial auctions with submodular bidders
• A theory of the learnable
• The Complexity of Markov Decision Processes
• The limitations of optimization from samples
• The adaptive complexity of maximizing a submodular function
• Submodular Maximization with Nearly Optimal Approximation, Adaptivity and Query Complexity
• Submodular Maximization with Nearly-optimal Approximation and Adaptivity in Nearly-linear Time
• An Exponential Speedup in Parallel Running Time for Submodular Maximization without Loss in Approximation
• Submodular Function Maximization in Parallel via the Multilinear Relaxation
• The sample complexity of revenue maximization
• Maximizing Social Influence in Nearly Optimal Time
• From convex optimization to randomized mechanisms
• Learning submodular functions
• Local Distribution and the Symmetry Gap: Approximability of Multiway Partitioning Problems

This page was built for publication: The Limitations of Optimization from Samples