Data-Mining

New interior-point approach for one- and two-class linear support vector machines using multiple variable splitting

  • Jordi Castro
    • Categories Data-Mining, Linear, Cone and Semidefinite Programming Tags , , , ,

    Multiple variable splitting is a general technique for decomposing problems by using copies of variables and additional linking constraints that equate their values. The resulting large optimization problem can be solved with a specialized interior-point method that exploits the problem structure and computes the Newton direction with a combination of direct and iterative solvers (i.e., … Read more

    Analysis non-sparse recovery for non-convex relaxed $\ell_q$ minimization

  • Jianwen Huang
  • Feng Zhang
  • Xinling Liu
  • Jianjun Wang
    • Categories Data-Mining, Nonsmooth Optimization, Unconstrained Optimization Tags , , , ,

    This paper studies construction of signals, which are sparse or nearly sparse with respect to a tight frame $D$ from underdetermined linear systems. In the paper, we propose a non-convex relaxed $\ell_q(0 Article Download View Analysis non-sparse recovery for non-convex relaxed $ell_q$ minimization

    Mixed-Integer Optimization with Constraint Learning

  • Donato Maragno
  • Holly Wiberg
  • Dimitris Bertsimas
  • Ş. İlker Birbil
  • Dick den Hertog
  • Adejuyigbe Fajemisin
    • Categories (Mixed) Integer Linear Programming, Applications - OR and Management Sciences, Data-Mining Tags , , ,

    We establish a broad methodological foundation for mixed-integer optimization with learned constraints. We propose an end-to-end pipeline for data-driven decision making in which constraints and objectives are directly learned from data using machine learning, and the trained models are embedded in an optimization formulation. We exploit the mixed-integer optimization-representability of many machine learning methods, including … Read more

    Inexact bilevel stochastic gradient methods for constrained and unconstrained lower-level problems

  • Tommaso Giovannelli
  • Griffin D. Kent
  • Luis Nunes Vicente
    • Categories Data-Mining, Nonlinear Optimization, Stochastic Programming Tags , , ,

    Two-level stochastic optimization formulations have become instrumental in a number ofmachine learning contexts such as continual learning, neural architecture search, adversariallearning, and hyperparameter tuning. Practical stochastic bilevel optimization problemsbecome challenging in optimization or learning scenarios where the number of variables ishigh or there are constraints. In this paper, we introduce a bilevel stochastic gradient method … Read more

    Sparse Plus Low Rank Matrix Decomposition: A Discrete Optimization Approach

  • Dimitris Bertsimas
  • Ryan Cory-Wright
  • Nicholas A. G. Johnson
    • Categories Applications - OR and Management Sciences, Data-Mining, Statistics Tags , , , ,

    We study the Sparse Plus Low-Rank decomposition problem (SLR), which is the problem of decomposing a corrupted data matrix into a sparse matrix of perturbations plus a low-rank matrix containing the ground truth. SLR is a fundamental problem in Operations Research and Machine Learning which arises in various applications, including data compression, latent semantic indexing, … Read more

    Solving a Class of Cut-Generating Linear Programs via Machine Learning

  • Danial Davarnia
  • Atefeh Rajabalizadeh
    • Categories Branch and Cut Algorithms, Data-Mining, Linear Programming Tags , , , ,

    Cut-generating linear programs (CGLPs) play a key role as a separation oracle to produce valid inequalities for the feasible region of mixed-integer programs. When incorporated inside branch-and-bound, the cutting planes obtained from CGLPs help to tighten relaxations and improve dual bounds. However, running the CGLPs at the nodes of the branch-and-bound tree is computationally cumbersome … Read more

    A stochastic alternating balance k-means algorithm for fair clustering

  • Suyun Liu
  • Luis Nunes Vicente
    • Categories Convex and Nonsmooth Optimization, Data-Mining, Nonlinear Optimization Tags , , , , ,

    In the application of data clustering to human-centric decision-making systems, such as loan applications and advertisement recommendations, the clustering outcome might discriminate against people across different demographic groups, leading to unfairness. A natural conflict occurs between the cost of clustering (in terms of distance to cluster centers) and the balance representation of all demographic groups … Read more

    Beyond Symmetry: Best Submatrix Selection for the Sparse Truncated SVD

  • Yongchun Li
  • Weijun Xie
    • Categories Combinatorial Optimization, Data-Mining, Integer Programming Tags , , , ,

    Truncated singular value decomposition (SVD), also known as the best low-rank matrix approximation, has been successfully applied to many domains such as biology, healthcare, and others, where high-dimensional datasets are prevalent. To enhance the interpretability of the truncated SVD, sparse SVD (SSVD) is introduced to select a few rows and columns of the original matrix … Read more

    Unbiased Subdata Selection for Fair Classification: A Unified Framework and Scalable Algorithms

  • Ye Qing
  • Weijun Xie
    • Categories (Mixed) Integer Nonlinear Programming, Data-Mining

    As an important problem in modern data analytics, classification has witnessed varieties of applications from different domains. Different from conventional classification approaches, fair classification concerns the issues of unintentional biases against the sensitive features (e.g., gender, race). Due to high nonconvexity of fairness measures, existing methods are often unable to model exact fairness, which can … Read more

    A dynamic programming approach to segmented isotonic regression

  • Victor Bucarey
  • Martine Labbé
  • Juan M. Morales
  • Salvador Pineda
    • Categories Data-Mining, Dynamic Programming, Energy Tags , , , , ,

    This paper proposes a polynomial-time algorithm to construct the monotone stepwise curve that minimizes the sum of squared errors with respect to a given cloud of data points. The fitted curve is also constrained on the maximum number of steps it can be composed of and on the minimum step length. Our algorithm relies on … Read more