Initial discussions

[lkdvos]

Looking at the readme file, that seems like a great place to start.
Some thoughts and considerations that I'm trying to collect here:

Features

The main features I would be looking for, which more or less aligns with what is currently proposed:

• Generic framework to formulate algorithms so I don't have to think too much about the structure, and how to combine the pieces. In order to make this flexible, it tends to be nice to have a bunch of different "entry-points": functions that can be hooked into using Julia's multiple dispatch. In that way, we can provide a generic framework for the algorithms, but if some algorithm needs to deviate, they can still overload at different stages.
• Common interface for logging: some utilities for logging, dealing with nested algorithms in a nice way (automatically handling indenting etc).
• Common interface for recording and returning information during solving
• Common interface for stopping criteria
• Common interface for "algorithm selection"/"configuration" -> how do we go from a bunch of keyword arguments to a standardized form to use in the algorithm

Some other goodies, such as:

• Progressbars?
• Dynamic tolerance scaling: subalgorithms have stopping criteria based on the state of the parent
• Multiple algorithms in sequence: for example algorithms that occur in two stages: typically first a cheap initial set of iterations, followed by a more expensive convergence procedure.

---

I like the abstraction in terms of tasks, here are my initial thoughs about that:

Whenever possible, I would like to design the functionality as much as possible around functions, and not types. I think this is one of the most common things that packages that want to be generic get wrong. This boils down to Julia having a type tree instead of a more generic type system. Often, having to decide if something has to subtype either abstract type A or B, is a big source of friction to adapt/extend into. Basically, I would try to design functions with fixed arity, such that the position of the argument determines its functionality, while the type can be anything. Here is an example of something like this, where we are only dispatching on the Algorithm type, but otherwise use positional arguments. (see bottom for the boilerplate).

I like the design in terms of separating static information about the problem from the mutable state during the problem.
I think I would even suggest splitting it a bit further, going for:

• Problem: static information about the problem to solve, can always assume this does not change during the solving
• Algorithm: full specification of the algorithm to solve with. Serves as a "glorified NamedTuple": it holds the settings, and is used to dispatch between different implementations. Again, assume this does not change during the solving.
• State: All information that is carried between iterations. This ideally has optional mutation. (possibly state = step!!(state, problem, algorithm)?)

---

Of course, all of this is guided by things that I've used and experimented with in the past, and one of the nice parts of sharing is merging things that we like and discarding things we don't like.
Let me therefore share some design patterns and approaches that I have particularly enjoyed, and think would make sense to put in a package like this. (Please do feel free to share yours, I think this can improve all our experiences)

• Algorithm combination: although I am not too happy about the name, having &(::Algorithm, ::Algorithm) is something that is used a lot and is very convenient.
• Dynamic tolerance algorithm wrapper: For nested algorithms, this ensures subalgorithms have stopping criteria based on the parent state.

[kellertuer]

Super nice ideas!

• logging: Is for me the same as I said with debugging, just pass in different IOBuffer (the debugs in Manopt.jl can do exactly that) – so maybe we can even name it more like logging

• record and stop – yes!

• I did not yet think about algorithm selection, also very nice. For configuration – I was thinking of doing some factories in between and/or dictionaries. But a very good point to think about

• progressbars might be a bit complicated if it is not 100% clear how many iterations there are, but they could be part of logging/debugging for sure

• not only dynamic tolerances, possibly also dynamic logging – in Manopt I have this trick that a sub solver only prints debug if the parent is “active debug mode”. For example if the parent only prints debug every 25th iteration – the sub solver also only gets activated in the 25th iteration

The model of Problem / Algorithm / State sounds good, I think for now I often combined Algorithm and state – and they were always mutating, why would we do non-mutation ones? But sure in general we could do non mutating ones.

I can check tomorrow for examples from my side as well – about nested algorithms for example. Thanks for all the ideas!

[lkdvos]

The non-mutating ones can be useful when you don't actually have a mutable struct. Perhaps not always necessary, but you can do things like: state = (half_of_state, other_half_of_state) (using a tuple), or have a lightweight state like a NamedTuple. Basically, I would say that we should try and not depend on the memory location being the same, even though often we would have (state === step!!(state, ...)).

[lkdvos]

