🤖 machine learning

Mirror descent algorithms with logarithmic barriers

This paper establishes tight $O(\log k / k)$ convergence rates for mirror descent and proximal mirror descent algorithms using logarithmic barriers in settings where solutions lie on the boundary, introducing a novel technique to handle divergent Bregman divergences, resolving a gap in relative smoothness theory, and comparing the approach with interior-point methods.

Original authors: Alberto De Marchi, Yura Malitsky, Adrien B. Taylor

Published 2026-08-25

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Alberto De Marchi, Yura Malitsky, Adrien B. Taylor

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the vast landscape of mathematical optimization, where computers seek the best possible solution to complex problems, there is a persistent challenge involving boundaries. Many real-world problems require finding a minimum value for a function while staying within a specific region, like a shape drawn on a map. Often, the best solution does not sit comfortably in the middle of this region but lies right on its edge. For decades, mathematicians have used a powerful tool called a "barrier" to keep their calculations safely inside the region, preventing them from crashing into the edge. This barrier acts like a steep, invisible wall that rises infinitely high as one approaches the boundary, forcing the algorithm to stay within safe limits. While this technique is the gold standard for many high-stakes calculations, a specific type of barrier known as the logarithmic barrier has been difficult to use with a popular class of algorithms called mirror descent. The problem is that when the optimal solution sits on the boundary, the mathematical distance the algorithm uses to measure progress explodes to infinity, causing the standard theories to break down and leaving researchers without a guarantee that the method will actually work.

A team of researchers has now resolved this long-standing issue, proving that mirror descent algorithms can indeed handle logarithmic barriers effectively, even when the solution lies on the boundary. They demonstrated that these methods converge to the correct answer at a predictable speed, specifically improving the error rate by a factor related to the logarithm of the number of steps taken. This finding is significant because it validates the use of these efficient algorithms in scenarios where the best answer is known to be on the very edge of the feasible region, a situation common in fields like engineering design and statistical modeling. The authors did not just claim this was possible; they constructed a rigorous mathematical proof and built a specific, difficult example to show that their predicted speed is the best one can hope for, meaning the method cannot be significantly improved upon without changing the fundamental approach.

The researchers focused on two variations of the mirror descent algorithm: one that takes a direct step based on the current slope of the function, and a "proximal" version that solves a slightly more complex sub-problem at each step to find the next position. In standard settings, if the solution is on the boundary, the mathematical distance between the starting point and the solution becomes infinite, rendering the usual speed guarantees useless. The team's breakthrough was a new technique to manage this infinite distance. They utilized a special property of the logarithmic barrier, which ensures that while the barrier grows infinitely high, its shape follows a specific, predictable curve that allows the algorithm to navigate the edge without losing its way. By carefully tracking how the algorithm's progress relates to this curve, they derived a new formula for how quickly the solution improves. Their analysis showed that the error decreases at a rate proportional to the logarithm of the number of steps divided by the number of steps themselves. This rate is not just a theoretical possibility; the authors proved it is "tight," meaning there are specific problems where the algorithm performs exactly at this speed and no faster, confirming that their analysis captures the true limits of the method.

To ensure their findings were robust, the team also compared their approach to interior-point methods, which are the established, highly sophisticated techniques currently used for problems involving logarithmic barriers. Interior-point methods are known for their speed but require very expensive calculations at every single step. The researchers showed that their proximal mirror descent approach is a direct and competitive alternative. While the new method might require slightly more total computational effort in some specific comparisons, it offers a much more general framework that does not rely on the rigid assumptions required by traditional interior-point methods. In fact, they demonstrated that for linear problems, the two methods are essentially equivalent, but for more complex, non-linear problems, the mirror descent approach provides a flexible and theoretically sound path forward. The authors also addressed a gap in the existing theory of "relative smoothness," a concept used to describe how well-behaved a function is relative to the barrier, showing that their new analysis fills a hole in the mathematical understanding of these algorithms.

