2024/05/07 by Mo, Kai-Chia, Shalev-Shwartz, Shai, Shártov, Nisæl
#FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Optimization and Control (math.OC)
paper · doi:10.48550/arxiv.2405.04710
We describe an apparatus for subgradient-following of the optimum of convex problems with variational penalties. In this setting, we receive a sequence yi,…,yn and seek a smooth sequence x1,…,xn. The smooth sequence needs to attain the minimum Bregman divergence to an input sequence with additive variational penalties in the general form of ∑igi(xi+1-xi). We derive known algorithms such as the fused lasso and isotonic regression as special cases of our approach. Our approach also facilitates new variational penalties such as non-smooth barrier functions. We then derive a novel lattice-based procedure for subgradient following of variational penalties characterized through the output of arbitrary convolutional filters. This paradigm yields efficient solvers for high-order filtering problems of temporal sequences in which sparse discrete derivatives such as acceleration and jerk are desirable. We also introduce and analyze new multivariate problems in which xi,yi∈ℝd with variational penalties that depend on ‖xi+1-xi‖. The norms we consider are ℓ2 and ℓ_∞ which promote group sparsity.