# Polynomial Precision Dependence Solutions to Alignment Research Center Matrix Completion Problems

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 4 of its 20 references that are in the map.
- First posted on arXiv 8 Jan 2024.

## Builds on (most cited first, 4 of 4)

- [Fixed-Rank Approximation of a Positive-Semidefinite Matrix from Streaming Data](https://mlsanity.com/paper/1706.05736/) (2017)
- [Optimal Convergence Rates for the Proximal Bundle Method](https://mlsanity.com/paper/2105.07874/) (2021)
- [Formalizing the presumption of independence](https://mlsanity.com/paper/2211.06738/) (2022)
- [Revisiting Spectral Bundle Methods: Primal-dual (Sub)linear Convergence Rates](https://mlsanity.com/paper/2008.07067/) (2020)

## Abstract (arXiv)

We present solutions to the matrix completion problems proposed by the Alignment Research Center that have a polynomial dependence on the precision varepsilon. The motivation for these problems is to enable efficient computation of heuristic estimators to formally evaluate and reason about different quantities of deep neural networks in the interest of AI alignment. Our solutions involve reframing the matrix completion problems as a semidefinite program (SDP) and using recent advances in spectral bundle methods for fast, efficient, and scalable SDP solving.