I have two sets of variables vectors $\{{\bf x}_i\}_{i=1}^N$ and $\{{\bf y}_{ij}\}_{(i,j) \in A}$ where $A = \{ (i,j) \text{ such that } i \in \{1,\dots,N\} \text{ and } j \in \{1,\dots,M\} \}$.
I'm looking for an iterative algorithm that solves the following optimization problem $$ \underset{\{{\bf x}_i\}_{i=1}^N, \{{\bf y}_{ij}\}_{(i,j) \in A}}{\min} \sum_{i=1}^N f_i\left({\bf x}_i, \sum_{j=1}^M {\bf y}_{ij}\right)$$ where the functions $f_i(\cdot)$ are differentiable.
To make myself clearer, let $N=2$ and $M=2$, then my optimization problem writes $$ \underset{{\bf x}_1, {\bf x}_2, {\bf y}_{11}, {\bf y}_{12}, {\bf y}_{21}, {\bf y}_{22}}{\min} f_1({\bf x}_1, {\bf y}_{11} + {\bf y}_{12}) + f_2({\bf x}_2, {\bf y}_{21} + {\bf y}_{22}) $$
Well, it seems that you can just differentiate the objective function and use any gradient-based method to optimize it.
Let's define the dependent variable:
$$z_i(y_{i1},...,y_{iM})=\sum_{j=1}^{M} y_{ij}$$
Then, your objective function is given by:
$$h(x_1,x_2,...,x_N,z_1,z_2,...,z_N) = \sum\limits_{i=1}^{N} f_i(x_i,z_i)$$
Its derivatives are given by:
$$\boxed{\frac{\partial h}{\partial x_i} = \frac{\partial f_i}{\partial x_i}}$$
$$\boxed{\frac{\partial h}{\partial y_{ij}} = \frac{\partial f_i}{\partial z_i}\,\frac{\partial z_i}{\partial y_{ij}} = \frac{\partial f_i}{\partial z_i}}$$
After computing all derivatives, you can use any gradient-based method, for example, a simple gradient descent algorithm
I consists in defining a step value $\alpha$, then updating each variable as:
$$x_i^{(k+1)} = x_i^{(k)} - \alpha \cdot \frac{\partial h}{\partial x_i}\!\left(x_i^{(k)},z_i^{(k)}\right)$$
$$y_{ij}^{(k+1)} = y_{ij}^{(k)} - \alpha \cdot \frac{\partial h}{\partial y_{ij}}\!\left(x_i^{(k)},z_i^{(k)}\right)$$
If the value of the objective function increases after a step, you should use smaller values for $\alpha$. If there are no constraints for the optimization problem, you may verify if the minimal value has been achieved by checking the value of each derivative (all of them must be zero at the optimal point).
It should be noted that, if there are no additional constraints to the problem, if a minimum exists, then there will be an infinite number of solutions, since any set of $y_{ij}$ with equivalent $\sum_{j=1}^{M} y_{ij}$ results in the same value for the objective function.