Actividades

Juan Reutter, Departamento de Ciencia de la Computación, Pontificia Universidad Católica de Chile.

Miércoles 24 de agosto de 2022, 13 hrs. (Presencial en Auditorio San Agustín; Link Zoom disponible escribiendo a Esta dirección de correo electrónico está siendo protegida contra los robots de spam. Necesita tener JavaScript habilitado para poder verlo.)

ABSTRACT

The power of Graph Neural Networks (GNNs) is commonly measured in terms of their ability to separate graphs: a GNN is more powerful when it can recognize more graphs as being different. Studying this metric in GNNs helps in understanding the limitations of GNNs for graph learning tasks, but there are few general techniques for doing this, and most results in this direction are geared at specific GNN architectures.

In this talk I will review our recent work in studying the separation power of GNNs. Our approach is to view GNNs as expressions specified in procedural languages that describe the computations in the layers of the GNNs, and then analyze these expressions to obtain bounds on the separation power of said GNNs. As we see, this technique gives us an elegant way to easily obtain bounds on the separation power of GNNs in terms of the Weisfeiler-Leman (WL) tests, which have become the yardstick to measure the separation power of GNNs. If time permits, I will also review some of the by-products of our characterization, including connections to logic and approximation results for GNNs. 

Nishant Mehta, Department of Computer Science, University of Victoria.

Miércoles 10 de agosto de 2022, 13 hrs. (Vía Zoom, enlace a través del correo Esta dirección de correo electrónico está siendo protegida contra los robots de spam. Necesita tener JavaScript habilitado para poder verlo.)

ABSTRACT

I will begin by introducing an online learning problem motivated by group fairness considerations. It is standard in online learning to prove sublinear upper bounds on the regret, a key performance measure in online learning and online convex optimization. An alternative concept is a best-case lower bound — the largest improvement an algorithm can obtain relative to the single best action in hindsight. Best-case lower bounds have connections to fairness: it is known that best-case lower bounds are instrumental in obtaining algorithms for the popular decision-theoretic online learning (DTOL) setting that satisfy a notion of group fairness. A parallel motivation of this work is to better understand the adaptivity of a learning algorithm; while some algorithms provably exhibit certain types of adaptivity, we show that they are provably prohibited from obtaining another desirable form of adaptivity (related to what is known as the shifting regret). Our contributions are a general method to provide best-case lower bounds in Follow the Regularized Leader (FTRL) algorithms with time-varying regularizers, which we use to show that best-case lower bounds are often of the same order as existing upper regret bounds: this includes situations with a fixed learning rate, decreasing learning rates, and adaptive gradient methods. We also show that the popular linearized version of FTRL can attain negative linear regret and hence does not admit non-trivial best-case lower bounds in general.

This is joint work with Cristóbal Guzmán and Ali Mortazavi.

 Benjamín Palacios, Departamento de Matemáticas, Pontificia Universidad Católica de Chile.

Miércoles 15 de junio de 2022, 13 hrs. (Presencial en Auditorio Edificio San Agustín.)

ABSTRACT

Photoacoustic Tomography (PAT) is a promising hybrid medical imaging modality that is able to generate high-resolution and high-contrast images by exploiting the coupling of electromagnetic pulses (in the visible region) and ultrasound waves via de photoacoustic effect. The mathematical problem splits into two steps, one involving the inversion of boundary acoustic data to determine the initial source of waves, and the second step uses this internal information to retrieve optical properties of the medium and it is commonly known as Quantitative PAT.

In this talk, I will introduce the modality and focus on the ultrasound propagation component which is mathematically modeled as an inverse initial source problem for the wave equation. I will then discuss mathematical aspects of this inverse problem and present some recent theoretical results. The last part of the presentation will be devoted to addressing some open questions related to reconstruction methods and numerical implementations.

Pablo Barceló, Instituto de Ingeniería Matemática y Computacional, Pontificia Universidad Católica de Chile.

Miércoles 25 de mayo de 2022, 13 hrs. (Presencial en Auditorio Edificio San Agustín.)

ABSTRACT

In several computer science applications one encounters the following problem: Given two edge-labeled graphs G and H, how many homomorphic images of H can be found in G? Atserias, Grohe, and Marx developed a tight bound for this number, denoted #Hom(H,G), which is now known as the AGM bound. The bound relates #Hom(H,G) with the fractional edge covers of H in a very elegant and direct way. We will present a self-contained and simple proof of this result using Holder's inequality.