ECE PhD Dissertation Defense: Berkan Kadioglu

PhD Dissertation Defense: An Analysis of Algorithms with Discrete Choice Models

Berkan Kadioglu

Location: Zoom Link

Abstract: In the first half of our work, we consider a rank regression setting, in which a dataset of $N$ samples with features in $\mathbb{R}^d$ is ranked by an oracle via $M$ pairwise comparisons.
Specifically, there exists a latent total ordering of the samples; when presented with a pair of samples, a noisy oracle identifies the one ranked higher w.r.t. the underlying total ordering.
A learner observes a dataset of such comparisons, and wishes to regress sample ranks from their features.
We show that to learn the model parameters with $\epsilon > 0$ accuracy, it suffices to conduct $M \in \Omega(dN\log^3 N/\epsilon^2)$ comparisons uniformly at random when $N$ is $\Omega(d/\epsilon^2)$.
Compared to learning from class labels, learning from comparison labels has two advantages: First, comparison labels reveal both inter and intra-class information, where class labels only contain the former.
Second, comparison labels also exhibit lower variability across different labelers.
This has been observed experimentally in multiple domains, including medicine \citep{campbell2016plus,kalpathy2016plus, stewart2005absolute} and recommendation systems \citep{schultz2004learning,zheng2009mining,brun2010towards, koren2011ordrec}, and is due to the fact that humans often find it easier to make relative, rather than absolute, judgements.
Many works focusing on empirically learning comparison labels show excellent performance in practice \citep{tian2019severity,yildiz2019classification}.
Our work provides a theoretical foundation for analyzing and understanding this empirical performance.
Moreover, we extend the problem we initially study to a harder setting.
We do this by moving from pairwise comparisons to multi-way comparisons.
Furthermore, we study an online variant of the previous problem where the goal is to maintain high user engagement throughout the learning period.
This of course, indirectly leads to the goal of learning parameters of the discrete choice model as accurately as possible, fast.
This new problem is directly related to a setting in which a retailer recommends products to customers.
A common problem in many recommendation tasks is to simultaneously learn the utilities of items to be recommended and maintain high user engagement.
We are generally constrained by a limit on the total number of items to be recommended at a time for an unknown time horizon.
Recently, bandit algorithms have been proposed for this setting where the multinomial logit model is assumed.
Bounds on error metrics are provided for upper confidence and Thompson sampling based algorithms.
In our paper, we propose a variational inference based Thompson sampling algorithm and identify the required properties to achieve $\tilde O(D^{3/2}\sqrt T)$ worst-case regret.
Through extensive experiments we show that our method performs much better than the recently proposed \emph{TSMNL} algorithm in many error metrics.
We further accelerate our algorithm to be used in practical settings.