Tensor Methods for Minimizing Convex Functions with Hölder Continuous Higher-Order Derivatives

  • Geovani Nunes Grapiglia
  • Yurii Nesterov
    • Categories Convex and Nonsmooth Optimization, Nonlinear Optimization Tags , , , ,

    In this paper we study p-order methods for unconstrained minimization of convex functions that are p-times differentiable with $\nu$-Hölder continuous pth derivatives. We propose tensor schemes with and without acceleration. For the schemes without acceleration, we establish iteration complexity bounds of $\mathcal{O}\left(\epsilon^{-1/(p+\nu-1)}\right)$ for reducing the functional residual below a given $\epsilon\in (0,1)$. Assuming that $\nu$ … Read more

    An analysis of noise folding for low-rank matrix recovery

  • Wang Hailin
  • Jianjun Wang
  • Jianwen Huang
  • Wang Wendong
  • Feng Zhang
    • Categories Approximation Algorithms, Convex Optimization, Data-Mining

    Previous work regarding low-rank matrix recovery has concentrated on the scenarios in which the matrix is noise-free and the measurements are corrupted by noise. However, in practical application, the matrix itself is usually perturbed by random noise preceding to measurement. This paper concisely investigates this scenario and evidences that, for most measurement schemes utilized in … Read more

    A convex relaxation to compute the nearest structured rank deficient matrix

  • Diego Cifuentes
    • Categories Semi-definite Programming Tags , , ,

    Given an affine space of matrices L and a matrix \theta in L, consider the problem of finding the closest rank deficient matrix to \theta on L with respect to the Frobenius norm. This is a nonconvex problem with several applications in estimation problems. We introduce a novel semidefinite programming (SDP) relaxation, and we show … Read more

    A linearly convergent stochastic recursive gradient method for convex optimization

  • Tiande Guo
  • Yan Liu
  • Xiao Wang
    • Categories Convex and Nonsmooth Optimization, Convex Optimization Tags , , , ,

    The stochastic recursive gradient algorithm (SARAH) [8] attracts much interest recently. It admits a simple recursive framework for updating stochastic gradient estimates. Motivated by this, in this paper, we propose a SARAH-I method incorporating importance sampling, whose linear conver- gence rate of the sequence of distances between iterates and the optima set is proven under … Read more

    General risk measures for robust machine learning

  • Émilie Chouzenoux
  • Jean-Christophe Pesquet
  • Henri Gérard
    • Categories Convex Optimization, Robust Optimization, Stochastic Programming Tags , , , , ,

    A wide array of machine learning problems are formulated as the minimization of the expectation of a convex loss function on some parameter space. Since the probability distribution of the data of interest is usually unknown, it is is often estimated from training sets, which may lead to poor out-of-sample performance. In this work, we … Read more

    Scalable Preconditioning of Block-Structured Linear Algebra Systems using ADMM

  • Carl D. Laird
  • Victor M. Zavala
  • Jose Rodriguez
    • Categories Parallel Algorithms, Quadratic Programming, Stochastic Programming

    We study the solution of block-structured linear algebra systems arising in optimization by using iterative solution techniques. These systems are the core computational bottleneck of many problems of interest such as parameter estimation, optimal control, network optimization, and stochastic programming. Our approach uses a Krylov solver (GMRES) that is preconditioned with an alternating method of … Read more

    Low-rank matrix recovery with composite optimization: good conditioning and rapid convergence

  • Vasileios Charisopoulos
  • Damek Davis
  • Mateo Díaz
  • Dmitriy Drusvyatskiy
  • Yudong Chen
  • Lijun Ding
    • Categories Convex and Nonsmooth Optimization Tags , , , ,

    The task of recovering a low-rank matrix from its noisy linear measurements plays a central role in computational science. Smooth formulations of the problem often exhibit an undesirable phenomenon: the condition number, classically defined, scales poorly with the dimension of the ambient space. In contrast, we here show that in a variety of concrete circumstances, … Read more

    Relative-error inertial-relaxed inexact versions of Douglas-Rachford and ADMM splitting algorithms

  • M. Marques Alves
  • Jonathan Eckstein
  • Jefferson Gonçalves Melo
  • Marina Geremia
    • Categories Convex and Nonsmooth Optimization Tags , , , , ,

    This paper derives new inexact variants of the Douglas-Rachford splitting method for maximal monotone operators and the alternating direction method of multipliers (ADMM) for convex optimization. The analysis is based on a new inexact version of the proximal point algorithm that includes both an inertial step and overrelaxation. We apply our new inexact ADMM method … Read more

    There’s No Free Lunch: On the Hardness of Choosing a Correct Big-M in Bilevel Optimization

  • Thomas Kleinert
  • Martine Labbé
  • Martin Schmidt
  • Fränk Plein
    • Categories (Mixed) Integer Linear Programming, Complementarity and Variational Inequalities Tags , , , ,

    One of the most frequently used approaches to solve linear bilevel optimization problems consists in replacing the lower-level problem with its Karush-Kuhn-Tucker (KKT) conditions and by reformulating the KKT complementarity conditions using techniques from mixed-integer linear optimization. The latter step requires to determine some big-M constant in order to bound the lower level’s dual feasible … Read more

    Trust-region methods for the derivative-free optimization of nonsmooth black-box functions

  • Giampaolo Liuzzi
  • Stefano Lucidi
  • Francesco Rinaldi
  • Luis Nunes Vicente
    • Categories Applications - Science and Engineering, Nonlinear Optimization, Nonsmooth Optimization Tags , , ,

    In this paper we study the minimization of a nonsmooth black-box type function, without assuming any access to derivatives or generalized derivatives and without any knowledge about the analytical origin of the function nonsmoothness. Directional methods have been derived for such problems but to our knowledge no model-based method like a trust-region one has yet … Read more