I've got an unconstrained optimization problem, and all function involved can be regarded as differentiable as you like. 

The variable is a rectangular matrix $M$. 
Target Function is $\sum_i f(w^i) +\sum_j g(w_j)$,
where $w^i,w_j$ corresponds to the i-th row and j-th column of $M$

The best I can get is to split vars to $f(a^i)$ and $g(b_j)$ with Alternating Direction Method of Multipliers and then solve smaller problems respectively. But the penalty term induces is still expensive.

Is there any preferable methods to solve problems with such structure?

Any thoughts would be helpful. Thanks in advance!