Stochastic and incremental subgradient methods for convex optimization on Hadamard spaces

Questo articolo introduce un nuovo tipo di subgradiente basato sulle funzioni di Busemann per spazi di Hadamard, permettendo di generalizzare i metodi stocastici e incrementali di subgradiente con garanzie di complessità e applicandoli a problemi come il calcolo delle medie $p$-e nelle varietà BHV degli alberi.

L'essenziale

🌍 Navigare nel "Mondo Curvo": Un nuovo modo per trovare il centro

Immagina di dover trovare il punto migliore per costruire una casa, ma invece di vivere su una mappa piatta e rettilinea come quella di una città europea, vivi in un mondo strano. Un mondo dove le strade non sono mai dritte, dove i triangoli non hanno angoli che sommano 180 gradi, e dove il "piatto" non esiste. Questo è il mondo degli spazi di Hadamard.

In questo mondo, ci sono cose come:

• Spazi iperbolici: Come un foglio di gomma che si espande all'infinito (pensa a una superficie a forma di sella o a un fungo).
• Spazi degli alberi (Tree Space): Un luogo dove ogni punto è un albero genealogico o un albero evolutivo. Qui, muoversi significa cambiare la forma di un albero, non solo spostarsi in linea retta.

Il problema? In questi mondi curvi, i metodi matematici classici che usiamo per trovare il "centro" o il "miglior punto" (ottimizzazione) spesso si rompono. È come se avessi una bussola che funziona perfettamente a Roma, ma che impazzisce se provi a usarla su una montagna o in mezzo all'oceano.

🧭 Il vecchio problema: La bussola rotta

Nella matematica classica (su un piano piatto), per trovare il punto migliore, usiamo i gradienti. Immagina di essere su una montagna e voler scendere al punto più basso. Il gradiente è come una freccia che ti dice: "Scendi in quella direzione!". È una freccia che punta in basso.

Ma in questi mondi curvi (Hadamard), non c'è un "piano" su cui disegnare frecce. Non puoi semplicemente disegnare una linea retta che punta giù. Gli scienziati hanno provato a usare mappe locali (come se guardassi solo i piedi e immaginassi che il terreno sia piatto lì), ma questo approccio è complicato, richiede calcoli pesanti e spesso fallisce se la curvatura del mondo è troppo strana.

💡 La nuova idea: Le "Frecce Busemann"

Gli autori di questo paper (Goodwin, Lewis, Lopez-Acedo e Nicolae) hanno avuto un'idea geniale. Invece di cercare di disegnare frecce su un piano che non esiste, hanno inventato un nuovo tipo di "bussola" basata su qualcosa chiamato Funzioni di Busemann.

La metafora della "Luce Lontana":
Immagina di essere in una stanza buia e di guardare verso una luce lontanissima all'orizzonte. Anche se la stanza è curva, la direzione in cui guardi quella luce è costante.

• Invece di dire "scendi verso il basso" (che non ha senso qui), dicono: "Cammina lungo un raggio che punta verso un punto all'infinito".
• La loro nuova "bussola" (il sottogradiente di Busemann) non è una freccia fissa, ma è come un raglio di luce che parte da dove sei e punta verso l'infinito, con una certa velocità.

È come se invece di dirti "vai giù", ti dicesse: "Corri lungo questo sentiero che si allontana verso l'orizzonte, e corri a questa velocità specifica".

🚶‍♂️ Come funziona l'algoritmo (Il viaggio)

Il paper introduce due nuovi metodi per trovare il punto migliore in questo mondo strano:

1. Il metodo Stocastico (Il viaggiatore fortunato):
   Immagina di dover trovare il centro di un gruppo di amici sparsi in una foresta curva. Invece di guardare tutti gli amici ogni volta, scegli un amico a caso, guardi in che direzione si trova rispetto a te, e fai un passo in quella direzione. Poi ne scegli un altro a caso. Ripeti.

   • La novità: Usano la loro nuova "bussola Busemann" per capire esattamente quanto velocemente e in quale direzione andare verso quell'amico.

2. Il metodo Incrementale (Il viaggiatore metodico):
   Qui non scegli a caso. Guardi il primo amico, fai un passo. Poi guardi il secondo, fai un passo. Poi il terzo. Come se stessi facendo un giro completo della foresta, passo dopo passo.

Perché è meglio?
Prima, per fare questi passi, dovevi risolvere equazioni matematiche molto difficili (come trovare il punto esatto dove una curva tocca un cerchio). Con il nuovo metodo, il passo è semplice: è solo un viaggio lungo un raggio. È come passare dal calcolare la traiettoria di un razzo (difficile) al camminare lungo un sentiero segnato (facile).

