Optimization in Data Science

Recursive Bound-Constrained AdaGrad with Applications to Multilevel and Domain Decomposition Minimization

  • Serge Gratton
  • Alena Kopanicakova
  • Philippe L. Toint
    • Categories Bound-constrained Optimization, Data Science Algorithms, Nonlinear Optimization Tags , , , , , ,

    Two OFFO (Objective-Function Free Optimization) noise tolerant algorithms are presented that handle bound constraints, inexact gradients and use second-order information when available. The first is a multi-level method exploiting a hierarchical description of the problem and the second is a domain-decomposition method covering the standard addditive Schwarz decompositions. Both are generalizations of the first-order AdaGrad … Read more

    A Randomized Algorithm for Sparse PCA based on the Basic SDP Relaxation

  • Alberto Del Pia
  • Dekun Zhou
    • Categories (Mixed) Integer Linear Programming, Data Science Algorithms, Semi-definite Programming

    Sparse Principal Component Analysis (SPCA) is a fundamental technique for dimensionality reduction, and is NP-hard. In this paper, we introduce a randomized approximation algorithm for SPCA, which is based on the basic SDP relaxation. Our algorithm has an approximation ratio of at most the sparsity constant with high probability, if called enough times. Under a … Read more

    Constrained Enumeration of Lucky Tickets: Prime Digits, Uniqueness, and Greedy Heuristics

  • Bismark Singh
    • Categories Basic Sciences Applications, Optimization in Data Science

    We revisit the classical Lucky Ticket (LT) enumeration problem, in which an even-digit number is called lucky if the sum of the digits of its first half equals to that of its second half. We introduce two new subclasses — SuperLucky Tickets (SLTs), where all digits are distinct, and LuckyPrime Tickets (LPTs), where all digits … Read more

    Complexity of normalized stochastic first-order methods with momentum under heavy-tailed noise

  • Chuan He
  • Zhaosong Lu
  • Defeng Sun
  • Zhanwang Deng
    • Categories Nonlinear Optimization, Optimization in Data Science, Unconstrained Optimization Tags , , ,

    In this paper, we propose practical normalized stochastic first-order methods with Polyak momentum, multi-extrapolated momentum, and recursive momentum for solving unconstrained optimization problems. These methods employ dynamically updated algorithmic parameters and do not require explicit knowledge of problem-dependent quantities such as the Lipschitz constant or noise bound. We establish first-order oracle complexity results for finding … Read more

    A Variational Analysis Approach for Bilevel Hyperparameter Optimization with Sparse Regularization

  • David Villacís
  • Pedro Pérez-Aros
  • Emilio Vilches
    • Categories Bilevel Optimization, Nonsmooth Optimization, Optimization in Data Science Tags , , ,

    We study a bilevel optimization framework for hyperparameter learning in variational models, with a focus on sparse regression and classification tasks. In particular, we consider a weighted elastic-net regularizer, where feature-wise regularization parameters are learned through a bilevel formulation. A key novelty of our approach is the use of a Forward-Backward (FB) reformulation of the … Read more

    Toward Decision-Oriented Prognostics: An Integrated Estimate-Optimize Framework for Predictive Maintenance

  • Zhuojun Xie
  • Adam Abdin
  • Yiping Fang
    • Categories Optimization in Data Science, Stochastic Programming Tags , , , ,

    Recent research increasingly integrates machine learning (ML) into predictive maintenance (PdM) to reduce operational and maintenance costs in data-rich operational settings. However, uncertainty due to model misspecification continues to limit widespread industrial adoption. This paper investigates a PdM framework in which sensor-driven prognostics inform decision-making under economic trade-offs within a finite decision space. We investigate … Read more

    Two-way Cutting-plane Algorithm for Best Subset Selection Considering Multicollinearity

  • Yuichi Takano
    • Categories Global Optimization, Integer Programming, Optimization in Data Science Tags , , , ,

    When linear dependence exists between some explanatory variables in a regression model, the estimates of regression coefficients become unstable, thereby making the interpretation of the estimation results unreliable. To eliminate such multicollinearity, we propose a high-performance method for selecting the best subset of explanatory variables for linear and logistic regression models. Specifically, we first derive … Read more

    Retrospective Approximation Sequential Quadratic Programming for Stochastic Optimization with General Deterministic Nonlinear Constraints

  • Shagun Gupta
  • Raghu Bollapragada
  • Albert S. Berahas
    • Categories Constrained Nonlinear Optimization, Nonlinear Optimization, Optimization in Data Science Tags , , , ,

    In this paper, we propose a framework based on the Retrospective Approximation (RA) paradigm to solve optimization problems with a stochastic objective function and general nonlinear deterministic constraints. This framework sequentially constructs increasingly accurate approximations of the true problems which are solved to a specified accuracy via a deterministic solver, thereby decoupling the uncertainty from … Read more

    Responsible Machine Learning via Mixed-Integer Optimization

  • Nathan Justin
  • Qingshi Sun
  • Andrés Gómez
  • Phebe Vayanos
    • Categories Applications - OR and Management Sciences, Integer Programming, Optimization in Data Science Tags , , , , , ,

    In the last few decades, Machine Learning (ML) has achieved significant success across domains ranging from healthcare, sustainability, and the social sciences, to criminal justice and finance. But its deployment in increasingly sophisticated, critical, and sensitive areas affecting individuals, the groups they belong to, and society as a whole raises critical concerns around fairness, transparency … Read more

    Fast Stochastic Second-Order Adagrad for Nonconvex Bound-Constrained Optimization

  • Stefania Bellavia
  • Serge Gratton
  • Benedetta Morini
  • Philippe L. Toint
    • Categories Bound-constrained Optimization, Data Science Algorithms, Nonlinear Optimization Tags , , , , , ,

    ADAGB2, a generalization of the Adagrad algorithm for stochastic optimization is introduced, which is also applicable to bound-constrained problems and capable of using second-order information when available. It is shown that, given  delta in (0,1) and epsilon in (0,1], the ADAGB2 algorithm needs at most O(epsilon^{-2}) iterations to ensure an epsilon-approximate first-order critical point of … Read more