Abstract
This paper introduces a unified mathematical framework for "optimal interpolation norms," a class of regularizers defined via infimal postcomposition in convex analysis. This construction encompasses several widely used regularizers, including the latent group lasso, the overlapping group lasso, and specific tensor norms. Beyond theoretical unification, we propose a stochastic block-coordinate version of the Douglas-Rachford algorithm designed to solve minimization problems involving these regularizers. A key feature of this algorithm is its guaranteed convergence for non-smooth loss functions even under random block updates. Numerical experiments on latent group lasso penalties demonstrate the algorithm's efficiency and stability.
Introduction
In machine learning and signal processing, regularization is a fundamental tool for inducing structural properties—such as sparsity or low-rank patterns—in model solutions. While simple regularizers like the $\ell_1$ norm are well-characterized, more complex structures often require specialized norms. Historically, these complex norms (e.g., overlapping group lasso) have been treated as isolated mathematical objects, leading to a fragmented landscape of optimization strategies.
This research addresses two primary challenges: the lack of a unified mathematical framework to describe these complex norms and the computational difficulty of optimizing them. Because these regularizers are typically non-smooth, standard proximal algorithms often struggle when the proximity operator of the full norm is computationally expensive or mathematically intractable. We propose a framework that decomposes these complex norms into simpler components and an algorithm that leverages this decomposition for efficient, stochastic optimization.
The Framework: Optimal Interpolation Norms
The core of our theoretical contribution is the use of infimal postcomposition to define a broad class of norms. We define a norm $\|y\|$ on a space $\mathcal{Y}$ as the result of an optimization problem: finding the "simplest" combination of components $x$ (measured by a set of simpler norms) that can be mapped back to $y$ via a linear operator $L$.
This "optimal interpolation" approach allows us to view sophisticated regularizers as compositions of manageable pieces. By identifying this underlying structure, we can systematically derive dual norms and proximity operators for an entire class of regularizers at once. This shifts the optimization challenge from the complex aggregate norm to the proximity operators of its simpler constituent parts.
Stochastic Block-Coordinate Douglas-Rachford
To solve optimization problems involving these interpolation norms, we adapt the Douglas-Rachford (DR) splitting method. Our proposed algorithm introduces two significant innovations:
- Block-Coordinate Updates: The algorithm updates only a subset (blocks) of variables at each step. This is critical for high-dimensional "big data" scenarios where the full model parameters may exceed memory capacity.
- Stochasticity and Non-Smoothness: Unlike many coordinate-descent methods that require the loss function to be smooth (differentiable), our stochastic version guarantees convergence "almost surely" even for non-smooth losses, such as the hinge loss used in Support Vector Machines (SVMs).
By decomposing the complex norm, the algorithm only requires the proximity operators of the simple components, transforming an intractable global problem into a sequence of computationally inexpensive local updates.
Experimental Validation
We validated the framework and algorithm using synthetic datasets to maintain controlled conditions for theoretical verification.
Computational Stability
In experiments involving the latent group lasso, we observed a remarkable property regarding "normalized iterations" (the total number of iterations multiplied by the fraction of blocks updated). The computational effort required to reach convergence remained nearly constant across different activation rates. For instance, updating 100% of blocks required approximately 14,515 iterations, while updating only 10% of blocks required approximately 100,829 iterations. When normalized, the 10% update rate actually showed a slight efficiency gain, suggesting that sparse, stochastic updates do not degrade the overall convergence rate in terms of total work performed.
Robustness and Recovery
The algorithm was tested on a binary classification task ($n=1000, d=10,000$) and a $k$-support norm test where the number of groups ($m=12,650$) exceeded the number of features. The algorithm successfully recovered sparse signals even in the presence of noise (25% flipped signs in classification labels), demonstrating its robustness in practical settings.
Conclusion and Future Work
This work provides a rigorous foundation for a wide class of regularizers and a scalable algorithm for their optimization. By unifying these norms under the umbrella of infimal postcomposition, we simplify both the theoretical analysis and the practical implementation of structured sparsity models.
Future research may extend these results to non-reflexive spaces and explore the application of this framework to more general convex functions beyond norms. Additionally, testing the algorithm on large-scale real-world benchmarks will be essential to evaluate how memory hierarchy and cache locality influence the efficiency of stochastic block updates in production environments.
Summary updated