🌳 L'esempio pratico: Gli Alberi Genealogici

Per dimostrare che funziona davvero, hanno usato un caso reale: gli spazi degli alberi (BHV Tree Space).
Immagina di avere 100 alberi genealogici diversi (o alberi evolutivi di virus) e di voler trovare l'"albero medio", quello che rappresenta meglio tutti loro.

• In questo spazio, un "punto" è un intero albero.
• Spostarsi significa cambiare la forma di un albero.
• Il loro algoritmo è riuscito a trovare l'albero medio in modo molto efficiente, anche quando gli alberi erano molto diversi tra loro.

🏆 Il risultato finale

In sintesi, questo paper ci dice:

"Non serve avere un piano piatto per trovare il centro delle cose. Se il mondo è curvo, basta cambiare il modo in cui guardiamo la direzione. Usando le 'Frecce Busemann' (raggi che puntano all'infinito), possiamo creare algoritmi semplici, veloci e sicuri per trovare la soluzione migliore, anche nei mondi più strani e curvi della matematica."

È come se avessero inventato un nuovo tipo di scarpe da trekking che permettono di camminare dritti anche su un terreno che sembra curvo, rendendo possibile l'esplorazione di territori che prima erano considerati troppo difficili da navigare.

Sommario tecnico

Ecco una sintesi tecnica dettagliata del paper "Stochastic and incremental subgradient methods for convex optimization on Hadamard spaces" in italiano.

Titolo: Metodi stocastici e incrementali di subgradiente per l'ottimizzazione convessa negli spazi di Hadamard

1. Il Problema e il Contesto

Il lavoro si occupa di problemi di ottimizzazione convessa definiti su un sottoinsieme $C$ di uno spazio metrico completo di Hadamard $(X, d)$. Gli spazi di Hadamard sono spazi metrici con curvatura non positiva (proprietà CAT(0)), che generalizzano gli spazi euclidei e di Hilbert, includendo varietà Riemanniane a curvatura sezionale non positiva, spazi di matrici definite positive, e strutture discrete come gli spazi degli alberi (es. spazio BHV per alberi filogenetici) e complessi cubici CAT(0).

L'obiettivo è risolvere problemi della forma:
$$\inf_{x \in C} f(x)$$
dove $f$ è una funzione convessa lungo le geodetiche. In particolare, il paper si concentra su strutture additive:
$$f(x) = \sum_{i=1}^m f_i(x)$$
dove ogni componente $f_i$ è convessa lungo le geodetiche.

La Sfida Principale:
Mentre i metodi di ottimizzazione classici (come i metodi del punto prossimale) sono ben definiti in questi spazi, i metodi basati sui subgradienti incontrano un ostacolo fondamentale: negli spazi euclidei, i subgradienti sono funzionali lineari (oggetti duali). Negli spazi di Hadamard, manca una struttura lineare, rendendo ambigua la definizione di subgradiente. I tentativi precedenti di definire subgradienti si basavano su linearizzazioni locali (spazi tangenti) e mappe esponenziali, richiedendo limiti inferiori sulla curvatura e rendendo l'analisi di complessità dipendente da parametri geometrici specifici.

2. Metodologia e Innovazioni Teoriche

Per superare l'assenza di struttura lineare, gli autori introducono un nuovo concetto di subgradiente basato sulle funzioni di Busemann.

A. Subgradienti di Busemann

Invece di utilizzare vettori nello spazio tangente, gli autori identificano i subgradienti con raggi geodetici a velocità costante.

• Definizione: Un elemento $[\xi, s] \in CX_\infty$ (dove $CX_\infty$ è il "cono di frontiera" dello spazio) è un subgradiente di Busemann per $f$ in $x$ se soddisfa una disuguaglianza analoga a quella classica:
  $$f(y) - f(x) \geq s \cdot (b_\xi(y) - b_\xi(x)) \quad \forall y \in C$$
  dove $b_\xi$ è la funzione di Busemann associata alla direzione $\xi$ e $s \geq 0$ è una "velocità".
• Vantaggi: Questa definizione è puramente geometrica e globale, non richiede limiti inferiori sulla curvatura e non dipende dalla linearizzazione locale.

B. Proprietà Chiave e Calcolo

• Funzioni Rappresentabili: Viene mostrato che molte funzioni naturali (come le funzioni distanza $d(x, a)$ e le loro composizioni con funzioni convesse non decrescenti) sono "Busemann subdifferentiabili".
• Limiti dell'Addizione: Un risultato cruciale è che la somma di funzioni Busemann subdifferentiabili non è necessariamente Busemann subdifferentiabile. Questo impedisce l'applicazione diretta di un singolo subgradiente alla funzione somma $f$.
• Soluzione: Per aggirare questo limite, gli autori adottano un approccio di splitting (separazione), trattando le componenti $f_i$ individualmente.

