Replica Symmetry Breaking and Algorithmic Thresholds in Empirical Risk Minimization under Multi-Index Model
The research investigates how fast polynomial-time algorithms can train neural networks when data and features are very large ($n, d o ext{infinity}$). Using statistical physics tools like the replica method, the authors predict an optimal performance limit. They then propose and rigorously prove that a specific incremental algorithm (IAMP) can actually achieve this predicted optimal performance in high dimensions.