2025/03/03 by Dan Garber, Garber, Dan
Mathematics · #Advanced Optimization Algorithms Research #FOS: Mathematics #Optimization and Control (math.OC)
paper · pdf · doi:10.48550/arxiv.2503.01432
openalex publication_date 2025/03/03 · openalex created_date 2025/10/12 · openalex updated_date 2026/07/28
Second-order methods are of great importance for composite convex optimization problems due to their local super-linear convergence rates (under appropriate assumptions). However, the presence of even a simple nonsmooth function in the model most often renders the subproblems in proximal Newton methods computationally difficult to solve in high dimensions. We introduce a novel approach based on a weak proximal Newton oracle (WPNO), which only requires solving such subproblems to accuracy that is comparable to that of the optimal solution of the global problem, while maintaining local super-linear convergence under standard assumptions. Mainly, unlike classical inexact proximal Newton schemes, the complexity of our WPNO is not tied to (approximately) minimizing each subproblem; instead, we establish that when the optimal solution of the global problem admits a sparse structure, the inner subproblem can be solved by specialized first-order methods whose cost scales directly with the sparsity of this solution rather than with the ambient dimension.