An efficient primal dual prox method for non-smooth optimization
From MaRDI portal
Publication:2339936
Abstract: We study the non-smooth optimization problems in machine learning, where both the loss function and the regularizer are non-smooth functions. Previous studies on efficient empirical loss minimization assume either a smooth loss function or a strongly convex regularizer, making them unsuitable for non-smooth optimization. We develop a simple yet efficient method for a family of non-smooth optimization problems where the dual form of the loss function is bilinear in primal and dual variables. We cast a non-smooth optimization problem into a minimax optimization problem, and develop a primal dual prox method that solves the minimax optimization problem at a rate of {assuming that the proximal step can be efficiently solved}, significantly faster than a standard subgradient descent method that has an convergence rate. Our empirical study verifies the efficiency of the proposed method for various non-smooth optimization problems that arise ubiquitously in machine learning by comparing it to the state-of-the-art first order methods.
Recommendations
- Perturbed proximal primal-dual algorithm for nonconvex nonsmooth optimization
- scientific article; zbMATH DE number 7404502
- Accelerated proximal stochastic dual coordinate ascent for regularized loss minimization
- A smooth primal-dual optimization framework for nonsmooth composite convex minimization
- Nonsmoothness in machine learning: specific structure, proximal identification, and applications
Cites work
- scientific article; zbMATH DE number 3715314 (Why is no real title available?)
- scientific article; zbMATH DE number 193625 (Why is no real title available?)
- scientific article; zbMATH DE number 1332320 (Why is no real title available?)
- scientific article; zbMATH DE number 2107836 (Why is no real title available?)
- A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
- A feature selection Newton method for support vector machine classification
- A first-order primal-dual algorithm for convex problems with applications to imaging
- A forward–backward splitting algorithm for the minimization of non-smooth convex functionals in Banach space
- A general framework for a class of first order primal-dual algorithms for convex optimization in imaging science
- An optimal method for stochastic composite optimization
- Are Loss Functions All the Same?
- Classification with a reject option using a hinge loss
- Convergence analysis of primal-dual algorithms for a saddle-point problem: from contraction perspective
- Convex multi-task feature learning
- Distributed optimization and statistical learning via the alternating direction method of multipliers
- ESTIMATING THE APPROXIMATION ERROR IN LEARNING THEORY
- Efficient online and batch learning using forward backward splitting
- Exact matrix completion via convex optimization
- Excessive Gap Technique in Nonsmooth Convex Minimization
- Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization
- Model Selection and Estimation in Regression with Grouped Variables
- Monotone Operators and the Proximal Point Algorithm
- Optimization with sparsity-inducing penalties
- Pegasos: primal estimated sub-gradient solver for SVM
- Primal-dual first-order methods with \({\mathcal {O}(1/\varepsilon)}\) iteration-complexity for cone programming
- Primal-dual splitting algorithm for solving inclusions with mixtures of composite, Lipschitzian, and parallel-sum type monotone operators
- Prox-Method with Rate of Convergence O(1/t) for Variational Inequalities with Lipschitz Continuous Monotone Operators and Smooth Convex-Concave Saddle Point Problems
- Quantile regression.
- SVM Soft Margin Classifiers: Linear Programming versus Quadratic Programming
- Smooth minimization of non-smooth functions
- Splitting Algorithms for the Sum of Two Nonlinear Operators
- The elements of statistical learning. Data mining, inference, and prediction
Cited in
(17)- scientific article; zbMATH DE number 7415112 (Why is no real title available?)
- Non-stationary First-Order Primal-Dual Algorithms with Faster Convergence Rates
- Approximately nearest neighborhood image search using unsupervised hashing via homogeneous kernels
- Online composite optimization with time-varying regularizers
- Nonsmoothness in machine learning: specific structure, proximal identification, and applications
- RSG: Beating Subgradient Method without Smoothness and Strong Convexity
- An asynchronous subgradient-proximal method for solving additive convex optimization problems
- First-order primal-dual methods for nonsmooth non-convex optimization
- The nearest polynomial to multiple given polynomials with a given zero: a unified optimization approach
- Dualize, split, randomize: toward fast nonsmooth optimization algorithms
- Point process estimation with Mirror Prox algorithms
- Efficient computation of the nearest polynomial by linearized alternating direction method
- Perturbed proximal primal-dual algorithm for nonconvex nonsmooth optimization
- A Smooth Double Proximal Primal-Dual Algorithm for a Class of Distributed Nonsmooth Optimization Problems
- A two-step fixed-point proximity algorithm for a class of non-differentiable optimization models in machine learning
- Running Primal-Dual Gradient Method for Time-Varying Nonconvex Problems
- Accelerate stochastic subgradient method by leveraging local growth condition
This page was built for publication: An efficient primal dual prox method for non-smooth optimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2339936)
