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

Structured problems arise in many applications. To solve these problems, itis important to leverage the structure information. This paper focuses onconvex problems with a finite-sum compositional structure. Finite-sum problemsappear as the sample average approximation of a stochastic optimization problemand also arise in machine learning with a huge amount of training data. Onepopularly used numerical approach for finite-sum problems is the stochasticgradient method (SGM). However, the additional compositional structureprohibits easy access to unbiased stochastic approximation of the gradient, sodirectly applying the SGM to a finite-sum compositional optimization problem(COP) is often inefficient.  We design new algorithms for solving strongly-convex and also convextwo-level finite-sum COPs. Our design incorporates the Katyusha accelerationtechnique and adopts the mini-batch sampling from both outer-level andinner-level finite-sum. We first analyze the algorithm for strongly-convexfinite-sum COPs. Similar to a few existing works, we obtain linear convergencerate in terms of the expected objective error, and from the convergence rateresult, we then establish complexity results of the algorithm to produce an$\varepsilon$-solution. Our complexity results have the same dependence on thenumber of component functions as existing works. However, due to the use ofKatyusha acceleration, our results have better dependence on the conditionnumber $\kappa$ and improve to $\kappa^{2.5}$ from the best-known $\kappa^3$.Finally, we analyze the algorithm for convex finite-sum COPs, which uses as asubroutine the algorithm for strongly-convex finite-sum COPs. Again, we obtainbetter complexity results than existing works in terms of the dependence on$\varepsilon$, improving to $\varepsilon^{-2.5}$ from the best-known$\varepsilon^{-3}$.

Katyusha Acceleration for Convex Finite-Sum Compositional Optimization