Generalized conditional subgradient and generalized mirror descent: duality, convergence, and symmetry

By Javier F. Peña. 2019

6 citations recorded by the source corpus.

We provide new insight into a {\em generalized conditional subgradient} algorithm and a {\em generalized mirror descent} algorithm for the convex minimization problem \[ \min_x \; \{f(Ax) + h(x)\}.\] As Bach showed in [{\em SIAM J. Optim.}, 25 (2015), pp. 115--129], applying either of these two algorithms to this problem is equivalent to applying the other one to its Fenchel dual. We leverage this duality relationship to develop new upper bounds and convergence results for the gap between the primal and dual iterates generated by these two algorithms. We also propose a new {\em primal-dual hybrid} algorithm that combines features of the conditional subgradient and mirror descent algorithms to solve the primal and dual problems in a symmetric fashion. Our algorithms and main results rely only on the availability of computable oracles for $\partial f$ and $\partial h^*$, and for $A$ and $A^*$.

Subfields: Algebra and Number Theory, Computational Theory and Mathematics, Numerical Analysis, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Algebra and Number Theory

In Computational Theory and Mathematics

In Numerical Analysis

In Optimization & Training

Citations in the corpus

Affine Invariant Analysis of Frank-Wolfe on Strongly Convex Sets (2020, methodology): “This has then been the basis for works extending the accelerated convergence analysis to non-smooth or non-strongly convex functions [Pena 2019; Gutman et al. 2020], which then explore new structural assumptions on f .”