Antonio Silveti-Falls ; Cesare Molinari ; Jalal Fadili - Inexact and Stochastic Generalized Conditional Gradient with Augmented Lagrangian and Proximal Step

jnsao:6480 - Journal of Nonsmooth Analysis and Optimization, September 1, 2021, Volume 2 - https://doi.org/10.46298/jnsao-2021-6480
Inexact and Stochastic Generalized Conditional Gradient with Augmented Lagrangian and Proximal Step

Authors: Antonio Silveti-Falls ; Cesare Molinari ; Jalal Fadili

In this paper we propose and analyze inexact and stochastic versions of the CGALP algorithm developed in [25], which we denote ICGALP , that allow for errors in the computation of several important quantities. In particular this allows one to compute some gradients, proximal terms, and/or linear minimization oracles in an inexact fashion that facilitates the practical application of the algorithm to computationally intensive settings, e.g., in high (or possibly infinite) dimensional Hilbert spaces commonly found in machine learning problems. The algorithm is able to solve composite minimization problems involving the sum of three convex proper lower-semicontinuous functions subject to an affine constraint of the form Ax = b for some bounded linear operator A. Only one of the functions in the objective is assumed to be differentiable, the other two are assumed to have an accessible proximal operator and a linear minimization oracle. As main results, we show convergence of the Lagrangian values (so-called convergence in the Bregman sense) and asymptotic feasibility of the affine constraint as well as strong convergence of the sequence of dual variables to a solution of the dual problem, in an almost sure sense. Almost sure convergence rates are given for the Lagrangian values and the feasibility gap for the ergodic primal variables. Rates in expectation are given for the Lagrangian values and the feasibility gap subsequentially in the pointwise sense. Numerical experiments verifying the predicted rates of convergence are shown as well.


Volume: Volume 2
Section: Original research articles
Published on: September 1, 2021
Submitted on: May 15, 2020
Keywords: Stochastic composite minimization,Proximal mapping,Augmented Lagrangian,Conditional gradient,Moreau envelope,[MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC],[STAT.ML]Statistics [stat]/Machine Learning [stat.ML]


Share

Consultation statistics

This page has been seen 33 times.
This article's PDF has been downloaded 14 times.