Riduzione al minimo del sistema L1-regolarizzato, convergente su posizione non minima?

Question

Questo è il mio primo post su StackOverflow, quindi se questa non è l'area corretta mi scuso. Sto lavorando per ridurre al minimo un sistema L1-regolarizzato.

Questo fine settimana è il mio primo tuffo nell'ottimizzazione, ho un sistema lineare base Y = X * B, X è una matrice n-by-p, B è un vettore p-by-1 dei coefficienti del modello e Y è un vettore di output n-by-1.

Sto cercando di trovare i coefficienti del modello, ho implementato sia la discesa del gradiente che gli algoritmi di discesa delle coordinate per minimizzare il sistema L1 regolarizzato. Per trovare la dimensione del mio passo sto usando l'algoritmo di backtracking, termino l'algoritmo osservando la norma-2 del gradiente e terminando se è 'abbastanza vicino' a zero (per ora sto usando 0.001).

La funzione che sto cercando di minimizzare è la seguente (0.5) * (norma ((Y - X * B), 2)^2) + lambda * norma (B, 1). (Nota: per norma (Y, 2) intendo il valore di norma 2 del vettore Y) La mia matrice X è 150 per 5 e non è sparsa.

Se imposto il parametro di regolarizzazione lambda a zero, dovrei convergere sulla soluzione dei minimi quadrati, posso verificare che entrambi i miei algoritmi lo fanno abbastanza bene e abbastanza rapidamente.

Se inizio ad aumentare lambda i miei coefficienti di modello tendono tutti verso zero, questo è quello che mi aspetto, i miei algoritmi non terminano mai, anche perché la norma-2 del gradiente è sempre un numero positivo. Per esempio, un lambda di 1000 mi darà coefficienti nell'intervallo 10^(- 19), ma la norma2 del mio gradiente è ~ 1.5, questo dopo diverse migliaia di iterazioni, mentre i miei valori di sfumatura convergono tutti in qualcosa nello 0 a 1 range, la mia dimensione del passo diventa estremamente piccola (gamma 10^(- 37)). Se lascio funzionare l'algoritmo più a lungo, la situazione non migliora, sembra che si sia bloccato in qualche modo.

Entrambi i miei algoritmi di discesa di gradienti e coordinate convergono sullo stesso punto e danno lo stesso numero di norma2 (gradiente) per la condizione di terminazione. Funzionano anche abbastanza bene con lambda di 0. Se uso un lambda molto piccolo (diciamo 0.001) ottengo convergenza, un lambda di 0.1 sembra convergere se lo faccio scorrere per un'ora o due, un lambda più grande e il il tasso di convergenza è così piccolo che è inutile.

Ho avuto alcune domande che penso potrebbero riguardare il problema?

Nel calcolo del gradiente sto usando un metodo di differenza finita (f (x + h) - f (x-h))/(2h)) con una h di 10^(- 5). Qualche idea su questo valore di h?

Un altro pensiero era che in questi piccolissimi passaggi si viaggiava avanti e indietro in una direzione quasi ortogonale al minimo, rendendo il tasso di convergenza così lento che è inutile.

Il mio ultimo pensiero è stato che forse dovrei usare un metodo di terminazione diverso, forse guardando il tasso di convergenza, se il tasso di convergenza è estremamente lento e poi terminare. È un metodo di terminazione comune?

Answer 1

La norma 1 non è differenziabile. Ciò causerà problemi fondamentali con molte cose, in particolare il test di terminazione che hai scelto; il gradiente cambierà drasticamente attorno al tuo minimo e non esisterà su un set di misura zero.

Il test di terminazione che si desidera veramente sarà simile a "c'è un vettore molto breve nel subgradient".

È abbastanza facile trovare il vettore più breve nel sottoregolatore di || Ax-b || _2^2 + lambda || x || _1.Scegli, saggiamente, una tolleranza eps e effettuare le seguenti operazioni:

1. Compute v = grad(||Ax-b||_2^2).

2. Se x[i] < -eps, quindi sottrarre lambda da v[i]. Se x[i] > eps, aggiungere lambda a v[i]. Se -eps <= x[i] <= eps, aggiungere il numero in [-lambda, lambda] a v[i] che riduce al minimo v[i].

Qui puoi eseguire il test di terminazione, trattando il gradiente come v. Ti consiglio inoltre di utilizzare v per il gradiente quando scegli dove dovrebbe essere il tuo prossimo iterato.