6 papers
Neural Sum-of-Squares: Certifying the Nonnegativity of Polynomials with Transformers
Nico Pelleriti, Christoph Spiegel, Shiwei Liu +3
Certifying nonnegativity of polynomials is a well-known NP-hard problem with direct applications spanning non-convex optimization, control, robotics, and beyond. A sufficient condi…
Linear Convergence of the Frank-Wolfe Algorithm over Product Polytopes
Gabriele Iommazzo, David Martínez-Rubio, Francisco Criado +2
We study the linear convergence of Frank-Wolfe algorithms over product polytopes. We analyze two condition numbers for the product polytope, namely the \emph{pyramidal width} and t…
Beyond Short Steps in Frank-Wolfe Algorithms
David Martínez-Rubio, Sebastian Pokutta
We introduce novel techniques to enhance Frank-Wolfe algorithms by leveraging function smoothness beyond traditional short steps. Our study focuses on Frank-Wolfe algorithms with s…
Implicit Riemannian Optimism with Applications to Min-Max Problems
Christophe Roux, David Martínez-Rubio, Sebastian Pokutta
We introduce a Riemannian optimistic online learning algorithm for Hadamard manifolds based on inexact implicit updates. Unlike prior work, our method can handle in-manifold constr…
Secant Line Search for Frank-Wolfe Algorithms
Deborah Hendrych, Mathieu Besançon, David Martínez-Rubio +1
We present a new step-size strategy based on the secant method for Frank-Wolfe algorithms. This strategy, which requires mild assumptions about the function under consideration, ca…
Black-Box Uniform Stability for Non-Euclidean Empirical Risk Minimization
Simon Vary, David Martínez-Rubio, Patrick Rebeschini
We study first-order algorithms that are uniformly stable for empirical risk minimization (ERM) problems that are convex and smooth with respect to -norms, . We propos…