Randomized block proximal damped Newton method for composite self-concordant minimization
From MaRDI portal
Publication:5355205
convergenceconvex optimizationiteration complexitydamped Newton methodcomposite self-concordant minimizationproximal damped Newton methodrandomized block proximal damped Newton method
Numerical mathematical programming methods (65K05) Learning and adaptive systems in artificial intelligence (68T05) Convex programming (90C25) Large-scale problems in mathematical programming (90C06) Interior-point methods (90C51) Methods involving semicontinuity and convergence; relaxation (49J45) Newton-type methods (49M15)
Abstract: In this paper we consider the composite self-concordant (CSC) minimization problem, which minimizes the sum of a self-concordant function and a (possibly nonsmooth) proper closed convex function . The CSC minimization is the cornerstone of the path-following interior point methods for solving a broad class of convex optimization problems. It has also found numerous applications in machine learning. The proximal damped Newton (PDN) methods have been well studied in the literature for solving this problem that enjoy a nice iteration complexity. Given that at each iteration these methods typically require evaluating or accessing the Hessian of and also need to solve a proximal Newton subproblem, the cost per iteration can be prohibitively high when applied to large-scale problems. Inspired by the recent success of block coordinate descent methods, we propose a randomized block proximal damped Newton (RBPDN) method for solving the CSC minimization. Compared to the PDN methods, the computational cost per iteration of RBPDN is usually significantly lower. The computational experiment on a class of regularized logistic regression problems demonstrate that RBPDN is indeed promising in solving large-scale CSC minimization problems. The convergence of RBPDN is also analyzed in the paper. In particular, we show that RBPDN is globally convergent when is Lipschitz continuous. It is also shown that RBPDN enjoys a local linear convergence. Moreover, we show that for a class of including the case where is Lipschitz differentiable, RBPDN enjoys a global linear convergence. As a striking consequence, it shows that the classical damped Newton methods [22,40] and the PDN [31] for such are globally linearly convergent, which was previously unknown in the literature. Moreover, this result can be used to sharpen the existing iteration complexity of these methods.
Recommendations
- Generalized self-concordant functions: a recipe for Newton-type methods
- Composite self-concordant minimization
- Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function
- An accelerated randomized proximal coordinate gradient method and its application to regularized empirical risk minimization
- Newton Sketch: A Near Linear-Time Optimization Algorithm with Linear-Quadratic Convergence
Cites work
- scientific article; zbMATH DE number 729680 (Why is no real title available?)
- A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
- A coordinate gradient descent method for nonsmooth separable minimization
- A highly efficient semismooth Newton augmented Lagrangian method for solving lasso problems
- A proximal-gradient homotopy method for the sparse least-squares problem
- A randomized nonmonotone block proximal gradient method for a class of structured nonlinear programming
- A semismooth Newton method with multidimensional filter globalization for \(l_1\)-optimization
- Accelerated block-coordinate relaxation for regularized optimization
- Accelerated, parallel, and proximal coordinate descent
- Adaptive First-Order Methods for General Sparse Inverse Covariance Selection
- Alternating direction algorithms for \(\ell_1\)-problems in compressive sensing
- An Asynchronous Parallel Stochastic Coordinate Descent Algorithm
- An accelerated randomized proximal coordinate gradient method and its application to regularized empirical risk minimization
- An algorithm for quadratic \(\ell_1\)-regularized optimization with a flexible active-set strategy
- An inexact proximal path-following algorithm for constrained convex minimization
- Block coordinate descent methods for semidefinite programming
- Communication-efficient distributed optimization of self-concordant empirical loss
- Composite self-concordant minimization
- Coordinate descent method for large-scale L2-loss linear support vector machines
- Efficiency of coordinate descent methods on huge-scale optimization problems
- Efficient random coordinate descent algorithms for large-scale structured nonconvex optimization
- First-Order Methods for Sparse Covariance Selection
- Fixed-Point Continuation Applied to Compressed Sensing: Implementation and Numerical Experiments
- Gradient methods for minimizing composite functions
- Introductory lectures on convex optimization. A basic course.
- Iteration complexity analysis of block coordinate descent methods
- Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function
- Model selection and estimation in the Gaussian graphical model
- On efficiently solving the subproblems of a level-set method for fused lasso problems
- On the complexity analysis of randomized block-coordinate descent methods
- On the convergence of block coordinate descent type methods
- Probing the Pareto frontier for basis pursuit solutions
- Proximal Newton-type methods for minimizing composite functions
- Randomized methods for linear constraints: convergence rates and conditioning
- Sparse Reconstruction by Separable Approximation
- Sparse inverse covariance estimation with the graphical lasso
- Stochastic dual coordinate ascent methods for regularized loss minimization
Cited in
(4)
This page was built for publication: Randomized block proximal damped Newton method for composite self-concordant minimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5355205)
