Timezone: »

 
Poster
A first-order primal-dual method with adaptivity to local smoothness
Maria-Luiza Vladarean · Yura Malitsky · Volkan Cevher

Tue Dec 07 08:30 AM -- 10:00 AM (PST) @
in Poster Session 1 »
We consider the problem of finding a saddle point for the convex-concave objective $\min_x \max_y f(x) + \langle Ax, y\rangle - g^*(y)$, where $f$ is a convex function with locally Lipschitz gradient and $g$ is convex and possibly non-smooth. We propose an adaptive version of the Condat-Vũ algorithm, which alternates between primal gradient steps and dual proximal steps. The method achieves stepsize adaptivity through a simple rule involving $\|A\|$ and the norm of recently computed gradients of $f$. Under standard assumptions, we prove an $\mathcal{O}(k^{-1})$ ergodic convergence rate. Furthermore, when $f$ is also locally strongly convex and $A$ has full row rank we show that our method converges with a linear rate. Numerical experiments are provided for illustrating the practical performance of the algorithm.
Keywords: Optimization

Author Information

Maria-Luiza Vladarean (Ecole Polytechnique Federale de Lausanne)

My fields of expertise are convex, non-convex and stochastic first-order methods. I'm also interested in the properties of ODE discretizations (specifically the pair GF/GD) and the connections between dynamical systems and optimization algorithms. I graduated with a Masters in Computer Science and a minor in Biocomputing from EPFL in 2016. I subsequently spent two years in the industry working as a Software Engineer at Amazon Video in London. At the end of 2018 I returned to EPFL to start my PhD in mathematical optimization, for which I've been lucky to receive the guidance of Prof. Nicolas Flammarion.

Yura Malitsky (Linköping University)
Volkan Cevher (EPFL)

More from the Same Authors