A Stochastic Levenberg--Marquardt Method Using Random Models with Complexity Results

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F22%3A00357703" target="_blank" >RIV/68407700:21230/22:00357703 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.1137/20M1366253" target="_blank" >https://doi.org/10.1137/20M1366253</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1137/20M1366253" target="_blank" >10.1137/20M1366253</a>

Jazyk výsledku

angličtina

Název v původním jazyce

A Stochastic Levenberg--Marquardt Method Using Random Models with Complexity Results

Popis výsledku v původním jazyce

Globally convergent variants of the Gauss--Newton algorithm are often the methods of choice to tackle nonlinear least-squares problems. Among such frameworks, Levenberg--Marquardt and trust-region methods are two well-established, similar paradigms. Both schemes have been studied when the Gauss--Newton model is replaced by a random model that is only accurate with a given probability. Trust-region schemes have also been applied to problems where the objective value is subject to noise: this setting is of particular interest in fields such as data assimilation, where efficient methods that can adapt to noise are needed to account for the intrinsic uncertainty in the input data. In this paper, we describe a stochastic Levenberg--Marquardt algorithm that handles noisy objective function values and random models, provided sufficient accuracy is achieved in probability. Our method relies on a specific scaling of the regularization parameter that allows us to leverage existing results for trust-region algorithms. Moreover, we exploit the structure of our objective through the use of a family of stationarity criteria tailored to least-squares problems. Provided the probability of accurate function estimates and models is sufficiently large, we bound the expected number of iterations needed to reach an approximate stationary point, which generalizes results based on using deterministic models or noiseless function values. We illustrate the link between our approach and several applications related to inverse problems and machine learning.

Název v anglickém jazyce

A Stochastic Levenberg--Marquardt Method Using Random Models with Complexity Results

Popis výsledku anglicky

Globally convergent variants of the Gauss--Newton algorithm are often the methods of choice to tackle nonlinear least-squares problems. Among such frameworks, Levenberg--Marquardt and trust-region methods are two well-established, similar paradigms. Both schemes have been studied when the Gauss--Newton model is replaced by a random model that is only accurate with a given probability. Trust-region schemes have also been applied to problems where the objective value is subject to noise: this setting is of particular interest in fields such as data assimilation, where efficient methods that can adapt to noise are needed to account for the intrinsic uncertainty in the input data. In this paper, we describe a stochastic Levenberg--Marquardt algorithm that handles noisy objective function values and random models, provided sufficient accuracy is achieved in probability. Our method relies on a specific scaling of the regularization parameter that allows us to leverage existing results for trust-region algorithms. Moreover, we exploit the structure of our objective through the use of a family of stationarity criteria tailored to least-squares problems. Provided the probability of accurate function estimates and models is sufficiently large, we bound the expected number of iterations needed to reach an approximate stationary point, which generalizes results based on using deterministic models or noiseless function values. We illustrate the link between our approach and several applications related to inverse problems and machine learning.

Druh

J_SC - Článek v periodiku v databázi SCOPUS

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

<a href="/cs/project/EF16_019%2F0000765" target="_blank" >EF16_019/0000765: Výzkumné centrum informatiky</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2022

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

SIAM/ASA Journal on Uncertainty Quantification

ISSN

2166-2525

e-ISSN

2166-2525

Svazek periodika

10

Číslo periodika v rámci svazku

1

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

30

Strana od-do

507-536

Kód UT WoS článku

—

EID výsledku v databázi Scopus

2-s2.0-85125866895