An overview on existing approaches

[kellertuer]

I would like to collect a few packages and their approaches to iterative things – got get an overview.

Maybe including a bit of details on

• how things are done
• what is good / bad
• what do you like from their approach
• what do you dislike?
• is the package maybe also a candidate do use this interface (because the developer might be interested, because it is one you would like to remodel anyways...)

As an example a lot of packages use callbacks within their iterations, for example for debug and such – while Manopt uses state-decorators. I like state-decorators for that since it is cleaner to set up than passing in any callback function.

Maybe one answer per package would be nice – I try to take a look around myself as well.

[kellertuer]

Manopt.jl

Let's start with the obvious from my side – a plan would be to use this interface to have a base/backend for Manopt.jl algorithms. The current state there is

• a Problem contains usually one (sometimes two) Manifolds and the objective (cost, grad, hessian...)
  • the objective can be decorated, e.g. with a cache (LRUCache.jl) or with the EuclideanObjective wrapper that converts the inner (Euclidean) objective to Riemannian ones when needed
  • the objective can also be wrapped into a counter for statistics (count function calls,...)
• a State that both indicates which solver to use – and stores all data that are needed throughout the iterations (the iterate, some constants, a stopping criterion...
  • states can be wrapped e.g. in a DebugState or a RecordState to perform additional things per iteration (instead of having callbacks)
• a larger set of Stopping Criteria that often work generically – for example use get_iterate(state) or such
• some factories, that turn .symbols into nice stuff. for example a solvers debug=[:Iteration, :Cost, :GradientNorm] keyword gets first turned into a vector of DebugActions and these then form a group of actions that are executed on every step
• main functions initialise(problem, state) and step!(problem, state) need to be implemented for a solver ¨
  • since DebugState is a state wrapper that just requires to write an own step! basically.
• A bit of message passing, for example a solver can “communicate” to its subsolver (sub algorithm) whether something in the parent is active or not. If the subsolver has debug prints, that is usually conditional on that the parents one is active. Then every n-th iteration a subsolver might even print a debug in every of its own iterations.

Things I learned until now might be nice to have

• Static data of an algorithm that is not in the problem (hence split state in two parts)
• an iterator based scheme – should still be possible with the wrapper-based ideas

[kellertuer]

I forgot to add: there are high level interfaces, but usually only about 4 lines that are everywhere the same (1. decorate / wrap problem/objective, 2. wrap state 3. solve 4. “unwrap result”)

[lkdvos]

MPSKit.jl

The obvious one from my side - the plan would also be to have this interface as a backend for the MPSKit.jl algorithms. The current state there is a bit more split and less unified, but I would like to have a more unified approach.

• algorithms are usually started with a signature f(init, operator, [cache]; kwargs...) where f would be fixedpoint, groundstate, leading_boundary, excitations
• kwargs get handled, spits out alg::Algorithm that more or less behaves the same as the variable kwargs but has defaults and consistency checks. (For example, alg.alg_eigsolve might hold Arnoldi(; tol=kwargs.tol / 10) or something like that).
• f(init, operator, [cache], alg::Algorithm) gets called and dispatches to an implementation of the algorithm.
• logging infrastructure centered around log = IterLog("algname"), which spits out a log message whenever loginit!(log, ...), logiter!(log, ...), logfinish!(log, ...) or logcancel!(log, ...) gets called, and can contain transient data such as initial time etc. No automated way to deal with logging of subalgorithms or customize logging beyond a predefined verbosity level (0-4).
• hardcoded stopping criteria
• callback function with a fixed signature that is called after every iteration

Things I would definitely improve when reworking this:

• Currently all boilerplate is copied, I would much rather design around functions like initialize and step!, stop, ...
• While callbacks are generic and could in theory be used to accomplish almost anything, users tend to not find them/know how to use them, and supplying reasonable often-used ones is a very nice feature
• Iterators seem nice but the devil is in the details to actually make that work out.
• Custom stopping criteria can be very valuable
• Handling nested logging is hard

[kellertuer]

Stoppping Criteria & nested logging I have ideas for; I am not so much a fan of callbacks, but I have a good idea to even include those in the “wrapper approach”

A library of stopping criteria is definitly on my list

I will check out iterators soon, would just like to understand the split algorithm/state before a bit better. I would love to understand iterators better as well first :) But very interesting to follow on that.

