nonsmooth optimization

Manifold Identification for Ultimately Communication-Efficient Distributed Optimization

  • Wei-Lin Chiang
  • Yu-Sheng Li
  • Ching-pei Lee
    • Categories Nonlinear Optimization, Nonsmooth Optimization, Parallel Algorithms Tags , , ,

    This work proposes a progressive manifold identification approach for distributed optimization with sound theoretical justifications to greatly reduce both the rounds of communication and the bytes communicated per round for partly-smooth regularized problems such as the $\ell_1$- and group-LASSO-regularized ones. Our two-stage method first uses an inexact proximal quasi-Newton method to iteratively identify a sequence … 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

    Stochastic Variance-Reduced Prox-Linear Algorithms for Nonconvex Composite Optimization

  • Lin Xiao
  • Junyu Zhang
    • Categories Nonlinear Optimization, Nonsmooth Optimization, Stochastic Programming Tags , , , ,

    We consider minimization of composite functions of the form $f(g(x))+h(x)$, where $f$ and $h$ are convex functions (which can be nonsmooth) and $g$ is a smooth vector mapping. In addition, we assume that $g$ is the average of finite number of component mappings or the expectation over a family of random component mappings. We propose … Read more

    Geometry of First-Order Methods and Adaptive Acceleration

  • Jingwei Liang
  • Clarice Poon
    • Categories Convex and Nonsmooth Optimization, Convex Optimization, Nonsmooth Optimization Tags , , , , , ,

    First-order operator splitting methods are ubiquitous among many fields through science and engineering, such as inverse problems, signal/image processing, statistics, data science and machine learning, to name a few. In this paper, we study a geometric property of first-order methods when applying to solve non-smooth optimization problems. With the tool of “partial smoothness”, we design … Read more

    A Distributed Quasi-Newton Algorithm for Primal and Dual Regularized Empirical Risk Minimization

  • Stephen Wright
  • Cong Han Lim
  • Ching-pei Lee
    • Categories Nonsmooth Optimization, Parallel Algorithms Tags , , , , , , ,

    We propose a communication- and computation-efficient distributed optimization algorithm using second-order information for solving empirical risk minimization (ERM) problems with a nonsmooth regularization term. Our algorithm is applicable to both the primal and the dual ERM problem. Current second-order and quasi-Newton methods for this problem either do not work well in the distributed setting or … Read more

    A simple Newton method for local nonsmooth optimization

  • Adrian Lewis
  • Calvin Wylie
    • Categories Nonsmooth Optimization Tags , , , ,

    Superlinear convergence has been an elusive goal for black-box nonsmooth optimization. Even in the convex case, the subgradient method is very slow, and while some cutting plane algorithms, including traditional bundle methods, are popular in practice, local convergence is still sluggish. Faster variants depend either on problem structure or on analyses that elide sequences of … Read more

    Numerical solution of generalized minimax problems

  • Ladislav Lukšan
  • Ctirad Matonoha
  • Jan Vlček
    • Categories Nonsmooth Optimization, Unconstrained Optimization Tags , , , , , , ,

    This contribution contains the description and investigation of four numerical methods for solving generalized minimax problems, which consists in the minimization of functions which are compositions of special smooth convex functions with maxima of smooth functions (the most important problem of this type is the sum of maxima of smooth functions). Section~1 is introductory. In … 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

    On the Relation between MPECs and Optimization Problems in Abs-Normal Form

  • Lisa Hegerhorst-Schultchen
  • Christian Kirches
  • Marc C. Steinbach
    • Categories Constrained Nonlinear Optimization Tags , , , ,

    We show that the problem of unconstrained minimization of a function in abs-normal form is equivalent to identifying a certain stationary point of a counterpart Mathematical Program with Equilibrium Constraints (MPEC). Hence, concepts introduced for the abs-normal forms turn out to be closely related to established concepts in the theory of MPECs. We give a … Read more

    A Distributed Quasi-Newton Algorithm for Empirical Risk Minimization with Nonsmooth Regularization

  • Stephen Wright
  • Cong Han Lim
  • Ching-pei Lee
    • Categories Data-Mining, Nonlinear Optimization, Parallel Algorithms Tags , , , , , , ,

    We propose a communication- and computation-efficient distributed optimization algorithm using second-order information for solving ERM problems with a nonsmooth regularization term. Current second-order and quasi-Newton methods for this problem either do not work well in the distributed setting or work only for specific regularizers. Our algorithm uses successive quadratic approximations, and we describe how to … Read more