PaperlayerView exact revision on arXiv

Source-linked AI summary

Neural Predictor-Corrector: Solving Homotopy Problems with Reinforcement Learning

Jiayao Mai, Bangyan Liao, Zhenjun Zhao, Yingping Zeng, Haoang Li, Javier Civera, Tailin Wu, Yi Zhou, Peidong Liu

arXiv:2602.03086v1cs.LGcs.CV

TL;DR

Existing homotopy solvers use task-specific heuristics for predictor-corrector step sizes and termination. NPC unifies these problems and learns adaptive policies with reinforcement learning, outperforming existing approaches in efficiency while improving stability across tasks.

  • Problem

    Homotopy solvers rely on manually designed, task-specific heuristics and lack a unified framework spanning diverse problem domains.

  • Method

    NPC models predictor-corrector policy selection as a sequential decision problem and learns adaptive policies through reinforcement learning.

  • Results

    Across four representative homotopy problems, NPC generalizes to unseen instances, consistently improves computational efficiency, and demonstrates superior numerical stability.

  • Takeaways & Limitations

    The results support learning-based policy search as a practical, generalizable alternative to traditional heuristic strategies for homotopy solvers.

  • Takeaways & Limitations

    Runtime comparisons are not directly comparable when implementations use different programming languages or hardware.

Abstract

from arXiv · show

The Homotopy paradigm, a general principle for solving challenging problems, appears across diverse domains such as robust optimization, global optimization, polynomial root-finding, and sampling. Practical solvers for these problems typically follow a predictor-corrector (PC) structure, but rely on hand-crafted heuristics for step sizes and iteration termination, which are often suboptimal and task-specific. To address this, we unify these problems under a single framework, which enables the design of a general neural solver. Building on this unified view, we propose Neural Predictor-Corrector (NPC), which replaces hand-crafted heuristics with automatically learned policies. NPC formulates policy selection as a sequential decision-making problem and leverages reinforcement learning to automatically discover efficient strategies. To further enhance generalization, we introduce an amortized training mechanism, enabling one-time offline training for a class of problems and efficient online inference on new instances. Experiments on four representative homotopy problems demonstrate that our method generalizes effectively to unseen instances. It consistently outperforms classical and specialized baselines in efficiency while demonstrating superior stability across tasks, highlighting the value of unifying homotopy methods into a single neural framework.

1 INTRODUCTION

The paper unifies diverse homotopy-based problems through their shared predictor-corrector structure and introduces Neural Predictor-Corrector (NPC) to learn solver policies with reinforcement learning. NPC uses amortized offline training and generalizes to unseen instances across four representative homotopy tasks.

  • Homotopy unification: Homotopy methods span robust optimization, global optimization, polynomial root-finding, and sampling under different names.Examples include Graduated Non-Convexity, Gaussian homotopy, homotopy continuation, and annealed Langevin dynamics.
  • Motivation: Practical solvers commonly use predictor-corrector structures but depend on manually designed, suboptimal, task-specific step-size and termination heuristics.The predictor advances along the outer homotopy interpolation, while the corrector iteratively refines the solution.
  • Neural Predictor-Corrector: NPC replaces heuristic rules by treating predictor and corrector strategy selection as sequential decision-making and learning policies with reinforcement learning.The framework is designed as a plug-and-play solver rather than separate per-problem solutions.
  • Amortized training: A single offline training phase over problem instances produces a policy that can be deployed on new instances without per-instance fine-tuning.This amortized training regime targets new instances from the same problem.
  • Evaluation: Experiments evaluate NPC on four representative homotopy tasks and validate strong generalization to previously unseen instances.The tasks cover robust optimization, global optimization, polynomial root-finding, and sampling.

2 RELATED WORKS

