moreau envelope

Understanding the Douglas-Rachford splitting method through the lenses of Moreau-type envelopes

  • Felipe Atenas
    • Categories Convex and Nonsmooth Optimization, Generalized Convexity/Monoticity, Nonsmooth Optimization Tags , , , ,

    We analyze the Douglas-Rachford splitting method for weakly convex optimization problems, by the token of the Douglas-Rachford envelope, a merit function akin to the Moreau envelope. First, we use epi-convergence techniques to show that this artifact approximates the original objective function via epigraphs. Secondly, we present how global convergence and local linear convergence rates for … Read more

    Weakly convex Douglas-Rachford splitting avoids strict saddle points

  • Felipe Atenas
    • Categories Generalized Convexity/Monoticity, Nonsmooth Optimization Tags , , , ,

    We prove that the Douglas-Rachford splitting method converges, almost surely, to local minimizers of semialgebraic weakly convex optimization problems, under the assumption of the strict saddle property. The approach consists of two steps: first, we prove a manifold identification result, and local smoothness of the involved iteration operator. Then, we proceed to show that strict … Read more

    Proximal bundle methods for hybrid weakly convex composite optimization problems

  • Jiaming Liang
  • Renato D.C. Monteiro
  • Honghao Zhang
    • Categories Nonlinear Optimization, Nonsmooth Optimization Tags , , , ,

    This paper establishes the iteration-complexity of proximal bundle methods for solving hybrid (i.e., a blend of smooth and nonsmooth) weakly convex composite optimization (HWC-CO) problems. This is done in a unified manner by considering a proximal bundle framework (PBF) based on a generic bundle update scheme which includes various well-known bundle update schemes. In contrast … Read more

    Escaping strict saddle points of the Moreau envelope in nonsmooth optimization

  • Damek Davis
  • Mateo Díaz
  • Dmitriy Drusvyatskiy
    • Categories Convex and Nonsmooth Optimization Tags , , ,

    Recent work has shown that stochastically perturbed gradient methods can efficiently escape strict saddle points of smooth functions. We extend this body of work to nonsmooth optimization, by analyzing an inexact analogue of a stochastically perturbed gradient method applied to the Moreau envelope. The main conclusion is that a variety of algorithms for nonsmooth optimization … Read more

    Algorithms for Difference-of-Convex (DC) Programs Based on Difference-of-Moreau-Envelopes Smoothing

  • Xu Andy Sun
  • Kaizhao Sun
    • Categories Constrained Nonlinear Optimization, Nonlinear Optimization, Nonsmooth Optimization Tags , , ,

    In this paper we consider minimization of a difference-of-convex (DC) function with and without linear constraints. We first study a smooth approximation of a generic DC function, termed difference-of-Moreau-envelopes (DME) smoothing, where both components of the DC function are replaced by their respective Moreau envelopes. The resulting smooth approximation is shown to be Lipschitz differentiable, … Read more

    The Landscape of the Proximal Point Method for Nonconvex-Nonconcave Minimax Optimization

  • Benjamin Grimmer
  • Haihao Lu
  • Vahab S. Mirrokni
  • Pratik Worah
    • Categories Robust Optimization, Unconstrained Optimization Tags , , , , , ,

    Minimax optimization has become a central tool for modern machine learning with applications in generative adversarial networks, robust optimization, reinforcement learning, etc. These applications are often nonconvex-nonconcave, but the existing theory is unable to identify and deal with the fundamental difficulties posed by nonconvex-nonconcave structures. In this paper, we study the classic proximal point method … Read more

    Moreau envelope of supremum functions with applications to infinite and stochastic programming

  • Pedro Pérez-Aros
  • Emilio Vilches
    • Categories Convex Optimization, Nonsmooth Optimization, Stochastic Programming Tags , , , , ,

    In this paper, we investigate the Moreau envelope of the supremum of a family of convex, proper, and lower semicontinuous functions. Under mild assumptions, we prove that the Moreau envelope of a supremum is the supremum of Moreau envelopes, which allows us to approximate possibly nonsmooth supremum functions by smooth functions that are also the … Read more

    On proximal point-type algorithms for weakly convex functions and their connection to the backward Euler method

  • Tim Hoheisel
  • Maxime Laborde
  • Adam Oberman
    • Categories Convex and Nonsmooth Optimization Tags , , , ,

    In this article we study the connection between proximal point methods for nonconvex optimization and the backward Euler method from numerical Ordinary Differential Equations (ODEs). We establish conditions for which these methods are equivalent. In the case of weakly convex functions, for small enough parameters, the implicit steps can be solved using a strongly convex … Read more

    Stochastic model-based minimization of weakly convex functions

  • Damek Davis
  • Dmitriy Drusvyatskiy
    • Categories Convex and Nonsmooth Optimization Tags , , , , ,

    We consider an algorithm that successively samples and minimizes stochastic models of the objective function. We show that under weak-convexity and Lipschitz conditions, the algorithm drives the expected norm of the gradient of the Moreau envelope to zero at the rate $O(k^{-1/4})$. Our result yields the first complexity guarantees for the stochastic proximal point algorithm … Read more

    Stochastic subgradient method converges at the rate (k^{-1/4})$ on weakly convex function

  • Damek Davis
  • Dmitriy Drusvyatskiy
    • Categories Nonsmooth Optimization Tags , ,

    We prove that the projected stochastic subgradient method, applied to a weakly convex problem, drives the gradient of the Moreau envelope to zero at the rate $O(k^{-1/4})$. Article Download View Stochastic subgradient method converges at the rate (k^{-1/4})$ on weakly convex function