A randomized block coordinate iterative regularized subgradient method for high-dimensional ill-posed convex optimization

Motivated by ill-posed optimization problems arising in image processing, we consider a bilevel optimization model, where we seek among the optimal solutions of the inner level problem, a solution that minimizes a secondary metric. Minimal norm gradient, sequential averaging, and iterative regularization appear among the known schemes developed for addressing this class of problems. However, to the best of our knowledge, none of these schemes address nondifferentiability and high-dimensionality of the solution space. Motivated by this gap, we consider the case where the solution space has a block structure and both objective functions are nondifferentiable. We develop a randomized block coordinate iterative regularized subgradient scheme (RB-IRG). Under a uniform distribution for selecting the blocks and a careful choice of the stepsize and regularization sequences, we establish the convergence of the sequence generated by RB-IRG scheme to the unique solution of the bilevel problem of interest in an almost sure sense. Furthermore, we derive a convergence rate of mathcal{O}left(frac{sqrt{d}}{k-{0.5-delta}}right)in terms of the expected objective value of the inner level problem, where ddenotes the number of blocks and delta > 0is an arbitrary small scalar. We demonstrate the performance of RB-IRG algorithm in solving the ill-posed problems arising in image processing.