Learning Nonparametric Choice Models with Discrete Fourier Analysis

Nonparametric choice models offer broad applicability and robustness. However, the exponentially large parameter space leads practitioners to use heuristics for estimation. We introduce an alternative approach to modeling and estimating nonparametric choice models using discrete Fourier analysis. We demonstrate that any choice function can be approximated with a small number of Fourier parameters. Our sample-efficient, active-learning algorithms, without requiring an explicit model description, need at most $\mathit{\text{poly}}(\log n,1/\epsilon )$ data queries to estimate any choice function up to $\epsilon$ accuracy. Computational studies show significant error reduction with Fourier methods compared with common heuristics for nonparametric choice estimation in both simulated and real data.

Funding: Haoyu Song received financial support from the National Science Foundation [Grant CCF-2128702].