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

Randomized algorithms are important for solving large-scale optimizationproblems. In this paper, we propose a fast sketching algorithm for least squareproblems regularized by convex or nonconvex regularization functions, Sketchingfor Regularized Optimization (SRO). Our SRO algorithm first generates a sketchof the original data matrix, then solves the sketched problem. Different fromexisting randomized algorithms, our algorithm handles general Frechetsubdifferentiable regularization functions in an unified framework. We presentgeneral theoretical result for the approximation error between the optimizationresults of the original problem and the sketched problem for regularized leastsquare problems which can be convex or nonconvex. For arbitrary convexregularizer, relative-error bound is proved for the approximation error.Importantly, minimax rates for sparse signal estimation by solving the sketchedsparse convex or nonconvex learning problems are also obtained using ourgeneral theoretical result under mild conditions. To the best of our knowledge,our results are among the first to demonstrate minimax rates for convex ornonconvex sparse learning problem by sketching under a unified theoreticalframework. We further propose an iterative sketching algorithm which reducesthe approximation error exponentially by iteratively invoking the sketchingalgorithm. Experimental results demonstrate the effectiveness of the proposedSRO and Iterative SRO algorithms.

Sketching for Convex and Nonconvex Regularized Least Squares with Sharp Guarantees