2021/05/15 by Jonathan Lacotte, Yifei Wang, Lacotte, Jonathan +3 · 1 citation
Computer Science · Engineering · #Stochastic Gradient Optimization Techniques #Sparse and Compressive Sensing Techniques #Face and Expression Recognition
paper · pdf · doi:10.48550/arxiv.2105.07291
We propose a randomized algorithm with quadratic convergence rate for convex\noptimization problems with a self-concordant, composite, strongly convex\nobjective function. Our method is based on performing an approximate Newton\nstep using a random projection of the Hessian. Our first contribution is to\nshow that, at each iteration, the embedding dimension (or sketch size) can be\nas small as the effective dimension of the Hessian matrix. Leveraging this\nnovel fundamental result, we design an algorithm with a sketch size\nproportional to the effective dimension and which exhibits a quadratic rate of\nconvergence. This result dramatically improves on the classical\nlinear-quadratic convergence rates of state-of-the-art sub-sampled Newton\nmethods. However, in most practical cases, the effective dimension is not known\nbeforehand, and this raises the question of how to pick a sketch size as small\nas the effective dimension while preserving a quadratic convergence rate. Our\nsecond and main contribution is thus to propose an adaptive sketch size\nalgorithm with quadratic convergence rate and which does not require prior\nknowledge or estimation of the effective dimension: at each iteration, it\nstarts with a small sketch size, and increases it until quadratic progress is\nachieved. Importantly, we show that the embedding dimension remains\nproportional to the effective dimension throughout the entire path and that our\nmethod achieves state-of-the-art computational complexity for solving convex\noptimization programs with a strongly convex component.\n