Reti a larghezza ridotta iterate: completezza di Turing con larghezza 4 su domini di input convessi e complessità della verifica

Abstract degli autori

Studiamo le iterate di una rete ReLU fissa $N$ di larghezza 4, ossia il sistema a tempo discreto $x_{k+1} = N(x_k)$ su $[0,1]^4$. In modo equivalente, $x_k$ è l’output di una rete con pesi condivisi composta da $k$ copie di $N$, oppure di una rete ricorrente priva di input esterni, avviata da $x_0$. Dimostriamo che per ogni macchina di Turing deterministica $M$ esiste una rete di questo tipo $N_M$. La rete può essere costruita a partire da $M$ in tempo polinomiale. La profondità di ogni iterazione è $\mathrm{poly}(|M|)$. Le iterate di $N_M$ simulano esattamente $M$ su ogni nastro codificato. Il numero di iterazioni è proporzionale al tempo di esecuzione di $M$. Inoltre, la quarta coordinata segnala in modo irreversibile ogni punto del cubo convesso $[0,1]^4$ la cui simulazione legge una cifra non valida. Questo segnale è il certificato che rende corrette le riduzioni di difficoltà nelle regioni di input convesse, il regime dei verificatori pratici. In precedenza, le regioni convesse erano inaccessibili a causa di un ostacolo dovuto alla continuità, intrinseco alle reti ReLU. La corrispondenza ha tre conseguenze. Primo, il problema di raggiungibilità per le reti ReLU iterate di larghezza 4 copre l’intera gerarchia della complessità lungo un’unica dimensione: è NP-completo con un limite in notazione unaria, NEXP-completo con un limite in notazione binaria e RE-completo (indecidibile) senza limite. Secondo, bastano due neuroni aggiuntivi in larghezza per estendere la difficoltà a tutte le comuni funzioni di attivazione lisce: con larghezza 6, il problema di verifica robusta (un problema con promessa e un gap $δ/2δ$) è NP-completo per $\tanh$, sigmoid, GELU, Swish, ELU e per qualsiasi funzione di attivazione continua non polinomiale, calcolabile in tempo polinomiale, che abbia una costante di Lipschitz calcolabile in tempo polinomiale. Terzo, l’intero spettro si trasferisce alle Neural ODE discretizzate in dimensione 5.