Incremental Majorization-Minimization Optimization with Application to Large-Scale Machine Learning

Abstract

Majorization-minimization algorithms consist of successively minimizing a sequence of upper bounds of the objective function. These upper bounds are tight at the current estimate, and each iteration monotonically drives the objective function downhill. Such a simple principle is widely applicable and has been very popular in various scientific fields, especially in signal processing and statistics. In this paper, we propose an incremental majorization-minimization scheme for minimizing a large sum of continuous functions, a problem of utmost importance in machine learning. We present convergence guarantees for non-convex and convex optimization when the upper bounds approximate the objective up to a smooth error; we call such upper bounds "first-order surrogate functions". More precisely, we study asymptotic stationary point guarantees for non-convex problems, and for convex ones, we provide convergence rates for the expected objective function value. We apply our scheme to composite optimization and obtain a new incremental proximal gradient algorithm with linear convergence rate for strongly convex functions. In our experiments, we show that our method is competitive with the state of the art for solving machine learning problems such as logistic regression when the number of training samples is large enough, and we demonstrate its usefulness for sparse estimation with non-convex penalties.

to appear in SIAM Journal on Optimization; final author's version

References in corpus (9)

• SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
• A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets
• Optimization with First-Order Surrogate Functions
• Stochastic Majorization-Minimization Algorithms for Large-Scale Optimization
• Proximal Stochastic Dual Coordinate Ascent
• Finito: A Faster, Permutable Incremental Gradient Method for Big Data Problems
• Fast Stochastic Alternating Direction Method of Multipliers
• A Stochastic Successive Minimization Method for Nonsmooth Nonconvex Optimization with Applications to Transceiver Design in Wireless Communication Networks
• Stochastic Bound Majorization

Cited by in corpus (6)

• SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
• Fast large-scale optimization by unifying stochastic gradient and quasi-Newton methods
• A Simple Practical Accelerated Method for Finite Sums
• A Distributed, Asynchronous and Incremental Algorithm for Nonconvex Optimization: An ADMM Based Approach
• Stochastic Variance-reduced Gradient Descent for Low-rank Matrix Recovery from Linear Measurements
• On the Linear Convergence of the Approximate Proximal Splitting Method for Non-Smooth Convex Optimization