The Limitations of Optimization from Samples
From MaRDI portal
Publication:5889795
DOI10.1145/3511018OpenAlexW2264490347MaRDI QIDQ5889795FDOQ5889795
Authors: Eric Balkanski, Aviad Rubinstein, Y. 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
Recommendations
Cites Work
- A threshold of ln n for approximating set cover
- Title not available (Why is that?)
- The Complexity of Markov Decision Processes
- Learning juntas
- Title not available (Why is that?)
- Combinatorial auctions with decreasing marginal utilities
- A theory of the learnable
- Near-optimal sensor placements in Gaussian processes: theory, efficient algorithms and empirical studies
- An improved approximation algorithm for combinatorial auctions with submodular bidders
- Statistical active learning algorithms for noise tolerance and differential privacy
- Testing coverage functions
- Title not available (Why is that?)
- Learning submodular functions
- Estimating diffusion networks: recovery conditions, sample complexity and soft-thresholding algorithm
- Symmetry and approximability of submodular maximization problems
- Local distribution and the symmetry gap: approximability of multiway partitioning problems
- Limitations of randomized mechanisms for combinatorial auctions
- From convex optimization to randomized mechanisms
- Random matrices and codes for the erasure channel
- Online submodular welfare maximization: greedy beats 1/2 in random order
- Maximizing social influence in nearly optimal time
- The sample complexity of revenue maximization
- Sampling and Representation Complexity of Revenue Maximization
- Sketching valuation functions
- The limitations of optimization from samples
- An Exponential Speedup in Parallel Running Time for Submodular Maximization without Loss in Approximation
- The adaptive complexity of maximizing a submodular function
- Submodular Maximization with Nearly-optimal Approximation and Adaptivity in Nearly-linear Time
- Submodular function maximization in parallel via the multilinear relaxation
- Submodular maximization with nearly optimal approximation, adaptivity and query complexity
- Optimal bounds on approximation of submodular and XOS functions by juntas
- Agnostic learning of disjunctions on symmetric distributions
- Tight bounds on \(\ell_1\) approximation and learning of self-bounding functions
This page was built for publication: The Limitations of Optimization from Samples
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5889795)
