nonconvex optimization

User manual of NewtBracket: “A Newton-Bracketing method for a simple conic optimization problem” with applications to QOPs in binary variables

  • Sunyoung Kim
  • Masakazu Kojima
  • Kim-Chuan Toh
    • Categories Linear, Cone and Semidefinite Programming Tags , , , ,

    We describe the Matlab package NewtBracket for solving a simple conic optimization problem that minimizes a linear objective function subject to a single linear equality constraint and a convex cone constraint. The problem is converted into the problem of finding the largest zero $y^*$ of a continuously differentiable (except at $y^*$) convex function $g : … Read more

    Exterior-point Optimization for Nonconvex Learning

  • Shuvomoy Das Gupta
  • Bartolomeo Stellato
  • Bart Paul Gerard Van Parys
    • Categories Constrained Nonlinear Optimization, Nonsmooth Optimization, Statistics Tags , , ,

    In this paper we present the nonconvex exterior-point optimization solver (NExOS)—a novel first-order algorithm tailored to constrained nonconvex learning problems. We consider the problem of minimizing a convex function over nonconvex constraints, where the projection onto the constraint set is single-valued around local minima. A wide range of nonconvex learning problems have this structure including … Read more

    Minimization of L1 over L2 for sparse signal recovery with convergence guarantee

  • Tao Min
    • Categories Applications - OR and Management Sciences Tags , , , , ,

    The ratio of the $L_1$ and $L_2$ norms, denoted by $L_1/L_2$, becomes attractive due to its scale-invariant property when approximating the $L_0$ norm to promote sparsity. In this paper, we incorporate the $L_1/L_2$ formalism into an unconstrained model in order to deal with both noiseless and noisy observations. To design an efficient algorithm, we derive … Read more

    Stochastic Multi-level Composition Optimization Algorithms with Level-Independent Convergence Rates

  • Krishnakumar Balasubramanian
  • Saeed Ghadimi
  • Anthony Nguyen
    • Categories Nonlinear Optimization, Statistics, Stochastic Programming Tags , , ,

    In this paper, we study smooth stochastic multi-level composition optimization problems, where the objective function is a nested composition of $T$ functions. We assume access to noisy evaluations of the functions and their gradients, through a stochastic first-order oracle. For solving this class of problems, we propose two algorithms using moving-average stochastic estimates, and analyze … Read more

    A unifying framework for the analysis of projection-free first-order methods under a sufficient slope condition

  • Francesco Rinaldi
  • Damiano Zeffiro
    • Categories Nonlinear Optimization Tags , , , ,

    The analysis of projection-free first order methods is often complicated by the presence of different kinds of “good” and “bad” steps. In this article, we propose a unifying framework for projection-free methods, aiming to simplify the converge analysis by getting rid of such a distinction between steps. The main tool employed in our framework is … Read more

    Accuracy and fairness trade-offs in machine learning: A stochastic multi-objective approach

  • Suyun Liu
  • Luis Nunes Vicente
    • Categories Data-Mining, Multi-Criteria Optimization, Stochastic Programming Tags , , , , , , , , ,

    In the application of machine learning to real life decision-making systems, e.g., credit scoring and criminal justice, the prediction outcomes might discriminate against people with sensitive attributes, leading to unfairness. The commonly used strategy in fair machine learning is to include fairness as a constraint or a penalization term in the minimization of the prediction … Read more

    Accelerated Inexact Composite Gradient Methods for Nonconvex Spectral Optimization Problems

  • Weiwei Kong
  • Renato D.C. Monteiro
    • Categories Convex and Nonsmooth Optimization, Nonlinear Optimization Tags , , , , ,

    This paper presents two inexact composite gradient methods, one inner accelerated and another doubly accelerated, for solving a class of nonconvex spectral composite optimization problems. More specifically, the objective function for these problems is of the form f_1 + f_2 + h where f_1 and f_2 are differentiable nonconvex matrix functions with Lipschitz continuous gradients, … Read more

    New convergence results for the inexact variable metric forward-backward method

  • Silvia Bonettini
  • Marco Prato
  • Simone Rebegoldi
    • Categories Nonlinear Optimization Tags , ,

    Forward–backward methods are valid tools to solve a variety of optimization problems where the objective function is the sum of a smooth, possibly nonconvex term plus a convex, possibly nonsmooth function. The corresponding iteration is built on two main ingredients: the computation of the gradient of the smooth part and the evaluation of the proximity … Read more

    A Line-Search Descent Algorithm for Strict Saddle Functions with Complexity Guarantees

  • Michael O'Neill
  • Stephen Wright
    • Categories Unconstrained Optimization Tags , ,

    We describe a line-search algorithm which achieves the best-known worst-case complexity results for problems with a certain “strict saddle” property that has been observed to hold in low-rank matrix optimization problems. Our algorithm is adaptive, in the sense that it makes use of backtracking line searches and does not require prior knowledge of the parameters … Read more

    Gradient Sampling Methods with Inexact Subproblem Solves and Gradient Aggregation

  • Frank E. Curtis
  • Minhan Li
    • Categories Nonsmooth Optimization Tags , , , ,

    Gradient sampling (GS) has proved to be an effective methodology for the minimization of objective functions that may be nonconvex and/or nonsmooth. The most computationally expensive component of a contemporary GS method is the need to solve a convex quadratic subproblem in each iteration. In this paper, a strategy is proposed that allows the use … Read more