We propose a randomized algorithm with quadratic convergence rate for convex optimization problems with a selfconcordant, composite, strongly convex objective function. Our method is based on performing an approximate Newton step using a random projection of the Hessian. Our first contribution is to show that, at each iteration, the embedding dimension (or sketch size) can be as small as the effective dimension of the Hessian matrix. Leveraging this novel fundamental result, we design an algorithm with a sketch size proportional to the effective dimension and which exhibits a quadratic rate of convergence. This result dramatically improves on the classical linearquadraticmore »
Strong Metric (Sub)regularity of Karush–Kuhn–Tucker Mappings for Piecewise LinearQuadratic ConvexComposite Optimization and the Quadratic Convergence of Newton’s Method
This work concerns the local convergence theory of Newton and quasiNewton methods for convexcomposite optimization: where one minimizes an objective that can be written as the composition of a convex function with one that is continuiously differentiable. We focus on the case in which the convex function is a potentially infinitevalued piecewise linearquadratic function. Such problems include nonlinear programming, minimax optimization, and estimation of nonlinear dynamics with nonGaussian noise as well as many modern approaches to largescale data analysis and machine learning. Our approach embeds the optimality conditions for convexcomposite optimization problems into a generalized equation. We establish conditions for strong metric subregularity and strong metric regularity of the corresponding setvalued mappings. This allows us to extend classical convergence of Newton and quasiNewton methods to the broader class of nonfinite valued piecewise linearquadratic convexcomposite optimization problems. In particular, we establish local quadratic convergence of the Newton method under conditions that parallel those in nonlinear programming.
 Award ID(s):
 1514559
 Publication Date:
 NSFPAR ID:
 10187912
 Journal Name:
 Mathematics of Operations Research
 Volume:
 45
 Issue:
 3
 Page Range or eLocationID:
 1164 to 1192
 ISSN:
 0364765X
 Sponsoring Org:
 National Science Foundation
More Like this


We investigate the approximability of the following optimization problem. The input is an n× n matrix A=(Aij) with real entries and an originsymmetric convex body K⊂ ℝn that is given by a membership oracle. The task is to compute (or approximate) the maximum of the quadratic form ∑i=1n∑j=1n Aij xixj=⟨ x,Ax⟩ as x ranges over K. This is a rich and expressive family of optimization problems; for different choices of matrices A and convex bodies K it includes a diverse range of optimization problems like maxcut, Grothendieck/noncommutative Grothendieck inequalities, small set expansion and more. While the literature studied these specialmore »

Abstract This paper examines a number of extrapolation and acceleration methods and introduces a few modifications of the standard Shanks transformation that deal with general sequences. One of the goals of the paper is to lay out a general framework that encompasses most of the known acceleration strategies. The paper also considers the Anderson Acceleration (AA) method under a new light and exploits a connection with quasiNewton methods in order to establish local linear convergence results of a stabilized version of the AA method. The methods are tested on a number of problems, including a few that arise from nonlinearmore »

We propose a bootstrap‐based calibrated projection procedure to build confidence intervals for single components and for smooth functions of a partially identified parameter vector in moment (in)equality models. The method controls asymptotic coverage uniformly over a large class of data generating processes. The extreme points of the calibrated projection confidence interval are obtained by extremizing the value of the function of interest subject to a proper relaxation of studentized sample analogs of the moment (in)equality conditions. The degree of relaxation, or critical level, is calibrated so that the function of θ , not θ itself, is uniformly asymptotically covered withmore »

Abstract The goal of this study is to develop a new computed tomography (CT) image reconstruction method, aiming at improving the quality of the reconstructed images of existing methods while reducing computational costs. Existing CT reconstruction is modeled by pixelbased piecewise constant approximations of the integral equation that describes the CT projection data acquisition process. Using these approximations imposes a bottleneck model error and results in a discrete system of a large size. We propose to develop a contentadaptive unstructured grid (CAUG) based regularized CT reconstruction method to address these issues. Specifically, we design a CAUG of the image domainmore »