Newton cubico affine-invariante con apprendenti deboli

Abstract degli autori

I moderni algoritmi di boosting del gradiente si basano sul metodo di Newton, che offre ottimi risultati empirici ma non dispone di garanzie di convergenza globale. Sebbene un recente lavoro sul boosting Gradient-Regularized Newton (GRN) abbia ottenuto un tasso globale di $\mathcal{O}(1/γ^{12}k^2)$, la sua analisi non è riuscita a sfruttare la geometria naturale dell’Hessiana e presenta una forte dipendenza da $γ^{12}$ legata a un «vantaggio debole del gradiente» $γ$ nel caso peggiore. In questo articolo affrontiamo questi limiti teorici generalizzando lo schema Affine-Invariant Cubic Newton (AICN) all’ottimizzazione convessa con apprendenti deboli. La nostra analisi si basa sui valori medi del coseno $\overlineΘ_k$ lungo il percorso di ottimizzazione e sui miglioramenti direzionali $δ_k$ nella norma indotta dall’Hessiana. Mostriamo che l’aggiornamento weak-AICN si riduce a un passo di Newton debole smorzato, con un’ampiezza del passo esplicita determinata da $δ_k$. Sotto l’ipotesi di autocordanza semi-forte, stabiliamo un tasso globale di $\mathcal{O}(1/\overlineΘ_k^4 k^2)$, migliorando significativamente il limite di weak-GRN. Dimostriamo inoltre un tasso lineare locale, la convergenza lineare globale per funzioni di perdita dominate dall’Hessiana e limiti inferiori per il coseno dell’angolo; presentiamo poi weak-AdaAICN, che regola in modo adattivo la regolarizzazione cubica. Infine, mostriamo che questo quadro si applica anche oltre il boosting del gradiente: la discesa coordinata di Newton emerge naturalmente come caso particolare dell’ottimizzazione con apprendenti deboli.