Category Theory
Zulip Server
Archive

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.

Stream: theory: applied category theory

Topic: convex optimization

Bryan Bischof (Apr 03 2020 at 05:46):

I was curious if anyone had references or anything they wanted to share about connections between convex optimization and ACT. I know there's the economics stream now, and that's one place where you might expect things to end up related, but I wanted to open up this conversation in case people knew things already, or were interested. Thanks!

Soichiro Fujii (Apr 03 2020 at 09:27):

@Simon Willerton has worked on an enriched categorical viewpoint of the Legendre-Fenchel transform, one of the most fundamental technique in convex optimization. See here for his paper, and here for a blog post.
The basic idea is that the Legendre-Fenchel transform can be seen as taking the “Hom’’ of $\overline{\mathbb{R}}$-profunctors, where $\overline{\mathbb{R}}=([-\infty,\infty],\geq,0,+)$ is the quantale of extended real line.
I am not sure if/how this relates to the popular ACT approaches, though.

Jules Hedges (Apr 03 2020 at 11:01):

Coool! That's going on my reading list

Jules Hedges (Apr 03 2020 at 11:04):

I have a mostly worked out account of optimisation from a very ACT perspective which I sort of explained somewhere up in #applied category theory > measuring non-compositionality, I never explicitly tied it to convex optimisation but that was the main "nice" setting I had in mind

Jules Hedges (Apr 03 2020 at 11:05):

But I've sort of abandoned that after finding that $\arg\max$ isn't functorial, which seems to defeat the point of it

Matteo Capucci (he/him) (Apr 03 2020 at 12:00):

Soichiro Fujii said:

Simon Willerton has worked on an enriched categorical viewpoint of the Legendre-Fenchel transform, one of the most fundamental technique in convex optimization. See here for his paper, and here for a blog post.
The basic idea is that the Legendre-Fenchel transform can be seen as taking the “Hom’’ of $\overline{\mathbb{R}}$-profunctors, where $\overline{\mathbb{R}}=([-\infty,\infty],\geq,0,+)$ is the quantale of extended real line (sometimes called the Lawvere quantale).
I am not sure if/how this relates to the popular ACT approaches, though.

That paper is so nice!! A great example of categorical insight in a classical subject. Thanks for linking it here!

Bryan Bischof (Apr 03 2020 at 14:57):

Thanks for the reference and replies. I definitely expected @Jules Hedges had some ideas here. I wonder about things like Lagrange multipliers type problems especially and shadow prices.

I’ll give the linked papers a peek and I’d be happy to read what you’ve already thought about Jules.

Jules Hedges (Apr 03 2020 at 14:59):

Part of the motivation for the compositional optimisation thing I was talking about was exactly that it could deal with Lagrange multipliers nicely. Not with any deep theory, just practical, to add a constraint to a variable you pull off a copy of that string in your diagram and stick a Langrange multiplier to it

Bryan Bischof (Apr 03 2020 at 15:04):

Ahh that sounds really interesting to my uses.

Nathaniel Virgo (Apr 03 2020 at 15:34):

Sounds really useful for information geometry as well, convex functions and Legendre transformations are everywhere there.

Jules Hedges (Apr 03 2020 at 15:42):

@Bryan Bischof This paper is sitting around unfinished. Since argmax isn't a functor, as far as I can tell it's cute but I can't think of any actual use for it. If you can think of a use for it, I'd like to hear about it!

Philip Zucker (Apr 03 2020 at 16:41):

I had a fun little prototype for a category flavored frontend to cvxpy I was fiddling with here http://www.philipzucker.com/categorical-combinators-for-convex-optimization-and-model-predictive-control-using-cvxpy/

Simon Willerton (Apr 03 2020 at 16:42):

I'm definitely interested in thinking about categories and optimization as @Soichiro Fujii hinted. My main obstruction at the moment is an admin heavy role I'm in that will last for another 18 months...

Philip Zucker (Apr 03 2020 at 16:44):

I've also been working on a prototype that does a little more heavy lifting using combinators for optimization via ADMM. ADMM is a fairly popular first order method for plugging together convex optimization solvers. It has some flavor of backprop and gauss-seidel iteration to it.

Bryan Bischof (Apr 03 2020 at 18:04):

Lots of super interesting things here. To your point @Nathaniel Virgo that’s the most exciting connection for me and would love to start reading any references you have.

And as always @Jules Hedges your work is so interesting but I don’t feel like I’m in a place to give you any guidance, mostly hoping to learn from you.

@Philip Zucker this is a great idea, I’ll try to give it a look. What’s the future of this project for you? I use cvxpy for my job already.

Paolo Perrone (Apr 05 2020 at 05:42):

Just thought I'd mention this: concave and convex functions are the lax and oplax morphisms of ordered convex spaces.

Bryan Bischof (Apr 06 2020 at 03:11):

That’s pretty cute.

Philip Zucker (Apr 14 2020 at 21:41):

I'm not sure what the future of the project is. At the moment I'm enjoying building quick little proofs of concept in python and experimenting with interfaces. I'm not sure if my energy is better spent trying to build things in Julia to interface with Catlab or if I should collect up all my little examples and put it all in a consistent repo somewhere.

Philip Zucker (Apr 14 2020 at 21:46):

The idea is still probably basically unusable without some serious ergonomic helpers. I vaguely think I need to somehow couple together the convex relations with labels built in FinSet in mimicry of the decorated/structured span stuff. At the moment the different wires are coupled together by position.

Evan Patterson (Apr 14 2020 at 22:47):

Hi @Philip Zucker , I think the stuff you've been exploring with convex relations is very cool. If you're interested in going the Julia route, I'd be happy to help where I can. In Catlab, we've recently created a new place for experiments that might eventually become part of the core library or their own packages. Of course, you could also just create your own repo for a Julia package. (Eventually, Catlab, SemanticModels, Petri.jl, and other packages in the nascent Julia ecosystem will be moved into a common GitHub organization to reflect what we see as fundamentally a community effort.)

James Fairbanks (Apr 14 2020 at 22:58):

I can second that the Catlab ecosystem is a really great place to do this stuff. The optimization community is active in Julia and very interested in modeling languages for optimization (see Jump.jl). You have a type system that is more helpful than Python’s but more opportunities to work with domain scientists/engineers than you would in Haskell.

Philip Zucker (Apr 14 2020 at 23:58):

Julia has a lot going for it. Almost the only downside is that python already has such broad usage and familiarity. It can be doubly tough to swallow a library with new concepts and a new language at the same time.

Evan Patterson (Apr 15 2020 at 00:12):

That's true. Python is a popular language that a lot of people feel comfortable working in. What I would say is that Julia is also a pretty friendly language. It's certainly not an esoteric language or one that someone coming from Python would find totally alien. Also, a lot of existing functionality in the Python ecosystem that people depend on is becoming available in Julia as well. So, the CVXPY library that Bryan mentioned upthread has a counterpart in Convex.jl, written by the same developers (Stephen Boyd's group at Stanford) and with a very similar API.

Jules Hedges (Apr 15 2020 at 09:57):

Ah, I wish I could help with this stuff, if only I knew any language close to Julia and had any time to spare...... I'm convinced this stuff is the future