Finding the convex envelope of a boundary datum using random geometric graphs

1. Il Problema

L'obiettivo principale della ricerca è approssimare l'inviluppo convesso di un dato al bordo all'interno di un dominio limitato $D \subset \mathbb{R}^d$ ($d \ge 2$).
Nello spazio euclideo continuo, l'inviluppo convesso $u^*$ di una funzione $f$ definita sul bordo $\partial D$ è definito come il più grande funzione convessa in $D$ che è minore o uguale a $f$ sul bordo. Matematicamente, se $D$ è strettamente convesso e $f$ è continua, $u^*$ è l'unica soluzione (nel senso di viscosità) del problema di Dirichlet:
$$\begin{cases} -\lambda_1(D^2 u)(x) = 0 & x \in D \\ u(x) = f(x) & x \in \partial D \end{cases}$$
dove $\lambda_1(D^2 u)$ è il più piccolo autovalore della matrice Hessiana di $u$. L'equazione $\lambda_1(D^2 u) = 0$ caratterizza la convessità.

Il problema affrontato dagli autori è discretizzare questo problema continuo utilizzando grafi geometrici casuali (Random Geometric Graphs - RGG) e dimostrare che la soluzione discreta converge all'inviluppo convesso continuo quando il numero di punti tende all'infinito.

2. Metodologia

Costruzione del Grafo e dei Dati

• Punti Casuali: Si considera una nuvola di punti $\chi_n = \{X_1, \dots, X_n\}$ distribuiti uniformemente e indipendentemente in un dominio (es. $[0,1]^d$).
• Grafo Geometrico: Si costruisce un grafo $G_n = G(\chi_n, r_n)$ dove i vertici sono i punti campionati e un'arco esiste tra $x$ e $y$ se la loro distanza euclidea è minore di un raggio di connessione $r_n$ ($|x-y| < r_n$).
• Regime di Superconnettività: Gli autori lavorano nel regime di "superconnettività", dove $n r_n^d / \log n \to \infty$. Questo garantisce che il grafo sia connesso con probabilità 1 per $n$ sufficientemente grande.
• Sottodomini: Si definisce $D_n$ come l'insieme dei punti del grafo all'interno di $D$ e $B_n$ come l'insieme dei punti vicini al bordo (o fuori da $D$).

Formulazione del Gioco e dell'Equazione Discreta

L'approccio si basa su un gioco a un giocatore (un controllore) giocato sul grafo:

1. Dinamica: Partendo da un vertice $x \in D_n$, il giocatore sceglie un vicino $y$ in un anello specifico di raggio $r_n$ (definito da parametri $\delta_n$).
2. Transizione: Il nuovo stato del gioco è scelto con probabilità $1/2$ tra $y$ e il suo "vicino riflesso approssimato" $y_x$ (il punto più vicino al riflesso geometrico di $y$ rispetto a $x$).
3. Obiettivo: Il giocatore mira a minimizzare il valore atteso del pagamento $f(x_\tau)$ al momento in cui il gioco esce da $D_n$ (raggiunge $B_n$).

Principio di Programmazione Dinamica (DPP):
Il valore del gioco $u_n(x)$ soddisfa un'equazione discreta che approssima l'operatore Hessiano:
$$u_n(x) = \min_{y \in N_x^{\delta_n}} \left( \frac{1}{2}u_n(y) + \frac{1}{2}u_n(y_x) \right), \quad x \in D_n$$
con condizioni al bordo $u_n(x) = f(x)$ per $x \in B_n$.
Questa equazione è la versione discreta della condizione che la derivata seconda in ogni direzione sia non negativa (convessità).

Strumenti Analitici