[kellertuer]

SciML

or precisely I looked at https://github.com/SciML/DifferentialEquations.jl and its solvers.
This is a tough job. Not only does that package just reexport others, pinning down where stuff is actually happening is hard when structs habe a 1-line doc string and functions usually none. I think

• https://github.com/SciML/OrdinaryDiffEq.jl/blob/643f96145354c5a522f8ec6c091202eacfbeec4a/src/solve.jl
• https://github.com/SciML/OrdinaryDiffEq.jl/blob/643f96145354c5a522f8ec6c091202eacfbeec4a/src/solve.jl#L507

are the main loop, so it is a while with a perform_step in which the first seems to couple the ODE Problem and the Algorithm into a couple (the integrator?) and the cache is what we called state here.

I first thought they would use some iterator scheme, but that solve! seems to indicate that that is not the case.

From own solvers we did, cf. https://github.com/JuliaManifolds/ManifoldDiffEq.jl/blob/e1a9ad772c261c2555107c046a962dfc33874a3c/src/frozen_solvers.jl#L50,
the perorm_step! seems to be the main method and a alg_cache function to initialise a cache – but that has a signature of 15(!) parameters, all undocumented.

Compared to them

• we should be more careful in documenting stuff
• they seem to have some generic keyword handling, which we might take inspiration from for the factories I mentioned. If so I would prefer to have them documented more like this: https://manoptjl.org/stable/plans/debug/#Manopt.DebugActionFactory-Tuple{Symbol}

[mateuszbaran]

alg_cache is basically for getting the default state for an algorithm. The idea is similar to the factory pattern for stopping criteria introduced recently in Manopt.jl. The variety of arguments of alg_cache is for passing anything at least one algorithm needs to cover some corner case. Most of the time the first three are sufficient, and they correspond to algorithm, and examples of point and tangent vector in Manopt.jl. IIRC the last one is for in-place/allocating distinction but SciML apparently considers booleans to be more appropriate than a special type for some reason 🤷 .

Almost all SciML also assumes that all points behave more or less like an AbstractArray (they need to have eltype, ndims, getindex) which is not great.

[kellertuer]

Good to know. So the alg_cache is in our current terminology maybe some create_state function or really just a State(problem, algorithm) constructor.

And yeah we should not depend on those details for iterates, for sure.

But before doing that more concrete I would like to take a look at a few more examples here and collect ideas over on #1.

[mateuszbaran]

I see, though I think SciML is not a particularly great source of inspiration, especially considering internal structure.

[kellertuer]

I mainly wanted to have it here as an inspiration what not to follow concerning internal structure.

[kellertuer]

Optim.jl

Optim.jl seems to have optimisers and their states, see e.g.

https://github.com/JuliaNLSolvers/Optim.jl/blob/master/src/multivariate/solvers/first_order/gradient_descent.jl

They sometimes have obj and x additionally (in init state?) and a d as a first argument in cg (direction?)

Besides that it seems they have a solver and a state – and where the problem resides is not fully clear to me.

Their general solver run, cf https://github.com/JuliaNLSolvers/Optim.jl/blob/b041bd63373cf2403180c6993eff235b5c010670/src/multivariate/optimize/optimize.jl#L52, seems quite involved and not just do update_state but a lot of other things as well (with a few isa ifs...)

So their general structure seems to maybe be a bit chaotic.

One things that might be nice to consider is, whether the “shortcut keyword” maxiter= (I would maybe prefer max_iterations= for readability could take the actually passed stopping criterion s and wrap that as s | StopAfterIteration(max_iterations)
In a similar fashion one could check whether other “shortcut keywords” might be useful.