high probability complexity

High-Probability Polynomial-Time Complexity of Restarted PDHG for Linear Programming

  • Zikai Xiong
    • Categories Linear Programming Tags , , ,

    The restarted primal-dual hybrid gradient method (rPDHG) is a first-order method that has recently received significant attention for its computational effectiveness in solving linear program (LP) problems. Despite its impressive practical performance, the theoretical iteration bounds for rPDHG can be exponentially poor. To shrink this gap between theory and practice, we show that rPDHG achieves … Read more

    First- and Second-Order High Probability Complexity Bounds for Trust-Region Methods with Noisy Oracles

  • Liyuan Cao
  • Albert S. Berahas
  • Katya Scheinberg
    • Categories Nonlinear Optimization, Unconstrained Optimization Tags , , ,

    In this paper, we present convergence guarantees for a modified trust-region method designed for minimizing objective functions whose value is computed with noise and for which gradient and Hessian estimates are inexact and possibly random. In order to account for the noise, the method utilizes a relaxed step acceptance criterion and a cautious trust-region radius … Read more