A MEMORY EFFICIENT INCREMENTAL GRADIENT METHOD FOR REGULARIZED MINIMIZATION

In this paper, we propose a new incremental gradient methodfor solving a regularized minimization problem whose objective is thesum of msmooth functions and a (possibly nonsmooth) convex function.This method uses an adaptive stepsize. Recently proposed incrementalgradient methods for a regularized minimization problem need O(mn)storage, where n is the number of variables. This is the drawback ofthem. But, the proposed new incremental gradient method requires onlyO(n) storage. 1. IntroductionIn this paper, we consider the regularized minimization problem whose formis(1) min x∈ℜ n F λ (x) := f(x) +λP(x),where λ > 0, P : ℜ n → (−∞,∞] is a proper, convex, lower semicontinuous(lsc) function [20], and(2) f(x) :=X mi=1 f i (x),where each function f i is real-valued and smooth (i.e., continuously differen-tiable) on an open subset of ℜ n containing domP = {x | P(x) < ∞}.The minimization problem (1) we consider arises in many applications suchas (supervised) learning [7, 12, 27], regression [17, 23], neural network training[11, 21, 29], and data mining/classification [5, 15, 22, 28]. For the l