Composite Self-Concordant Minimization

Abstract

We propose a variable metric framework for minimizing the sum of a self-concordant function and a possibly non-smooth convex function, endowed with an easily computable proximal operator. We theoretically establish the convergence of our framework without relying on the usual Lipschitz gradient assumption on the smooth part. An important highlight of our work is a new set of analytic step-size selection and correction procedures based on the structure of the problem. We describe concrete algorithmic instances of our framework for several interesting applications and demonstrate them numerically on both synthetic and real data.

46 pages, 9 figures

References in corpus (2)

• Iterative Thresholding Algorithm for Sparse Inverse Covariance Estimation
• Learning Heteroscedastic Models by Convex Programming under Group Sparsity

Cited by in corpus (22)

• Convex Optimization for Big Data
• Sparsity Based Poisson Denoising with Dictionary Learning
• Poisson Matrix Recovery and Completion
• Proximal extrapolated gradient methods for variational inequalities
• Convexity in source separation: Models, geometry, and algorithms
• Dropping Convexity for Faster Semi-definite Optimization
• Inexact Proximal-Point Penalty Methods for Constrained Non-Convex Optimization
• An inexact subsampled proximal Newton-type method for large-scale machine learning
• Golden Ratio Algorithms for Variational Inequalities
• Self-Concordant Analysis of Frank-Wolfe Algorithms
• A Newton Frank-Wolfe Method for Constrained Self-Concordant Minimization
• Composite Convex Optimization with Global and Local Inexact Oracles
• Poisson Matrix Completion
• Generalized Self-Concordant Functions: A Recipe for Newton-Type Methods
• Quasi-Newton Methods: Superlinear Convergence Without Line Searches for Self-Concordant Functions
• A General Convergence Result for Mirror Descent with Armijo Line Search
• Randomized block proximal damped Newton method for composite self-concordant minimization
• Efficient proximal gradient algorithms for joint graphical lasso
• Golden ratio algorithms with new stepsize rules for variational inequalities
• An Inexact Interior-Point Lagrangian Decomposition Algorithm with Inexact Oracles
• A scalable system for primal-dual optimization
• Nonparametric Finite Mixture Models with Possible Shape Constraints: A Cubic Newton Approach