AI Paper Atlas

Research map / Learning theory and algorithms / Sample complexity

The Adaptive Complexity of Maximizing a Gross Substitutes Valuation

Ron Kupfer, Sharon Qian, Eric Balkanski, Yaron Singer

NeurIPS 2020 · Learning theory and algorithms › Sample complexity · approach: Statistical-query lower bounds · 0 citations (OpenAlex)

Read the paperCheck your idea against 137,217 papers

AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Measured effects reported in the paper

What was changedWhereMeasuredEffect
Use GSAS (adaptive sequencing with low initial threshold) instead of Trimmed Greedy under the same round budgetGSAS · Synthetic OXS graphs G1-G4normalized valuationImproved
Use GSAS instead of Adaptive SamplingGSAS · Twitter graph (Figure 2)normalized valuationImproved
Learn the OXS valuation by sampling then run greedy (Learned Opt) instead of querying the true functionLearned Opt baseline · Synthetic OXS graphs G1-G4normalized valuationHurt
Increase cardinality k from small values to larger values (k above 80)GSAS · Twitter graphs G5-G8number of rounds relative to GreedyImproved
Compare GSAS with Greedy at small k (below 80)GSAS · Twitter graphs G5-G8normalized valuationNo clear effect
Lower the initial threshold to OPT/(eps k) instead of max f(a)GSAS · Theory (adaptivity)adaptive roundsImproved
Use Top-k instead of GSAS when valuation is purely additive or purely unit-demandTop-k baseline · UD-additivity spectrum (n=1024, k=32)normalized valuationNo clear effect
Use GSAS on valuations between unit-demand and additive instead of baselinesGSAS · UD-additivity spectrum, m from 1 to 1024normalized valuationImproved
Allow queries of non-feasible sets (stronger model) for non-adaptive algorithmsNon-adaptive algorithms (lower bound) · Theoryapproximation ratio: 1/2 + epsHurt

Closest papers by meaning

Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.

Open scime draft

Get the next scime Dispatch and a monthly field update

Free. We send a confirmation link first; every email has a one-click unsubscribe. Privacy