Towards a theory of long-step algorithms for large scale optimization
Abstract
In this proposal we aim at addressing the step-size issue for first-order methods at a theoretical level. Our motivation comes from problems such as the phase recovery problem, Poisson inverse problems, or nonnegative matrix factorization. As a general guideline, we intend to understand how the geometry and the structure of a problem can be used to devise long-steps methods. We shall work according to two complementary approaches:1. The geometric approach. Here Lipschitz continuity of the gradient, and thus the length of stepsizes, are seen through the convexity property of some kernel function encoding the geometric features of the objective. This very fruitful approach allows one to choose non vanishing step-sizes for very steep functions arising in applications like for instance the log functions inherent to Poisson inverse problems.2. The decomposition approach. This technique is based on a preliminary reformulation of the problem as a composite problem involving “simple functions". Then, by using highly decomposed local models and a protocol we call multiprox, we design new classes of methods with in-built step-sizes. Complexity, acceleration, and efficiency of these methods will be studied in depth with expected application to signal processing and machine learning.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Jul 11, 2018
- Source ID
- FA95501810226
Entities
People
- Jerome Bolte
Organizations
- Air Force Office of Scientific Research
- Toulouse School of Economics
- United States Air Force