Hybrid Stochastic Gradient Descent Algorithms forStochastic Nonconvex Optimization

We introduce a hybrid stochastic estimator to design stochastic gradient algorithms for solving stochastic optimization problems. Such a hybrid estimator is a convex combination of two existing biased and unbiased estimators and leads to some useful property on its variance. We limit our consideration to a hybrid SARAH-SGD for nonconvex expectation problems. However, our idea … Read more

Non-Stationary First-Order Primal-Dual Algorithms with Fast Convergence Rates

In this paper, we propose two novel non-stationary first-order primal-dual algorithms to solve nonsmooth composite convex optimization problems. Unlike existing primal-dual schemes where the parameters are often fixed, our methods use pre-defined and dynamic sequences for parameters. We prove that our first algorithm can achieve O(1/k) convergence rate on the primal-dual gap, and primal and … Read more

ProxSARAH: An Efficient Algorithmic Framework for Stochastic Composite Nonconvex Optimization

We propose a new stochastic first-order algorithmic framework to solve stochastic composite nonconvex optimization problems that covers both finite-sum and expectation settings. Our algorithms rely on the SARAH estimator introduced in (Nguyen et al., 2017a) and consist of two steps: a proximal gradient and an averaging step making them different from existing nonconvex proximal-type algorithms. … Read more

Proximal Alternating Penalty Algorithms for Nonsmooth Constrained Convex Optimization

We develop two new proximal alternating penalty algorithms to solve a wide range class of constrained convex optimization problems. Our approach mainly relies on a novel combination of the classical quadratic penalty, alternating, Nesterov’s acceleration, and homotopy techniques. The first algorithm is designed to solve generic and possibly nonsmooth constrained convex problems without requiring any … Read more

Non-stationary Douglas-Rachford and alternating direction method of multipliers: adaptive stepsizes and convergence

We revisit the classical Douglas-Rachford (DR) method for finding a zero of the sum of two maximal monotone operators. Since the practical performance of the DR method crucially depends on the stepsizes, we aim at developing an adaptive stepsize rule. To that end, we take a closer look at a linear case of the problem … Read more

Sieve-SDP: a simple facial reduction algorithm to preprocess semidefinite programs

We introduce Sieve-SDP, a simple algorithm to preprocess semidefinite programs (SDPs). Sieve-SDP belongs to the class of facial reduction algorithms. It inspects the constraints of the problem, deletes redundant rows and columns, and reduces the size of the variable matrix. It often detects infeasibility. It does not rely on any optimization solver: the only subroutine … Read more

Self-concordant inclusions: A unified framework for path-following generalized Newton-type algorithms

We study a class of monotone inclusions called “self-concordant inclusion” which covers three fundamental convex optimization formulations as special cases. We develop a new generalized Newton-type framework to solve this inclusion. Our framework subsumes three schemes: full-step, damped-step and path-following methods as specific instances, while allows one to use inexact computation to form generalized Newton … Read more

Generalized Self-Concordant Functions: A Recipe for Newton-type Methods

We study the smooth structure of convex functions by generalizing a powerful concept so-called \textit{self-concordance} introduced by Nesterov and Nemirovskii in the early 1990s to a broader class of convex functions, which we call \textit{generalized self-concordant functions}. This notion allows us to develop a unified framework for designing Newton-type methods to solve convex optimization problems. … Read more

A simple preprocessing algorithm for semidefinite programming

We propose a very simple preprocessing algorithm for semidefinite programming. Our algorithm inspects the constraints of the problem, deletes redundant rows and columns in the constraints, and reduces the size of the variable matrix. It often detects infeasibility. Our algorithm does not rely on any optimization solver: the only subroutine it needs is Cholesky factorization, … Read more

An optimal first-order primal-dual gap reduction framework for constrained convex optimization

We introduce an analysis framework for constructing optimal first-order primal-dual methods for the prototypical constrained convex optimization tem- plate. While this class of methods offers scalability advantages in obtaining nu- merical solutions, they have the disadvantage of producing sequences that are only approximately feasible to the problem constraints. As a result, it is theoretically challenging … Read more