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

A popular approach to minimize a finite-sum of convex functions is stochasticgradient descent (SGD) and its variants. Fundamental research questionsassociated with SGD include: (i) To find a lower bound on the number of timesthat the gradient oracle of each individual function must be assessed in orderto find an $\epsilon$-minimizer of the overall objective; (ii) To designalgorithms which guarantee to find an $\epsilon$-minimizer of the overallobjective in expectation at no more than a certain number of times (in terms of$1/\epsilon$) that the gradient oracle of each functions needs to be assessed(i.e., upper bound). If these two bounds are at the same order of magnitude,then the algorithms may be called optimal. Most existing results along thisline of research typically assume that the functions in the objective share thesame condition number. In this paper, the first model we study is the problemof minimizing the sum of finitely many strongly convex functions whosecondition numbers are all different. We propose an SGD method for this modeland show that it is optimal in gradient computations, up to a logarithmicfactor. We then consider a constrained separate block optimization model, andpresent lower and upper bounds for its gradient computation complexity. Next,we propose to solve the Fenchel dual of the constrained block optimizationmodel via the SGD we introduced earlier, and show that it yields a loweriteration complexity than solving the original model by the ADMM-type approach.Finally, we extend the analysis to the general composite convex optimizationmodel, and obtain gradient-computation complexity results under certainconditions.

A Gradient Complexity Analysis for Minimizing the Sum of Strongly Convex Functions with Varying Condition Numbers