As an addendum after some more discussions with @mtfishman : something that I've always found to be quite elegant is the "iterator" approach, which I've first seen in IterativeSolvers.jl but have since seen in various forms and incarnations throughout the Julia ecosystem.
Basically, the idea is to wrap solving in an iterator (fragment from IterativeSolvers.jl docs:

function my_solver!(x, A, b)
    iterable = MySolverIterable(x, A, b)
    for item in iterable end
    return iterable.x
end

What is nice about this approach is that it allows you to insert arbitrary callback functions between iterations. (Also, I just think it looks very elegant).

See also:

• https://docs.sciml.ai/DiffEqDocs/stable/basics/integrator/#Initialization-and-Stepping
• https://github.com/QuantumKitHub/MPSKit.jl/blob/master/src/states/ortho.jl

The biggest problem is that it tends to clash with some of the concepts that are linked with Base.iterate(iter, state) = next, state:

• For iterative algorithms, iter is typically best considered stateful: you are no longer guaranteed that first(iter) == first(iter), and instead you would get something like deepcopy(iter) == (first(iter); first(iter); iter).
• For efficiency, it's probably not a great idea to have an independent copy of next after every iteration, and rather you want to mutate this in-place. This does however result in collect(take(iter, 5)) giving a vector with 5 times the exact same object, ie you cannot simply use this pattern to collect the state at each iteration (map(copy, take(iter, 5)) would work).
• In this interface, state is visible only for the algorithm, while next is visible only for the user. In order for changes that the user makes on next to be visible by the algorithm, these must share memory.
• Having users insert arbitrary functions that mutate the state might break algorithms, especially those that have some dependencies between iterations (LBFGS, CG, Krylov, ...). Protecting from this is hard.

Some of these things have also partially been discussed here and here

The SCIML interface does have some particularly nice features that wrap an iterator and influence how it returns information, possibly every n iterations, with detailed information, ...

I'd love to hear your take on this as well, since I do think it has some advantages as well as disadvantages.

[kellertuer]

I first have to wrap my head around bit more about <our idea of splitting algorithm and state already. ;)

I do not understand your code snipped nor the iterator approach for now – but inserting callbacks is not so complicated in the other approach either, since debug/record/... anyways have their “spot” to be called (in Manopt realised by state-wrappers, though there might be other solutions).
So could you elaborate a bit on the iterator idea? I do not understand it (not iterators per se but how they would be used here)
For anything SciML -related, my feeling is often that most of SciML ist mainly undocumented, at least not to the extend I would need to understand something. What they call cache, I would probably consider our idea of a state – though also there I never understood their cache really.

So my take on that in short is: I have nearly no clue what SciML is doing (and I tried for a few times, since we use their ODEsolvers every now and then, they mainly keep breaking our CI) – and for the generic idea – I have not yet understood it. As opposed to the step!(prob, alg, state) that I have understood ;)
So maybe you could elaborate a bit more? For example for the iterators I do not see any other stopping criterion than maxiter for now?

[lkdvos]

This is not really a SCIML approach and really predates their adoption of this pattern (or different versions of it). I would definitely say it's IterativeSolvers that came up with this. (making a point out of this because I also don't particularly think SCIML tends to be a great example)

Some sketch, mapping some parts of our previous discussion and the readme, obviously names and argument orders etc susceptible to bike-shedding:

Algorithm definition:

mutable struct IterativeSolver
    const algorithm
    const problem
    state
end
function IterativeSolver(algorithm, problem, args...)
    state = # algorithm setup
    return IterativeSolver(algorithm, problem, state)
end

function Base.iterate(iterable::IterativeSolver, state=iterable.state)
    # stopping criterium
    isdone(iterable, state) && return nothing
    
    # main iteration of the algorithm
    nextstate = step!!(state, iterable.problem, iterable.algorithm)
    
    # bookkeeping
    iterable.state = nextstate
    item = user_facing_returns(iterable, nextstate) # decide what the iterator returns

    return item, nextstate
end

Base.isdone(iterable::IterativeSolver, state=iterable.state) = # stopping criterium

Algorithm usage:

function my_solver!(initial_guess, algorithm, problem)
    iterable = IterativeSolver(algorithm, solver, initial_guess)
    for item in iterable end
    return iterable.x
    # possibly equivalent: return last(iterable)
end

# advanced usage, with callbacks:
iterable = IterativeSolver(algorithm, solver, initial_guess)
for (i, item) in enumerate(iterable)
    my_advanced_function!(item)
    @info "my really cool logging feature" iter=i
    push!(my_observables, observe(item))
end

As you can see this does not really meaningfully change any of the functionality, it's more about code organization I think.
There are some cool tricks you can play with it, enumerate being the simplest example to give you access to the iteration number.
Some other things that can be achieved, just as illustration:

struct TimeoutIterable
    iterable
    max_time
    start_time
end
TimeoutIterable(iterable, max_time) = TimeoutIterable(iterable, max_time, start_time=Base.time())

Base.iterate(iterable, state...) = iterate(iterable.iterable, state...)
Base.isdone(iterable, state...) = (Base.time() - iterable.start_time) > iterable.maxtime || isdone(iterable.iterable, state...)

[kellertuer]

Thanks for that long example. I did not mean to say SciML came up with it, just because you mentioned them as a reference, theirs did not help me to understand what it does. So I do agree, they are maybe not a good example

I like that longer example and I think I roughly understand that. Neat! SO yeah let's maybe go for that as well. I can sketch a few first things in code the next few days

Also when you mention IterativeSolvers besides “who might join such an interface?” (when to ask for input but also whom to have in mind as audience to use the interface) – we should also check a bit what exists maybe already. Maybe both would be good new discussion points.

Thanks for all your comments here :)

[kellertuer]