Predictor-corrector methods span multiple domains but have largely developed independently. Learning and reinforcement-learning approaches improve selected homotopy components or algorithmic parameters, yet prior work does not provide a transferable, amortized policy for full predictor-corrector control across diverse homotopy classes.

  • Research gap: Homotopy-related research lines have largely evolved independently despite predictor-corrector solvers appearing across multiple domains.This fragmentation motivates reviewing the classical, learning-based, and reinforcement-learning approaches together.
  • Classical PC algorithms: Classical predictor-corrector schemes trace solution trajectories along explicit homotopy interpolations.Examples include Graduated Non-Convexity for robust optimization and Gaussian homotopy methods for tracking minimizers during bandwidth reduction.
  • Learning-based improvements for homotopy workflows: Prior learning-based methods improve Gaussian homotopy, sampling, combinatorial optimization, and polynomial root-finding.However, these methods either target a single homotopy component or require specialized training for each instance.
  • Reinforcement learning for optimization and sampling: Reinforcement learning has been used to learn optimizers or adapt algorithmic parameters for some optimization and sampling tasks.These works do not address full predictor-corrector control across diverse homotopy classes.

3 HOMOTOPY PARADIGM AS A UNIFIED PERSPECTIVE

The section presents homotopy as a unified framework that continuously transforms simple problems into complex targets and shows that practical solvers share a predictor-corrector structure. It uses four representative applications to demonstrate this framework’s breadth and motivate learned policy optimization.

  • 3.1 Homotopy Paradigm: Homotopy continuously interpolates from a source problem with known solutions to a complex target while tracing the implicit solution trajectory.The interpolation is defined by H(x, 0) = f(x) and H(x, 1) = g(x), with x∗(t) tracked as t varies from 0 to 1.
  • 3.2 Predictor-Corrector Framework: Predictor-corrector methods track this trajectory by predicting the next homotopy level and iteratively refining the solution estimate.The corrector prevents bias from accumulating across homotopy levels.
  • 3.2 Predictor-Corrector Framework: Heuristic choices of predictor schedules and corrector iteration counts can cause inefficiency, instability, or inaccurate trajectory tracking.These limitations motivate adaptive or learning-based strategies for robust and efficient solution tracking.
  • 3.3 Representative Problems: Four applications instantiate the unified framework: robust optimization uses GNC, global optimization uses Gaussian Homotopy, root-finding uses Homotopy Continuation, and sampling uses Annealed Langevin Dynamics.Their implementations pair problem-specific predictors with correctors such as nonlinear least squares, Gaussian smoothing refinement, Gauss-Newton iteration, or Langevin dynamics.
  • 3.3 Representative Problems: These examples demonstrate the broad applicability of homotopy and the central role of predictor-corrector strategies, motivating learning-based policy optimization.The applications span robust optimization, global optimization, polynomial root-finding, and sampling.

4 NEURAL PREDICTOR-CORRECTOR WITH REINFORCEMENT LEARNING

NPC unifies homotopy solving by replacing fixed predictor-corrector heuristics with neural policies learned through reinforcement learning. It makes adaptive sequential decisions for path advancement and correction, balancing trajectory accuracy with computational efficiency and generalizing through amortized training.

  • NPC formulation: NPC replaces heuristic step-size schedules and termination criteria with neural parameterizations learned via reinforcement learning.The framework addresses trajectories requiring small steps during sharp transitions and larger steps along smooth regions.
  • NPC formulation: At each iteration, the neural module selects predictor and corrector actions, the predictor advances the homotopy level, and the corrector refines the solution until convergence criteria are met.The iterative loop also collects corrector statistics and convergence velocity for subsequent decisions.
  • State and action design: The policy state includes the current homotopy level, corrector statistics, and convergence velocity, while actions specify the step size and corrector termination.Convergence velocity uses relative objective-value change for optimization and root-finding, and statistical-distance change such as KSD for sampling.
  • Reinforcement learning: RL is used because early non-differentiable decisions affect the entire trajectory, and cumulative rewards can evaluate their sequential effects across instances.The reward combines step-wise accuracy with a terminal efficiency bonus formulated as Tmax − T.
  • Generalization: Amortized training over a distribution of problem instances produces policies that can be applied efficiently to unseen instances within the same problem class.This avoids relying on consistent local trajectory geometry, an assumption that can cause overfitting to training landscapes.

5 EXPERIMENTS

