ResearchOptimized firstorder methods for convex minimizationFirstorder algorithms are favorable when solving largescale optimization problems, since their periteration computational cost mildly depends on the problem dimension. In particular, Nesterov's fast gradient method (FGM) is widely used as it is computationally efficient and achieves the optimal rate for the decrease of smooth convex functions, where denotes the number of iterations. In search of the bestperforming firstorder methods [Y. Drori and M. Teboulle, Math. Program., 2016], two papers below propose and discuss a new firstorder method, named an optimized gradient method (OGM), that is computationally as efficient as FGM and has a worstcase cost function rate that is twice smaller than that of FGM. Recently this OGM has been found to exactly achieve the optimal worstcase cost function rate of firstorder methods for solving (largedimensional) smooth convex problems [Y. Drori, J. Complexity, 2017].
The paper below generalizes the formulation of OGM and analyzes its worstcase rates for both the cost function and the gradient. This paper then proposes a new algorithm called OGMOG (OG for optimized over gradient) that has the best known analytical worstcase rate on the gradient norm decrease among nonadaptivestep firstorder methods for smooth convex minimization.
The following paper somewhat extends the above approach for the nonsmooth composite convex problems.
Adaptive restart of the optimized gradient method (OGM)Adpative restart of FGM [B. Odonoghue and E. Candes, Found. Comp. Math., 2015] has been found useful for improving the worstcase rate when the function parameter is unknown or when the iterates of the algorithm enter a locally strongly convex region. Building upon the success of accelerating FGM, the paper below investigates similar heuristic acceleration of OGM.
Fast optimization methods for statistical Xray CT reconstructionRadiation exposure to patients from computed tomography (CT) imaging has been criticized for its increased risk of cancer. Statistical Xray CT image reconstruction can provide diagnostic quality images, unlike the conventional filtered backprojection methods, from safer lowdose CT scans (yielding very noisy measurement data). However, statistical reconstruction requires very long computation time, and the following papers below are the efforts to accelerate this statistical reconstruction and thus potentially reduce the dose usage for the public health. Each work is based on the distributed computing, Nesterov's FGM, and majorizationminimization, with the combination of ordered subsets technique (that is an instance of incremental/stochastic gradient methods for tomography problems).
The above works are now patented jointly with General Electric (GE) as below.
