Generalized Convexity/Monoticity

Extending the Reach of First-Order Algorithms for Nonconvex Min-Max Problems with Cohypomonotonicity

  • Ahmet Alacaoglu
  • Donghwan Kim
  • Stephen Wright
    • Categories Complementarity and Variational Inequalities, Generalized Convexity/Monoticity, Nonlinear Optimization, Stochastic Programming

    \(\) We focus on constrained, \(L\)-smooth, nonconvex-nonconcave min-max problems either satisfying \(\rho\)-cohypomonotonicity or admitting a solution to the \(\rho\)-weakly Minty Variational Inequality (MVI), where larger values of the parameter \(\rho>0\) correspond to a greater degree of nonconvexity. These problem classes include examples in two player reinforcement learning, interaction dominant min-max problems, and certain synthetic test problems … 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

    Weak convexity and approximate subdifferentials

  • Felipe Atenas
  • Wim van Ackooij
  • Claudia Sagastizábal
    • Categories Complementarity and Variational Inequalities, Generalized Convexity/Monoticity, Nonsmooth Optimization

    We explore and construct an enlarged subdifferential for weakly convex functions. The resulting object turns out to be continuous with respect to both the function argument and the enlargement parameter. We carefully analyze connections with other constructs in the literature and extend well-known variational principles to the weakly convex setting. By resorting to the new … Read more

    Convergence of the Chambolle–Pock Algorithm in the Absence of Monotonicity

  • Brecht Evens
    • Categories Generalized Convexity/Monoticity, Nonsmooth Optimization Tags , , , , ,

    The Chambolle-Pock algorithm (CPA), also known as the primal-dual hybrid gradient method (PDHG), has surged in popularity in the last decade due to its success in solving convex/monotone structured problems. This work provides convergence results for problems with varying degrees of (non)monotonicity, quantified through a so-called oblique weak Minty condition on the associated primal-dual operator. … Read more

    Range of the displacement operator of PDHG with applications to quadratic and conic programming

  • Tao Jiang
  • Walaa M. Moursi
  • Stephen A. Vavasis
    • Categories Generalized Convexity/Monoticity, Quadratic Programming, Second-Order Cone Programming Tags , , , , ,

    Primal-dual hybrid gradient (PDHG) is a first-order method for saddle-point problems and convex programming introduced by Chambolle and Pock. Recently, Applegate et al. analyzed the behavior of PDHG when applied to an infeasible or unbounded instance of linear programming, and in particular, showed that PDHG is able to diagnose these conditions. Their analysis hinges on … Read more

    Convexity and continuity of specific set-valued maps and their extremal value functions

  • Gabriele Eichfelder
  • Tobias Gerlach
  • Stefan Rocktäschel
    • Categories Convex Optimization, Generalized Convexity/Monoticity, Nonlinear Optimization Tags , , ,

    In this paper, we study several classes of set-valued maps, which can be used in set-valued optimization and its applications, and their respective maximum and minimum value functions. The definitions of these maps are based on scalar-valued, vector-valued, and cone-valued maps. Moreover, we consider those extremal value functions which are obtained when optimizing linear functionals … Read more

    On convexity and quasiconvexity of extremal value functions in set optimization

  • Tobias Gerlach
  • Stefan Rocktäschel
    • Categories Generalized Convexity/Monoticity Tags

    We study different classes of convex and quasiconvex set-valued maps defined by means of the lower-less order relation and the upper-less order relation. The aim of this paper is to formulate necessary and especially sufficient conditions for the convexity/quasiconvexity of extremal value functions. Citation DOI: 10.23952/asvao.3.2021.3.04 Article Download View On convexity and quasiconvexity of extremal … Read more

    Calculating Optimistic Likelihoods Using (Geodesically) Convex Optimization

  • Daniel Kuhn
  • Viet Anh Nguyen
  • Soroosh Shafieezadeh-Abadeh
  • Wolfram Wiesemann
  • Man-Chung Yue
    • Categories Generalized Convexity/Monoticity, Semi-definite Programming, Stochastic Programming Tags , , ,

    A fundamental problem arising in many areas of machine learning is the evaluation of the likelihood of a given observation under different nominal distributions. Frequently, these nominal distributions are themselves estimated from data, which makes them susceptible to estimation errors. We thus propose to replace each nominal distribution with an ambiguity set containing all distributions … Read more

    Characterizations of explicitly quasiconvex vector functions w.r.t. polyhedral cones

  • Christian Günther
  • Nicolae Popovici
    • Categories Generalized Convexity/Monoticity

    The aim of this paper is to present new characterizations of explicitly cone-quasiconvex vector functions with respect to a polyhedral cone of a finite-dimensional Euclidean space. These characterizations are given in terms of classical explicit quasiconvexity of certain real-valued functions, defined by composing the vector-valued function with appropriate scalarization functions, namely the extreme directions of … Read more

    Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptron

  • Francis Bach
  • Mark Schmidt
  • Sharan Vaswani
    • Categories Convex Optimization, Generalized Convexity/Monoticity Tags , , ,

    Modern machine learning focuses on highly expressive models that are able to fit or interpolate the data completely, resulting in zero training loss. For such models, we show that the stochastic gradients of common loss functions satisfy a strong growth condition. Under this condition, we prove that constant step-size stochastic gradient descent (SGD) with Nesterov … Read more