Adaptive Algorithms for Relatively Lipschitz Continuous Convex Optimization Problems

Fedor Stonyakin, A. Titov, Mohammad Alkousa, Oleg Savchuk, Dmitry PasechnyukarXiv 2021 · DOI · arXiv

Abstract

Recent advancements in convex optimization have introduced the concepts of relative smoothness and relative strong convexity. These frameworks expand the applicability of gradient-type methods by measuring objective behavior against a reference function via Bregman divergences rather than standard Euclidean norms. However, many existing methods require prior knowledge of global constants, such as the relative Lipschitz constant, which are often difficult to estimate in practice. This paper proposes a suite of adaptive algorithms for minimizing convex Lipschitz continuous functions and solving variational inequalities. We introduce a "universal" method that automatically adjusts to both relatively smooth and relatively Lipschitz continuous functionals, achieving optimal convergence rates without manual parameter tuning. Numerical experiments on the Intersection of Ellipsoids Problem and constrained Support Vector Machines demonstrate the practical efficiency of these adaptive approaches.

Introduction

In classical convex optimization, the efficiency of first-order methods typically hinges on two properties: $L$-smoothness (Lipschitz continuity of the gradient) or $M$-Lipschitz continuity of the objective function. Traditionally, these properties are defined with respect to the standard Euclidean norm. However, modern high-dimensional problems in machine learning and resource allocation often fail to satisfy these conditions globally, or possess constants that are computationally prohibitive to determine.

To address this, researchers recently proposed "relative" versions of these properties. By replacing the Euclidean distance with a Bregman divergence—derived from a strictly convex reference function—one can often find a geometry in which a "nasty" function behaves more predictably. While this theoretical shift is powerful, it introduces a new challenge: the algorithms generally require the user to provide the relative constants ($L$ or $M$) to ensure convergence. This paper bridges the gap between theory and practice by developing adaptive methods that "feel out" these constants on the fly.

Relative Geometry and Adaptivity

The core of our approach lies in the transition from global norm-based constraints to local Bregman-based constraints. A function $f$ is relatively Lipschitz continuous with respect to a reference function $h$ if the change in $f$ is bounded by the Bregman divergence of $h$.

Our proposed algorithms utilize a "check-and-double" strategy. Instead of requiring a fixed global constant, the methods start with an initial estimate and verify a local condition at each step. If the condition is violated, the estimate is adjusted, and the step is recalculated. This ensures that the algorithm remains sensitive to the local curvature of the objective function.

The Inexactness Trick and Universal Methods

A key contribution of this work is the introduction of a controlled artificial inaccuracy ($\delta$) into the optimization model. This allows for the development of algorithms (such as Algorithms 2 and 4 in the full text) that handle non-smoothness more robustly.

Furthermore, we present "universal" algorithms (Algorithms 5 and 6). These are designed to be agnostic to the problem class; the user does not need to specify whether the objective is relatively smooth or relatively Lipschitz. The algorithm automatically detects the "degree" of smoothness it encounters, hitting the optimal convergence rate for either class: $O(1/\epsilon)$ for smooth problems and $O(1/\epsilon^2)$ for Lipschitz problems.

Numerical Experiments

We evaluated the proposed adaptive frameworks on two distinct problem types designed to test mathematical robustness:

  1. Intersection of Ellipsoids Problem (IEP): This is a non-differentiable and non-Lipschitz problem where the goal is to find a point common to multiple ellipsoids. Using synthetic data generated via random diagonal matrices and Gaussian distributions, we found that our adaptive Algorithm 4 significantly outperformed the recently proposed AdaMirr algorithm in terms of both solution quality and convergence stability.
  2. Constrained Support Vector Machines (SVM): We modeled this as a Lagrange saddle-point problem. While the theoretical bound for non-smooth problems is $O(1/\epsilon^2)$, our empirical results showed the algorithm often behaved closer to $O(1/\epsilon)$. This suggests that the adaptive mechanism effectively exploits local smoothness that global theory might overlook.

Key Insights

  • Geometry as a Tool: A function that appears non-smooth in Euclidean space can often be treated as smooth by selecting an appropriate Bregman divergence.
  • Cost of Adaptivity: The theoretical cost of not knowing the constants upfront is minimal—primarily a logarithmic number of extra sub-problem evaluations.
  • Fluid Boundaries: The universal approach demonstrates that the distinction between smooth and non-smooth optimization is less rigid than previously thought; a single adaptive framework can traverse both regimes effectively.

Conclusion and Future Work

This paper provides a robust theoretical and empirical foundation for adaptive methods in relative optimization. By removing the requirement for prior knowledge of Lipschitz constants, these methods make advanced Bregman-based optimization accessible to a wider range of practical applications.

Future research will focus on extending these adaptive frameworks to stochastic optimization, where gradients are subject to noise, and exploring higher-order tensor methods to further accelerate convergence in extremely high-dimensional settings. While current methods require an estimate of the distance to the optimal set ($R$) for stopping criteria, developing fully parameter-free methods remains a priority.

Summary updated

Abstract

Recently there were proposed some innovative convex optimization concepts, namely, relative smoothness [1] and relative strong convexity [2,3]. These approaches have significantly expanded the class of applicability of gradient-type methods with optimal estimates of the convergence rate, which are invariant regardless of the dimensionality of the problem. Later Yu. Nesterov and H. Lu introduced some modifications of the Mirror Descent method for convex minimization problems with the corresponding analogue of the Lipschitz condition (so-called relative Lipschitz continuity). By introducing an artificial inaccuracy to the optimization model, we propose adaptive methods for minimizing a convex Lipschitz continuous function, as well as for the corresponding class of variational inequalities. We also consider an adaptive "universal" method, applicable to convex minimization problems both on the class of relatively smooth and relatively Lipschitz continuous functionals with optimal estimates of the convergence rate. The universality of the method makes it possible to justify the applicability of the obtained theoretical results to a wider class of convex optimization problems. We also present the results of numerical experiments.
BibTeX
@misc{stonyakin2021adaptive,
  author = {Fedor Stonyakin and A. Titov and Mohammad Alkousa and Oleg Savchuk and Dmitry Pasechnyuk},
  title = {{Adaptive Algorithms for Relatively Lipschitz Continuous Convex Optimization Problems}},
  year = {2021},
  eprint = {2107.05765},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2107.05765},
}
Figure