Efficient Path Following Algorithms and Its Applications to Case Influence Assessment

• Activity Number: 319 - SLDS CSpeed 6
• Type: Contributed
• Date/Time: Wednesday, August 11, 2021 : 3:30 PM to 5:20 PM
• Sponsor: Section on Statistical Learning and Data Science
• Author(s): Qiuyu Gu* and Renxiong Liu and Yunzhang Zhu
• Companies: The Ohio State University and Ohio State University and Ohio State University
• Keywords: path following algorithm; case influence; case weight; optimization

Abstract

We present a path-following algorithm for a parametric optimization problem, which consists of a family of similar optimization problems indexed by a single parameter. The algorithm is motivated by case influence assessment using case influence graph, where case weight is introduced for each case [Cook, 1986], and computing a case influence graph is equivalent to solving a parametric optimization problem indexed by case weight. Our algorithm is based on the finding that the closeness between the approximated solution path and the true solution path depends on two quantities: how finely the grid points are and how accurate the optimization algorithm runs at each grid point. We call them interpolation error and optimization error respectively. Our algorithm is designed such that the two quantities are well balanced, without causing redundant computation. We demonstrate through simulation that our algorithm performs better than some standard numerical ODE solvers in terms of accuracy and runtime. We also show that our algorithm can be used to efficiently assess the case influence and identify the mislabeled images in the CIFAR-10 dataset.