English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Several classical adaptive optimization algorithms, such as line search andtrust region methods, have been recently extended to stochastic settings wherefunction values, gradients, and Hessians in some cases, are estimated viastochastic oracles. Unlike the majority of stochastic methods, these methods donot use a pre-specified sequence of step size parameters, but adapt the stepsize parameter according to the estimated progress of the algorithm and use itto dictate the accuracy required from the stochastic approximations. Therequirements on stochastic approximations are, thus, also adaptive and theoracle costs can vary from iteration to iteration. The step size parameters inthese methods can increase and decrease based on the perceived progress, butunlike the deterministic case they are not bounded away from zero due topossible oracle failures, and bounds on the step size parameter have not beenpreviously derived. This creates obstacles in the total complexity analysis ofsuch methods, because the oracle costs are typically decreasing in the stepsize parameter, and could be arbitrarily large as the step size parameter goesto 0. Thus, until now only the total iteration complexity of these methods hasbeen analyzed. In this paper, we derive a lower bound on the step sizeparameter that holds with high probability for a large class of adaptivestochastic methods. We then use this lower bound to derive a framework foranalyzing the expected and high probability total oracle complexity of anymethod in this class. Finally, we apply this framework to analyze the totalsample complexity of two particular algorithms, STORM and SASS, in the expectedrisk minimization problem.

Sample Complexity Analysis for Adaptive Optimization Algorithms with Stochastic Oracles