• Teoria delle Soluzioni di Viscosità: Utilizzata per caratterizzare la soluzione continua e gestire la convergenza.
• Disuguaglianze di Concentrazione: Vengono utilizzati risultati di concentrazione empirica (Bousquet, Talagrand) per dimostrare che, con probabilità 1, per $n$ sufficientemente grande, ogni vertice ha vicini in tutte le direzioni necessarie all'interno dell'anello di connessione. Questo è cruciale per approssimare la derivata seconda in ogni direzione.
• Principio di Confronto: Dimostrato sia per l'equazione discreta (DPP) che per quella continua, garantendo l'unicità della soluzione.

3. Contributi Chiave

1. Costruzione di un Schema Discreto Convergente: Gli autori propongono un metodo basato su grafi casuali per approssimare l'inviluppo convesso, collegando la teoria dei giochi stocastici, l'apprendimento semi-supervisionato su grafi e le equazioni alle derivate parziali (PDE).
2. Controllo Preciso dei Parametri: Un contributo tecnico significativo è la determinazione precisa delle condizioni asintotiche sui parametri $r_n$ (raggio di connessione) e $\delta_n$ (spessore dell'anello). In particolare, richiedono:
   • $n r_n^d / \log n \to \infty$ (connettività).
   • $\sqrt{n} r_n^{2d} / \log n \to \infty$ (condizione più forte necessaria per la convergenza).
   • $\delta_n = o(r_n)$ e $\alpha_n = o(r_n)$ (per garantire che l'anello sia sufficientemente sottile e che i punti riflettenti approssimati siano vicini al riflesso esatto).
3. Dimostrazione di Convergenza Uniforme: Viene provato che, quasi certamente rispetto alla misura di probabilità, la funzione valore del gioco definita sul grafo converge uniformemente alla soluzione continua dell'inviluppo convesso quando $n \to \infty$.
4. Gestione del Bordo: Viene affrontata la delicatezza tecnica delle stime vicino al bordo per garantire che il dato al bordo venga assunto con continuità, un aspetto spesso critico nelle approssimazioni di PDE su grafi.

4. Risultati Principali

• Teorema 1: Sotto le condizioni sui parametri, il valore del gioco $u_n$ è l'unica soluzione del Principio di Programmazione Dinamica discreta (DPP) sul grafo.
• Teorema 2: La successione delle funzioni valore estese al dominio continuo ($\tilde{u}_n$) converge uniformemente, con probabilità 1, all'inviluppo convesso $u$ del dato al bordo $f$, che è l'unica soluzione di viscosità del problema continuo.
• Indipendenza dai Parametri: Il limite della successione è indipendente dai parametri specifici del gioco (come $r_n$ o $\delta_n$), purché soddisfino le condizioni di scala, e dipende solo dal dato al bordo $f$.

5. Significato e Implicazioni

• Ponte tra Discreto e Continuo: Il lavoro fornisce un quadro rigoroso per comprendere come procedure di apprendimento su grafi (semi-supervised learning) possano approssimare operatori differenziali non lineari complessi (come il primo autovalore dell'Hessiano) nel limite continuo.
• Applicazioni in Ottimizzazione e Apprendimento: Poiché le funzioni convesse sono fondamentali nell'ottimizzazione e l'inviluppo convesso è uno strumento chiave per estendere dati in modo coerente, questo metodo offre un approccio probabilistico e computazionalmente trattabile per problemi di estensione convessa in spazi ad alta dimensione.
• Robustezza: L'uso di grafi casuali rende il metodo robusto rispetto alla distribuzione dei dati, purché sia uniforme, e non richiede una griglia strutturata, rendendolo adatto a dati sparsi o irregolari.
• Nuovi Regimi di Connettività: Il paper chiarisce le condizioni necessarie affinché un grafo geometrico casuale possa supportare l'approssimazione di operatori di secondo ordine, distinguendo tra regimi di densità e di superconnettività.

In sintesi, il paper dimostra che un semplice gioco stocastico su una nuvola di punti casuali, opportunamente scalato, converge matematicamente alla soluzione di un problema di PDE non lineare complesso, offrendo un nuovo strumento teorico per l'analisi numerica e l'apprendimento automatico geometrico.