Bounding the domain of the objective function by using Bregman Divergence instead of Euclidean norm

[ErwanMeunier]

Hello,

To the best of my knowledge, PESTO allows to represent algorithms involving (i) a bounded domain via the Euclidean norm (ii) a mirror step based on the mirror map (NoLips like methods) 1.
Is there a mean to, in some sense, mixing (i) and (ii) so as to represent the boundedness of the domain by using the mirror map $h$?
Formally, what I would like to do is:

$$D_h(x,y) \leq R^2 \quad \forall x, y$$
where $D_h$ is the Bregman Divergence equipped with kernel $h$ and for some constant $R$.

Kind regards,
Erwan

[AdrienTaylor]

Hello Erwan,

Thank you for your interest and question! So, in short: yes, you can.
However, I am not sure the "direct" approach will be tight, and a bit of care should be taken to do it properly. In particular, if you call h.value(x) each time you want to put one of those constraints in the PEP, the SDP might be uselessly huge.

To help you, I need you to be a bit more specific about what you want to do (for instance: do you want to study mirror descent with such a constraint on the size of the set?)

Best,

Adrien

[ErwanMeunier]

Hello Adrien,

Thank you for your help and your consideration. Yes, it's exactly what I am aimed at. In practice, I am studying an online decentralized optimization algorithm [1] using (i) mirror descent in the update policy:

together with an assumption (ii) on the domain $\mathcal{X}$, which is in some sense bounded using the Bregman Divergence (the kernel is denoted $\mathcal{R}$):

I have succesfully managed to represent the mirror descent and the rest of [1] by relying on [2] and [3] but I am struggling to represent (ii). By the way, I use the spectral relaxation described in [3] to represent the communication matrix $W$, thus I am no longer tight in most cases, but I look forward to hear you advises to get a worst-case bound as tight as possible.

I hope I've made myself clear.

Best,

Erwan

References:
[1] S. Shahrampour and A. Jadbabaie, "Distributed Online Optimization in Dynamic Environments Using Mirror Descent," in IEEE Transactions on Automatic Control, vol. 63, no. 3, pp. 714-725, March 2018, doi: 10.1109/TAC.2017.2743462.

[2] Bousselmi, Nizar & Hendrickx, Julien & Glineur, François. (2023). "Interpolation Conditions for Linear Operators and applications to Performance Estimation Problems".

[3] S. Colla and J. M. Hendrickx, "Automatic Performance Estimation for Decentralized Optimization," in IEEE Transactions on Automatic Control, vol. 68, no. 12, pp. 7136-7150, Dec. 2023, doi: 10.1109/TAC.2023.3251902.

[AdrienTaylor]

Hello Erwan,

Sorry for the late reply; I was off on vacation!
As a starting point, I think you should write a code for the mirror descent setup you want to study in the centralized scenario.
In this case, there is already one tricky part: you should make sure that you do not evaluate too many (sub)gradients of the function that you use for evaluating the Bregman divergences. This is somewhat simpler in PEPit (https://pepit.readthedocs.io/en/0.3.2/), but the problem there is that the decentralized algorithms are not deployed. In PESTO, the easiest way is to provide your points with names/'tags' (see UserManual here: https://github.com/PerformanceEstimation/Performance-Estimation-Toolbox/blob/master/UserGuide.pdf).

So in short: start & validate your code with the simplest possible setups first, and add the more advanced ingredients afterwards!

Cheers,
Adrien

[ErwanMeunier]

Hello Adrien,

Thank you again for the advises! :)

Best,
Erwan

[AdrienTaylor]

My pleasure; I am also happy to help with debugging and/or to discuss it remotely if necessary.

For mirror descent, there are a few examples already implemented (in the "relative smoothness" setup), which you can use as a starting point :)

Cheers,

Adrien