David Martínez-Rubio

activity

20202026

most citedGlobal Riemannian Acceleration in Hyperbolic and Spherical Spaces

4 citations · 7 across the 19 of their papers we have counts for

collaborators

23 papers

math.OC2026

Facial distance and diameter

Antoine Deza, David Martínez-Rubio, Javier Peña +1

The facial distance of a polytope, equivalently its pyramidal width, is a geometric condition measure that appears in the convergence bounds for Frank--Wolfe algorithms. Peña and W…

math.OC2026

Near-Optimal Acceleration for Smooth $ℓ_{p}$ / $ℓ_{q}$ Nondual Convex First-Order Oracle Optimization

David Martínez-Rubio, Brian Bullins, Cristóbal Guzmán +1

We study the optimization of convex objectives with $(L, κ - 1)$ -Hölder-continuous gradients in $ℓ_{q}$ over $R B_{p}^{d}$ , $1 < κ \leq 2$ . (MG26) provides selectors with a movement bound fo…

math.OC2026

Stable Movement for Nondual Lipschitz Convex Optimization: Efficiency and Nearly Optimal Oracle Rates

David Martínez-Rubio, Cristóbal Guzmán

We study efficient algorithms for realizing the first-order oracle complexity of optimization of $G$ -Lipschitz convex functions with respect to the $ℓ_{q}$ -norm over an $\ell_{p…

math.OC2026

The First-Order Oracle Complexity of Lipschitz Convex Optimization in Nondual Settings

David Martínez-Rubio, Brian Bullins, Cristóbal Guzmán +1

We study first-order black-box convex optimization over an $ℓ_{p}$ -ball for objectives Lipschitz in the $ℓ_{q}$ -norm, solving in the affirmative the nonsmooth version of the COLT…

math.OC2026

Oracle Complexity of Stochastic Fixed-Point Equations with Nonexpansive Maps

Jelena Diakonikolas, Cristóbal Guzmán, David Martínez-Rubio

We study the oracle complexity of computing a point with small fixed-point residual $∥ T (x) - x ∥ \leq ε$ , for a general norm $∥ \cdot ∥$ and a self-map $T$ of a compact convex set.…

math.OC2026

Optimal Gradient-Norm Minimization in Non-Euclidean Hölder-Smooth Convex Optimization

Nico Pelleriti, Maryam Shiran, David Martínez-Rubio +2

Minimizing gradients of a convex function is an important problem across optimization and learning tasks. The gradient provides a directly computable certificate of approximate sta…

math.OC2026

Complexity of Classical Acceleration for $ℓ_{1}$ -Regularized PageRank

Kimon Fountoulakis, David Martínez-Rubio

We study the degree-weighted work required to compute $ℓ_{1}$ -regularized PageRank using the standard accelerated proximal-gradient method (FISTA). For non-accelerated methods (IS…

cs.LG2025

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…

math.OC2025

Smooth Quasar-Convex Optimization with Constraints

David Martínez-Rubio

Quasar-convex functions form a broad nonconvex class with applications to linear dynamical systems, generalized linear models, and Riemannian optimization, among others. Current ne…

math.OC2025

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…

math.OC2025

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…

math.OC2025

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…

math.OC2025

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…

cs.LG2024

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 $p$ -norms, $p \geq 1$ . We propos…

math.OC2024

Non-Euclidean High-Order Smooth Convex Optimization

Juan Pablo Contreras, Cristóbal Guzmán, David Martínez-Rubio

We develop algorithms for the optimization of convex objectives that have Hölder continuous $q$ -th derivatives by using a $q$ -th order oracle, for any $q \geq 1$ . Our algorithms wo…

math.OC2024

Convergence and Trade-Offs in Riemannian Gradient Descent and Riemannian Proximal Point

David Martínez-Rubio, Christophe Roux, Sebastian Pokutta

In this work, we analyze two of the most fundamental algorithms in geodesically convex optimization: Riemannian gradient descent and (possibly inexact) Riemannian proximal point. W…

math.OC2023

Strong Convexity of Sets in Riemannian Manifolds

Damien Scieur, David Martínez-Rubio, Thomas Kerdreux +2

Curvature properties of convex objects, such as strong convexity, are important in designing and analyzing convex optimization algorithms in the Hilbertian or Riemannian settings.…

math.OC2023

Open Problem: Polynomial linearly-convergent method for geodesically convex optimization?

Christopher Criscitiello, David Martínez-Rubio, Nicolas Boumal

Let $f : M \to R$ be a Lipschitz and geodesically convex function defined on a $d$ -dimensional Riemannian manifold $M$ . Does there exist a first-o…

math.OC2023★ 1 cited

Accelerated Methods for Riemannian Min-Max Optimization Ensuring Bounded Geometric Penalties

David Martínez-Rubio, Christophe Roux, Christopher Criscitiello +1

In this work, we study optimization problems of the form $min_{x} max_{y} f (x, y)$ , where $f (x, y)$ is defined on a product Riemannian manifold $M \times N$ and i…

math.OC2023★ 1 cited

Accelerated and Sparse Algorithms for Approximate Personalized PageRank and Beyond

David Martínez-Rubio, Elias Wirth, Sebastian Pokutta

It has recently been shown that ISTA, an unaccelerated optimization method, presents sparse updates for the $ℓ_{1}$ -regularized personalized PageRank problem, leading to cheap ite…

math.OC2022★ 1 cited

Accelerated Riemannian Optimization: Handling Constraints with a Prox to Bound Geometric Penalties

David Martínez-Rubio, Sebastian Pokutta

We propose a globally-accelerated, first-order method for the optimization of smooth and (strongly or not) geodesically-convex functions in a wide class of Hadamard manifolds. We a…

math.OC2021

Fast Algorithms for Packing Proportional Fairness and its Dual

Francisco Criado, David Martínez-Rubio, Sebastian Pokutta

The proportional fair resource allocation problem is a major problem studied in flow control of networks, operations research, and economic theory, where it has found numerous appl…

math.OC2020★ 4 cited

Global Riemannian Acceleration in Hyperbolic and Spherical Spaces

David Martínez-Rubio

We further research on the accelerated optimization phenomenon on Riemannian manifolds by introducing accelerated global first-order methods for the optimization of $L$ -smooth and…

Facial distance and diameter

Near-Optimal Acceleration for Smooth ℓp​ / ℓq​ Nondual Convex First-Order Oracle Optimization

Stable Movement for Nondual Lipschitz Convex Optimization: Efficiency and Nearly Optimal Oracle Rates

The First-Order Oracle Complexity of Lipschitz Convex Optimization in Nondual Settings

Oracle Complexity of Stochastic Fixed-Point Equations with Nonexpansive Maps

Optimal Gradient-Norm Minimization in Non-Euclidean Hölder-Smooth Convex Optimization

Complexity of Classical Acceleration for ℓ1​-Regularized PageRank

Neural Sum-of-Squares: Certifying the Nonnegativity of Polynomials with Transformers

Smooth Quasar-Convex Optimization with Constraints

Linear Convergence of the Frank-Wolfe Algorithm over Product Polytopes

Beyond Short Steps in Frank-Wolfe Algorithms

Implicit Riemannian Optimism with Applications to Min-Max Problems

Secant Line Search for Frank-Wolfe Algorithms

Black-Box Uniform Stability for Non-Euclidean Empirical Risk Minimization

Non-Euclidean High-Order Smooth Convex Optimization

Convergence and Trade-Offs in Riemannian Gradient Descent and Riemannian Proximal Point

Strong Convexity of Sets in Riemannian Manifolds

Open Problem: Polynomial linearly-convergent method for geodesically convex optimization?

Accelerated Methods for Riemannian Min-Max Optimization Ensuring Bounded Geometric Penalties

Accelerated and Sparse Algorithms for Approximate Personalized PageRank and Beyond

Accelerated Riemannian Optimization: Handling Constraints with a Prox to Bound Geometric Penalties

Fast Algorithms for Packing Proportional Fairness and its Dual

Global Riemannian Acceleration in Hyperbolic and Spherical Spaces

Near-Optimal Acceleration for Smooth $ℓ_{p}$ / $ℓ_{q}$ Nondual Convex First-Order Oracle Optimization

Complexity of Classical Acceleration for $ℓ_{1}$ -Regularized PageRank