Review
I made a video going through the solution in the easiest case of 3x3 matrices. This might help people trying to understand the problem and/or get people interested https://youtu.be/0d66hPBC38Y
I think logarithmic dependence on epsilon will be difficult, especially for problem one. To demonstrate this, consider the problem of approximating the maximum eigenvalue of a sparse (let's say m = O(n)) PSD matrix with trace at most n. The obvious algorithms to try aren't fast enough:
Intuitively, power iteration-style methods exploit sparsity by taking matrix-vector products exclusively, which yields slow (polynomial in epsilon) convergence.
To argue that problem one is difficult, I claim that one natural candidate completion is the all-zero completion, resulting in a sparse matrix. This suggests (but does not prove!) that the problem of determining existence of PSD completions requires determining whether the resulting sparse completion is PSD - equivalently, whether its minimum eigenvalue is nonnegative. The reduction to the max eigenvalue problem then follows by taking spectral shifts ( for ).
It's unclear to me whether problem two has a similar dependence, but given the similarity of the problems I'm skeptical that logarithmic dependence in epsilon is possible. If anyone has ideas for a similar reduction I'd love to discuss!
(comment based on work co-authored w @Somsubhro Bagchi)
note: Som and I have discussed a similar objection with @paulfchristiano, who seemed ok with solutions with convergence polynomial in epsilon but still O(mn) in the "typical case" (eg. for problem 1, with enough precision to determine (non)existence of PSD completions). After constraining all diagonal elements of A to be 1, we're somewhat optimistic such weaker convergence is attainable.
Question 1 is very likely NP-hard. https://arxiv.org/abs/1203.6602 shows:
We consider the decision problem asking whether a partial rational symmetric matrix with an all-ones diagonal can be completed to a full positive semidefinite matrix of rank at most k. We show that this problem is $\NP$-hard for any fixed integer k≥2.
I'm still stretching my graph-theory muscles to see if this technically holds for (and so precisely implies the NP-hardness of Question 1.) But even without that, for applied use cases we can just fix to a very large number to see that practical algorithms are unlikely.
Nope, I’m withdrawing this answer. I looked closer into the proof and I think it’s only meaningful asymptotically, in a low rank regime. The technique doesn’t work for analyzing full-rank completions.
It can be decided in time by semidefinite programming, and I'd guess that most researchers would expect it can be done in time (which is the runtime of PSD testing, i.e. the case when ).
More generally, there's a large literature on positive semidefinite completions which is mostly concerned with finding completions with particular properties. Sorry for not better flagging the state of this problem. Those techniques don't seem super promising for getting to .
I think it can be done in , where I recall for non-expert's convenience that is the exponent of matrix multiplication / inverse / PSD testing / etc. (all are identical). Let be the space of matrices and let be the -dimensional vector space of matrices with zeros in all non-specified entries of the problem. The maximum-determinant completion is the (only?) one whose inverse is in . Consider the map and its projection where we zero out all of the other entries. The function can be evaluated in time . We wish to solve . This should be doable using a Picard or Newton iteration, with a number of steps that depends on the desired precision.
Would it be useful if I try to spell this out more precisely? Of course, this would not be enough to reach in the small case. Side-note: The drawback of having posted this question in multiple places at the same time is that the discussion is fragmented. I could move the comment to mathoverflow if you think it is better.
Agree about the downside of fragmented discussion, I left some time for MO discussion before posting the bounty but I don't know how much it helped.
I agree that some approach like that seems like it could work for . I'm not familiar with those techniques and so don't know a technique that needs iterations rather than or . For Newton iteration it seems like you need some kind of bound on the condition number.
But I haven't thought about it much, since it seems like something fundamentally different is needed to break . I believe that one of those might just work out of the box.
Wait which algorithm for semidefinite programming are you using? The ones I've seen look like they should translate to a runtime even slower than For example the one here:
https://arxiv.org/pdf/2009.10217.pdf
Also, do you have a source for the runtime of PSD testing being ? I assume no lower bound is known, i.e. I doubt PSD testing is hard for matrix multiplication. Am I wrong about that?
That's a good question. From what I've seen, PSD testing can be done by trying to make a Cholesky decomposition (writing the matrix as with lower-triangular) and seeing if it fails. The Cholesky decomposition is an decomposition in which the lower-triangular and upper-triangular are simply taken to have the same diagonal entries, so PSD testing should have the same complexity as decomposition. Wikipedia quotes Bunch and Hopcroft 1974 who show that decomposition can be done in by Strassen, and presumably the more modern matrix multiplication algorithms also give an improvement for .
I also doubt that PSD testing is hard for matrix multiplication, even though you can get farther than you'd think. Given a positive-definite matrix whose inverse we are interested in, consider the block matrix . It is positive-definite if and only if all principal minors are positive. The minors that are minors of are positive by assumption, and the bigger minors are equal to times minors of , so altogether the big matrix is positive-definite iff is. Continuing in this direction, we can get in time (times ) any specific component of . This is not enough at all to get the full inverse.
There is a simple intuition for why PSD testing cannot be hard for matrix multiplication or inversion: regardless of how you do it and what matrix you apply it to, it only gives you one bit of information. Getting even just one bit of information about each matrix element of the result requires applications of PSD testing. The only way out would be if one only needed to apply PSD testing to tiny matrices.
Thanks for the clarification! I assumed the question was using the bit computation model (biased by my own experience), in which case the complexity of SDP in the general case still seems to be unknown (https://math.stackexchange.com/questions/2619096/can-every-semidefinite-program-be-solved-in-polynomial-time)
Yeah, I can believe the problem is NP hard if you need to distinguish eigenvalues in time rather than . I don't understand exact arithmetic very well but it seems wild (e.g my understanding is that no polynomial time algorithm is known for testing ).
We intend to leave this prize open until the end of September. At that point we will distribute prizes (probably just small prizes for useful arguments and algorithms, but no full solution).
I now pretty strongly suspect that the version of problem 1 with logarithmic dependence on is not solvable. We would award a prize for an algorithm running in time which can distinguish matrices with no PSD completion from those with a completion where the ratio of min to max eigenvalue is at least . And of course a lower bound is still fair game.
That said, I don't expect any new submissions to win prizes and so wouldn't recommend that anyone start working on it.
Are the math formulas (= presumably LaTeX) in this post broken for everyone, or just for me? (That is, I see strings full of backslashes, like "").
Yeah, looks like it broke this morning, and I just fixed it again. Having RSS imports with LaTeX and non-admin editors is a bit fickle at the moment (since we have to sanitize the HTML to avoid security vulnerabilities).
Oh, yeah, this happens when switching back and forth from the LessWrong editor to Markdown and vice-versa. Love if someone fixed it, also because in LessWrong editor I don't know how or if you can make block equations - just inline ones.
Command + M for block equations (it says so in the help text that shows up in an empty LW editor text box).
And huh, I am surprised that LaTeX doesn't translate correctly. I feel like I've used that recently. Can you ping us on Intercom with a context where it didn't work?
Gah, I assumed this was some notation I'd never seen before. (Then again, even if this was written out in clear LaTeX I wouldn't understand it.)
Asking for some clarifications:
1. For both problems, should the solution work for an adversarially chosen set of m entries?
2. For both problems, can we read more entries of the matrix if it helps our solution? In particular can we WLOG assume we know the diagonal entries in case that helps in some way.
Here are two self-contained algorithmic questions that have come up in our research. We're offering a bounty of $5k for a solution to either of them—either an algorithm, or a lower bound under any hardness assumption that has appeared in the literature.
Question 1 (existence of PSD completions): given m entries of an n×n matrix, including the diagonal, can we tell in time ~O(nm) whether it has any (real, symmetric) positive semidefinite completion? Proving that this task is at least as hard as dense matrix multiplication or PSD testing would count as a resolution.
Question 2 (fast “approximate squaring”): given A∈Rn×n and a set of m=Ω(n) entries of AAT, can I find some PSD matrix that agrees with AAT in those m entries in time ~O(nm)?
We'll pay $5k for a solution to either problem. The offer is open for each problem for 3 months or until the problem gets solved (whichever happens first). Winners are welcome to publish solutions independently. Otherwise, if the result ends up being a significant part of a paper, we’ll invite them to be a coauthor.
We’ll also consider smaller prizes for partial progress, or anything that we find helpful for either solving the problem or realizing we should give up on it.
To understand the motivation for these questions, you can read our paper on Formalizing the presumption of independence and in particular Appendix D.7.2. ARC is trying to find efficient heuristic estimators as a formalization of defeasible reasoning about quantities like the variance of a neural network's output. These two questions are very closely related to one of the simplest cases where we haven't yet found any reasonable linear time heuristic estimator.
We don’t expect to receive many incorrect proposals, but if we receive more than 5 we may start applying a higher standard in order to save our time. If we can’t understand a solution quickly, we may ask you to provide more details, and if we still can’t understand it we may reject it. We expect a correct solution to be about as clear and easy to verify as a paper published at STOC.
For both problems, it’s OK if we incorrectly treat a matrix as PSD as long as all of its eigenvalues are at least −ε for a small constant ε. ~O hides polylogarithmic factors in n, ε, and the max matrix entry. Feel free to ask for other clarifications on our question on Math Overflow, on Facebook, or by email.
To submit a solution, send an email to prize@alignment.org.