Primal-Dual Coarse Correction Optimizer

Integrate this as an optimizer wrapper around a selected parameter block, not as a new forward-network layer. Start with a CNN or small transformer containing a large matrix \(\theta\in\mathbb{R}^n\). Choose a fixed coarse basis \(P\in\mathbb{R}^{n\times r}\), with \(r\ll n\), using block-constant parameters, a 2D Haar/DCT basis for convolution kernels, or rank-r factors for a linear layer. Set the restriction to \(R=P^\top\) after column normalization. Every \(T\) fine optimizer steps, set \(z_0=R\theta\) and run \(m=3\)--\(10\) coarse updates on a fresh minibatch. For each coarse iteration, compute \(q_j=K_Hz_j\); update the dual variable by \(y_{j+1}=\operatorname{prox}_{\sigma G_H^*}(y_j+\sigma q_j)\); then update the primal variable by \(z_{j+1}=\operatorname{prox}_{\tau F_H}(z_j-\tau[\nabla E_H(z_j)+K_H^\top y_{j+1}])\). Use \(\tau\sigma\|K_H\|^2<0.9\), estimating \(\|K_H\|\) with 5--10 power iterations. Form \(d=P(z_m-z_0)\), evaluate the fine loss at \(\theta+d\) on a small validation minibatch, and accept with backtracking \(\alpha\in\{1,1/2,1/4\}\); otherwise skip the correction. For a first nonsmooth test, use \(F_H=\iota_{[-c,c]^r}\), whose proximal map is coordinatewise clipping, or \(G_H(q)=\lambda\|q\|_1\), whose proximal map is soft-thresholding. The paper supplies the composite objective and restriction/prolongation correction structure; minibatch gradients, operator norms, and acceptance statistics are estimated empirically. First experiment: train a 6-layer CNN on CIFAR-10, comparing AdamW with identical fine-step FLOPs against AdamW plus coarse corrections on convolution kernels. Measure training loss versus optimizer steps and wall-clock time, final accuracy, correction acceptance rate, and constraint violations. A successful signal is 10--20% fewer fine steps to reach baseline accuracy without increased wall-clock time, or improved stability at the same learning rate.