Statistics

Cutting-plane algorithm for sparse estimation of the Cox proportional-hazards model

  • Hiroki Saishu
  • Kota Kudo
  • Yuichi Takano
    • Categories (Mixed) Integer Nonlinear Programming, Branch and Cut Algorithms, Statistics Tags , , , , ,

    Survival analysis is a family of statistical methods for analyzing event occurrence times. In this paper, we address the mixed-integer optimization approach to sparse estimation of the Cox proportional-hazards model for survival analysis. Specifically, we propose a high-performance cutting-plane algorithm based on reformulation of bilevel optimization for sparse estimation. This algorithm solves the upper-level problem … Read more

    Blessing of Nonconvexity in Deep Linear Models: Depth Flattens the Optimization Landscape Around the True Solution

  • Jianhao Ma
  • Salar Fattahi
    • Categories Nonlinear Optimization, Statistics Tags , ,

    This work characterizes the effect of depth on the optimization landscape of linear regression, showing that, despite their nonconvexity, deeper models have more desirable optimization landscape. We consider a robust and over-parameterized setting, where a subset of measurements are grossly corrupted with noise and the true linear model is captured via an $N$-layer linear neural … Read more

    Metrizing Fairness

  • Yves Rychener
  • Bahar Tașkesen
  • Daniel Kuhn
    • Categories Statistics, Stochastic Programming, Unconstrained Optimization Tags , , , , ,

    We study supervised learning problems for predicting properties of individuals who belong to one of two demographic groups, and we seek predictors that are fair according to statistical parity. This means that the distributions of the predictions within the two groups should be close with respect to the Kolmogorov distance, and fairness is achieved by … Read more

    Riemannian Stochastic Proximal Gradient Methods for Nonsmooth Optimization over the Stiefel Manifold

  • Bokun Wang
  • Shiqian Ma
  • Lingzhou Xue
    • Categories Nonlinear Optimization, Statistics

    Riemannian optimization has drawn a lot of attention due to its wide applications in practice. Riemannian stochastic first-order algorithms have been studied in the literature to solve large-scale machine learning problems over Riemannian manifolds. However, most of the existing Riemannian stochastic algorithms require the objective function to be differentiable, and they do not apply to … Read more

    Global Convergence of Sub-gradient Method for Robust Matrix Recovery: Small Initialization, Noisy Measurements, and Over-parameterization

  • Jianhao Ma
  • Salar Fattahi
    • Categories Statistics, Unconstrained Optimization Tags ,

    In this work, we study the performance of sub-gradient method (SubGM) on a natural nonconvex and nonsmooth formulation of low-rank matrix recovery with $\ell_1$-loss, where the goal is to recover a low-rank matrix from a limited number of measurements, a subset of which may be grossly corrupted with noise. We study a scenario where the … Read more

    A Graph-based Decomposition Method for Convex Quadratic Optimization with Indicators

  • Peijing Liu
  • Salar Fattahi
  • Andrés Gómez
  • Simge Küçükyavuz
    • Categories (Mixed) Integer Nonlinear Programming, Statistics Tags , , , , , ,

    In this paper, we consider convex quadratic optimization problems with indicator variables when the matrix Q defining the quadratic term in the objective is sparse. We use a graphical representation of the support of Q, and show that if this graph is a path, then we can solve the associated problem in polynomial time. This … Read more

    Statistical Inference of Contextual Stochastic Optimization with Endogenous Uncertainty

  • Junyu Cao
  • Rui Gao
    • Categories Robust Optimization, Statistics, Stochastic Programming Tags

    This paper considers contextual stochastic optimization with endogenous uncertainty, where random outcomes depend on both contextual information and decisions. We analyze the statistical properties of solutions from two prominent approaches: predict-then-optimize (PTO), which first predicts a model between outcomes, contexts, and decisions, and then optimizes the downstream objective; and estimate- then-optimize (ETO), which directly estimates … 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

    Comparing Solution Paths of Sparse Quadratic Minimization with a Stieltjes Matrix

  • Ziyu He
  • Shaoning Han
  • Andrés Gómez
  • Ying Cui
  • Jong-Shi Pang
    • Categories Nonsmooth Optimization, Quadratic Programming, Statistics Tags , , ,

    This paper studies several solution paths of sparse quadratic minimization problems as a function of the weighing parameter of the bi-objective of estimation loss versus solution sparsity. Three such paths are considered: the “L0-path” where the discontinuous L0-function provides the exact sparsity count; the “L1-path” where the L1-function provides a convex surrogate of sparsity count; … Read more

    A Stochastic Sequential Quadratic Optimization Algorithm for Nonlinear Equality Constrained Optimization with Rank-Deficient Jacobians

  • Albert S. Berahas
  • Frank E. Curtis
  • Michael J. O'Neill
  • Daniel P. Robinson
    • Categories Constrained Nonlinear Optimization, Statistics Tags , , , ,

    A sequential quadratic optimization algorithm is proposed for solving smooth nonlinear equality constrained optimization problems in which the objective function is defined by an expectation of a stochastic function. The algorithmic structure of the proposed method is based on a step decomposition strategy that is known in the literature to be widely effective in practice, … Read more