Live data from Hacker News

A large scale non-linear optimization library

github.com

31–34 of 34 posts

Re: A large scale non-linear optimization library

#31

Earlier quoted context omitted.

There are a lot of large-scale optimization problems in industry that are still compute bound. Currently available solvers are either single threaded on the CPU, or offer "parallelism" by running copies of the same problem on multiple threads, but with different initial conditions in hopes that one happens to converge faster.

Most large-scale optimization outside of neural nets is bottlenecked by function evaluation

I'll contend that this depends. For example, in mixed-integer linear programs, the function evaluations are trivial, but the combinatorial search is expensive. Alternatively, for nonlinear, continuous optimization problems with constraints, the primary cost is often the preconditioning or factorization of the systems associated either with an augmented or KKT systems. That said, for unconstrained or bound constrained, nonlinear, continuous optimization problems, I largely agree. And, even with general constraints, it's sometimes the case it's the function evaluations. Mostly, I wanted to contend that the linear system solves can often be the limiting factor and better large scale factorization codes are needed.

Re: A large scale non-linear optimization library

#32
post #23

We used it in a project that performed document recognition and analysis. It was useful for aligning the fields to be extracted from the source image as we formulated it as an optimization problem. It was straightforward to use and it contains some neat loss functions that reduce the effect of outliers (e.g. CauchyLoss).

That sounds really interesting. Do you have any more details? If you prefer to reply privately, my contact details are in my HN profile.

Thanks, I've replied privately

Re: A large scale non-linear optimization library

#34

Earlier quoted context omitted.

They are iterative and path dependent, no?

Having implemented them myself on an ad hoc basis in pytorch, I don't see how they're much different than training a deep learning model.

There are two "directions" along which you can parallelize: - explore different parts of the parameter hyperspace in parallel. - for a given parametrization, split the model and/or objective function so that its parts can be computed in parallel.

The second approach is model-specific, and gives you nice speedups (make your model N times faster, and you will converge N times faster), but is often not particularly well-suited for accelerators (which includes GPUs) due to the latency of moving data back and forth, but again with model-specific tuning you can maybe make it work. Most of the time SIMD on CPU is best here for most traditional problems.

The first approach, which already pretty much requires the second so that the model and the optimization can run on the same computing unit, well it isn't particularly great since you're doing computations that are suboptimal and/or redundant to begin with. Any speedup isn't obvious, depends on the optimization algorithm and the convergence characteristics of your problem. Also as you follow along some paths in parallel, you'll eventually need to sync up, and since they have divergent control flow, this means you're not able to make the most of the computing resources which will be stalling quite often. Often, with enough tuning for your particular problem and method, you can make it work.

So why don't generic libraries do it on GPU? Because unless you tune everything for your particular problem, it's just not going to perform as well as on CPU.

Post reply on HN