finite-sum optimization

Trust-region algorithms: probabilistic complexity and intrinsic noise with applications to subsampling techniques

  • Stefania Bellavia
  • Gianmarco Gurioli
  • Benedetta Morini
  • Philippe L. Toint
    • Categories Nonlinear Systems and Least-Squares, Unconstrained Optimization Tags , , , , ,

    A trust-region algorithm is presented for finding approximate minimizers of smooth unconstrained functions whose values and derivatives are subject to random noise. It is shown that, under suitable probabilistic assumptions, the new method finds (in expectation) an epsilon-approximate minimizer of arbitrary order q > 0 in at most O(epsilon^{-(q+1)}) inexact evaluations of the function and … Read more

    A Fully Stochastic Second-Order Trust Region Method

  • Frank E. Curtis
  • Rui Shi
    • Categories Nonlinear Optimization, Stochastic Programming, Unconstrained Optimization Tags , , , , , ,

    A stochastic second-order trust region method is proposed, which can be viewed as a second-order extension of the trust-region-ish (TRish) algorithm proposed by Curtis et al. [INFORMS J. Optim. 1(3) 200–220, 2019]. In each iteration, a search direction is computed by (approximately) solving a trust region subproblem defined by stochastic gradient and Hessian estimates. The … Read more

    Adaptive cubic regularization methods with dynamic inexact Hessian information and applications to finite-sum minimization

  • Stefania Bellavia
  • Benedetta Morini
  • Gianmarco Gurioli
    • Categories Unconstrained Optimization Tags

    Abstract. We consider the Adaptive Regularization with Cubics approach for solving nonconvex optimization problems and propose a new variant based on inexact Hessian information chosen dynamically. The theoretical analysis of the proposed procedure is given. The key property of ARC framework, constituted by optimal worst-case function/derivative evaluation bounds for first- and second-order critical point, is … Read more

    Adaptive Cubic Regularization methods with dynamic inexact Hessian information and applications to finite-sum minimization

  • Stefania Bellavia
  • Benedetta Morini
  • Gianmarco Gurioli
    • Categories Unconstrained Optimization Tags

    We consider the Adaptive Regularization with Cubics approach for solving nonconvex optimization problems and propose a new variant based on inexact Hessian information chosen dynamically. The theoretical analysis of the proposed procedure is given. The key property of ARC framework, constituted by optimal worst-case function/derivative evaluation bounds for first- and second-order critical point, is guaranteed. … Read more

    Random Gradient Extrapolation for Distributed and Stochastic Optimization

  • Guanghui Lan
  • Yi Zhou
    • Categories Convex Optimization, Stochastic Programming Tags , , , ,

    In this paper, we consider a class of finite-sum convex optimization problems defined over a distributed multiagent network with $m$ agents connected to a central server. In particular, the objective function consists of the average of $m$ ($\ge 1$) smooth components associated with each network agent together with a strongly convex term. Our major contribution … Read more