  We study non-parametric estimation of choice models, which were introduced to
alleviate unreasonable assumptions in traditional parametric models, and are
prevalent in several application areas. Existing literature focuses only on the
static observational setting where all of the observations are given upfront,
they are not equipped with explicit convergence rate guarantees, and
consequently they cannot provide an a priori analysis for the model accuracy vs
sparsity trade-off on the actual estimated model returned by their algorithms.
As opposed to this, we focus on estimating a non-parametric choice model from
observational data in a \emph{dynamic} setting, where observations are obtained
over time. We show that choice model estimation can be cast as a convex-concave
saddle-point (SP) joint estimation and optimization (JEO) problem, and we
provide a primal-dual framework for deriving algorithms to solve this based on
online convex optimization. By tailoring our framework carefully to the choice
model estimation problem, we obtain tractable algorithms with provable
convergence guarantees and explicit bounds on the sparsity of the estimated
model. Our numerical experiments confirm the effectiveness of the algorithms
derived from our framework.