Experiments evaluate NPC across robust optimization, non-convex minimization, polynomial root-finding, and sampling, with training on selected problem instances to assess generalization. Across these settings, NPC maintains comparable solution quality while improving efficiency, and ablations show that all RL state components contribute to iteration efficiency.

  • GNC robust optimization: NPC is evaluated on GNC point cloud registration with 95% outliers and multi-view triangulation with 50% outliers, comparing against Classic GNC and IRLS.The model is trained solely on the Aquarius dataset, while rotation, translation, and 3D reconstruction errors assess accuracy.
  • GH non-convex minimization: NPC-accelerated GH substantially reduces iterations and runtime versus Classic GH on Ackley, Himmelblau, and Rastrigin benchmarks while maintaining comparable solution quality.Baselines include SLGHr, SLGHd, PGS, and CPL; SLGHd and PGS occasionally fail to reach the target.
  • HC root-finding: NPC is evaluated with HC on polynomial-system benchmarks and UPnP generalized camera pose estimation, with success rate and average tracking time reported.Runtimes are not directly comparable because Simulator HC uses C++ whereas the other methods use Python.
  • ALD sampling: NPC-accelerated ALD is tested on a 40-mode GMM, 10-dimensional funnel, and DW-4 against classic ALD and applicable iDEM baselines.Evaluation uses Wasserstein-2 distance and Kernelized Stein Discrepancy, with NPC trained on a randomized 10-mode GMM.
  • Ablation and efficiency–precision trade-off: Removing any single RL state component increases corrector iterations relative to the full state, typically causing smaller predictor steps and a more conservative strategy.The ablation retrains NPC separately on six GNC point cloud registration datasets.
  • Ablation and efficiency–precision trade-off: NPC learns a policy that balances predictor step size and corrector behavior, avoiding manual homotopy-parameter exploration in the efficiency–precision trade-off.Classical methods typically require more iterations to achieve higher precision.

6 CONCLUSION

The paper introduces NPC, a reinforcement-learning framework that unifies diverse homotopy solvers under a predictor-corrector structure. It replaces handcrafted heuristics with learned policies and demonstrates efficient, stable generalization to unseen instances.

  • Contributions: NPC unifies robust optimization, global optimization, polynomial system root-finding, and sampling under the homotopy paradigm, whose solvers universally follow a predictor-corrector structure.This unified view supports a general neural solver framework.
  • Contributions: NPC replaces handcrafted heuristics with adaptive learned policies and uses amortized training for one-time offline training and efficient, training-free deployment on new instances.The amortized regime separates training from online inference.
  • Empirical findings: Extensive experiments show that NPC generalizes effectively to unseen instances, consistently improves computational efficiency over existing approaches, and exhibits superior numerical stability.These findings support learning-based policy selection for homotopy solvers.

7 ETHICS STATEMENT

The work presents NPC as a unified learning-based solver for homotopy-governed problems and reports no identified ethical risks from its evaluation or primary application.

  • Research scope: NPC unifies diverse problem domains governed by the homotopy paradigm into a single learning-based solver framework.The framework is intended to provide a general solver across these domains.
  • Data and evaluation: The experiments use publicly available academic benchmarks and synthetic data without human subjects or sensitive personal information.The evaluation does not involve collecting or processing human-subject data.
  • Potential impacts: The authors foresee no direct negative societal impacts or dual-use concerns, identifying scientific inquiry as the primary application.They characterize NPC as a more efficient and robust tool for scientific inquiry.

8 REPRODUCIBILITY STATEMENT … A.2.1 THE GAUSSIAN HOMOTOPY ALGORITHM