C. Algoritmi Proposti

Gli autori sviluppano due varianti di algoritmi che generalizzano i metodi stocastici e incrementali euclidei:

1. Metodo Stocastico di Subgradiente di Busemann (Algoritmo 1): Ad ogni iterazione, viene scelta casualmente una componente $f_i$, calcolato il suo subgradiente di Busemann $[\xi, s]$, e si esegue un passo lungo il raggio geodetico associato a $\xi$ con velocità $s$ e passo $t_k$.
2. Metodo Incrementale di Subgradiente di Busemann (Algoritmo 2): Le componenti vengono visitate ciclicamente, aggiornando la soluzione passo dopo passo.

Entrambi gli algoritmi utilizzano un "oracolo" che restituisce la direzione $\xi$ e la velocità $s$ per ogni componente.

3. Risultati Principali

A. Analisi di Complessità

Il contributo teorico più significativo è la dimostrazione che questi metodi mantengono le stesse garanzie di complessità dei loro analoghi euclidei, senza dipendere da limiti di curvatura inferiori.

• Tasso di Convergenza: Sotto ipotesi standard (diametro limitato del dominio o condizioni sui passi), il metodo richiede $O(\epsilon^{-2})$ iterazioni per approssimare il valore ottimo entro una tolleranza $\epsilon$.
• Teoremi 6.2 e 6.4: Forniscono limiti superiori rigorosi per l'errore atteso (nel caso stocastico) e deterministico (nel caso incrementale), dimostrando che la convergenza è garantita anche in spazi non manifolds (come gli spazi degli alberi).

B. Applicazione al Problema della Mediana (p-mean)

Gli algoritmi sono applicati al problema della mediana (Weber problem, $p=1$) e più in generale ai problemi di $p$-mean in spazi di Hadamard:
$$\min_x \sum_{i=1}^m w_i d(x, a_i)^p$$
In particolare, viene dimostrato che le funzioni distanza sono Busemann subdifferentiabili, rendendo questi problemi risolvibili con i nuovi metodi.

C. Esperimenti Computazionali

Gli autori testano gli algoritmi nello spazio degli alberi di Billera-Holmes-Vogtmann (BHV), specificamente $T_4$ (alberi con 4 foglie).

• Confronto: Vengono confrontati con i metodi prossimali ciclici (Algoritmo 5).
• Risultati: Gli esperimenti mostrano che i metodi di subgradiente (specialmente quello incrementale) sono competitivi e talvolta superiori in termini di velocità di convergenza pratica, pur mantenendo una complessità teorica simile.
• Fenomeno di "Stickiness": Viene illustrato come gli algoritmi gestiscano correttamente casi in cui la mediana giace su una faccia di dimensione inferiore dello spazio (fenomeno di "stickiness" tipico degli spazi cubici), un caso in cui i metodi basati su gradienti Riemanniani potrebbero fallire o richiedere trattamenti speciali.

4. Significato e Impatto

1. Generalizzazione Senza Vincoli di Curvatura: Il lavoro rimuove la necessità di limiti inferiori sulla curvatura (spesso presenti nella letteratura precedente sugli spazi CAT(0)), rendendo gli algoritmi applicabili a una classe più ampia di spazi, inclusi quelli singolari come gli spazi degli alberi.
2. Approccio Primal e Globale: L'uso delle funzioni di Busemann offre una visione "primal" (geometrica diretta) dell'ottimizzazione, evitando la complessità delle mappe esponenziali e delle strutture duali locali.
3. Fondamento per l'Ottimizzazione Strutturata: Dimostra che, nonostante la mancanza di additività dei subgradienti di Busemann, l'approccio di splitting (stocastico/incrementale) è la via corretta per estendere l'ottimizzazione convessa a spazi non lineari complessi.
4. Applicabilità Reale: La capacità di risolvere problemi di mediana in spazi di alberi (cruciali in biologia evolutiva per l'analisi filogenetica) con garanzie teoriche solide apre nuove strade per l'analisi dei dati in spazi metrici non euclidei.

In sintesi, il paper fornisce un quadro teorico solido e algoritmi pratici per l'ottimizzazione convessa in spazi di Hadamard, superando le limitazioni dei metodi basati su linearizzazione locale e offrendo un'alternativa robusta ai metodi prossimali, specialmente per problemi strutturati e su larga scala.