Information Retrieval Under Network Uncertainty: Robust Internet Ranking

Internet ranking algorithms play a crucial role in information technologies and numerical analysis due to their efficiency in high dimensions and wide range of possible applications, including scientometrics and systemic risk in finance (SinkRank, DebtRank, etc.). The traditional approach to internet ranking goes back to the seminal work of Sergey Brin and Larry Page, who developed the initial method PageRank (PR) in order to rank websites in search engine results. Recent works have studied robust reformulations of the PageRank model for the case when links in the network structure may vary; that is, some links may appear or disappear influencing the transportation matrix defined by the net-work structure. We make a further step forward, allowing the network to vary not only in links, but also in the number of nodes. We focus on growing network structures and pro-pose a new robust formulation of the PageRank problem for uncertain networks with fixed growth rate. Defining the robust PageRank in terms of a nonconvex optimization problem, we bound our formulation from above by a convex but nonsmooth optimization problem. Driven by the approximation quality, we analyze the resulting optimality gap theoretically and demonstrate cases for its reduction. In the numerical part of the article, we propose some techniques which allow us to obtain the solution efficiently for middle-size networks avoiding all nonsmooth points. Furthermore, we propose a coordinate-wise descent method with near-optimal step size and address high-dimensional cases using multino-mial transition probabilities. We analyze the impact of the network growth on ranking and numerically assess the approximation quality using real-world data sets on movie reposito-ries and on journals on computational complexity.

Scalable Convex Optimization Methods for Semidefinite Programming

Alp Yurtsever

With the ever-growing data sizes along with the increasing complexity of the modern problem formulations, contemporary applications in science and engineering impose heavy computational and storage burdens on the optimization algorithms. As a result, there is a recent trend where heuristic approaches with unverifiable assumptions are overtaking more rigorous, conventional methods at the expense of robustness and reproducibility. My recent research results show that this trend can be overturned when we jointly exploit dimensionality reduction and adaptivity in optimization at its core. I contend that even the classical convex optimization did not reach yet its limits of scalability. Many applications in signal processing and machine learning cast a fitting problem from limited data, introducing spatial priors to be able to solve these otherwise ill-posed problems. Data is small, the solution is compact, but the search space is high in dimensions. These problems clearly suffer from the wasteful use of storage resources by the classical optimization algorithms. This problem is prevalent. Storage is a critical bottleneck that prevents us from solving many important large-scale optimization problems. For example, semidefinite programs (SDP) often have low-rank solutions. However, SDP algorithms require us to store a matrix decision variable in the ambient dimensions. This dissertation presents a convex optimization paradigm which makes it possible to solve trillion dimensional SDP relaxations to combinatorial decision problems on a regular personal computer. The key idea is to use an optimization procedure that performs compact updates, and to maintain only a small sketch of the decision variable. Once the iterations terminate, we can recover an approximate solution from the information stored in this sketch. We start by formalizing this idea for a model problem with low-rank solutions. Based on the classical conditional gradient method, we propose the first convex optimization algorithm with optimal storage guarantees for this model problem. Then, we develop and describe the key ingredients to extend our results for a broader set of problems, SDP in particular. SDP formulations are key in signal processing, machine learning, and other engineering applications. By greatly enhancing the scalability of optimization algorithms for solving SDP formulations, we can potentially unlock new results in important scientific applications.

EPFL2019

An Accelerated First-Order Method for Non-convex Optimization on Manifolds

Nicolas Boumal, Christopher Arnold Criscitiello

We describe the first gradient methods on Riemannian manifolds to achieve accelerated rates in the non-convex case. Under Lipschitz assumptions on the Riemannian gradient and Hessian of the cost function, these methods find approximate first-order critical points faster than regular gradient descent. A randomized version also finds approximate second-order critical points. Both the algorithms and their analyses build extensively on existing work in the Euclidean case. The basic operation consists in running the Euclidean accelerated gradient descent method (appropriately safe-guarded against non-convexity) in the current tangent space, then moving back to the manifold and repeating. This requires lifting the cost function from the manifold to the tangent space, which can be done for example through the Riemannian exponential map. For this approach to succeed, the lifted cost function (called the pullback) must retain certain Lipschitz properties. As a contribution of independent interest, we prove precise claims to that effect, with explicit constants. Those claims are affected by the Riemannian curvature of the manifold, which in turn affects the worst-case complexity bounds for our optimization algorithms.

SPRINGER2022

One dimensional and multiscale models for blood flow circulation

The aim of this work is to provide mathematically sound and computationally effective tools for the numerical simulation of the interaction between fluid and structures as occurring, for instance, in the simulation of the human cardiovascular system. This problem is global, in the sense that local changes can modify the solution far away. From the point of view of computing and modelling this calls for the use of multiscale methods, where simplified models are used to treat the global problem leaving to more accurate models the local description. Moreover it is characterised by the appearance of pressure waves inside the vessels. In large arteries the vessel wall dynamics can be described by a thin elastic membrane model (Navier equation) while the fluid motion can be represented by the Navier-Stokes equations for incompressible Newtonian fluids. Unfortunately, given the high levels of details furnished by this model, its computational complexity is dramatically high. Therefore reduced models have been developed. In particular, one-dimensional models, originally introduced by Euler, seem to be appropriate for the study in the time-space domain of pressure wave propagation induced by the interaction between the fluid and the vessel wall in the arterial tree. These reduced models are obtained after integrating the Navier-Stokes equations over a vessel section, supposed to be circular, and assuming an algebraic wall law to describe the relationship between pressure and wall deformation. They can be used in place of the more complex three dimensional fluid-structure models or in cooperation with them (multiscale approach). The first part of this work deals with one dimensional models. A reduced 1D model taken from literature is presented and analysed. Some extensions of the basic model, in particular with respect to vessel wall law (generalised string model) and more complex geometries (bifurcated and curved arteries), are also considered. Numerical schemes are proposed and some numerical results are presented. In the second part of this thesis we focus on a multiscale model. We consider a 55 arterial tree, described by the 1D model, coupled with lumped parameter models for heart and capillaries. In particular, specific attention has been devoted to the coupling between the left ventricle and the arterial system, whose physiopathological relevance is well known. This mathematical model gives good results in numerical tests and is able to describe the relevant features of the pressure wave propagation and reflections within the arterial system.

EPFL2004

Scalable Convex Optimization Methods for Semidefinite Programming

Alp Yurtsever

EPFL2019

One dimensional and multiscale models for blood flow circulation

EPFL2004