The paper provides reproducibility resources and implementation details for GNC and Gaussian homotopy algorithms, including their predictor-corrector procedures, optimization methods, and experimental settings.

  • 8 REPRODUCIBILITY STATEMENT: Datasets, synthetic-data parameters, implementation details, and experimental hyperparameters are specified, with code and pretrained models planned for public release.These materials are described as supporting reproducibility across the experiments.
  • A.1.1 THE GRADUATED NON-CONVEXITY ALGORITHM: GNC reformulates least-squares optimization with a robust kernel and Black-Rangarajan Duality, introducing weights and penalties tied to the robust cost.The weight can subsequently be solved in closed form from the homotopy level and residual.
  • A.1.1 THE GRADUATED NON-CONVEXITY ALGORITHM: GNC prediction updates each measurement weight rather than the optimization variable, while correction updates x with a nonlinear optimization method.This predictor-corrector formulation follows the equations specified for the reformulated problem.
  • A.1.1 THE GRADUATED NON-CONVEXITY ALGORITHM: Point cloud registration uses a Gauss-Newton corrector, whereas multi-view triangulation uses a Levenberg-Marquardt algorithm.The LM corrector is described as more robust for multi-view triangulation.
  • A.1.1 THE GRADUATED NON-CONVEXITY ALGORITHM: GNC reward scaling uses λ1 = 103 and λ2 = 10^-3 for point cloud registration, versus λ1 = 10^-1 and λ2 = 10^-3 for multi-view triangulation.The different λ1 setting for triangulation is attributed to its significantly larger noise scale.
  • A.2.1 THE GAUSSIAN HOMOTOPY ALGORITHM: Gaussian homotopy changes the shape of H(x, t) implicitly by varying the predictor’s homotopy level t.The predictor does not directly modify x during this process.
  • A.2.1 THE GAUSSIAN HOMOTOPY ALGORITHM: Gaussian homotopy correction uses Polyak momentum with zero initial velocity, α = 0.01, and β = 0.8.Here, β controls the influence of past gradients and α determines the update step size.
  • A.2.1 THE GAUSSIAN HOMOTOPY ALGORITHM: When analytical gradients are infeasible for some Gaussian homotopy functions, a zeroth-order method numerically approximates them, with reward scaling λ1 = 1 and λ2 = 10^-3.The numerical approximation follows the cited calculation formula.

A.2.2 THE NON-CONVEX FUNCTION MINIMIZATION BENCHMARKS · A.3 DETAILS OF PROBLEM 3 : POLYNOMIAL ROOT-FINDING VIA HC (SEC. 5.4) · A.3.1 THE HOMOTOPY-CONTINUATION ALGORITHM

The benchmarks include Ackley, Himmelblau, and Rastrigin optimization problems, while the polynomial root-finding method combines Padé prediction with Newton correction. The implementation specifies Padé orders, a power-series fallback, a convergence criterion, and reward-scaling values.

  • A.2.2 THE NON-CONVEX FUNCTION MINIMIZATION BENCHMARKS: The non-convex minimization benchmarks include Ackley, Himmelblau, and Rastrigin optimization problems.
  • A.2.2 THE NON-CONVEX FUNCTION MINIMIZATION BENCHMARKS: The Himmelblau benchmark is defined by f(x, y) = (x2 + y −11)2 + (x + y2 −7)2.
  • A.3.1 THE HOMOTOPY-CONTINUATION ALGORITHM: The polynomial system root-finding problem is modeled in the form of Eq. (3).
  • A.3.1 THE HOMOTOPY-CONTINUATION ALGORITHM: The predictor estimates x(t + ∆t) using a Padé approximation polynomial Rn,m(x) = Rn(x) Qm(x).
  • A.3.1 THE HOMOTOPY-CONTINUATION ALGORITHM: The Padé principle constructs Pn(x) and Qm(x) so that Qm(x)f(x) − Pn(x) has approximation order at least n + m + 1.
  • A.3.1 THE HOMOTOPY-CONTINUATION ALGORITHM: The implementation sets n = 2 and m = 1, yielding p0 = c0, p1 = c1 + q1c0, and p2 = c2 + q1c1.
  • A.3.1 THE HOMOTOPY-CONTINUATION ALGORITHM: When the Padé denominator approaches zero, prediction reverts to the power series x(t + ∆t) = c0 + c1∆t + c2∆t2 + c3∆t3.
  • A.3.1 THE HOMOTOPY-CONTINUATION ALGORITHM: The corrector uses Newton updates until ∆x < ϵ, with reward scaling set to λ1 = 10−3 and λ2 = 10−1.

A.3.2 THE POLYNOMIAL SYSTEM BENCHMARKS … C FULL RELATED WORK

