Generalized self-concordant functions: a recipe for Newton-type methods
From MaRDI portal
Publication:2330645
DOI10.1007/S10107-018-1282-4zbMATH Open1430.90464arXiv1703.04599OpenAlexW2603538444MaRDI QIDQ2330645FDOQ2330645
Authors: Tianxiao Sun, Quoc Tran Dinh 
Publication date: 22 October 2019
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Abstract: We study the smooth structure of convex functions by generalizing a powerful concept so-called self-concordance introduced by Nesterov and Nemirovskii in the early 1990s to a broader class of convex functions, which we call generalized self-concordant functions. This notion allows us to develop a unified framework for designing Newton-type methods to solve convex optimiza- tion problems. The proposed theory provides a mathematical tool to analyze both local and global convergence of Newton-type methods without imposing unverifiable assumptions as long as the un- derlying functionals fall into our generalized self-concordant function class. First, we introduce the class of generalized self-concordant functions, which covers standard self-concordant functions as a special case. Next, we establish several properties and key estimates of this function class, which can be used to design numerical methods. Then, we apply this theory to develop several Newton-type methods for solving a class of smooth convex optimization problems involving the generalized self- concordant functions. We provide an explicit step-size for the damped-step Newton-type scheme which can guarantee a global convergence without performing any globalization strategy. We also prove a local quadratic convergence of this method and its full-step variant without requiring the Lipschitz continuity of the objective Hessian. Then, we extend our result to develop proximal Newton-type methods for a class of composite convex minimization problems involving generalized self-concordant functions. We also achieve both global and local convergence without additional assumption. Finally, we verify our theoretical results via several numerical examples, and compare them with existing methods.
Full work available at URL: https://arxiv.org/abs/1703.04599
Recommendations
- Self-concordant inclusions: a unified framework for path-following generalized Newton-type algorithms
- Composite convex minimization involving self-concordant-like cost functions
- A Newton Frank-Wolfe method for constrained self-concordant minimization
- Globalized inexact proximal Newton-type methods for nonconvex composite functions
- Generalized self-concordant analysis of Frank-Wolfe algorithms
convex optimizationglobal convergencelocal convergencequadratic convergenceNewton-type methodproximal Newton methodgeneralized self-concordance
Convex programming (90C25) Computational methods for problems pertaining to operations research and mathematical programming (90-08)
Cites Work
- Newton methods for nonlinear problems. Affine invariance and adaptive algorithms.
- Disciplined convex programming
- A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
- Templates for convex cone problems with applications to sparse signal recovery
- Distance-Weighted Discrimination
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Benchmarking optimization software with performance profiles.
- A stochastic quasi-Newton method for large-scale optimization
- Smooth minimization of non-smooth functions
- Introductory lectures on convex optimization. A basic course.
- Adaptive restart for accelerated gradient schemes
- Gradient methods for minimizing composite functions
- Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions
- Title not available (Why is that?)
- Strongly Regular Generalized Equations
- Title not available (Why is that?)
- An inexact perturbed path-following method for Lagrangian decomposition in large-scale separable convex optimization
- Local analysis of Newton-type methods for variational inequalities and nonlinear programming
- On the implementation and usage of SDPT3 -- a Matlab software package for semidefinite-quadratic-linear programming, version 4.0
- Iterative Solution of Nonlinear Equations in Several Variables
- A class of stochastic programs with decision dependent uncertainty
- Self-concordant analysis for logistic regression
- Convex analysis and monotone operator theory in Hilbert spaces
- A Characterization of Superlinear Convergence and Its Application to Quasi-Newton Methods
- Cubic regularization of Newton method and its global performance
- Time-Optimal Path Tracking for Robots: A Convex Optimization Approach
- Accelerating the cubic regularization of Newton's method on convex problems
- Implementation and evaluation of SDPA 6.0 (Semidefinite Programming Algorithm 6.0)
- Regularized Newton method for unconstrained convex optimization
- Title not available (Why is that?)
- Composite self-concordant minimization
- Proximal Newton-type methods for minimizing composite functions
- Efficient evaluation of scaled proximal operators
- Path-following gradient-based decomposition algorithms for separable convex optimization
- Balancing sparse matrices for computing eigenvalues
- Methods for scaling to doubly stochastic form
- A hybrid proximal extragradient self-concordant primal barrier method for monotone variational inequalities
- Adaptivity of averaged stochastic gradient descent to local strong convexity for logistic regression
- Sub-sampled Newton methods
- Newton Sketch: A Near Linear-Time Optimization Algorithm with Linear-Quadratic Convergence
- Exact and inexact subsampled Newton methods for optimization
- Self-concordant inclusions: a unified framework for path-following generalized Newton-type algorithms
- Quasi-Newton methods: superlinear convergence without line searches for self-concordant functions
- Randomized block proximal damped Newton method for composite self-concordant minimization
- Restarting the accelerated coordinate descent method with a rough strong convexity estimate
- Composite convex minimization involving self-concordant-like cost functions
Cited In (16)
- Composite convex optimization with global and local inexact oracles
- The method of randomized Bregman projections for stochastic feasibility problems
- Finite-sample analysis of \(M\)-estimators using self-concordance
- Self-concordant inclusions: a unified framework for path-following generalized Newton-type algorithms
- Scalable Frank-Wolfe on generalized self-concordant functions via simple steps
- Semi-discrete optimal transport: hardness, regularization and numerical solution
- A new homotopy proximal variable-metric framework for composite convex minimization
- SCORE: approximating curvature information under self-concordant regularization
- Composite convex minimization involving self-concordant-like cost functions
- Greedy quasi-Newton methods with explicit superlinear convergence
- Title not available (Why is that?)
- Optimal step length for the Newton method: case of self-concordant functions
- A Newton Frank-Wolfe method for constrained self-concordant minimization
- Generalized self-concordant analysis of Frank-Wolfe algorithms
- Differentially private inference via noisy optimization
- Randomized block proximal damped Newton method for composite self-concordant minimization
Uses Software
This page was built for publication: Generalized self-concordant functions: a recipe for Newton-type methods
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2330645)
