Optimization in Data Science

Learning-to-Optimize with PAC-Bayesian Guarantees: Theoretical Considerations and Practical Implementation

  • Michael Sucker
  • Jalal Fadili
  • Peter Ochs
    • Categories Optimization in Data Science, Other Topics Tags ,

    We use the PAC-Bayesian theory for the setting of learning-to-optimize. To the best of our knowledge, we present the first framework to learn optimization algorithms with provable generalization guarantees (PAC-Bayesian bounds) and explicit trade-off between convergence guarantees and convergence speed, which contrasts with the typical worst-case analysis. Our learned optimization algorithms provably outperform related ones … Read more

    Stochastic Aspects of Dynamical Low-Rank Approximation in the Context of Machine Learning

  • Arsen Hnatiuk
  • Lisa Kusch
  • Jonas Kusch
  • Nicolas R. Gauger
  • Andrea Walther
    • Categories Data Science Theory, Nonlinear Optimization, Optimization in Data Science Tags , , , ,

    The central challenges of today’s neural network architectures are the prohibitive memory footprint and training costs associated with determining optimal weights and biases. A large portion of research in machine learning is therefore dedicated to constructing memory-efficient training methods. One promising approach is dynamical low-rank training (DLRT), which represents and trains parameters as a low-rank … Read more

    Data Collaboration Analysis with Orthonormal Basis Selection and Alignment

  • Keiyu Nosaka
  • Yuichi Takano
  • Akiko Yoshise
    • Categories Linear, Cone and Semidefinite Programming, Optimization in Data Science, Other Topics

    Data Collaboration (DC) enables multiple parties to jointly train a model without exposing their private datasets. Each party privately transforms its data using a secret linear basis and shares only the resulting intermediate representations. Existing theory asserts that any target basis spanning the same subspace as the secret bases should suffice; however, empirical evidence reveals … Read more

    Robust support vector machines via conic optimization

  • Shaoning Han
  • Andrés Gómez
    • Categories (Mixed) Integer Nonlinear Programming, Cone Programming, Optimization in Data Science Tags , , , ,

    We consider the problem of learning support vector machines robust to uncertainty. It has been established in the literature that typical loss functions, including the hinge loss, are sensible to data perturbations and outliers, thus performing poorly in the setting considered. In contrast, using the 0-1 loss or a suitable non-convex approximation results in robust … Read more

    Data-Driven Reliable Facility Location Design

  • Hao Shen
  • Mengying Xue
  • Z.J. Max Shen
    • Categories Data Science Applications, Network Optimization, Supply Chain Management Tags , , ,

    We study the reliable (uncapacitated) facility location (RFL) problem in a data-driven environment where historical observations of random demands and disruptions are available. Owing to the combinatorial optimization nature of the RFL problem and the mixed-binary randomness of parameters therein, the state-of-the-art RFL models applied to the data-driven setting either suggest overly conservative solutions, or … Read more

    Mixed-Integer Linear Optimization for Semi-Supervised Optimal Classification Trees

  • Jan Pablo Burgard
  • Maria Eduarda Pinheiro
  • Martin Schmidt
    • Categories (Mixed) Integer Linear Programming, Optimization in Data Science Tags , ,

    Decision trees are one of the most famous methods for solving classification problems, mainly because of their good interpretability properties. Moreover, due to advances in recent years in mixed-integer optimization, several models have been proposed to formulate the problem of computing optimal classification trees. The goal is, given a set of labeled points, to split … Read more

    Block Majorization Minimization with Extrapolation and Application to $\beta$-NMF

  • Le Thi Khanh Hien
  • Valentin Leplat
  • Nicolas Gillis
    • Categories Constrained Nonlinear Optimization, Convex and Nonsmooth Optimization, Optimization in Data Science Tags , , , ,

    We propose a Block Majorization Minimization method with Extrapolation (BMMe) for solving a class of multi-convex optimization problems. The extrapolation parameters of BMMe are updated using a novel adaptive update rule. By showing that block majorization minimization can be reformulated as a block mirror descent method, with the Bregman divergence adaptively updated at each iteration, … Read more

    Optimal counterfactual explanations for k-Nearest Neighbors using Mathematical Optimization and Constraint Programming

  • Thibaut Vidal
  • Ricardo Fukasawa
  • Louis-Martin Rousseau
  • Claudio Contardo
    • Categories Applications - Science and Engineering, Data Science Algorithms Tags , , , ,

    Within the topic of explainable AI, counterfactual explanations to classifiers have received significant recent attention. We study counterfactual explanations that try to explain why a data point received an undesirable classification by providing the closest data point that would have received a desirable one. Within the context of one the simplest and most popular classification … Read more

    It’s All in the Mix: Wasserstein Classification and Regression with Mixed Features

  • Mohammad Reza Belbasi
  • Aras Selvi
  • Wolfram Wiesemann
    • Categories Optimization in Data Science, Robust Optimization Tags , , ,

    Problem definition: A key challenge in supervised learning is data scarcity, which can cause prediction models to overfit to the training data and perform poorly out of sample. A contemporary approach to combat overfitting is offered by distributionally robust problem formulations that consider all data-generating distributions close to the empirical distribution derived from historical samples, … Read more

    Accelerated Gradient Dynamics on Riemannian Manifolds: Faster Rate and Trajectory Convergence

  • Tejas Natu
  • Camille Castera
  • Jalal Fadili
  • Peter Ochs
    • Categories Convex Optimization, Optimization in Data Science Tags , , ,

    In order to minimize a differentiable geodesically convex function, we study a second-order dynamical system on Riemannian manifolds with an asymptotically vanishing damping term of the form \(\alpha/t\). For positive values of \(\alpha\), convergence rates for the objective values and convergence of trajectory is derived. We emphasize the crucial role of the curvature of the … Read more