Hacker News Reader

Comment by waheoo | Hacker News Reader

Why is this noteworthy?

(I assume this is common knowledge or at least should be)

This method converges unconditionally for any input with the required sparsity when using numerical representations with a fixed number of bits. No traditional sparse iterative solver has that property without further conditioning the matrix or increasing the run-time to handle the higher precision. As they lay out in the paper (third paragraph of introduction section on the preprint), for certain (rare in practice) matrices direct solvers still offered better runtime if convergence is demanded for all inputs with a certain sparsity.

This article (not the paper) definitely oversells the immediate practical applications; nobody is going to throw out their CG solver and pick this method up in practice to guarantee convergence in this manner.

In practice, are there maybe a few problems for which this guarantee unlocks a big performance speedup? How might this be used practically?

Marrix multiplication is fundamental to basically any numerical method you can think of, with applications ranging from machine learning to numerical solutions to differential equations to graph algorithms used in network analysis

Not sure why you’re being downvoted here; I’d like to know why this is noteworthy as well!

With a sparse system, you might run into dependency chains that effectively make it dense.

Like in an adjacency matrix for a graph, you may have a lot of sparsity, but if you're forced to consider neighbors of neighbors, the adjacency matrix you need is A^2. This can be dense even if A is quite sparse.

It's being downvoted because it comes across as someone arrogantly dismissing an important work because they have no idea what they are talking about. If they instead asked "why is this noteworthy? in my ignorance this seems obvious", they might have gotten a better reception.

Interesting, I just took it at face value. I wonder what the % split is.

It wasn't known to anyone before.

deep learning uses a lot lot of sparse linear systems

For some easy to grok examples: imagine MNIST, where all the pixels besides the writing are 0; or a recommendation system, where column i has the users rating for movie i, or number of times they listened to song i; or any one-got encoding scheme

> or any one-got encoding scheme

Typo: should be one-hot encoding scheme.

Sparsity of input isn't often relatively easy to achieve, as you suggest.

Sparsity of intermediate layers requires more work. (But is often a good regularization technique.)

Humorously “one-got” is almost a apt description :)

It does, but the problem this algorithm handles is dealing with demanding convergence for all input matrices without adding an additional “n” factor to handle increased precision. Meanwhile deep learning is moving in the direction of 16-bit floating point and 8-bit integer scalars.

Reply on news.ycombinator.com