A Stochastic Objective-Function-Free Adaptive Regularization Method with Optimal Complexity

Serge Gratton; Sadok Jerad; Philippe Toint

A Stochastic Objective-Function-Free Adaptive Regularization Method with Optimal Complexity

Serge Gratton, Sadok Jerad, Philippe Toint

Namur Institute for Complex Systems

Research output: Working paper

30 Downloads (Pure)

Abstract

A fully stochastic second-order adaptive-regularization method for unconstrained nonconvex optimization is presented which never computes the objective-function value, but yet achieves the optimal $\mathcal{O}(\epsilon^{-3/2})$ complexity bound for finding first-order critical points. The method is noise-tolerant and the
inexactness conditions required for convergence depend on the history of past steps. Applications to cases where derivative evaluation is inexact and to minimization of finite sums by sampling are discussed. Numerical experiments on large binary classification problems illustrate the potential of the new method.

Original language	English
Publisher	Arxiv
Number of pages	32
Volume	2407.08018
Publication status	Submitted - 10 Jul 2024

Access to Document

gjt5Licence: Unspecified

2 Article
1 Preprint
1 Working paper

Complexity of Adagrad and other first-order methods for nonconvex optimization problems with bounds and convex constraints
Toint, P., 10 Jul 2024, Arxiv.
Research output: Working paper

File
An optimally fast objective-function-free minimization algorithm using random subspaces
Bellavia, S., Gratton, S., Morini, B. & TOINT, P., 25 Oct 2023, Arxiv, 23 p.
Research output: Working paper › Preprint

File
Convergence properties of an Objective-Function-Free Optimization regularization algorithm, including an 0(epsilon^{-3/2}) complexity bound
Gratton, S., Jerad, S. & TOINT, P., Feb 2023, In: SIAM Journal on Optimization. 33, 3, p. 1621-1646
Research output: Contribution to journal › Article › peer-review

File

2 Active

Complexity in nonlinear optimization
Toint, P. (CoI), Gould, N. I. M. (CoI) & Cartis, C. (CoI)
1/11/08 → …
Project: Research
ADALGOPT: ADALGOPT - Advanced algorithms in nonlinear optimization
Sartenaer, A. (CoI) & Toint, P. (CoI)
1/01/87 → …
Project: Research Axis

1 Participation in workshop, seminar, course

ALGOPT2024 workshop on Algorithmic Optimization
Toint, P. (Contributor)
27 Aug 2024 → 30 Aug 2024
Activity: Participating in or organising an event types › Participation in workshop, seminar, course

Cite this

@techreport{e6e36278768b474d865a926400a2a6a7,

title = "A Stochastic Objective-Function-Free Adaptive Regularization Method with Optimal Complexity",

abstract = "A fully stochastic second-order adaptive-regularization method for unconstrained nonconvex optimization is presented which never computes the objective-function value, but yet achieves the optimal $\mathcal{O}(\epsilon^{-3/2})$ complexity bound for finding first-order critical points. The method is noise-tolerant and theinexactness conditions required for convergence depend on the history of past steps. Applications to cases where derivative evaluation is inexact and to minimization of finite sums by sampling are discussed. Numerical experiments on large binary classification problems illustrate the potential of the new method.",

author = "Serge Gratton and Sadok Jerad and Philippe Toint",

year = "2024",

month = jul,

day = "10",

language = "English",

volume = "2407.08018",

publisher = "Arxiv",

type = "WorkingPaper",

institution = "Arxiv",

}

TY - UNPB

T1 - A Stochastic Objective-Function-Free Adaptive Regularization Method with Optimal Complexity

AU - Gratton, Serge

AU - Jerad, Sadok

AU - Toint, Philippe

PY - 2024/7/10

Y1 - 2024/7/10

N2 - A fully stochastic second-order adaptive-regularization method for unconstrained nonconvex optimization is presented which never computes the objective-function value, but yet achieves the optimal $\mathcal{O}(\epsilon^{-3/2})$ complexity bound for finding first-order critical points. The method is noise-tolerant and theinexactness conditions required for convergence depend on the history of past steps. Applications to cases where derivative evaluation is inexact and to minimization of finite sums by sampling are discussed. Numerical experiments on large binary classification problems illustrate the potential of the new method.

AB - A fully stochastic second-order adaptive-regularization method for unconstrained nonconvex optimization is presented which never computes the objective-function value, but yet achieves the optimal $\mathcal{O}(\epsilon^{-3/2})$ complexity bound for finding first-order critical points. The method is noise-tolerant and theinexactness conditions required for convergence depend on the history of past steps. Applications to cases where derivative evaluation is inexact and to minimization of finite sums by sampling are discussed. Numerical experiments on large binary classification problems illustrate the potential of the new method.

M3 - Working paper

VL - 2407.08018

BT - A Stochastic Objective-Function-Free Adaptive Regularization Method with Optimal Complexity

PB - Arxiv

ER -

A Stochastic Objective-Function-Free Adaptive Regularization Method with Optimal Complexity

Abstract

Access to Document

Fingerprint

Research output

Complexity of Adagrad and other first-order methods for nonconvex optimization problems with bounds and convex constraints

An optimally fast objective-function-free minimization algorithm using random subspaces

Convergence properties of an Objective-Function-Free Optimization regularization algorithm, including an 0(epsilon^{-3/2}) complexity bound

Projects

Complexity in nonlinear optimization

ADALGOPT: ADALGOPT - Advanced algorithms in nonlinear optimization

Activities

ALGOPT2024 workshop on Algorithmic Optimization

Cite this