Learning with optimal interpolation norms

Patrick L. Combettes, Andrew M. McDonald, Charles A. Micchelli, Massimiliano Pontil

TL;DR

This paper introduces a unified framework for a broad class of norms used in machine learning and signal processing, called "optimal interpolation norms." They develop a novel randomized block-coordinate algorithm to efficiently solve optimization problems involving these norms, demonstrating its effectiveness and convergence properties even for non-smooth objectives.

What Problem Does This Paper Address?

Many modern data analysis tasks, particularly in machine learning and signal processing, rely on regularization techniques to promote desired structures in solutions to optimization problems. These structures often manifest as specific sparsity patterns in data representations. While various structured sparsity regularizers exist (e.g., group lasso, overlapping group lasso, norms for tensors), they are often defined in ad-hoc ways. This paper aims to unify these diverse regularizers under a single, mathematically elegant framework based on optimal interpolation. Furthermore, solving optimization problems with these complex regularizers can be computationally challenging. The paper addresses this by developing an efficient and robust numerical algorithm.

Methods

The core contribution is the introduction of "optimal interpolation norms" defined by the formula:

$||y|| = \inf_{x \in X} |||F(x)|||$ subject to $Lx = y$

Here, $X$ and $Y$ are Banach spaces, $L: X \to Y$ is a linear operator, $F: X \to \mathbb{R}^m$ is a mapping composed of simpler norms, and $||| \cdot |||$ is a norm on $\mathbb{R}^m$. This framework elegantly captures existing norms and allows for the construction of new ones. The paper then develops a randomized block-coordinate Douglas-Rachford algorithm to solve minimization problems of the form $\min_x \Phi(x) + \Psi(Bx)$, where $\Phi$ is a sum of simple norms and $\Psi$ is a loss function. This algorithm leverages the structure of the optimal interpolation norms, requiring only the proximity operators of the individual components, making it computationally efficient and robust to non-smoothness and random updates.

Datasets

Not discussed in the paper. The paper focuses on theoretical development and numerical experiments on synthetic data generated according to specific models.

Key Insights and Ideas

  • Unified Framework: The "optimal interpolation norm" provides a powerful and general way to define and understand a wide range of structured sparsity regularizers, bridging the gap between diverse existing methods.
  • Algorithmic Efficiency: The randomized block-coordinate Douglas-Rachford algorithm is a significant advancement. It breaks down complex optimization problems into simpler subproblems, allowing for efficient computation even with non-smooth objectives and partial updates.
  • Robustness: The algorithm's convergence is guaranteed even when the objective functions are not differentiable and when random updates are performed, making it highly practical for real-world applications.
  • Flexibility: The ability to activate blocks of norms randomly offers significant flexibility in handling large-scale problems, allowing adaptation to available computational resources.

Key Results

  • The paper establishes basic properties and dual norms for the proposed class of optimal interpolation norms.
  • It demonstrates how existing norms like the latent group lasso, overlapping group lasso, and tensor norms can be represented within this framework.
  • The proposed randomized block-coordinate Douglas-Rachford algorithm is shown to converge to a solution for minimization problems involving these norms.
  • Numerical experiments on binary classification with hinge loss and latent group lasso penalty show that the algorithm's performance (in terms of normalized iterations) is stable across different activation rates, highlighting the effectiveness of partial updates.

Limitations and Future Work

  • Computational Cost: While the algorithm is efficient, the paper notes that in large-scale problems, evaluating all proximity operators at each iteration can still be computationally demanding. The random sweeping approach mitigates this but still requires careful implementation.
  • Generalization: The paper focuses on norms. The authors mention that the framework can be extended to more general convex functions, suggesting future work in this direction.
  • Specific Applications: While the paper presents numerical experiments, further exploration of the algorithm's performance on a wider range of real-world datasets and problem types would be beneficial. The authors suggest that the algorithm can be used to solve more general versions of the optimization problems where the regularizer is not strictly a norm but a function of the form (2.3).

Summary updated

Abstract

We analyze a class of norms defined via an optimal interpolation problem involving the composition of norms and a linear operator. This construction, known as infimal postcomposition in convex analysis, is shown to encompass various of norms which have been used as regularizers in machine learning, signal processing, and statistics. In particular, these include the latent group lasso, the overlapping group lasso, and certain norms used for learning tensors. We establish basic properties of this class of norms and we provide dual norms. The extension to more general classes of convex functions is also discussed. A stochastic block-coordinate version of the Douglas-Rachford algorithm is devised to solve minimization problems involving these regularizers. A prominent feature of the algorithm is that it yields iterates that converge to a solution in the case of non smooth losses and random block updates. Finally, we present numerical experiments with problems employing the latent group lasso penalty.
BibTeX
@article{combettes2019learning,
  author = {Patrick L. Combettes and Andrew M. McDonald and Charles A. Micchelli and Massimiliano Pontil},
  title = {{Learning with optimal interpolation norms}},
  journal = {Numer. Algorithms},
  year = {2019},
  doi = {10.1007/s11075-018-0568-1},
}
Figure