Untangling Lariats: Subgradient Following of Variationally Penalized Objectives
<|reference_start|>Untangling Lariats: Subgradient Following of Variationally Penalized Objectives: We describe a novel subgradient following apparatus for calculating the optimum of convex problems with variational penalties. In this setting, we receive a sequence $y_i,\ldots,y_n$ and seek a smooth sequence $x_1,\ldots,x_n$. The smooth sequence attains the minimum Bregman divergence to an input sequence with additive variational penalties in the general form of $\sum_i g_i(x_{i+1}-x_i)$. We derive, as special cases of our apparatus, known algorithms for the fused lasso and isotonic regression. Our approach also facilitates new variational penalties such as non-smooth barrier functions. We next derive and analyze multivariate problems in which $\mathbf{x}_i,\mathbf{y}_i\in\mathbb{R}^d$ and variational penalties that depend on $\|\mathbf{x}_{i+1}-\mathbf{x}_i\|$. The norms we consider are $\ell_2$ and $\ell_\infty$ which promote group sparsity. Last but not least, we derive a lattice-based subgradient following for variational penalties characterized through the output of arbitrary convolutional filters. This paradigm yields efficient solvers for problems in which sparse high-order discrete derivatives such as acceleration and jerk are desirable.<|reference_end|>
@article{mo2024untangling,
    title={Untangling Lariats: Subgradient Following of Variationally Penalized
  Objectives},
    author={Kai-Chia Mo, Shai Shalev-Shwartz, Nis{ae}l Sh'artov},
    journal={arXiv preprint arXiv:2405.04710},
    year={2024},
    archivePrefix={arXiv},
    eprint={2405.04710},
    primaryClass={cs.LG math.OC}
}