DeepAI

# Harder, Better, Faster, Stronger Convergence Rates for Least-Squares Regression

We consider the optimization of a quadratic objective function whose gradients are only accessible through a stochastic oracle that returns the gradient at any given point plus a zero-mean finite variance random error. We present the first algorithm that achieves jointly the optimal prediction error rates for least-squares regression, both in terms of forgetting of initial conditions in O(1/n 2), and in terms of dependence on the noise and dimension d of the problem, as O(d/n). Our new algorithm is based on averaged accelerated regularized gradient descent, and may also be analyzed through finer assumptions on initial conditions and the Hessian matrix, leading to dimension-free quantities that may still be small while the " optimal " terms above are large. In order to characterize the tightness of these new bounds, we consider an application to non-parametric regression and use the known lower bounds on the statistical performance (without computational limits), which happen to match our bounds obtained from a single pass on the data and thus show optimality of our algorithm in a wide variety of particular trade-offs between bias and variance.

03/03/2022

### Accelerated SGD for Non-Strongly-Convex Least Squares

We consider stochastic approximation for the least squares regression pr...
09/29/2010

### Optimal learning rates for Kernel Conjugate Gradient regression

We prove rates of convergence in the statistical sense for kernel-based ...
07/04/2023

### Accelerated stochastic approximation with state-dependent noise

We consider a class of stochastic smooth convex optimization problems un...
02/03/2022

### Multiclass learning with margin: exponential rates with no bias-variance trade-off

We study the behavior of error bounds for multiclass classification unde...
05/08/2019

### Optimal Statistical Rates for Decentralised Non-Parametric Regression with Linear Speed-Up

We analyse the learning performance of Distributed Gradient Descent in t...
06/17/2022
{"ft_lang_label":"__label__en","ft_lang_prob":0.9074702,"math_prob":0.9350593,"size":1255,"snap":"2023-40-2023-50","text_gpt3_token_len":231,"char_repetition_ratio":0.089528374,"word_repetition_ratio":0.0,"special_character_ratio":0.17848605,"punctuation_ratio":0.06481481,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9910351,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2023-09-22T06:12:52Z\",\"WARC-Record-ID\":\"<urn:uuid:7bf407a3-8483-47fa-a170-efaec6110985>\",\"Content-Length\":\"119565\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:6759c4f3-5b65-492f-b455-ec6ade216a35>\",\"WARC-Concurrent-To\":\"<urn:uuid:777485e2-4b38-4399-b334-f4ef49c14f4e>\",\"WARC-IP-Address\":\"34.215.82.175\",\"WARC-Target-URI\":\"http://api.deepai.org/publication/harder-better-faster-stronger-convergence-rates-for-least-squares-regression\",\"WARC-Payload-Digest\":\"sha1:75C7HOCLEXK4BKA5UATSBKYKCDIZORL4\",\"WARC-Block-Digest\":\"sha1:P3E4IM7JE3OOUIDB2XZIGGQEKFEMUOL3\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2023/CC-MAIN-2023-40/CC-MAIN-2023-40_segments_1695233506329.15_warc_CC-MAIN-20230922034112-20230922064112-00478.warc.gz\"}"}