Two-dimensional parallel tempering for constrained optimization

Area of Science:

• Computational Physics
• Machine Learning
• Optimization Algorithms

Background:

• Sampling Boltzmann distributions is crucial for machine learning and optimization.
• Ising machines offer hardware acceleration for these tasks.
• Soft constraints in Ising models often hinder practical implementation by affecting mixing or feasibility.

Purpose of the Study:

• To develop an improved sampling method for constrained Ising problems.
• To address the limitations of conventional parallel tempering (PT) in handling soft constraints.
• To enhance the efficiency and applicability of Ising machines.

Main Methods:

• Introduced a two-dimensional parallel tempering (2D-PT) algorithm.
• Incorporated a second dimension of replicas to interpolate penalty strengths.
• Applied 2D-PT to graph sparsification with copy constraints and sparsified Wishart instances.

Main Results:

• 2D-PT ensures constraint satisfaction in final replicas.
• The algorithm improves mixing in heavily constrained replicas.
• Achieved near-ideal mixing (KL divergence O(1/t)) in graph sparsification.
• Demonstrated orders-of-magnitude speedup over conventional PT for Wishart instances.
• Eliminated the need for explicit penalty strength tuning.

Conclusions:

• 2D-PT is a robust method for constrained Ising problems.
• The algorithm enhances performance on existing Ising machines.
• Offers a broadly applicable solution for efficient constrained optimization.