114:00 — Improved L-BFGS Methods for Large-Scale Unconstrained Optimization

New techniques for modifying the limited memory L-BFGS method for large-scale unconstrained optimization will be considered. They modify the L-BFGS update based on testing appropriate conditions in a sense to be defined. One technique reduces the number of the BFGS updates without destroying the quality of the L-BFGS Hessian. In another technique, the difference in gradients of the objective function, which appears in the BFGS updating formula, is modified by certain formulae whenever necessary so that a sufficient positive curvature condition is satisfied. A possible combination of the best features of the above two techniques will be stated as one for the L-BFGS method. Numerical results will be described to show that the proposed techniques improve the performance of the L-BFGS method substantially in several cases.

214:30 — A Decentralized Primal-Dual Method with Quasi-Newton Tracking

  • Liping Wang, Nanjing University of Aeronautics And Astronautics

This talk considers the decentralized optimization problem of minimizing a finite sum of strongly convex and twice continuously differentiable functions over a fixed-connected undirected network. A fully decentralized primal-dual method (DPDM) and its generalization (GDPDM), which allows for multiple primal steps per iteration, are proposed. In our method, both primal and dual updates use second-order information while Hessian approximations are constructed by simple algebraic calculations and at most matrix-vector products. Specifically, the primal update combines the single loop Jacobi with the BFGS method for efficient computation and distributed communication. The dual update newly embodies a second-order correction built with a new dual gradient variation with Barzilai-Borwein (BB) stepsize. Additionally, on each node, the local direction asymptotically approaches the centralized quasi-Newton direction. Under some mild assumptions, decentralized primal-dual method (DPDM) and its generation (GDPDM) are shown to have a global linear convergence rate for solving strongly convex decentralized optimization problems. Numerical results on linear regression problem illustrate that GDPDM is less impacted by deterioration of condition number of the objective function than existed methods. The numerical behavior on logistic regression demonstrates progressiong perfomance of decentralized primal-dual method in iterative convergence as well as distributed communication.

315:00 — ** MOVED TO FRIDAY AM REMOTE SESSION ** Group SLOPE Penalized Low-Rank Tensor Regression

We aim to seek a selection and estimation procedure for a class of tensor regression problems with multivariate covariates and matrix responses, which can provide theoretical guarantees for model selection in finite samples. Considering the frontal slice sparsity and low-rankness inherited in the coefficient tensor, we formulate the regression procedure as a group SLOPE penalized low-rank tensor optimization problem based on an orthogonal decomposition, namely TgSLOPE. This procedure provably controls the newly introduced tensor group false discovery rate (TgFDR), provided that the predictor matrix is column orthogonal. Moreover, we propose conditions to guarantee the global identifiability of the coefficient tensor to be estimated based on the so-called Kruskal rank, and establish the asymptotically minimax convergence with respect to the TgSLOPE estimate risk. For efficient problem resolution, we equivalently transform the TgSLOPE problem into a difference-of-convex (DC) program with the level-coercive objective function. This allows us to solve the reformulation problem of TgSLOPE by an efficient proximal DC algorithm (DCA) with global convergence, provided that the predictor matrix is full column rank. Numerical studies conducted both on synthetic data and a real human brain connection data illustrate the efficacy of the proposed TgSLOPE estimation procedure.

415:30 — Revisit Iterative Complexity of Some Projection Methods for Monotone Linear Variational Inequalities

For monotone linear variational inequality problems, projection methods play an important role, due to its low computational cost when the projection onto the set is simple. Though its global convergence is well understood, its iteration complexity is established until the recent work of Chen, Fu, He and Yuan (Journal of Optimization Theory and Applications, 2017). While the non-ergodic complexity is measured by the natural residual, the ergodic complexity is measured by the restricted dual gap function. Moreover, the non-ergodic complexity is measured with the best case (the minimal of the iterate), and we are more interest in the last iterate. In this paper, we give a simple proof of the ergodic complexity measured by the natural residual, and the non-ergodic complexity of the last iterate (for Algorithm-I). Under some additional conditions, we also presented their linear rate of convergence.