We present a proximal quasi-Newton method in which the approximation of the Hessian has the special format of “identity minus rank one” (IMRO) in each iteration. The proposed structure enables us to effectively recover the proximal point. The algorithm is applied to @math -regularized least squares problems arising in many applications including sparse recovery in compressive sensing, machine learning, and statistics. Our numerical experiment suggests that the proposed technique competes favorably with other state-of-the-art solvers for this class of problems. We also provide a complexity analysis for variants of IMRO, showing that it matches known best bounds.
Shuffling the linear and quadratic terms and ignoring the constants in , it can equivalently be written as x^ k+1 = 1 2 |x-(x^k- f(x^k) |^2 +p(x) . Using the notion of @math operator we conclude that x^ k+1 = p (x^k- f(x^k) ). The iterative scheme of is the generalized gradient method" or proximal gradient method". Note that it actually coincides with steepest descent method in the absence of @math . It is also sometimes called Forward-backward Splitting Method" @cite_38 @cite_12 . It gets its name from the two separate stages during each iteration while minimizing ; the first stage is taking a forward step @math involving only @math , and the second stage is a backward step @math which involves only @math . Finding the proximal point may not be a trivial task in general, but for solving @math it can be computed efficiently because the @math -norm is separable.
@cite_38 @cite_12
2198227614 2727154576 2962721705 2787445655
We develop a new proximal-gradient method for minimizing the sum of a differentiable, possibly nonconvex, function plus a convex, possibly nondifferentiable, function. The key features of the proposed method are the definition of a suitable descent direction, based on the proximal operator associated to the convex part of the objective function, and an Armijo-like rule to determine the stepsize along this direction ensuring the sufficient decrease of the objective function. In this frame, we especially address the possibility of adopting a metric which may change at each iteration and an inexact computation of the proximal point defining the descent direction. For the more general nonconvex case, we prove that all limit points of the iterates sequence are stationary, while for convex objective functions we prove the convergence of the whole sequence to a minimizer, under the assumption that a minimizer exists. In the latter case, assuming also that the gradient of the smooth part of the objective function... A stochastic Forward-Backward algorithm with a constant step is studied. At each time step, this algorithm involves an independent copy of a couple of random maximal monotone operators. Defining a mean operator as a selection integral, the differential inclusion built from the sum of the two mean operators is considered. As a first result, it is shown that the interpolated process obtained from the iterates converges narrowly in the small step regime to the solution of this differential inclusion. In order to control the long term behavior of the iterates, a stability result is needed in addition. To this end, the sequence of the iterates is seen as a homogeneous Feller Markov chain whose transition kernel is parameterized by the algorithm step size. The cluster points of the Markov chains invariant measures in the small step regime are invariant for the semiflow induced by the differential inclusion. Conclusions regarding the long run behavior of the iterates for small steps are drawn. It is shown that when the sum of the mean operators is demipositive, the probabilities that the iterates are away from the set of zeros of this sum are small in Ces aro mean. The ergodic behavior of these iterates is studied as well. Applications of the proposed algorithm are considered. In particular, a detailed analysis of the random proximal gradient algorithm with constant step is performed. Successive quadratic approximations, or second-order proximal methods, are useful for minimizing functions that are a sum of a smooth part and a convex, possibly nonsmooth part that promotes regularization. Most analyses of iteration complexity focus on the special case of proximal gradient method, or accelerated variants thereof. There have been only a few studies of methods that use a second-order approximation to the smooth part, due in part to the difficulty of obtaining closed-form solutions to the subproblems at each iteration. In fact, iterative algorithms may need to be used to find inexact solutions to these subproblems. In this work, we present global analysis of the iteration complexity of inexact successive quadratic approximation methods, showing that an inexact solution of the subproblem that is within a fixed multiplicative precision of optimality suffices to guarantee the same order of convergence rate as the exact version, with complexity related in an intuitive way to the measure of inexactness. Our result allows flexible choices of the second-order term, including Newton and quasi-Newton choices, and does not necessarily require increasing precision of the subproblem solution on later iterations. For problems exhibiting a property related to strong convexity, the algorithms converge at global linear rates. For general convex problems, the convergence rate is linear in early stages, while the overall rate is O(1 k). For nonconvex problems, a first-order optimality criterion converges to zero at a rate of (O(1 k ) ). This paper analyzes the iteration-complexity of a quadratic penalty accelerated inexact proximal point method for solving linearly constrained nonconvex composite programs. More specifically, the objective function is of the form @math where @math is a differentiable function whose gradient is Lipschitz continuous and @math is a closed convex function with bounded domain. The method, basically, consists of applying an accelerated inexact proximal point method for solving approximately a sequence of quadratic penalized subproblems associated to the linearly constrained problem. Each subproblem of the proximal point method is in turn approximately solved by an accelerated composite gradient method. It is shown that the proposed scheme generates a @math -approximate stationary point in at most @math . Finally, numerical results showing the efficiency of the proposed method are also given.