AA5 – Variational Problems in Data-Driven Applications


AA5-1 (was EF1-14)

Sparsity and Sample-Size Efficiency in Structured Learning

Project Heads

Sebastian Pokutta

Project Members

David Martínez-Rubio

Project Duration

01.01.2022 − 31.12.2023

Located at



In this project, we will investigate the properties of sparse solutions induced through learning algorithms that promote sparsity. In particular, we want to look at sparsity as being a consequence of model and the implicit sparsity bias of the chosen optimization method. A related question is sample-size efficiency, as these algorithms also tend to have a much higher sample-size efficiency by implicitly restricting the degrees of freedom. Another example of potential sparsity exploitation is PageRank, we will attempt to obtain state of the art PageRank optimization algorithms whose running time scales with the sparsity of the solution, rather than depending on the whole graph. Riemannian optimization is another related field that exploits the geometry of Riemannian constraints to have iterates intrinsically in these manifolds, that are lower dimensional than the embedding space.

We will also look at algorithms that are able to quickly approximate the optimal fair resource allocation, given a notion of fairness in some problems. For instance, under the fairness axioms of Pareto optimality, independence of irrelevant alternative, affine invariance and symmetry, the optimal fair allocation can be posed as an optimization problem. This direction of research concerns the study of finding allocations that approximate this or other fair allocations efficiently.

Related Publications

Produced by this project:

  1. Martínez-Rubio, D., Wirth, E., and Pokutta, S. (2023). Accelerated and Sparse Algorithms for Approximate Personalized PageRank and Beyond. Proceedings of Annual Workshop on Computational Learning Theory. [arXiv]
  2. Martínez-Rubio, D., and Pokutta, S. (2023). Accelerated Riemannian Optimization: Handling Constraints with a Prox to Bound Geometric Penalties. Proceedings of Annual Workshop on Computational Learning Theory. [arXiv]
  3. Martínez-Rubio, D., Roux, C., Criscitiello, C., and Pokutta, S. (2022). Accelerated Riemannian Min-Max Optimization Ensuring Bounded Geometric Penalties. [arXiv]
  4. Criado, F., Martínez-Rubio, D., and Pokutta, S. (2022). Fast Algorithms for Packing Proportional Fairness and Its Dual. Proceedings of Conference on Neural Information Processing Systems. (in collaboration with AA3-7) [arXiv]