The work concludes by offering a clear path for future exploration. The researchers noted that while their current proof relies on the specific shape of the logarithmic barrier, there may be ways to improve the bounds further by incorporating other known properties of these barriers, such as their scaling behavior. They also highlighted that while faster "accelerated" versions of mirror descent exist for simpler problems, it remains an open question whether such speedups are possible when using these complex logarithmic barriers. For now, the paper stands as a definitive proof that mirror descent algorithms can safely and efficiently navigate the treacherous edges of optimization problems, turning a previously broken tool into a reliable instrument for finding solutions where they are most needed.

Technical Summary: Mirror Descent Algorithms with Logarithmic Barriers

1. Problem Statement

The paper addresses the convex minimization problem:
$\min_{x \in \mathbb{R}^d} f(x) \quad \text{subject to} \quad x \in C \cap S$
where $C$ and $S$ are nonempty closed convex sets. The set $S$ is treated explicitly, while the potentially complex set $C$ is handled via a logarithmic barrier function $h: C \to \mathbb{R} \cup \{+\infty\}$ . The function $h$ serves as the distance-generating function (mirror) defining the Bregman divergence:
$D_h(y, x) := h(y) - h(x) - \langle \nabla h(x), y - x \rangle$
The authors consider two algorithmic variants:

Mirror Descent (MD): An explicit update using the linearization of $f$ .
Proximal Mirror Descent (proxMD): An implicit update minimizing the full objective $f$ plus the Bregman term.

The Core Difficulty: Standard convergence analyses for mirror descent rely on the bound $f(x_k) - f^\star \leq \frac{D_h(x^\star, x_0)}{\sum \alpha_i}$ . However, when the optimal solution $x^\star$ lies on the boundary of $C$ (a common scenario), and $h$ is a logarithmic barrier (which blows up at the boundary), the term $D_h(x^\star, x_0)$ becomes infinite. Consequently, classical guarantees become vacuous. While logarithmic barriers have been used in specific contexts (e.g., relative smoothness conditions for D-optimal design and Poisson inverse problems), prior theory lacked quantitative convergence guarantees for mirror descent in these settings when the solution lies on the boundary. This work aims to derive such non-vacuous convergence rates.

2. Methodology and Theoretical Framework

2.1. Exp-Concavity and Log-Barriers

The authors utilize the property that a logarithmic barrier $h$ is $\nu$ -exp-concave. A function $h$ is $\nu$ -exp-concave if $x \mapsto \exp(-h(x)/\nu)$ is concave. This property is strictly stronger than convexity and provides the inequality:
$\nu \exp\left(\frac{h(x) - h(y)}{\nu}\right) + \langle \nabla h(x), y - x \rangle \leq \nu$
This inequality is the key technical tool used to bound the "blow-up" terms that arise when iterates approach the boundary.

2.2. Lyapunov Analysis

The convergence proofs for both (proxMD) and (MD) rely on constructing a Lyapunov function. For (proxMD), the analysis defines a sequence $B_k$ (accumulated stepsizes) and a potential function:
$\Psi_k = B_k (f(x_k) - f^\star) + \langle \nabla h(x_k), x_k - x^\star \rangle$
By analyzing the difference $\Psi_{k+1} - \Psi_k$ , the authors derive a recursive inequality involving a residual term $H_k$ . Crucially, the $\nu$ -exp-concavity of $h$ allows them to bound $H_k$ by terms involving $\log(B_{k+1}/B_k)$ rather than unbounded quantities.

2.3. Relative Smoothness

For the Mirror Descent (MD) variant, the paper assumes relative smoothness: $f$ is $L$ -relatively smooth with respect to $h$ if $D_f(x, y) \leq L D_h(x, y)$ . This condition is known to hold for problems like D-optimal design and Poisson inverse problems when $h$ is a log-barrier.

2.4. Tightness via Performance Estimation

