Scalable Kernel Logistic Regression with Nyström Approximation:
  Theoretical Analysis and Application to Discrete Choice Modelling
José Ángel Martín-Baos Ricardo García-Ródenas Luis Rodriguez-Benitez Michel Bierlaire
The application of kernel-based Machine Learning (ML) techniques to discrete
choice modelling using large datasets often faces challenges due to memory
requirements and the considerable number of parameters involved in these
models. This complexity hampers the efficient training of large-scale models.
This paper addresses these problems of scalability by introducing the Nystr\"om
approximation for Kernel Logistic Regression (KLR) on large datasets. The study
begins by presenting a theoretical analysis in which: i) the set of KLR
solutions is characterised, ii) an upper bound to the solution of KLR with
Nystr\"om approximation is provided, and finally iii) a specialisation of the
optimisation algorithms to Nystr\"om KLR is described. After this, the
Nystr\"om KLR is computationally validated. Four landmark selection methods are
tested, including basic uniform sampling, a k-means sampling strategy, and two
non-uniform methods grounded in leverage scores. The performance of these
strategies is evaluated using large-scale transport mode choice datasets and is
compared with traditional methods such as Multinomial Logit (MNL) and
contemporary ML techniques. The study also assesses the efficiency of various
optimisation techniques for the proposed Nystr\"om KLR model. The performance
of gradient descent, Momentum, Adam, and L-BFGS-B optimisation methods is
examined on these datasets. Among these strategies, the k-means Nystr\"om KLR
approach emerges as a successful solution for applying KLR to large datasets,
particularly when combined with the L-BFGS-B and Adam optimisation methods. The
results highlight the ability of this strategy to handle datasets exceeding
200,000 observations while maintaining robust performance.