Oh the TimeoutIterable I do not like so much I would prefer a generic version with stopping criteria that can be combined with | or &(e.g. the nice and readable from StopAfterIteration(400) | StopWhenChangeLess(1e-9) since that is nicely readable. But those are probably details we‘ll figure out along the way.

[lkdvos]

Definitely agree with the stopping criteria being a separate issue, better handled like you describe.
I'm mostly trying to come up with good illustrations and brainstorming :).
A different example might be:

struct Checkpointed
    iterable
    frequency
end

function Base.iterate(iterable::CheckPointed, state...)
    next = iterate(iterable.iterable, state...)
    isnothing(next) && return nothing
    item, state = next
    for _ in 1:iterable.frequency-1
        next = iterate(iterable.iterable, state)
        isnothing(next) && break
        item, state = next
    end
    return item, state
end

[kellertuer]

I think one point I would like to understand a bit more – philosophically – from your ideas is the split between Algorithm and its state.

Until now my mental model was often

• We have a Problem that contains all data describing the problem itself (a cost, maybe a gradient, for me the manifold...) – this is static data that does not change throughout the iterations
• We have an AlgorithmState that contains parameters of the algorithm: a step size (maybe even with the last computed one), a current iterate, maybe some relaxation parameter that might influence a step... These usually change throughout the iterations and interact, but some of them might actually be static as well – something like a constant step size in a stochastic gradient descent.

What is the benefit of splitting the last point into two and how to split that?

• The Algorithm would specify the algorithm with all its static properties (generically which step size to use? So maybe just the Armijo type?)
• the state would carry an instance of the step size (since like Armijo it has to remember its last one to restart the next, the current iterate...

Would that mean one can create_state(a::Algorithm) – but for the start we would still need the 0th iteration as init(p::Problem, a::Algorithm, s::State) ?
How would one best do such a split and what are the advantages?

[lkdvos]

I think obviously the exact way of splitting tends to vary a bit depending on the use-case, but what I tend to think of is this:

There is the information that defines how to do iterations and what that should be (think of this as hyperparameters perhaps)

• stopping criteria
• actual solver algorithm and relevant hyperparameters (eg ConjugateGradient with HagerZhang linesearch)
• how/what to log and debug
  This tends to be static: even though the actual logging might depend on the iterations, the hyperparameters that are used to decide this are static.

There is the information that defines the current state of the algorithm:

• what is my current best guess
• what is my current gradient, the norm thereof, ...
• ...

Basically, you could summarize this as: if I forget the information about the current state of the algorithm, and only remember the algorithm, I could start the exact same routine all over again, but it would start from iteration 0.
Conversely, if I forget the algorithm but remember the current state, I could conceivably continue with a different algorithm, perhaps to do a more expensive but more accurate tail of the iterations.

Keep in mind, this is mostly an organizational thing in my mind, and the code does not actually need to reflect this.
Investigating it a bit further, I think it stems mostly from the fact that we typically don't have an explicit Problem struct, so we needed something else to dispatch on.
I think more and more that the difference does not matter too much, I can probably make either thing work and fit.

In any case, I think it's something we can iterate on anyways, there's not really any difference between the two things below:

struct State
    some_information
    some_other_information
end
state

contains the same amount of information as

struct State
    some_information
end
struct Algorithm
    some_other_information
end
(state, alg)

[kellertuer]

That sounds reasonable. So that is the same idea I understood: The Algorithm is enough information to initialise a state.

That is an interesting split, because a lot of elements, like a stopping criterion always have a static part (the threshold for a change) and a state one (store the last iterate to check change in iterates).

But sure thinking about Alg/State split is an interesting thing to take into account.

[kellertuer]

I looked a bit at the iterator interface – besides the naming,
where I would use step!(problem, algorithm, state, k) to implement the k-th step that would require to implement (k, state) = iterate(k, state), where the state would probably be the three tuple (problem, algorithm, state) and the name would not indicate mutation.

Besides this naming thing being a negative point, I do not yet see a positive point in using the iterate interface.

[kellertuer]

That sounds like a very good plan, yes!
I think if we encounter a good reason for supporting the iterator scheme/interface, it might be nice to support that. For now I do not see much of a benefit.

Nice. I think we have most things discussed then. I will try to find a bit of time and get started with the first few things soon then.

[lkdvos]

Let me know if you want me to chip in somewhere, give opinions or test something out. I can definitely also try to set something up, but I guess we should not do this both at the same time?

[kellertuer]

I would do the first steps here always as PRs to discuss I think. That way, we could even start in different areas of the discussed things – at least after we have fixed the main abstract types. For them my only point to discuss would be whether we use AbstractAlgorithm or Algroithm for the main types as scheme.

[lkdvos]

I think I prefer Algorithm, I don't think Abstract_ here adds a lot of value.

[kellertuer]

Ok, honestly I also have not been super consistent with that throughout (just within single) packages, so I am fine with both. Then let's do interfaces with generic names but not Abstract

[kellertuer]

Sorry for a bit of delay here. I hope to continue with an idea for a debug state soon