The paper specifies polynomial-system benchmarks, details annealed Langevin sampling and its evaluation, introduces reinforcement learning, and situates the unified predictor-corrector framework within prior work.

  • A.3.2 THE POLYNOMIAL SYSTEM BENCHMARKS: The polynomial benchmarks comprise the Katsura-n, Cyclic-n, Noon-n, and Chandra-n polynomial systems.The implementations set c = 1.1 for Noon-n and c = 0.51234 for Chandra-n.
  • A.4 DETAILS OF PROBLEM 4 : SAMPLING VIA ALD (SEC. 5.5): The ALD sampling problem obtains initial samples from a simple distribution and updates them through time-dependent potentials.Its predictor varies the homotopy level t, while the corrector updates sample positions using Langevin steps with Gaussian noise.
  • A.4.1 THE ANNEALED LANGEVIN DYNAMIC SAMPLING ALGORITHM: ALD reward scaling uses λ1 = 10 and λ2 = 10−3.These values are specified in the experiment details.
  • A.4.2 DISTRIBUTIONS: The distribution benchmarks include a 10-dimensional funnel distribution and a 4-particle double-well potential.The double-well implementation sets τ = 1, a = 0, b = −4, and c = 0.9.
  • A.4.3 METRIC: Evaluation uses Wasserstein-2 distance and Kernelized Stein Discrepancy, with the POT package for W2 and a standard RBF kernel for KSD.The W2 implementation uses Python Optimal Transport, while KSD uses the standard RBF kernel.
  • B BACKGROUND ON REINFORCEMENT LEARNING: Reinforcement learning formulates sequential decision-making as a Markov Decision Process with states, actions, transitions, rewards, initial-state distribution, and discount factor γ.The objective is an optimal policy maximizing expected cumulative reward along trajectories.
  • C FULL RELATED WORK: The related-work review organizes prior research into classical predictor-corrector algorithms, learning-based homotopy improvements, and reinforcement learning for optimization and sampling.It positions the paper as the first to unify methods that share predictor-corrector structure but evolved independently.
  • C FULL RELATED WORK: Prior learning-based work includes problem-specific Gaussian homotopy training, learned starting systems for polynomial root-finding, combinatorial optimization annealing, and path-space sampling frameworks.Related reinforcement-learning studies formulate optimizers as policies or dynamically select algorithmic parameters such as damping factors.

D LIMITATION AND FUTURE WORK

The paper identifies manual reward-scale tuning as a limitation because reward imbalance can destabilize training and induce myopic trajectory tracking. Future work will pursue automatic reward-scale adaptation and adaptive reward normalization to eliminate this manual tuning.

  • Limitation: NPC reward scales require manual tuning for each problem instance according to noise level to achieve stable and efficient training.Step-wise reward scale affects convergence time, while an oversized terminal reward can overwhelm step-wise guidance.
  • Limitation: Reward imbalance can prevent correct solution-trajectory tracking and cause myopic strategies that prematurely reach termination.The limitation arises when terminal rewards nullify the guidance provided by step-wise rewards.
  • Future Work: Future work proposes automatically adapting the reward scale to make training robust without manual tuning.A more fundamental direction is adaptive normalization of the reward function.

E FULL EXPERIMENTAL RESULTS

The section provides complete experimental results for GNC point cloud registration, GH non-convex minimization, and HC polynomial root-finding, supplemented by box plots of selected outcomes. It also documents training setups and cautions that HC runtimes are not directly comparable across implementations.

  • Complete experimental results: Tables 8–10 give full results for GNC point cloud registration, GH non-convex function minimization, and HC polynomial system root-finding experiments.Table 8 reports rotation and translation errors on a log10 scale; Table 10 reports success rate and average tracking time per solution path.
  • Training setups: The GNC agent is trained on the Aquarius sequence for point cloud registration.
  • Training setups: The GH agent is trained on Ackley functions with randomized parameters and evaluated on the canonical fixed-parameter version.
  • Supplementary visualizations: Figure 5 visualizes selected performance distributions over 50 independent trials to compare method stability and efficiency.The shown examples include bunny-sequence rotation error and runtime for point cloud registration.
  • Runtime caveat: HC runtimes are not directly comparable because Simulator HC is implemented in C++, whereas the other methods are implemented in Python.
  • Training setups: HC training uses a separate set of polynomial systems with randomized coefficients.
Loading 2602.03086v1…