[ABE-L] COLMEA - 22 de novembro - PUC-Rio

[Maria Eulalia Vares]

Prezados colegas,



O *COLMEA - Colóquio Interinstitucional Modelos Estocásticos e Aplicações *-
tem mais um encontro no próximo dia 22 de novembro de 2023, a partir das
14:00h, na PUC-Rio. Nesta ocasião teremos palestras de Philip Thompson (FGV
EMAp)  e Oliver Riordan (Oxford).



*Programa: *
14:00 h - 15:20h  Philip Thompson (FGV EMAp)
*Outlier-robust additive matrix decomposition and robust matrix completion*



15:40h - 17:00h   Oliver Riordan (Oxford)
*The chromatic number of random graphs*


17:00h Discussão e lanche

*Local:*
Sala de reuniões do Decanato do CTC,

12 º andar do prédio Cardeal Leme,
PUC-Rio



Informações mais completas sobre o COLMEA podem ser encontradas aqui:
http://www.im.ufrj.br/~coloquiomea/

Todos são muito bem-vindos. Agradecemos também pela divulgação em suas
instituições. Resumos das palestras no final da mensagem.

Atenciosamente,

O comitê organizador:
Americo Cunha (UERJ)
Evaldo M.F. Curado (CBPF)
João Batista M. Pereira (UFRJ)
Leandro P. R. Pimentel (UFRJ)
Maria Eulalia Vares (UFRJ)
Nuno Crokidakis (UFF)
Roberto I. Oliveira (IMPA)
Simon Griffiths (PUC-Rio)
Yuri F. Saporito (FGV-EMAp)







*Outlier-robust additive matrix decomposition and robust matrix completion*

Philip Thompson (FGV EMAp)

We study least-squares trace regression when the parameter is the sum of a
$r$-low-rank matrix with a $s$-sparse matrix and a fraction $\epsilon$ of
the labels is corrupted. For subgaussian distributions, we highlight three
needed design properties, each one derived from a different process
inequality: the ``product process inequality'', ``Chevet's inequality'' and
the ``multiplier process inequality''. Jointly, these properties entail the
near-optimality of a tractable estimator with respect to the effective
dimensions  $d_{\textrm{eff},r}$ and $d_{\textrm{eff},s}$ for the low-rank
and sparse components,  $\epsilon$ and the failure probability $\delta$.
The near-optimal rate has the form $\mathsf{r}(n,d_{\textrm{eff},r}) +
\mathsf{r}(n,d_{\textrm{eff},s}) + \sqrt{(1+\log(1/\delta))/n}+
\epsilon\log(1/\epsilon).$  Here,
$\mathsf{r}(n,d_{\textrm{eff},r})+\mathsf{r}(n,d_{\textrm{eff},s})$ is the
optimal rate in average when there is no contamination. Our estimator is
adaptive to $(s,r,\epsilon,\delta)$ and, for fixed absolute constant $c>0$,
it attains the mentioned rate with probability $1-\delta$ uniformly over
all  $\delta\ge\exp(-cn)$. Disconsidering matrix decomposition, our
analysis also entails optimal bounds for a robust estimator adapted to the
noise variance. Finally, we consider robust matrix completion. We highlight
a new property for this problem: one can robustly and optimally estimate
the incomplete matrix regardless of the magnitude of the corruption. Our
estimators are based on ``sorted'' versions of Huber's loss. We present
simulations matching the theory. In particular, it reveals the superiority
of ``sorted'' Huber's losses over the classical Huber's loss.



*The chromatic number of random graphs*

Oliver Riordan (Oxford)


The chromatic number of a graph is the minimum number of colours needed to
colour the vertices so that adjacent vertices receive distinct colours.
While this sounds like a game, in applications it is a very important
property, corresponding to the minimum number of groups a set must be
divided into to avoid any incompatible pairs within each group. The
chromatic number is also studied purely theoretically, which will be the
point of view here.

A basic question is: considering all possible graphs on $n$ vertices, what
do their chromatic numbers look like? How often does each possible value
occur? Or, rephrasing, what is the distribution of the chromatic number of
a graph chosen uniformly at random? Writing $X$ for this random variable,
we can look for reasonable upper and lower bounds on the mean of $X$, and
upper and lower bounds on the variance of $X$. For the last combination,
nothing was known until a recent breakthrough of Annika Heckel. In this
talk I will discuss some of the history of the problem, and try to describe
some of the ideas Annika used, which she and I have since taken further.
-------------- Próxima Parte ----------
Um anexo em HTML foi limpo...
URL: <http://lists.ime.usp.br/pipermail/abe/attachments/20231118/c7b223d9/attachment.htm>