Optimization in Data Science

An extrapolated and provably convergent algorithm for nonlinear matrix decomposition with the ReLU function

  • Nicolas Gillis
  • Margherita Porcelli
  • Giovanni Seraghiti
    • Categories Data Science Algorithms, Optimization in Data Science, Other Topics Tags , ,

    Nonlinear matrix decomposition (NMD) with the ReLU function, denoted ReLU-NMD, is the following problem: given a sparse, nonnegative matrix \(X\) and a factorization rank \(r\), identify a rank-\(r\) matrix \(\Theta\) such that \(X\approx \max(0,\Theta)\). This decomposition finds application in data compression, matrix completion with entries missing not at random, and manifold learning. The standard ReLU-NMD … Read more

    A Rank-One-Update Method for the Training of Support Vector Machines

  • Florian Jarre
    • Categories Bound-constrained Optimization, Convex Optimization, Data Science Algorithms Tags , ,

    This paper considers convex quadratic programs associated with the training of support vector machines (SVM). Exploiting the special structure of the SVM problem a new type of active set method with long cycles and stable rank-one-updates is proposed and tested (CMU: cycling method with updates). The structure of the problem allows for a repeated simple … Read more

    Spherical Support Vector Machine for Interval-Valued Data

  • Rui Malha
  • Paula Alexandra Amaral
    • Categories Data Science Algorithms, Nonlinear Optimization, Quadratic Programming Tags , ,

    In this work we propose a generalization of the Spherical Support Vector Machine method, in which the separator is a sphere, applied to Interval-valued data. This type of data belongs to a more general class, known as Symbolic Data, for which features are described by sets, intervals or histograms instead of classic arrays. This paradigm … Read more

    prunAdag: an adaptive pruning-aware gradient method

  • Margherita Porcelli
  • Giovanni Seraghiti
  • Philippe L. Toint
    • Categories Data Science Algorithms, Nonlinear Optimization Tags , , ,

    A pruning-aware adaptive gradient method is proposed which classifies the variables in two sets before updating them using different strategies. This technique extends the “relevant/irrelevant” approach of Ding (2019) and Zimmer et al. (2022) and allows a posteriori sparsification of the solution of model parameter fitting problems. The new method is proved to be convergent … Read more

    Multiple Kernel Learning-Aided Column-and-Constraint Generation Method

  • Biao Han
    • Categories Applications - OR and Management Sciences, Optimization in Data Science, Robust Optimization Tags , , , ,

    Two-stage robust optimization (two-stage RO), due to its ability to balance robustness and flexibility, has been widely used in various fields for decision-making under uncertainty. This paper proposes a multiple kernel learning (MKL)-aided column-and-constraint generation (CCG) method to address this issue in the context of data-driven decision optimization, and releases a corresponding registered Julia package, … Read more

    Computing Counterfactual Explanations for Linear Optimization: A New Class of Bilevel Models and a Tailored Penalty Alternating Direction Method

  • Henri Lefebvre
  • Martin Schmidt
    • Categories Energy, Nonlinear Optimization, Optimization in Data Science Tags , , , ,

    Explainable artificial intelligence is one of the most important trends in modern machine-learning research. The idea is to explain the outcome of a model by presenting a certain change in the input of the model so that the outcome changes significantly. In this paper, we study this question for linear optimization problems as an automated … Read more

    Stochastic first-order methods with multi-extrapolated momentum for highly smooth unconstrained optimization

  • Chuan He
    • Categories Optimization in Data Science, Unconstrained Optimization Tags , , , , ,

    In this paper we consider an unconstrained stochastic optimization problem where the objective function exhibits a high order of smoothness. In particular, we propose a stochastic first-order method (SFOM) with multi-extrapolated momentum, in which multiple extrapolations are performed in each iteration, followed by a momentum step based on these extrapolations. We show that our proposed … Read more

    A Generalized Voting Game for Categorical Network Choices

  • Lin Yueh
  • Stefano Nasini
  • Martine Labbé
    • Categories Combinatorial Optimization, Data Science Algorithms, Game Theory Tags , , ,

    This paper presents a game-theoretical framework for data classification and network discovery, focusing on pairwise influences in multivariate choices. The framework consists of two complementary games in which individuals, connected through a signed weighted graph, exhibit network similarity. A voting rule captures the influence of an individual’s neighbors, categorized as attractive (friend-like) or repulsive (enemy-like), … Read more

    Enhancing Top Efficiency by Minimizing Second-Best Scores: A Novel Perspective on Super Efficiency Models in DEA

  • Tomonari Kitahara
  • Takashi Tsuchiya
    • Categories Applications - OR and Management Sciences, Linear, Cone and Semidefinite Programming, Optimization in Data Science Tags , ,

    In this paper, we reveal a new characterization of the super-efficiency model for Data Envelopment Analysis (DEA). In DEA, the efficiency of each decision making unit (DMU) is measured by the ratio the weighted sum of outputs divided by the weighted sum of inputs.In order to measure efficiency of a DMU, ${\rm DMU}_j$, say, in CCR … Read more