To demonstrate that the derived rates are not artifacts of loose proofs, the authors construct a specific counterexample using Performance Estimation Problems (PEP). They interpolate a convex function $f$ and a 1-exp-concave barrier $h$ such that the (proxMD) iterates exactly achieve the derived lower bound. This construction involves a 2-dimensional matching example where the objective and barrier are defined via sampled points satisfying specific interpolation conditions.

3. Key Results

3.1. Convergence Rates

The paper establishes that both (MD) and (proxMD) achieve a convergence rate of $O(\frac{\log k}{k})$ when using a logarithmic barrier, even if the solution lies on the boundary.

Proximal Mirror Descent (Theorem 1): For a sequence of stepsizes $\alpha_i$ , let $A_k = \sum_{i=1}^k \alpha_i$ . The error bound is:
$f(x_k) - f^\star \leq \frac{\langle \nabla h(x_0), x_0 - x^\star \rangle + 2\nu + \frac{\nu}{4}\log\left(\frac{A_k}{A_1}\right)}{A_k}$
With constant stepsizes $\alpha_k = \alpha$ , this yields $O(\frac{\log k}{k})$ . With geometrically growing stepsizes, the rate is exponential but with a slightly worse total complexity compared to Interior Point Methods (IPMs).
Mirror Descent (Theorem 2): Under relative smoothness with stepsize $\alpha = 1/L$ , the bound is:
$f(x_k) - f^\star \leq \frac{f(x_0) - f^\star + L(\langle \nabla h(x_0), x_0 - x^\star \rangle + 2\nu + \nu \log k)}{k+1}$
This also confirms the $O(\frac{\log k}{k})$ rate.

3.2. Tightness (Theorem 3)

The authors prove that the $O(\frac{\log k}{k})$ rate is tight. Specifically, for $\nu=1$ and constant stepsizes, there exists a problem instance where:
$k(f(x_k) - f^\star) \sim 1 + \frac{1}{4}\log k$
This confirms that the logarithmic factor is inherent to the method when using log-barriers and solutions are on the boundary, not a deficiency of the analysis.

3.3. Comparison with Interior Point Methods (IPMs)

The paper compares (proxMD) with classical IPMs.

IPMs can be viewed as "fixed-center" versions of (proxMD) where the prox-center is fixed at the analytic center $x_0$ (i.e., $x_k = \arg\min \{f(x) + \frac{1}{\alpha_k} D_h(x, x_0)\}$ ).
Complexity: Classical IPMs with $\nu$ -self-concordant barriers achieve $O(\nu \log(1/\delta))$ complexity.
ProxMD: The authors show that (proxMD) with geometrically growing stepsizes achieves a total complexity of $O(\nu \log^2(1/\delta))$ .
Conclusion: While (proxMD) is slightly worse in total complexity (due to the $\log^2$ factor vs. $\log$ ), it is a direct alternative that does not require the specific self-concordance structure, relying only on exp-concavity.

4. Significance and Contributions

The paper claims three primary contributions:

Resolution of the Boundary Blow-up: It provides the first quantitative convergence guarantees for mirror descent and proximal mirror descent using logarithmic barriers when the optimal solution lies on the boundary. While log-barriers were previously used in relative smoothness contexts, prior theory did not provide convergence rates for these specific settings where the Bregman divergence term $D_h(x^\star, x_0)$ blows up.
Tightness of Rates: It establishes that the $O(\frac{\log k}{k})$ rate is optimal for this setting, resolving a gap in the understanding of relative smoothness applications to log-barriers.
Bridge to Interior Point Methods: It clarifies the relationship between Bregman-type proximal methods and IPMs. It demonstrates that (proxMD) can be viewed as a generalization of IPMs, offering a unified perspective, albeit with a slightly higher complexity bound for nonlinear objectives.

The work suggests that while Interior Point Methods remain superior in total complexity for specific self-concordant settings, proximal mirror descent offers a viable, more general first-order alternative that handles the boundary blow-up issue through exp-concavity, without requiring the solution to remain strictly in the interior or the objective to be moved into the constraints.