Optimization Online


Dynamic Data-Driven Estimation of Non-Parametric Choice Models

Nam Ho-Nguyen(hnh***at***andrew.cmu.edu)
Fatma Kilinc-Karzan(fkilinc***at***andrew.cmu.edu)

Abstract: We study non-parametric models to estimate consumer choice behavior from observational data. These models have recently been introduced to overcome issues of suboptimal fit inherent in the traditional parametric models. Due to their minimal assumptions on consumer behavior, non-parametric models are shown to have improved predictive performance and thus draw growing interest in practice and academia. However, the generic nature of these models presents new computational challenges: learning an appropriate non-parametric model requires solving an optimization problem with a factorial number of variables. This is intractable even for small-scale problems with only a few items to sell. In this paper, we present a generic yet simple framework based on convex conjugacy, saddle point duality and online convex optimization to efficiently learn a non-parametric choice model from consumer choice data. Our method enjoys provable convergence guarantees (in terms of the number of iterations required) and extends naturally to the dynamic case where new observations are added to the data set. Nevertheless, each iteration of our method, as well as existing approaches from the literature, require solving a combinatorial subproblem. In order to provide a completely efficient method, we examine this combinatorial subproblem in detail and identify conditions on the assortment structure under which it can be solved efficiently.

Keywords: non-parametric choice model, conjugacy, duality, online convex optimization

Category 1: Applications -- OR and Management Sciences (Marketing )

Category 2: Convex and Nonsmooth Optimization (Convex Optimization )


Download: [PDF]

Entry Submitted: 02/18/2017
Entry Accepted: 02/19/2017
Entry Last Modified: 02/18/2017

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society