# Weak Proximal Newton Oracles for Composite Convex Optimization

arXiv: https://arxiv.org/abs/2503.01432 · HTML: https://mlsanity.com/paper/2503.01432/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Mar 2025.

## Built on by (most cited first, 1 of 1)

- [Complexities of Weak Proximal Oracle Methods for Composite Convex Optimization](https://mlsanity.com/paper/2609.24423/) (2026)

## Abstract (arXiv)

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 textitweak 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.