You're reading the public-facing archive of the Category Theory Zulip server.
To join the server you need an invite. Anybody can get an invite by contacting Matteo Capucci at name dot surname at gmail dot com.
For all things related to this archive refer to the same person.
Kyle Wilkinson (Dec 01 2023 at 19:43):As has been pointed out in this forum by Jules Hedges (and maybe others), and is general knowledge in the field of optimization, optimization problems are not compositional, unless trivially so (i.e., they are independent such that they don't share variables or constraints). Recent work involving convex optimization (like with convex bifunctions) gets at ways to directly compose optimization problems and the resulting category does in fact have some nice additional hypergraph structure. But, such composition amounts to a solution of one problem becoming a perturbation of the next problem's constraints, which is basically just currying the convex function, as was pointed out by Stein/Samuelson at ACT-23.
However, and sort of the main point I am getting at, in practice there are ways of solving such problems anyway. Of "creating" non-trivial compositionality, perhaps. In other words, it is generally a common solution technique to iteratively solve a set of subproblems and force them to converge to an overall solution, which is in fact optimal for the composed problem, but may be (and probably will be) sub-optimal for any of the subproblems in isolation. So coordination acts to broker the set of sub-solutions toward a common goal.
So we still have "non-compositionality" since optimality remains not compositional. The optimal solutions of the subproblems still do not directly compose into the overall optimal solution. However, we have in some sense side-stepped the issue by switching back and forth between the subproblems and the overall problem via a coordination mechanism, allowing one or the other (sub- or overall-) solutions to be sub-optimal as needed. In optimization, this mechanism often operates via principles of duality.
Is there any categorical notion which might capture this idea of iterative "forcing" of compositionality? Perhaps convergence would be a better term. For example, has anyone used a higher-category model which can capture iteration, convergence, coordination, or something similar as higher morphisms?
JR (Dec 01 2023 at 19:52):What about homotopy methods
Kyle Wilkinson (Dec 01 2023 at 20:01):JR said:
What about homotopy methods
Sure, I would be interested in exploring this, too, though I do not yet have much exposure to homotopy.
JR (Dec 01 2023 at 21:00):See https://www.osti.gov/servlets/purl/876373-8hy6gp/ and imagine doing this for each function in a composition, say by using a common parameter.
David Egolf (Dec 01 2023 at 23:35):This stuff interests me a lot because it sounds relevant to image reconstruction for medical imaging, which is a long-standing interest of mine!
A couple related questions occurs to me: What are some situations where we want to model things that exchange information with one another? And what tools can be used to do this?
For example, to make a larger model from several regional models for how disease is spreading, one presumably needs to allow for data to flow between the two submodels: if disease is spreading towards the edge of the region modelled by one submodel, this should presumably impact the predictions of the neighbouring region submodel.
David Egolf (Dec 01 2023 at 23:40):(I believe that @Kyle Wilkinson is specifically interested in the situation where multiple iterative optimization problems can be run in parallel with exchange of information. This is notably different from having several sub-problems that run in sequence, where the result of one sub-problem determines the starting conditions or constraints for the next sub-problem).
JR (Dec 02 2023 at 01:01):David Egolf said:
(I believe that Kyle Wilkinson is specifically interested in the situation where multiple iterative optimization problems can be run in parallel with exchange of information. This is notably different from having several sub-problems that run in sequence, where the result of one sub-problem determines the starting conditions or constraints for the next sub-problem).
Belief propagation is in this vein
JR (Dec 02 2023 at 01:02):See also Message-Passing Algorithms for Inference and Optimization
Nathaniel Virgo (Dec 02 2023 at 09:44):I'd really love to know "what's really going on" with message passing algorithms - it seems like there should be some interesting higher categorical structure there. It always seemed to me a bit like lenses/optics, except that instead of having one forward pass and one backward pass it keeps going forward and backward indefinitely.
JR (Dec 02 2023 at 15:07):Nathaniel Virgo said:
I'd really love to know "what's really going on" with message passing algorithms - it seems like there should be some interesting higher categorical structure there. It always seemed to me a bit like lenses/optics, except that instead of having one forward pass and one backward pass it keeps going forward and backward indefinitely.
Take a look at MacKay’s book online, which frames BP and neural nets in a common way and you may recall the Backprop as functor (= chain rule as functor) perspective on neural nets as something of interest.
Nathaniel Virgo (Dec 03 2023 at 02:03):That's what I'm referring to I think - I'm saying I'd like to see that properly worked out some time. I don't think message passing is literally an instance of the machinery in 'backprop as functor' (maybe I'm wrong?) but it's clearly related.
Simon Burton (Dec 03 2023 at 08:01):Backprop & message passing: it's all about distributivity .
Jean-Baptiste Vienney (Dec 03 2023 at 17:10):Maybe you could be interested by this paper: The logic of message-passing (Cockett & Pastro). If you're interested by the quantum version, these slides: Quantum Message Passing Logic - Part One, Part Two (Priyaa Varshinee).
Jean-Baptiste Vienney (Dec 03 2023 at 17:14):In fact Part One is mainly a tutorial on the first paper and Part Two about trying to make it quantum.
Kyle Wilkinson (Dec 04 2023 at 17:14):Thanks for the links and leads. I suppose it is the way of category theory to involve very general concepts as answers for specific applications! They've been helpful.
Perhaps extensions of resource theory into concurrent processes may prove useful. In particular, this recent paper by Nester and Voorneveld https://arxiv.org/pdf/2305.16899.pdf may be relevant.
The toy example they give is one of kneading and baking dough into bread. In the typical monoidal resource theory, we'd set it up as dough-->oven-->(bread+oven). But this implies a series structure on the processing line. If we want to run those two subprocesses independently, passing outputs of one subsystem to another for further processing, then Nester's cornering construction allows for it. They then go on to construct a representation of iteration between the processes.
What I am not clear on yet is whether their process can be made bidirectional. It is clear that the "decider" Bob can choose to have the inputs from Alice be recalculated, or to reiterate the process, but it is not clear whether Bob can update values which Alice then must use in her process. But, I've only done a cursory read.
Kyle Wilkinson (Dec 04 2023 at 17:17):It is the ability for Bob to pass back values to Alice which I think encompasses the idea of coordination, with Bob as the coordinator. Coordination in this case implies that "Alice" is in fact several entities who all pass information to Bob independently of each other.
David Egolf (Dec 04 2023 at 17:27):There's a nice picture in that paper which illustrates the toy example:
toy example
The authors explain this as "The cell on the left describes a procedure for transforming dough into nothing by kneading it and sending the result away along the right boundary, and the cell in the middle describes a procedure for transforming an oven into bread and an oven by receiving dough along the left boundary and then using the oven to bake it." (In the original picture, there's a third cell on the right, which I haven't included here).
So I think the "dough" is being passed between two subsystems.
Kyle Wilkinson (Dec 04 2023 at 17:44):David Egolf said:
So I think the "dough" is being passed between two subsystems.
Yes.*
The dough is passed one-way. Once baked, it is never kneaded again of course. I would interpret the iteration portion of their method to involve the oven process receiving the dough and deciding that the gluten is not developed enough and that it needs more kneading, thus the first kneading process is iterated once more. I'm curious if there is some way of sending additional information back, more than just "try again." To continue the example, perhaps something like: "you (subprocesses) thought this was good dough. To me, this is lacking in XYZ quantity. Update your level of kneading accordingly and try again."
*Edit: Actually, the dough is being passed down the line. There is a clear dependency/directionality here. So, you are correct, but the nuance I am trying to grab hold of is something being passed to a coordinator, which then makes a decision on whether to reiterate and also influences the reiteration. So in this case, I am thinking of the oven subprocess as existing "above" the kneading subprocess. But of course the oven may exist "below" some other process, too.
Spencer Breiner (Dec 04 2023 at 21:38):Kyle Wilkinson said:
What I am not clear on yet is whether their process can be made bidirectional. It is clear that the "decider" Bob can choose to have the inputs from Alice be recalculated, or to reiterate the process, but it is not clear whether Bob can update values which Alice then must use in her process. But, I've only done a cursory read.
If I understand correctly, there are two operations turning vertical wires (= horizontal one-cells) into horizontal wires, denoted and , which can be thought of as "send " and "receive ". I prefer the notation and .
Spencer Breiner (Dec 04 2023 at 21:44):I find things easier to think about if we imagine adding in a (directed?) graph of locations/addresses and channels/paths to the cornering construction in that paper. Then we could imagine that the associated double category has objects corresponding to locations and types "send/receive along " for edges in the graph.
In order to "straighten out" a parallel process into the the base monoidal category, you would (at minimum) need to bring data together to a common location before comparison.
Spencer Breiner (Dec 04 2023 at 21:47):The one-object case from the paper would correspond to a graph with one vertex and one reflexive edge, and (for me) it's the conflation of sending location and receiving location that makes the theory a bit tricky to follow.
JR (Dec 10 2023 at 03:26):https://arxiv.org/abs/2201.11876
Kyle Wilkinson (Dec 11 2023 at 16:48):JR said:
This looks pretty promising, thanks! At first glance, it describes arriving at global conditions from a set of local conditions with possible overlap, which is basically what I am looking for.
JR (Dec 13 2023 at 13:29):https://proceedings.allerton.csl.illinois.edu/media/files/0115.pdf
JR (Dec 26 2023 at 17:51):image.png
From Jakob Hansen's dissertation
Kyle Wilkinson (Dec 26 2023 at 21:19):JR said:
image.png
From Jakob Hansen's dissertation
Thank you. This appears essentially like what I am looking for, only I am not familiar enough with the background material. I can understand the optimization aspects (KKT conditions and so forth), but does anyone know any accessible sources on sheaf cohomology for someone with no exposure?
Incidentally, I see now why folks here have been mentioning cohomology as a way of getting around or at least quantifying non-compositionality.
JR (Dec 26 2023 at 21:22):Rosiak's book treats (cellular) sheaf cohomology with some detailed examples.
John Baez (Dec 27 2023 at 10:25):It can't hurt too much to read the Wikipedia article on sheaf cohomology. It may be hard to follow, but at least it's short, it starts with a sketch of what sheaf cohomology was originally used for, it states many of the fundamental facts about sheaf cohomology, and it has links to definitions of all the concepts it assumes you know (like "sheaf", of course).
Kyle Wilkinson (Dec 30 2023 at 20:00):JR said:
Rosiak's book treats (cellular) sheaf cohomology with some detailed examples.
Thanks! This is a good source for describing basics of category theory, too for any beginners who might be interested. It also has a partial focus on philosophical considerations, which I find interesting apart from the math.
Kyle Wilkinson (Dec 30 2023 at 20:05):John Baez said:
It can't hurt too much to read the Wikipedia article...
I imagine you are already aware as you have been looking into music theory math, but in the Rosiak book, he mentions some music theory from R-modules. A footnote from there:
''16. Modules play a large role in much of mathematical music theory, especially variants of R{O, P, L, D} and the module of integers mod 12 (under addition), together with its affine transformations. At least as far back as Lewin (see Lewin (2010), originally published in 1987), transformations between musical elements (instead of musical objects like the C major chord) became the focus of many music theorists, where the transformations in question often form a group. Certain elements of algebra, especially group theory, have accordingly been used for some time to systematize the treatment of common operations on musical chords, and geometrical models of musical structure have also been considered by a few authors (such as Tymoczko (2011)). Approaches to questions of music theory that incorporate category theory (starting with Mazzola (1985)) are somewhat harder to come by, but the reader curious about more category theoretic takes on music may find interesting Popoff, Andreatta, and Ehresmann (2018), Noll (2005), and the work of Guerino Mazzola and followers. The module R{O, P, L, D} presented above, together with further uses of it, is discussed in Mazzola and Andreatta (2006).''