Source-linked AI summary
Mirror descent algorithms with logarithmic barriers
Alberto De Marchi, Yura Malitsky, Adrien B. Taylor
TL;DR
The paper studies convex minimization with logarithmic barriers, where standard mirror-descent analysis lacks quantitative convergence guarantees and the barrier blows up at the boundary. It derives convergence rates for mirror descent and proximal mirror descent, establishes their tightness, and compares the proximal method with interior-point methods.
Problem
The paper addresses the lack of quantitative convergence guarantees for mirror descent in convex minimization settings involving logarithmic barriers.
Method
The paper treats a logarithmic barrier as the mirror function defining the Bregman divergence and derives convergence rates for mirror descent and proximal mirror descent.
Results
The paper derives convergence rates for both mirror descent and proximal mirror descent and shows that these rates are tight.
Takeaways & Limitations
Proximal mirror descent can serve as a direct alternative to interior-point methods, although with slightly worse total complexity.
Takeaways & Limitations
The paper generally remains agnostic about how the mirror-descent and proximal-mirror-descent subproblems are solved, except in its interior-point-method discussion.
Abstract
from arXiv · showhide
This work derives convergence guarantees for mirror descent and proximal mirror descent algorithms when a logarithmic barrier is used as a distance-generating function. Standard approaches cannot be applied when the solution lies on the boundary, where the Bregman divergence blows up. We show that, in a specific setting, both methods enjoy an $O(\log k / k)$ rate, which is also tight. In addition, our contributions include: (i) a new technique for handling the blow-up; (ii) a resolution of a gap in the theory of relative smoothness; and (iii) a comparison of the proposed approach with interior-point methods.
1 Introduction
The paper studies mirror descent and proximal mirror descent with logarithmic barriers, whose standard convergence analysis fails when optima lie on the boundary. It develops convergence guarantees, addresses relative smoothness, and compares the proximal method with interior-point methods.
- Approach: The proposed framework treats simple constraints explicitly and handles complicated constraints through a logarithmic-barrier Bregman geometry.The barrier serves as the distance-generating function defining the Bregman divergence used by mirror and proximal mirror descent.
- Motivation: Logarithmic barriers are finite in the interior but blow up at the boundary, making classical Bregman-divergence guarantees vacuous when the optimum lies on the boundary.This boundary behavior is the central obstacle for applying standard mirror-descent analyses.
- Contributions: The paper derives convergence rates for both mirror descent and proximal mirror descent, proves tightness, and resolves a gap in relative-smoothness theory.The introduction identifies these as central contributions alongside the comparison with interior-point methods.
- Motivation: Quantitative convergence guarantees for mirror descent with log-barriers had not previously been established for motivating applications such as D-optimal design and Poisson linear inverse problems.These examples satisfy relative-smoothness conditions with respect to logarithmic barriers.
- Comparison with interior-point methods: Proximal mirror descent is presented as a direct alternative to interior-point methods, with slightly worse total complexity.Classical interior-point methods are described as lazy versions of proximal mirror descent because they do not update the prox-center.
- Scope and assumptions: The convergence analysis generally remains agnostic about how the mirror-descent and proximal subproblems are solved, except in the interior-point comparison.The paper also notes that its main result uses only convexity and the logarithmic-barrier structure under the stated setup.
2 Preliminaries
The preliminaries define the convex optimization setting, relative geometry, and logarithmic barriers used throughout the paper. They also state feasibility and well-posedness assumptions for the Bregman subproblems.
- Basic convex optimization setting: The optimization problem minimizes a convex function over the intersection of two nonempty closed convex sets, with a finite optimum attained at x⋆.The sets are denoted C and S, and the objective is defined on C ∩S.
- Analytical assumptions: The preliminaries introduce relative smoothness and exp-concavity as structural tools for analyzing mirror descent with barriers.The text notes that exp-concavity provides a characterization stronger than convexity for the barrier function.
- Geometric preliminaries: The relative interior and relative boundary are used to describe where barrier-based iterates and optima lie.The relative boundary is rbd(C) = C \ ri(C), and every nonempty convex set has a nonempty relative interior.
- Logarithmic barriers: A logarithmic barrier is finite on ri(C), diverges on rbd(C), and can be written as h(x) = −ν log(−ϕ(x)) when ϕ is negative in the relative interior and zero on the relative boundary.The paper also characterizes such barriers through ν-exp-concavity and boundary blow-up.
- Well-posedness: The Bregman subproblems are assumed to admit minimizers for every positive stepsize and every y ∈ri(C), ensuring that their solutions remain in ri(C).Coercivity or compactness can guarantee this assumption, but the paper keeps it explicit.
- Bregman geometry: The barrier h defines the Bregman divergence used as the distance-generating geometry for the algorithms.The divergence is defined from h and its chosen subgradient.
3 Proximal mirror descent
Proximal mirror descent is analyzed through a Lyapunov inequality that controls the boundary blow-up of logarithmic barriers. The resulting convergence bounds cover constant and geometric stepsizes, with the geometric schedule yielding a linear rate.
- Lyapunov analysis: The Lyapunov analysis accumulates Bregman-divergence terms in both directions and uses exp-concavity of the log-barrier to control the boundary blow-up.The proof introduces H_k within a telescoping inequality and bounds these terms using the barrier's exp-concavity.
- Main result: Theorem 1 establishes the main convergence bound for proximal mirror descent under the stated well-posedness assumptions.The theorem applies to the iterates of (proxMD) for every k ≥ 1, with A_k defined as the cumulative stepsize.
- Specific stepsize schedules: Constant stepsizes yield a logarithmic-over-iteration convergence rate for proximal mirror descent.Corollary 1 specializes the general theorem to α_k = α.
- Specific stepsize schedules: Geometric stepsizes produce f(x_k) − f⋆ = O((1 + ˜µ)^−k) for any ˜µ < µ.The schedule is defined by α_{k+1} = µA_k, making A_k grow geometrically.
- Structured barriers: Structured distance-generating functions can combine a boundary-finite component with an exp-concave barrier while retaining bounds akin to Theorem 1.This construction permits quadratic regularization without requiring the entire distance-generating function to be exp-concave.
4 Mirror descent
Mirror descent with logarithmic barriers is analyzed by combining standard mirror-descent inequalities with a bound on the additional barrier term. Under the paper's assumptions, the resulting guarantees include an O(log k / k) rate, while stronger assumptions can yield a direct proximal-point interpretation.
- Relative smoothness: Relative smoothness means that the Bregman divergence of f is bounded by L times the Bregman divergence of h.Under this condition, the standard mirror-descent analysis uses stepsize 1/L.
- 4.1 Mirror descent: The mirror-descent proof controls the additional H_k term using exp-concavity of the logarithmic barrier.The resulting Lyapunov inequality includes H_k, with H_k bounded by ν/B_k in the fixed-stepsize analysis.
- 4.1 Mirror descent: Theorem 2 establishes convergence for mirror descent with the stepsize specified in the theorem.The proof telescopes the Lyapunov inequality after setting the cumulative-weight initialization used in the analysis.
- 4.1 Mirror descent: Using the barrier w = Lh − f and unit stepsizes makes the mirror-descent update a proximal mirror-descent instance, so Theorem 1 gives a 4 log(k) / k bound.This direct route requires w to be ν-exp-concave.
- 4.1 Mirror descent: The direct proximal-point interpretation is more restrictive because requiring Lh − f to be exp-concave is stronger than requiring h to be exp-concave.The paper motivates the stronger assumption using the D-optimal design problem.
- 4.2 Mirror flow: Mirror flow provides continuous-time intuition: the objective is monotone and the analysis reaches essentially the same bound as in the discrete case.The flow analysis is presented under S = R^d with a twice-differentiable, strictly convex, ν-exp-concave h.
- 4.3 Linear objectives: For linear objectives, mirror descent and proximal mirror descent coincide, and they coincide with interior-point methods up to a stepsize adjustment.The linear-objective analysis is simpler but does not generally extend when S is not R^d or when S is not affine.
5 Tightness of the bounds
The paper constructs explicit two-dimensional examples showing that the O(log(k)/k) proximal mirror descent bound is attainable under a log-barrier. The construction interpolates convex objective and exp-concave barrier data while satisfying the algorithm’s optimality conditions.
- Tightness result: The example proves tightness of the log(k)/k bound for proximal mirror descent.The construction fixes ν = 1, αk = 1, and an initialization with ∇h(x0) = 0; general positive α and ν follow by scaling.
- Construction: The objective and barrier are reconstructed from sampled data using interpolation conditions.Sf interpolates a convex function f, while Sh interpolates a 1-exp-concave barrier h.
- Construction: The objective and barrier samples share iterates and are coupled through proximal mirror descent optimality conditions.For differentiable h and S = R^d, the coupling becomes ∇h(xi+1) = ∇h(xi) − ∇f(xi+1).
- Barrier construction: The barrier is defined as h(x) = −log(−ϕ(x)) on the convex sublevel domain C = {x: ϕ(x) ≤ 0}.Its domain is ri(C) = {x: ϕ(x) < 0}, and h is +∞ outside that domain.
- Verification: The constructed samples satisfy the required interpolation inequalities, including cases where those inequalities are tight.The verification establishes the convex interpolation for f and the exp-concave interpolation for h, yielding a valid proximal mirror descent run attaining the bound.
6 Proximal mirror descent vs interior-point methods
The paper compares proximal mirror descent with interior-point methods from first-order and second-order computational viewpoints. Under assumptions tailored to IPMs, proximal mirror descent performs only slightly worse, while the comparison remains an idealized proof of concept.
- Computational viewpoints: Mirror descent counts outer iterations with cheap subproblems, whereas IPMs count inner Newton iterations with expensive iterations.These are described as first-order and second-order computational viewpoints, respectively.
- Proximal mirror descent: Geometrically growing stepsizes can make proximal mirror descent fast under broad assumptions.Corollary 2 provides the relevant guarantee for fixed x0 and geometrically growing αk.
- Overall comparison: Proximal mirror descent is presented as a direct alternative to interior-point methods, with slightly worse total complexity.The comparison is made under assumptions designed specifically for IPMs, so it is not fully general.
- Scope: The comparison assumes exact solution of all subproblems and is explicitly described as a proof of concept.More detailed analyses, closer to short-step IPM analyses, are left for future work.
- Newton analysis: The Newton analysis separates globalization cost from the final local quadratic phase.The resulting bound depends on the initial objective gap and the accuracy target ε.
- Complexity comparison: For fixed initial point and stepsize, the leading Newton-iteration term scales as O(...).The paper compares this scaling with classical IPM bounds and notes equivalence up to stepsize adjustment for linear objectives.
7 Remarks and outlook
The paper identifies stronger barrier structure and approximate-solver analyses as directions for improving its bounds and assessing numerical advantages.
- Future bounds: Improved bounds may require modeling log-barriers with structure beyond exp-concavity, such as log-homogeneity.Log-homogeneity is identified as a property used in interior-point-method analyses.
- Open directions: The paper leaves open whether stronger assumptions on the distance-generating function can support accelerated convergence.It also points to approximate solvers and combinations of proximal mirror methods with interior-point strategies as future directions.
- Algorithmic trade-off: Interior-point strategies use exponentially growing stepsizes that can strongly ill-condition subproblems, whereas proximal mirror schemes use bounded but potentially large stepsizes.The distinction is presented as a possible source of numerical advantages for proximal mirror methods.