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

In this paper, we study the lower complexity bounds for finite-sumoptimization problems, where the objective is the average of $n$ individualcomponent functions. We consider Proximal Incremental First-order (PIFO)algorithms which have access to the gradient and proximal oracles for eachcomponent function. To incorporate loopless methods, we also allow PIFOalgorithms to obtain the full gradient infrequently. We develop a novelapproach to constructing the hard instances, which partitions the tridiagonalmatrix of classical examples into $n$ groups. This construction is friendly tothe analysis of PIFO algorithms. Based on this construction, we establish thelower complexity bounds for finite-sum minimax optimization problems when theobjective is convex-concave or nonconvex-strongly-concave and the class ofcomponent functions is $L$-average smooth. Most of these bounds are nearlymatched by existing upper bounds up to log factors. We can also derive similarlower bounds for finite-sum minimization problems as previous work under bothsmoothness and average smoothness assumptions. Our lower bounds imply thatproximal oracles for smooth functions are not much more powerful than gradientoracles.

Lower Complexity Bounds of Finite-Sum Optimization Problems: The Results and Construction