Κοινή χρήση τεχνολογίας

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

Περίληψη

Η στοχαστική βελτιστοποίηση είναι ένα ζωτικό συστατικό της μηχανικής μάθησης και στον πυρήνα της βρίσκεται ο αλγόριθμος στοχαστικής διαβάθμισης (SGD), μια μέθοδος που έχει χρησιμοποιηθεί ευρέως από τότε που προτάθηκε για πρώτη φορά πριν από περισσότερα από 60 χρόνια. Τα τελευταία οκτώ χρόνια, γίναμε μάρτυρες μιας συναρπαστικής νέας εξέλιξης: τεχνικές μείωσης διασποράς για μεθόδους στοχαστικής βελτιστοποίησης. Αυτές οι μέθοδοι μείωσης της διακύμανσης (μέθοδοι VR) έχουν καλή απόδοση σε σενάρια που επιτρέπουν πολλαπλές επαναλήψεις των δεδομένων εκπαίδευσης, παρουσιάζοντας ταχύτερη σύγκλιση από το SGD, τόσο στη θεωρία όσο και στην πράξη. Αυτή η αύξηση της ταχύτητας υπογραμμίζει το αυξανόμενο ενδιαφέρον για τις μεθόδους VR και το ταχέως συσσωρευμένο ερευνητικό αποτέλεσμα σε αυτόν τον τομέα. Αυτό το άρθρο εξετάζει βασικές αρχές και σημαντικές προόδους στις μεθόδους VR για βελτιστοποίηση περιορισμένων συνόλων δεδομένων, με στόχο να ενημερώσει τους μη ειδικούς αναγνώστες. Εστιάζουμε κυρίως σε κυρτά περιβάλλοντα βελτιστοποίησης και παρέχουμε μια αναφορά σε αναγνώστες που ενδιαφέρονται για επεκτάσεις ελαχιστοποίησης μη κυρτών συναρτήσεων.

Λέξεις κλειδιά Μείωση διακύμανσης

1. Εισαγωγή

Στον τομέα της έρευνας μηχανικής μάθησης, ένα βασικό και σημαντικό ζήτημα είναι ο τρόπος προσαρμογής του μοντέλου σε ένα τεράστιο σύνολο δεδομένων. Για παράδειγμα, μπορούμε να εξετάσουμε την τυπική περίπτωση ενός γραμμικού μοντέλου ελαχίστων τετραγώνων:

$${{\rm X}}^{\ast }\in \mathrm{\alpha \rho \sigma o\lambda }\underset{{\rm X}\in {\mathbb{R}}^{\rho \epsilon }}{\mathrm{\epsilon \lambda ά\chi }}\frac{1}{n}\sum _{{\rm E}\gamma ώ=1}^n({έ\nu \alpha }_{{\rm E}\gamma ώ}^{{\rm T}}{\rm X}-{\sigma \iota }_{{\rm E}\gamma ώ}{)}^2$$

Σε αυτό το μοντέλο έχουμε $\rho \epsilon$ παραμέτρους, οι οποίες αντιπροσωπεύονται από διανύσματα${\rm X}\in {\mathbb{R}}^{\rho \epsilon }$ δεδομένος.Στο μεταξύ, έχουμε σε ετοιμότητα$n$ σημεία δεδομένων, συμπεριλαμβανομένων των διανυσμάτων χαρακτηριστικών${έ\nu \alpha }_{{\rm E}\gamma ώ}\in {\mathbb{R}}^{\rho \epsilon }$ και την τιμή στόχο${\sigma \iota }_{{\rm E}\gamma ώ}\in \mathbb{R}$ .Η διαδικασία προσαρμογής του μοντέλου είναι να προσαρμόσει αυτές τις παραμέτρους έτσι ώστε το προβλεπόμενο αποτέλεσμα του μοντέλου${έ\nu \alpha }_{{\rm E}\gamma ώ}^{{\rm T}}{\rm X}$ κατά μέσο όρο όσο το δυνατόν πιο κοντά στην τιμή στόχο${\sigma \iota }_{{\rm E}\gamma ώ}$。

Γενικότερα, μπορεί να χρησιμοποιήσουμε μια συνάρτηση απώλειας ${\phi ά}_{{\rm E}\gamma ώ}({\rm X})$ Για να μετρήσετε τις προβλέψεις του μοντέλου και το${\rm E}\gamma ώ$ Πόσο κοντά είναι τα σημεία δεδομένων:

$${{\rm X}}^{\ast }\in \mathrm{\alpha \rho \sigma o\lambda }\underset{{\rm X}\in {\mathbb{R}}^{\rho \epsilon }}{\mathrm{\epsilon \lambda ά\chi }}\phi ά({\rm X}):=\frac{1}{n}\sum _{{\rm E}\gamma ώ=1}^n{\phi ά}_{{\rm E}\gamma ώ}({\rm X})$$

λειτουργία απώλειας ${\phi ά}_{{\rm E}\gamma ώ}({\rm X})$ Εάν είναι μεγαλύτερο, υποδηλώνει ότι οι προβλέψεις του μοντέλου αποκλίνουν πολύ από τα δεδομένα εάν${\phi ά}_{{\rm E}\gamma ώ}({\rm X})$ Ίσο με μηδέν, το μοντέλο ταιριάζει απόλυτα στα σημεία δεδομένων.λειτουργία$\phi ά({\rm X})$ Αντικατοπτρίζει τη μέση απώλεια του μοντέλου σε ολόκληρο το σύνολο δεδομένων.

Προβλήματα όπως η φόρμα (2) παραπάνω ισχύουν όχι μόνο για προβλήματα γραμμικών ελαχίστων τετραγώνων, αλλά και σε πολλά άλλα μοντέλα που μελετώνται στη μηχανική μάθηση. Για παράδειγμα, σε ένα μοντέλο λογιστικής παλινδρόμησης λύνουμε για:

$${{\rm X}}^{\ast }\in \mathrm{\alpha \rho \sigma o\lambda }\underset{{\rm X}\in {\mathbb{R}}^{\rho \epsilon }}{\mathrm{\epsilon \lambda ά\chi }}\frac{1}{n}\sum _{{\rm E}\gamma ώ=1}^n\mathrm{\iota \delta oύ\sigma o\lambda }(1+{\mu \iota }^{-{\sigma \iota }_{{\rm E}\gamma ώ}{έ\nu \alpha }_{{\rm E}\gamma ώ}^{{\rm T}}{\rm X}})+\frac{\lambda }{2}\Vert {\rm X}{\Vert }_2^2$$

Εδώ, έχουμε να κάνουμε με bi ∈ { − 1 , + 1 } b_i σε {-1, +1}σιΕγώ​∈{−1,+1} Για ένα πρόβλημα δυαδικής ταξινόμησης, η πρόβλεψη βασίζεται σε${έ\nu \alpha }_{{\rm E}\gamma ώ}^{{\rm T}}{\rm X}$ σύμβολα.Ένας όρος τακτοποίησης εισάγεται επίσης στον τύπο$\frac{\lambda }{2}\Vert {\rm X}{\Vert }_2^2$ για να αποφευχθεί η υπερβολική προσαρμογή των δεδομένων, όπου$\Vert {\rm X}{\Vert }_2^2$ εξπρές${\rm X}$ Το τετράγωνο της Ευκλείδειας νόρμας του .

Στα περισσότερα εποπτευόμενα μοντέλα μάθησης, η διαδικασία εκπαίδευσης μπορεί να εκφραστεί ως μορφή (2), συμπεριλαμβανομένων των κανονικοποιημένων ελαχίστων τετραγώνων L1, της μηχανής διανυσμάτων υποστήριξης (SVM), της ανάλυσης κύριων συστατικών, των τυχαίων πεδίων υπό όρους και των βαθιών νευρωνικών δικτύων κ.λπ.

Μια βασική πρόκληση στις σύγχρονες περιπτώσεις προβλημάτων είναι ο αριθμός των σημείων δεδομένων $n$ Πιθανώς εξαιρετικά μεγάλο. Συχνά ασχολούμαστε με σύνολα δεδομένων που ξεπερνούν κατά πολύ το εύρος των terabyte και μπορούν να προέρχονται από διαφορετικές πηγές όπως το Διαδίκτυο, οι δορυφόροι, οι απομακρυσμένοι αισθητήρες, οι χρηματοοικονομικές αγορές και τα επιστημονικά πειράματα. Για να αντιμετωπίσουμε τόσο μεγάλα σύνολα δεδομένων, μια κοινή προσέγγιση είναι η χρήση του αλγόριθμου στοχαστικής διαβάθμισης (SGD), ο οποίος χρησιμοποιεί μόνο έναν μικρό αριθμό τυχαία επιλεγμένων σημείων δεδομένων σε κάθε επανάληψη. Επιπλέον, υπήρξε μια απότομη αύξηση πρόσφατα στο ενδιαφέρον για τις μεθόδους στοχαστικής κλίσης μείωσης διακύμανσης (VR), οι οποίες έχουν ταχύτερους ρυθμούς σύγκλισης από τις παραδοσιακές μεθόδους στοχαστικής κλίσης.

Σχήμα 1. Σχετικά με το πρόβλημα λογιστικής παλινδρόμησης που βασίζεται στο σύνολο δεδομένων των μανιταριών [7], η μέθοδος gradient descent (GD), accelerated gradient descent (AGD, accelerated GD in [50]), στοχαστική κλίση κάθοδος (SGD) και ADAM [30] σε σύγκριση με τις μεθόδους μείωσης διακύμανσης (VR) SAG και SVRG, όπου n = 8124, d = 112.

1.1 Μέθοδοι κλίσης και στοχαστικής κλίσης

Το Gradient descent (GD) είναι ένας κλασικός αλγόριθμος που χρησιμοποιείται για την επίλυση του παραπάνω προβλήματος (2) και ο επαναληπτικός τύπος ενημέρωσης είναι ο ακόλουθος:
$${{\rm X}}_{\kappa +1}={{\rm X}}_{\kappa }-\gamma \frac{1}{n}\sum _{{\rm E}\gamma ώ=1}^n\nabla {\phi ά}_{{\rm E}\gamma ώ}({{\rm X}}_{\kappa })$$

εδώ,$\gamma$ είναι μια σταθερή τιμή βήματος μεγαλύτερη από το μηδέν.Κατά τη διάρκεια κάθε επανάληψης του αλγορίθμου GD, κάθε σημείο δεδομένων πρέπει να είναι${\rm E}\gamma ώ$ Υπολογίστε την κλίση$\nabla {\phi ά}_{{\rm E}\gamma ώ}({{\rm X}}_{\kappa })$, που σημαίνει ότι το GD απαιτεί όλα $n$ εκτελέστε μια πλήρη διέλευση σημείων δεδομένων.Όταν το μέγεθος του συνόλου δεδομένων$n$ Όταν γίνεται πολύ μεγάλο, το κόστος κάθε επανάληψης του αλγορίθμου GD γίνεται πολύ υψηλό, περιορίζοντας έτσι την εφαρμογή του.

Ως εναλλακτική, μπορούμε να εξετάσουμε τη μέθοδο στοχαστικής κλίσης κατάβασης (SGD), η οποία προτάθηκε για πρώτη φορά από τους Robbins και Monro και ο επαναληπτικός τύπος ενημέρωσης είναι ο ακόλουθος:
$${{\rm X}}_{\kappa +1}={{\rm X}}_{\kappa }-\gamma \nabla {\phi ά}_{{{\rm E}\gamma ώ}_{\kappa }}({{\rm X}}_{\kappa })$$

Ο αλγόριθμος SGD λειτουργεί χρησιμοποιώντας μόνο τη διαβάθμιση ενός τυχαία επιλεγμένου σημείου δεδομένων σε κάθε επανάληψη. $\nabla {\phi ά}_{{{\rm E}\gamma ώ}_{\kappa }}({{\rm X}}_{\kappa })$ για να μειώσετε το κόστος κάθε επανάληψης. Στο Σχήμα 1, μπορούμε να δούμε ότι το SGD επιτυγχάνει πιο σημαντική πρόοδο από το GD (συμπεριλαμβανομένων των μεθόδων επιταχυνόμενης GD) στα αρχικά στάδια της διαδικασίας βελτιστοποίησης.Το γράφημα δείχνει την πρόοδο της βελτιστοποίησης ως προς τις εποχές, οι οποίες ορίζονται ως ο υπολογισμός όλων$n$ Ο αριθμός των κλίσεων για τα δείγματα εκπαίδευσης. Ο αλγόριθμος GD εκτελεί μία επανάληψη σε κάθε γύρο, ενώ ο αλγόριθμος SGD εκτελεί μία επανάληψη σε κάθε γύρο$n$ επαναλήψεις.Χρησιμοποιούμε γύρους ως βάση για τη σύγκριση των SGD και GD, επειδή υπό την υπόθεση$n$ Σε πολύ μεγάλες περιπτώσεις, το κύριο κόστος και των δύο μεθόδων συγκεντρώνεται στην κλίση$\nabla {\phi ά}_{{\rm E}\gamma ώ}({{\rm X}}_{\kappa })$ υπολογισμός.

1.2 Πρόβλημα διακύμανσης

Ας εξετάσουμε την τυχαία ευρετηρίαση ${{\rm E}\gamma ώ}_{\kappa }$ από τη συλλογή { 1 , … , n } {1, ldots, n}{1,…,n} Στην περίπτωση της ομοιόμορφης τυχαίας επιλογής, αυτό σημαίνει ότι για όλους${\rm E}\gamma ώ$,επιλέγω ${{\rm E}\gamma ώ}_{\kappa }={\rm E}\gamma ώ$ Η πιθανότητα$\Pi [{{\rm E}\gamma ώ}_{\kappa }={\rm E}\gamma ώ]$ ίσος$\frac{1}{n}$ . σε αυτήν την περίπτωση,$\nabla {\phi ά}_{{{\rm E}\gamma ώ}_{\kappa }}({{\rm X}}_{\kappa })$ όπως και$\nabla \phi ά({{\rm X}}_{\kappa })$ Ο εκτιμητής είναι αμερόληπτος επειδή, με τον ορισμό της προσδοκίας, έχουμε:
$$\mu \iota [\nabla {\phi ά}_{{{\rm E}\gamma ώ}_{\kappa }}({{\rm X}}_{\kappa })|{{\rm X}}_{\kappa }]=\frac{1}{n}\sum _{{\rm E}\gamma ώ=1}^n\nabla {\phi ά}_{{\rm E}\gamma ώ}({{\rm X}}_{\kappa })=\nabla \phi ά({{\rm X}}_{\kappa })(6)$$

Αν και η μέθοδος SGD (Stochastic Gradient Descent) δεν εγγυάται τη συνάρτηση σε κάθε επανάληψη $\phi ά$ Η τιμή του θα μειώνεται, αλλά κατά μέσο όρο κινείται προς την αρνητική πλήρη κλίση, η οποία αντιπροσωπεύει την καθοδική κατεύθυνση.

Ωστόσο, η ύπαρξη ενός αμερόληπτου εκτιμητή κλίσης δεν αρκεί για να διασφαλιστεί η σύγκλιση των επαναλήψεων SGD. Για να επεξηγήσει αυτό το σημείο, το σχήμα 2 (αριστερά) δείχνει την επαναληπτική τροχιά του SGD κατά την εφαρμογή μιας συνάρτησης λογιστικής παλινδρόμησης χρησιμοποιώντας ένα σταθερό μέγεθος βήματος στο σύνολο δεδομένων τεσσάρων κατηγοριών που παρέχεται από το LIBSVM [7].Οι ομόκεντρες ελλείψεις στο σχήμα αντιπροσωπεύουν τα περιγράμματα της συνάρτησης, δηλαδή την τιμή της συνάρτησης$\phi ά({\rm X})=\nu \tau o$ αντίστοιχο σημείο${\rm X}$ μαζεύω,$\nu \tau o$ είναι μια συγκεκριμένη σταθερά στο σύνολο των πραγματικών αριθμών.διαφορετικές σταθερές τιμές$\nu \tau o$ Αντιστοιχεί σε διαφορετικές ελλείψεις.

Η επαναληπτική τροχιά του SGD δεν συγκλίνει στη βέλτιστη λύση (που υποδεικνύεται από έναν πράσινο αστερίσκο στο σχήμα), αλλά σχηματίζει ένα σύννεφο σημείου γύρω από τη βέλτιστη λύση. Αντίθετα, δείχνουμε στο σχήμα 2 την επαναληπτική τροχιά μιας μεθόδου μείωσης διακύμανσης (VR), στοχαστική μέση κλίση (SAG), χρησιμοποιώντας το ίδιο σταθερό μέγεθος βήματος, το οποίο θα παρουσιάσουμε αργότερα. Ο λόγος που το SGD αποτυγχάνει να συγκλίνει σε αυτό το παράδειγμα είναι ότι η ίδια η στοχαστική κλίση δεν συγκλίνει στο μηδέν, και επομένως, η μέθοδος SGD σταθερού βήματος (5) δεν σταματά ποτέ.Αυτό έρχεται σε έντονη αντίθεση με τις μεθόδους gradient descent (GD), οι οποίες φυσικά σταματούν ως${{\rm X}}_{\kappa }$ Προσεγγίσεις${{\rm X}}^{\ast }$,βαθμίδα $\nabla \phi ά({{\rm X}}_{\kappa })$ θα τείνει στο μηδέν.

Σχήμα 2. Διαγράμματα συνόλου επιπέδων για δισδιάστατη λογιστική παλινδρόμηση χρησιμοποιώντας επαναληπτικές μεθόδους SGD σταθερού βήματος (αριστερά) και SAG (δεξιά). Ο πράσινος αστερίσκος δείχνει xλύνω.

1.3 Κλασική μέθοδος μείωσης διασποράς

επεξεργασία λόγω $\nabla {\phi ά}_{{\rm E}\gamma ώ}({{\rm X}}_{\kappa })$ Υπάρχουν αρκετές κλασικές τεχνικές για προβλήματα μη σύγκλισης που προκαλούνται από τη διακύμανση των τιμών.Για παράδειγμα, οι Robbins και Monro [64] χρησιμοποιούν μια σειρά από φθίνοντα βήματα${\gamma }_{\kappa }$ για την επίλυση του προβλήματος της διακύμανσης, διασφαλίζοντας ότι το προϊόν${\gamma }_{\kappa }\nabla {\phi ά}_{{{\rm E}\gamma ώ}_{\kappa }}({{\rm X}}_{\kappa })$ μπορεί να συγκλίνει στο μηδέν. Ωστόσο, η προσαρμογή αυτής της ακολουθίας βημάτων μείωσης για να αποφευχθεί η διακοπή του αλγορίθμου πολύ νωρίς ή πολύ αργά είναι ένα δύσκολο πρόβλημα.

Μια άλλη κλασική τεχνική για τη μείωση της διακύμανσης είναι η χρήση πολλαπλών $\nabla {\phi ά}_{{\rm E}\gamma ώ}({{\rm X}}_{\kappa })$ μέσο όρο για να αποκτήσετε την πλήρη κλίση$\nabla \phi ά({\rm X})$ ακριβέστερη εκτίμηση. Αυτή η προσέγγιση ονομάζεται minibatch και είναι ιδιαίτερα χρήσιμη όταν πολλαπλές κλίσεις μπορούν να αξιολογηθούν παράλληλα. Αυτό έχει ως αποτέλεσμα μια επανάληψη της φόρμας:
$${{\rm X}}_{\kappa +1}={{\rm X}}_{\kappa }-\gamma \frac{1}{|{\sigma \iota }_{\kappa }|}\sum _{{\rm E}\gamma ώ\in {\sigma \iota }_{\kappa }}\nabla {\phi ά}_{{\rm E}\gamma ώ}({{\rm X}}_{\kappa })(7)$$
σε${\sigma \iota }_{\kappa }$ είναι ένα τυχαίο σύνολο δεικτών,$|{\sigma \iota }_{\kappa }|$ εξπρές${\sigma \iota }_{\kappa }$ το μέγεθος του.αν${\sigma \iota }_{\kappa }$ Ομοιόμορφη δειγματοληψία με αντικατάσταση, τότε η διακύμανση αυτής της εκτίμησης κλίσης σχετίζεται με το "μέγεθος παρτίδας"$|{\sigma \iota }_{\kappa }|$ είναι αντιστρόφως ανάλογη, επομένως η διακύμανση μπορεί να μειωθεί αυξάνοντας το μέγεθος της παρτίδας.

Ωστόσο, το κόστος τέτοιων επαναλήψεων είναι ανάλογο με το μέγεθος της παρτίδας, επομένως αυτή η μορφή μείωσης της διακύμανσης έχει κόστος αυξημένου υπολογιστικού κόστους.

Μια άλλη κοινή στρατηγική για τη μείωση της διακύμανσης και τη βελτίωση της εμπειρικής απόδοσης του SGD είναι η προσθήκη "ορμής", ένας επιπλέον όρος που βασίζεται στην κατεύθυνση που χρησιμοποιήθηκε σε προηγούμενα βήματα. Ειδικότερα, η μορφή του SGD με ορμή έχει ως εξής:
$${{\rm X}}_{\kappa +1}={{\rm X}}_{\kappa }-\gamma {{\rm M}}_{\kappa }(9)$$
όπου η παράμετρος ορμής$\beta$ Βρίσκεται στην περιοχή (0, 1).Αν η αρχική ορμή${{\rm M}}_0=0$, και επέκταση σε (8) ${{\rm M}}_{\kappa }$ Για ενημερώσεις, λαμβάνουμε${{\rm M}}_{\kappa }$ είναι ο σταθμισμένος μέσος όρος των προηγούμενων κλίσεων:
$${{\rm M}}_{\kappa }=\sum _{t=0}^{\kappa }{\beta }^{\kappa -t}\nabla {\phi ά}_{{{\rm E}\gamma ώ}_t}({{\rm X}}_t)(10)$$
επομένως,${{\rm M}}_{\kappa }$ είναι το σταθμισμένο άθροισμα των στοχαστικών κλίσεων.επειδή${\sum }_{t=0}^{\kappa }{\beta }^{\kappa -t}=\frac{1-{\beta }^{\kappa +1}}{1-\beta }$, μπορούμε να μετατρέψουμε $\frac{1-\beta }{1-{\beta }^{\kappa }}{{\rm M}}_{\kappa }$ Θεωρείται ως σταθμικός μέσος όρος στοχαστικών κλίσεων.Αν το συγκρίνουμε με την έκφραση για την πλήρη κλίση$\nabla \phi ά({{\rm X}}_{\kappa })=\frac{1}{n}{\sum }_{{\rm E}\gamma ώ=1}^n\nabla {\phi ά}_{{\rm E}\gamma ώ}({{\rm X}}_{\kappa })$ Για να συγκρίνουμε, μπορούμε$\frac{1-\beta }{1-{\beta }^{\kappa }}{{\rm M}}_{\kappa }$(καθώς ${{\rm M}}_{\kappa }$ ) ερμηνεύεται ως εκτίμηση της πλήρους κλίσης. Αν και αυτό το σταθμισμένο άθροισμα μειώνει τη διακύμανση, εγείρει επίσης βασικά ζητήματα.Εφόσον το σταθμισμένο άθροισμα (10) δίνει μεγαλύτερη βαρύτητα στις πρόσφατες κλίσεις του δείγματος, δεν θα συγκλίνει στην πλήρη κλίση$\nabla \phi ά({{\rm X}}_{\kappa })$ , το τελευταίο είναι ένας απλός μέσος όρος. Η πρώτη μέθοδος μείωσης της διακύμανσης που θα δούμε στην Ενότητα ΙΙ-Α λύνει αυτό το πρόβλημα χρησιμοποιώντας έναν απλό μέσο όρο αντί για οποιοδήποτε σταθμισμένο μέσο όρο.

1.4 Σύγχρονες μέθοδοι μείωσης διασποράς

Σε αντίθεση με τις κλασικές μεθόδους, χρησιμοποιούν απευθείας μία ή περισσότερες $\nabla {\phi ά}_{{\rm E}\gamma ώ}({{\rm X}}_{\kappa })$ όπως και$\nabla \phi ά({{\rm X}}_{\kappa })$ Κατά προσέγγιση, οι σύγχρονες μέθοδοι μείωσης διασποράς (VR) χρησιμοποιούν διαφορετική στρατηγική.Αυτές οι μέθοδοι χρησιμοποιούν$\nabla {\phi ά}_{{\rm E}\gamma ώ}({{\rm X}}_{\kappa })$ για να ενημερώσετε την εκτίμηση κλίσης${\sigma o\lambda }_{\kappa }$, στόχος του οποίου είναι να κάνει ${\sigma o\lambda }_{\kappa }$ πλησιάζοντας$\nabla \phi ά({{\rm X}}_{\kappa })$ .Συγκεκριμένα ελπίζουμε${\sigma o\lambda }_{\kappa }$ ικανός να ικανοποιήσει${\sigma o\lambda }_{\kappa }\approx \nabla \phi ά({{\rm X}}_{\kappa })$ . Με βάση τέτοιες εκτιμήσεις κλίσης, εκτελούμε στη συνέχεια ένα κατά προσέγγιση βήμα κλίσης της φόρμας:
$${{\rm X}}_{\kappa +1}={{\rm X}}_{\kappa }-\gamma {\sigma o\lambda }_{\kappa }(11)$$
εδώ$\gamma >0$ είναι η παράμετρος μεγέθους βήματος.

Για να διασφαλιστεί ότι χρησιμοποιείται σταθερό μέγεθος βήματος $\gamma$ Όταν η επανάληψη (11) μπορεί να συγκλίνει, πρέπει να διασφαλίσουμε ότι η εκτίμηση της κλίσης${\sigma o\lambda }_{\kappa }$ Η διακύμανση τείνει στο μηδέν. Μαθηματικά, αυτό μπορεί να εκφραστεί ως:
$$\mu \iota \left[\Vert {\sigma o\lambda }_{\kappa }-\nabla \phi ά({{\rm X}}_{\kappa }){\Vert }^2\right]\to 0\text{όπως και}\kappa \to \infty (12)$$
προσδοκίες εδώ$\mu \iota$ βασίζεται στον αλγόριθμο μέχρι το$\kappa$ Όλες οι τυχαίες μεταβλητές υπολογίζονται για επαναλήψεις. Η ιδιότητα (12) διασφαλίζει ότι η μέθοδος VR ​​μπορεί να σταματήσει όταν επιτευχθεί η βέλτιστη λύση. Θεωρούμε αυτή την ιδιότητα ως χαρακτηριστικό γνώρισμα της προσέγγισης VR και επομένως την αποκαλούμε ιδιότητα VR. Αξίζει να σημειωθεί ότι η έκφραση «μειωμένη» διακύμανση μπορεί να είναι παραπλανητική, γιατί στην πραγματικότητα η διακύμανση τείνει στο μηδέν. Η ιδιότητα (12) είναι ένας βασικός παράγοντας που επιτρέπει στις μεθόδους VR να επιτύχουν ταχύτερη σύγκλιση στη θεωρία (υπό κατάλληλες υποθέσεις) και στην πράξη (όπως φαίνεται στο Σχήμα 1).

1.5 Πρώτο παράδειγμα μεθόδου μείωσης διακύμανσης: SGD²

Μια απλή μέθοδος βελτίωσης μπορεί να κάνει τον αναδρομικό τύπο SGD (5) να επιτύχει σύγκλιση χωρίς να μειώσει το μέγεθος του βήματος, δηλαδή να μεταφράσει κάθε κλίση Η συγκεκριμένη μέθοδος είναι η αφαίρεση $\nabla {\phi ά}_{{\rm E}\gamma ώ}({{\rm X}}^{\ast })$, αυτή η μέθοδος ορίζεται ως εξής:
$${{\rm X}}_{\kappa +1}={{\rm X}}_{\kappa }-\gamma (\nabla {\phi ά}_{{{\rm E}\gamma ώ}_{\kappa }}({{\rm X}}_{\kappa })-\nabla {\phi ά}_{{{\rm E}\gamma ώ}_{\kappa }}({{\rm X}}^{\ast }))(13)$$
Αυτή η μέθοδος ονομάζεται SGD² [22].Αν και συνήθως δεν μπορούμε να γνωρίζουμε με βεβαιότητα κάθε$\nabla {\phi ά}_{{\rm E}\gamma ώ}({{\rm X}}^{\ast })$ , αλλά το SGD², για παράδειγμα, μπορεί να επεξηγήσει καλά τα βασικά χαρακτηριστικά της μεθόδου μείωσης της διακύμανσης.Επιπλέον, πολλές μέθοδοι μείωσης της διακύμανσης μπορούν να θεωρηθούν ως μια κατά προσέγγιση μορφή της μεθόδου SGD² αυτές οι μέθοδοι δεν βασίζονται στα γνωστά$\nabla {\phi ά}_{{\rm E}\gamma ώ}({{\rm X}}^{\ast })$, αλλά αντίθετα χρησιμοποιήστε μια μέθοδο που μπορεί να γίνει κατά προσέγγιση $\nabla {\phi ά}_{{\rm E}\gamma ώ}({{\rm X}}^{\ast })$ εκτιμώμενη αξία.

Αξίζει να σημειωθεί ότι το SGD² χρησιμοποιεί μια αμερόληπτη εκτίμηση της πλήρους κλίσης.επειδή$\nabla \phi ά({{\rm X}}^{\ast })=0$,ΦΑ:
$$\mu \iota [\nabla {\phi ά}_{{{\rm E}\gamma ώ}_{\kappa }}({{\rm X}}_{\kappa })-\nabla {\phi ά}_{{{\rm E}\gamma ώ}_{\kappa }}({{\rm X}}^{\ast })]=\nabla \phi ά({{\rm X}}_{\kappa })-\nabla \phi ά({{\rm X}}^{\ast })=\nabla \phi ά({{\rm X}}_{\kappa })$$
Επιπλέον, όταν το SGD² φτάσει στη βέλτιστη λύση, φυσικά θα σταματήσει γιατί για οποιαδήποτε${\rm E}\gamma ώ$,έχω:
$$(\nabla {\phi ά}_{{\rm E}\gamma ώ}({\rm X})-\nabla {\phi ά}_{{\rm E}\gamma ώ}({{\rm X}}^{\ast })){|}_{{\rm X}={{\rm X}}^{\ast }}=0$$

Κατόπιν περαιτέρω παρατήρησης, με ${{\rm X}}_{\kappa }$ κοντά${{\rm X}}^{\ast }$(για συνεχόμενα $\nabla {\phi ά}_{{\rm E}\gamma ώ}$), το SGD² ικανοποιεί την ιδιότητα μείωσης διασποράς (12) επειδή:
$$\begin{gathered} \mu \iota \left[\Vert {\sigma o\lambda }_{\kappa }-\nabla \phi ά({{\rm X}}_{\kappa }){\Vert }^2\right]= \\ \mu \iota \left[\Vert \nabla {\phi ά}_{{{\rm E}\gamma ώ}_{\kappa }}({{\rm X}}_{\kappa })-\nabla {\phi ά}_{{{\rm E}\gamma ώ}_{\kappa }}({{\rm X}}^{\ast })-\nabla \phi ά({{\rm X}}_{\kappa }){\Vert }^2\right]\le \mu \iota \left[\Vert \nabla {\phi ά}_{{{\rm E}\gamma ώ}_{\kappa }}({{\rm X}}_{\kappa })-\nabla {\phi ά}_{{{\rm E}\gamma ώ}_{\kappa }}({{\rm X}}^{\ast }){\Vert }^2\right] \end{gathered}$$
Εδώ χρησιμοποιούμε Lemma 2, let${\rm X}=\nabla {\phi ά}_{{{\rm E}\gamma ώ}_{\kappa }}({{\rm X}}_{\kappa })-\nabla {\phi ά}_{{{\rm E}\gamma ώ}_{\kappa }}({{\rm X}}^{\ast })$, και εκμεταλλεύτηκε $\mu \iota [\nabla {\phi ά}_{{{\rm E}\gamma ώ}_{\kappa }}({{\rm X}}_{\kappa })-\nabla {\phi ά}_{{{\rm E}\gamma ώ}_{\kappa }}({{\rm X}}^{\ast })]=\nabla \phi ά({{\rm X}}_{\kappa })$ φύση. Αυτή η ιδιότητα υποδεικνύει ότι το SGD² έχει μεγαλύτερη ταχύτητα σύγκλισης από τις παραδοσιακές μεθόδους SGD, τις οποίες έχουμε αναλυτικά στο Παράρτημα Β.

1.6 Μέθοδος ταχείας σύγκλισης της μείωσης της διακύμανσης

Σε αυτήν την ενότητα θα εισαγάγουμε δύο τυπικές παραδοχές που χρησιμοποιούνται για την ανάλυση της μεθόδου μείωσης της διακύμανσης (VR) και θα συζητήσουμε το αποτέλεσμα επιτάχυνσης που μπορεί να επιτευχθεί με αυτές τις παραδοχές σε σύγκριση με την παραδοσιακή μέθοδο SGD. Πρώτον, υποθέτουμε ότι η κλίση έχει συνέχεια Lipschitz, που σημαίνει ότι ο ρυθμός μεταβολής της κλίσης είναι πεπερασμένος.

Υπόθεση 1 (Συνέχεια Lipschitz)

Υποθέτουμε ότι η συνάρτηση $\phi ά$είναι διαφοροποιήσιμο και είναι $\mu \epsilon \gamma ά\lambda o$- ομαλή, για όλους ${\rm X}$ και$y$ και κάποιος$0<\mu \epsilon \gamma ά\lambda o<\infty$,Οι παρακάτω προϋποθέσεις:
$$\Vert \nabla \phi ά({\rm X})-\nabla \phi ά(y)\Vert \le \mu \epsilon \gamma ά\lambda o\Vert {\rm X}-y\Vert (14)$$
Αυτό σημαίνει ότι κάθε$\phi ά{\rm E}\gamma ώ:{\mathbb{R}}^{\rho \epsilon }\to \mathbb{R}$ είναι διαφοροποιήσιμο,${\mu \epsilon \gamma ά\lambda o}_{{\rm E}\gamma ώ}$- ομαλή, ορίζουμε ${\mu \epsilon \gamma ά\lambda o}_{\text{Μέγιστη}}$ Για max ⁡ { L 1 , . . . , L n } μέγ.{L_1, . . . , L_n}Μέγιστη{μεγάλο1​,...,μεγάλοn​}。

Αν και αυτό θεωρείται γενικά μια αδύναμη υπόθεση, στα επόμενα κεφάλαια θα συζητήσουμε μεθόδους VR που είναι κατάλληλες για μη ομαλά προβλήματα. Για μια διπλά διαφοροποιήσιμη μονομεταβλητή συνάρτηση,$\mu \epsilon \gamma ά\lambda o$-Η ομαλότητα μπορεί να κατανοηθεί διαισθητικά ως: ισοδυναμεί με την υπόθεση ότι η δεύτερη παράγωγος είναι $\mu \epsilon \gamma ά\lambda o$ ανώτατο όριο, δηλαδή$|{\phi ά}^{\prime \prime }({\rm X})|\le \mu \epsilon \gamma ά\lambda o$ για όλα${\rm X}\in {\mathbb{R}}^{\rho \epsilon }$ .Για δύο διαφοροποιήσιμες συναρτήσεις πολλαπλών μεταβλητών, είναι ισοδύναμο με την υπόθεση Hessian matrix${\nabla }^2\phi ά({\rm X})$ Η μοναδική τιμή του$\mu \epsilon \gamma ά\lambda o$ ανώτατο όριο.

Υπόθεση 2 (ισχυρή κυρτότητα)

Η δεύτερη υπόθεση που θεωρούμε είναι ότι η συνάρτηση (f) είναι $\mu$-Έντονα κυρτό, που σημαίνει ότι για ένα ορισμένο $\mu >0$,λειτουργία ${\rm X}\mapsto \phi ά({\rm X})-\frac{\mu }{2}\Vert {\rm X}{\Vert }^2$ Είναι κυρτό.Επιπλέον, για κάθε${\rm E}\gamma ώ=1,...,n$，$\phi ά{\rm E}\gamma ώ:{\mathbb{R}}^{\rho \epsilon }\to \mathbb{R}$ Είναι κυρτό.

Αυτή είναι μια ισχυρή υπόθεση.Στο πρόβλημα των ελαχίστων τετραγώνων, το καθένα (fi$ είναι κυρτό, αλλά η συνολική συνάρτηση (f) βρίσκεται μόνο στον πίνακα σχεδίασης${\rm E}{\rm N}{\rm A}:=[{έ\nu \alpha }_1,...,{έ\nu \alpha }_n]$ Είναι έντονα κυρτό μόνο αν έχει πλήρη σειρά σειράς. Το πρόβλημα κανονικοποιημένης λογιστικής παλινδρόμησης L2 ικανοποιεί αυτήν την υπόθεση λόγω της ύπαρξης του όρου κανονικοποίησης, όπου$\mu \ge \lambda$。

Μια σημαντική κατηγορία προβλημάτων που ικανοποιούν αυτές τις παραδοχές είναι τα προβλήματα βελτιστοποίησης της μορφής:
$${{\rm X}}^{\ast }\in \mathrm{\alpha \rho \sigma o\lambda }\underset{{\rm X}\in {\mathbb{R}}^{\rho \epsilon }}{\mathrm{\epsilon \lambda ά\chi }}\phi ά({\rm X})=\frac{1}{n}\sum _{{\rm E}\gamma ώ=1}^n{\ell }_{{\rm E}\gamma ώ}({έ\nu \alpha }_{{\rm E}\gamma ώ}^{{\rm T}}{\rm X})+\frac{\lambda }{2}\Vert {\rm X}{\Vert }^2(15)$$
όπου κάθε συνάρτηση «απώλειας».${\ell }_{{\rm E}\gamma ώ}:\mathbb{R}\to \mathbb{R}$ είναι δύο φορές διαφοροποιήσιμο και η δεύτερη παράγωγός του${\ell }_{{\rm E}\gamma ώ}^{\prime \prime }$ περιορίζεται στο 0 και σε κάποιο άνω όριο${\rm M}$ μεταξύ. Αυτό περιλαμβάνει μια ποικιλία συναρτήσεων απώλειας με κανονικοποίηση L2 στη μηχανική μάθηση, όπως τα ελάχιστα τετράγωνα, η λογιστική παλινδρόμηση, η παλινδρόμηση probit, η ισχυρή παλινδρόμηση Huber κ.λπ.Σε αυτή την περίπτωση, για όλους${\rm E}\gamma ώ$,Εχουμε ${\mu \epsilon \gamma ά\lambda o}_{{\rm E}\gamma ώ}\le {\rm M}\Vert {έ\nu \alpha }_{{\rm E}\gamma ώ}{\Vert }^2+\lambda$ και$\mu \ge \lambda$。

Σύμφωνα με αυτές τις παραδοχές, ο ρυθμός σύγκλισης της μεθόδου gradient descent (GD) καθορίζεται από τον αριθμό συνθήκης $\kappa :=\mu \epsilon \gamma ά\lambda o/\mu$ Αποφασίζω. Ο αριθμός συνθήκης είναι πάντα μεγαλύτερος ή ίσος με 1 και όταν είναι σημαντικά μεγαλύτερος από 1, τα περιγράμματα της συνάρτησης γίνονται πολύ ελλειπτικά, προκαλώντας την ταλάντωση των επαναλήψεων της μεθόδου GD.Αντίθετα, όταν$\kappa$ Όταν είναι κοντά στο 1, η μέθοδος GD συγκλίνει πιο γρήγορα.

Στις παραδοχές 1 και 2, η μέθοδος VR ​​συγκλίνει με γραμμικό ρυθμό.Λέμε ότι η τιμή της συνάρτησης μιας τυχαίας μεθόδου ({f(x_k)}) δίνεται από$0<\rho \le 1$ Ο ρυθμός γραμμικής σύγκλισης (υπό προσδοκία), εάν υπάρχει σταθερά$\nu \tau o>0$ Κάνει:
$$\mu \iota [\phi ά({{\rm X}}_{\kappa })]-\phi ά({{\rm X}}^{\ast })\le (1-\rho {)}^{\kappa }\nu \tau o={\rm O}(\exp (-\kappa \rho ))\forall \kappa (16)$$
Αυτό έρχεται σε αντίθεση με τις κλασσικές μεθόδους SGD που βασίζονται μόνο σε αμερόληπτες εκτιμήσεις της κλίσης σε κάθε επανάληψη, οι οποίες λαμβάνουν μόνο υπογραμμικούς ρυθμούς υπό αυτές τις παραδοχές:
$$\mu \iota [\phi ά({{\rm X}}_{\kappa })]-\phi ά({{\rm X}}^{\ast })\le {\rm O}(1/\kappa )$$
Το ελάχιστο που ικανοποιεί αυτή την ανισότητα$\kappa$ Ονομάζεται επαναληπτική πολυπλοκότητα του αλγορίθμου. Τα ακόλουθα είναι η επαναληπτική πολυπλοκότητα και το κόστος μιας επανάληψης για βασικές παραλλαγές των μεθόδων GD, SGD και VR:

Ο συνολικός χρόνος εκτέλεσης ενός αλγορίθμου καθορίζεται από το γινόμενο της πολυπλοκότητας της επανάληψης και του χρόνου εκτέλεσης της επανάληψης.χρησιμοποιείται εδώ${\kappa }_{\text{Μέγιστη}}:={\mathrm{{\rm M}έ\gamma \iota \sigma \tau \eta }}_{{\rm E}\gamma ώ}{\mu \epsilon \gamma ά\lambda o}_{{\rm E}\gamma ώ}/\mu$ .Ειδοποίηση${\kappa }_{\text{Μέγιστη}}\ge \kappa$Επομένως, η πολυπλοκότητα της επανάληψης της GD είναι μικρότερη από αυτή της μεθόδου VR.

Ωστόσο, δεδομένου ότι το κόστος ανά επανάληψη του GD είναι αυτό της μεθόδου VR $n$ φορές, η μέθοδος VR ​​είναι ανώτερη όσον αφορά τον συνολικό χρόνο λειτουργίας.

Το πλεονέκτημα των κλασικών μεθόδων SGD είναι ότι ο χρόνος λειτουργίας τους και ο ρυθμός σύγκλισης δεν εξαρτώνται από $n$, αλλά έχει μια ανοχή $ϵ$ Η εξάρτηση του είναι πολύ χειρότερη, γεγονός που εξηγεί την κακή απόδοση του SGD όταν η ανοχή είναι μικρή.

Στο Παράρτημα Β, παρέχουμε μια απλή απόδειξη που δείχνει ότι η μέθοδος SGD² έχει την ίδια επαναληπτική πολυπλοκότητα με τη μέθοδο VR.

2. Μέθοδος μείωσης βασικής διακύμανσης

Η ανάπτυξη μεθόδων μείωσης διακύμανσης (VR) έχει περάσει από διάφορα στάδια και η αρχική παρτίδα μεθόδων είχε ως αποτέλεσμα σημαντικά βελτιωμένα ποσοστά σύγκλισης. Η αρχή αυτής της σειράς μεθόδων είναι ο αλγόριθμος SAG. Στη συνέχεια, ο αλγόριθμος στοχαστικής ανάβασης διπλής συντεταγμένης (SDCA), ο αλγόριθμος MISO, ο αλγόριθμος μείωσης της διακύμανσης στοχαστικής διακύμανσης (SVRG/S2GD) και ο αλγόριθμος SAGA (που σημαίνει "βελτιωμένο" SAG) βγήκαν ο ένας μετά τον άλλο.

Σε αυτό το κεφάλαιο, ρίχνουμε μια πιο προσεκτική ματιά σε αυτές τις πρωτοποριακές μεθόδους VR. Στο Κεφάλαιο 4, θα διερευνήσουμε μερικές νεότερες μεθόδους που παρουσιάζουν ανώτερα χαρακτηριστικά σε σύγκριση με αυτές τις βασικές μεθόδους σε συγκεκριμένα σενάρια εφαρμογών.

2.1 Μέθοδος στοχαστικής μέσης κλίσης (SAG)

Η εξερεύνηση της μεθόδου μείωσης της πρώτης διακύμανσης (VR) ξεκινά με τη μίμηση της δομής πλήρους κλίσης.Από την πλήρη κλίση$\nabla \phi ά({\rm X})$ ειναι ολα$\nabla {\phi ά}_{{\rm E}\gamma ώ}({\rm X})$ ένας απλός μέσος όρος των κλίσεων, στη συνέχεια η εκτίμησή μας για την πλήρη κλίση${\sigma o\lambda }_{\kappa }$ Θα πρέπει επίσης να είναι ο μέσος όρος αυτών των εκτιμήσεων κλίσης. Αυτή η ιδέα οδήγησε στην πρώτη μας μέθοδο VR: τη μέθοδο στοχαστική μέση κλίση (SAG).

Η μέθοδος SAG [37], [65] είναι μια τυχαιοποιημένη έκδοση της μεθόδου πρώιμης αυξητικής συγκεντρωτικής κλίσης (IAG) [4]. Η βασική ιδέα του SAG είναι αυτή για κάθε σημείο δεδομένων${\rm E}\gamma ώ$ διατηρεί μια εκτίμηση$v_{ik}\approx \nabla {\phi ά}_{{\rm E}\gamma ώ}({{\rm X}}_{\kappa })$ .Στη συνέχεια, χρησιμοποιήστε αυτά$v_{ik}$ Ο μέσος όρος των τιμών χρησιμοποιείται ως εκτίμηση της πλήρους κλίσης, δηλαδή:
$${\overline{\sigma o\lambda }}_{\kappa }=\frac{1}{n}\sum _{\iota =1}^n{v}_{jk}\approx \frac{1}{n}\sum _{\iota =1}^n\nabla {\phi ά}_{\iota }({{\rm X}}_{\kappa })=\nabla \phi ά({{\rm X}}_{\kappa })(18)$$

Σε κάθε επανάληψη του SAG, από το σύνολο { 1 , … , n } {1, ldots, n}{1,…,n} Εξαγωγή ευρετηρίου από${{\rm E}\gamma ώ}_{\kappa }$, και στη συνέχεια ενημερώνεται σύμφωνα με τους ακόλουθους κανόνες $v_{jk}$：
$$v_{jk}^{\kappa +1}=\{\begin{array}{ll}\nabla {\phi ά}_{{{\rm E}\gamma ώ}_{\kappa }}({{\rm X}}_{\kappa }),& \text{αν}\iota ={{\rm E}\gamma ώ}_{\kappa }\\ v_{jk}^{\kappa },& \text{αν}\iota \ne {{\rm E}\gamma ώ}_{\kappa }\end{array}(19)$$
Ανάμεσά τους, το καθένα$v_{0{\rm E}\gamma ώ}$ Μπορεί να αρχικοποιηθεί στο μηδέν ή$\nabla {\phi ά}_{{\rm E}\gamma ώ}({{\rm X}}_0)$ κατά προσέγγιση τιμή.Με τη λύση${{\rm X}}^{\ast }$ προσέγγιση, το καθένα$v_{ik}$ θα συγκλίνει σταδιακά σε$\nabla {\phi ά}_{{\rm E}\gamma ώ}({{\rm X}}^{\ast })$, ικανοποιώντας έτσι την ιδιότητα VR (12).

Για να εφαρμόσουμε αποτελεσματικά το SAG, πρέπει να δώσουμε προσοχή στον υπολογισμό ${\overline{\sigma o\lambda }}_{\kappa }$ για να αποφύγετε κάθε φορά να ξεκινάτε το ποσό από την αρχή$n$ διάνυσμα, γιατί αυτό είναι$n$ Το κόστος είναι μεγάλο όταν είναι μεγάλο.Ευτυχώς, αφού κάθε επανάληψη έχει μόνο μία$v_{ik}$ Οι όροι θα αλλάξουν και δεν χρειάζεται να υπολογίζουμε εκ νέου ολόκληρο το άθροισμα κάθε φορά.Συγκεκριμένα, υποθέστε ότι κατά την επανάληψη$\kappa$ Ευρετήριο εξάγεται από${{\rm E}\gamma ώ}_{\kappa }$, τότε υπάρχει:
$${\overline{\sigma o\lambda }}_{\kappa }=\frac{1}{n}\sum _{\begin{array}{c}\iota =1\\ \iota \ne {{\rm E}\gamma ώ}_{\kappa }\end{array}}^n{v}_{jk}+\frac{1}{n}{v}_{{{\rm E}\gamma ώ}_{\kappa }}^{\kappa }={\overline{\sigma o\lambda }}_{\kappa -1}-\frac{1}{n}{v}_{{{\rm E}\gamma ώ}_{\kappa }}^{\kappa -1}+\frac{1}{n}{v}_{{{\rm E}\gamma ώ}_{\kappa }}^{\kappa }(20)$$

Δεδομένου ότι εκτός από $v_{{{\rm E}\gamma ώ}_{\kappa }}$ τα πάντα εκτός από$v_{jk}$ Οι τιμές παραμένουν όλες οι ίδιες, απλώς αποθηκεύουμε την καθεμία$\iota$ Ένα διάνυσμα που αντιστοιχεί σε$v_{\iota }$ . Ο αλγόριθμος 1 δείχνει τη συγκεκριμένη εφαρμογή της μεθόδου SAG.

Η SAG είναι η πρώτη στοχαστική μέθοδος για την επίτευξη γραμμικής σύγκλισης και η πολυπλοκότητα της επανάληψης είναι ${\rm O}(({\kappa }_{\text{Μέγιστη}}+n)\mathrm{\iota \delta oύ\sigma o\lambda }(1/ϵ))$, χρησιμοποιώντας το μέγεθος βήματος $\gamma ={\rm O}(1/{\mu \epsilon \gamma ά\lambda o}_{\text{Μέγιστη}})$ . Αυτή η γραμμική σύγκλιση μπορεί να παρατηρηθεί στο σχήμα 1.Αξίζει να σημειωθεί ότι λόγω${\mu \epsilon \gamma ά\lambda o}_{\text{Μέγιστη}}$- Ομαλή λειτουργία για οποιοδήποτε ${\mu \epsilon \gamma ά\lambda o}^{\prime }\ge {\mu \epsilon \gamma ά\lambda o}_{\text{Μέγιστη}}$ Πολύ${\mu \epsilon \gamma ά\lambda o}^{\prime }$- Οι ομαλές, μέθοδοι SAG επιτυγχάνουν γραμμικούς ρυθμούς σύγκλισης για αρκετά μικρά μεγέθη βημάτων, σε αντίθεση με τις κλασσικές μεθόδους SGD, οι οποίες επιτυγχάνουν μόνο υπογραμμικούς ρυθμούς με ακολουθίες μειούμενων μεγεθών βημάτων που είναι δύσκολο να προσαρμοστούν στην πράξη.

Εκείνη την εποχή, η γραμμική σύγκλιση του SAG ήταν μια σημαντική πρόοδος επειδή υπολόγιζε μόνο μία στοχαστική κλίση (επεξεργασία ενός μόνο σημείου δεδομένων) σε κάθε επανάληψη. Ωστόσο, η απόδειξη σύγκλισης που παρέχεται από τους Schmidt et al [65] είναι πολύ περίπλοκη και βασίζεται σε βήματα που έχουν επαληθευτεί από υπολογιστή. Ένας βασικός λόγος για τον οποίο το SAG είναι δύσκολο να αναλυθεί είναι αυτός${\sigma o\lambda }_{\kappa }$ είναι μια μεροληπτική εκτίμηση της κλίσης.

Στη συνέχεια, εισάγουμε τη μέθοδο SAGA, μια παραλλαγή της SAG που εκμεταλλεύεται την έννοια των συμμεταβλητών για να δημιουργήσει μια αμερόληπτη παραλλαγή της μεθόδου SAG που έχει παρόμοια απόδοση αλλά είναι πιο εύκολο να αναλυθεί.

---

Αλγόριθμος 1: Μέθοδος SAG

1. Παράμετροι: μέγεθος βήματος $\gamma >0$
2. αρχικοποίηση:${{\rm X}}_0$，$v_{{\rm E}\gamma ώ}=0\in {\mathbb{R}}^{\rho \epsilon }$ Για${\rm E}\gamma ώ=1,\dots ,n$
3. σωστά $\kappa =1,\dots ,{\rm T}-1$ υλοποιώ, εφαρμόζω:
   α. Τυχαία επιλογή ik ∈ { 1 , … , n } i_k σε {1, ldots, n}Εγώκ​∈{1,…,n}
   β. Υπολογίστε${\overline{\sigma o\lambda }}_{\kappa }={\overline{\sigma o\lambda }}_{\kappa -1}-\frac{1}{n}{v}_{{{\rm E}\gamma ώ}_{\kappa }}^{\kappa -1}$
   γ$v_{{{\rm E}\gamma ώ}_{\kappa }}^{\kappa }=\nabla {\phi ά}_{{{\rm E}\gamma ώ}_{\kappa }}({{\rm X}}_{\kappa })$
   δ. Ενημέρωση εκτίμησης κλίσης${\overline{\sigma o\lambda }}_{\kappa }={\overline{\sigma o\lambda }}_{\kappa }+\frac{1}{n}{v}_{{{\rm E}\gamma ώ}_{\kappa }}^{\kappa }$
   ε. Ενημέρωση${{\rm X}}_{\kappa +1}={{\rm X}}_{\kappa }-\gamma {\overline{\sigma o\lambda }}_{\kappa }$
4. Παραγωγή:${{\rm X}}_{{\rm T}}$

2.2.Μέθοδος SAGA

Μια μειωμένη βασική αμερόληπτη εκτίμηση κλίσης $\nabla {\phi ά}_{{{\rm E}\gamma ώ}_{\kappa }}({{\rm X}}_{\kappa })$ Η προσέγγιση της διακύμανσης γίνεται μέσω της χρήσης των λεγόμενων συμμεταβλητών ή μεταβλητών ελέγχου.Για${\rm E}\gamma ώ=1,\dots ,n$,στήνω $v_{{\rm E}\gamma ώ}\in {\mathbb{R}}^{\rho \epsilon }$ είναι ένας φορέας.Χρησιμοποιώντας αυτά τα διανύσματα, μπορούμε να μετατρέψουμε την πλήρη κλίση$\nabla \phi ά({\rm X})$ Ξαναγράφτηκε ως:
$$\nabla \phi ά({\rm X})=\frac{1}{n}\sum _{{\rm E}\gamma ώ=1}^n(\nabla {\phi ά}_{{\rm E}\gamma ώ}({\rm X})-v_{{\rm E}\gamma ώ}+v_{{\rm E}\gamma ώ})=\frac{1}{n}\sum _{{\rm E}\gamma ώ=1}^n\nabla {\phi ά}_{{\rm E}\gamma ώ}({\rm X})-v_{{\rm E}\gamma ώ}+\frac{1}{n}\sum _{\iota =1}^n{v}_{\iota }$$
$$:=\frac{1}{n}\sum _{{\rm E}\gamma ώ=1}^n\nabla {\phi ά}_{{\rm E}\gamma ώ}({\rm X},v)(21)$$
που ορίζει$\nabla {\phi ά}_{{\rm E}\gamma ώ}({\rm X},v):=\nabla {\phi ά}_{{\rm E}\gamma ώ}({\rm X})-v_{{\rm E}\gamma ώ}+\frac{1}{n}{\sum }_{\iota =1}^n{v}_{\iota }$ .Τώρα, μπορούμε τυχαία να κάνουμε δείγμα α$\nabla {\phi ά}_{{\rm E}\gamma ώ}({\rm X},v)$ για την κατασκευή της πλήρους κλίσης$\nabla \phi ά({\rm X})$ Μια αμερόληπτη εκτίμηση του i ∈ { 1 , … , n } i σε {1, ldots, n}Εγώ∈{1,…,n}, μπορείτε να εφαρμόσετε τη μέθοδο SGD και να χρησιμοποιήσετε την εκτίμηση κλίσης:
$${\sigma o\lambda }_{\kappa }=\nabla {\phi ά}_{{{\rm E}\gamma ώ}_{\kappa }}({{\rm X}}_{\kappa },v)=\nabla {\phi ά}_{{{\rm E}\gamma ώ}_{\kappa }}({{\rm X}}_{\kappa })-v_{{{\rm E}\gamma ώ}_{\kappa }}+\frac{1}{n}\sum _{\iota =1}^n{v}_{\iota }(22)$$

για παρατήρηση $v_{{\rm E}\gamma ώ}$ Η διαφορά ζεύγους επιλογής${\sigma o\lambda }_{\kappa }$ επιρροή, μπορούμε${\sigma o\lambda }_{\kappa }=\nabla {\phi ά}_{{{\rm E}\gamma ώ}_{\kappa }}({{\rm X}}_{\kappa },v)$ Αντικατάσταση και χρήση${\mu \iota }_{{\rm E}\gamma ώ}\sim \frac{1}{n}[v_{{\rm E}\gamma ώ}]=\frac{1}{n}{\sum }_{\iota =1}^n{v}_{\iota }$ Για να υπολογίσουμε την προσδοκία, παίρνουμε:
$$\mu \iota \left[\Vert \nabla {\phi ά}_{{\rm E}\gamma ώ}({{\rm X}}_{\kappa })-v_{{\rm E}\gamma ώ}+{\mu \iota }_{{\rm E}\gamma ώ}\sim \frac{1}{n}[v_{{\rm E}\gamma ώ}-\nabla {\phi ά}_{{\rm E}\gamma ώ}({{\rm X}}_{\kappa })]{\Vert }^2\right]\le \mu \iota \left[\Vert \nabla {\phi ά}_{{\rm E}\gamma ώ}({{\rm X}}_{\kappa })-v_{{\rm E}\gamma ώ}{\Vert }^2\right](23)$$
Το Lemma 2 χρησιμοποιείται εδώ, όπου${\rm X}=\nabla {\phi ά}_{{\rm E}\gamma ώ}({{\rm X}}_{\kappa })-v_{{\rm E}\gamma ώ}$ .Αυτό το φράγμα (23) δείχνει ότι αν$v_{{\rm E}\gamma ώ}$ μαζί με$\kappa$ Η αύξηση είναι κοντά στο$\nabla {\phi ά}_{{\rm E}\gamma ώ}({{\rm X}}_{\kappa })$ , μπορούμε να αποκτήσουμε χαρακτηριστικά VR (12).Γι' αυτό καλούμε$v_{{\rm E}\gamma ώ}$ είναι συμμεταβλητές και μπορούμε να τις επιλέξουμε για να μειώσουμε τη διακύμανση.

Για παράδειγμα, αυτή η προσέγγιση εφαρμόζεται επίσης με τη μέθοδο SGD² (13), όπου $v_{{\rm E}\gamma ώ}=\nabla {\phi ά}_{{\rm E}\gamma ώ}({{\rm X}}^{\ast })$ .Ωστόσο, αυτό δεν χρησιμοποιείται συνήθως στην πράξη γιατί συνήθως δεν γνωρίζουμε$\nabla {\phi ά}_{{\rm E}\gamma ώ}({{\rm X}}^{\ast })$ .Μια πιο πρακτική επιλογή είναι$v_{{\rm E}\gamma ώ}$ όπως γνωρίζουμε${\overline{{\rm X}}}_{{\rm E}\gamma ώ}\in {\mathbb{R}}^{\rho \epsilon }$ κοντινή κλίση$\nabla {\phi ά}_{{\rm E}\gamma ώ}({\overline{{\rm X}}}_{{\rm E}\gamma ώ})$ . SAGA για κάθε λειτουργία${\phi ά}_{{\rm E}\gamma ώ}$ χρησιμοποιήστε ένα σημείο αναφοράς${\overline{{\rm X}}}_{{\rm E}\gamma ώ}\in {\mathbb{R}}^{\rho \epsilon }$, και χρησιμοποιήστε συμμεταβλητές $v_{{\rm E}\gamma ώ}=\nabla {\phi ά}_{{\rm E}\gamma ώ}({\overline{{\rm X}}}_{{\rm E}\gamma ώ})$, καθένα από τα οποία ${\overline{{\rm X}}}_{{\rm E}\gamma ώ}$ θα είναι η τελευταία μας αξιολόγηση${\phi ά}_{{\rm E}\gamma ώ}$ σημείο. Χρησιμοποιώντας αυτές τις συμμεταβλητές, μπορούμε να κατασκευάσουμε μια εκτίμηση κλίσης, ακολουθώντας την (22), δίνοντας:
$${\sigma o\lambda }_{\kappa }=\nabla {\phi ά}_{{{\rm E}\gamma ώ}_{\kappa }}({{\rm X}}_{\kappa })-\nabla {\phi ά}_{{{\rm E}\gamma ώ}_{\kappa }}({\overline{{\rm X}}}_{{{\rm E}\gamma ώ}_{\kappa }})+\frac{1}{n}\sum _{\iota =1}^n\nabla {\phi ά}_{\iota }({\overline{{\rm X}}}_{\iota })(24)$$

Για να εφαρμόσουμε το SAGA μπορούμε να αποθηκεύσουμε διαβαθμίσεις $\nabla {\phi ά}_{{\rm E}\gamma ώ}({\overline{{\rm X}}}_{{\rm E}\gamma ώ})$ αντί$n$ σημείο αναφοράς${\overline{{\rm X}}}_{{\rm E}\gamma ώ}$ .Ας υποθέσουμε δηλαδή$v_{\iota }=\nabla {\phi ά}_{\iota }({\overline{{\rm X}}}_{\iota })$ Για j ∈ { 1 , … , n } j σε {1, ldots, n}ι∈{1,…,n}, σε κάθε επανάληψη, ενημερώνουμε μια στοχαστική κλίση όπως το SAG $v_{\iota }$。

Αλγόριθμος 2 SAGA

1. Παράμετροι: μέγεθος βήματος $\gamma >0$
2. αρχικοποίηση:${{\rm X}}_0$，$v_{{\rm E}\gamma ώ}=0\in {\mathbb{R}}^{\rho \epsilon }$ Για${\rm E}\gamma ώ=1,\dots ,n$
3. συμπεριφορά $\kappa =1,\dots ,{\rm T}-1$ επαναλήψεις:
   α. Τυχαία επιλογή ik ∈ { 1 , … , n } i_k σε {1, ldots, n}Εγώκ​∈{1,…,n}
   β. Αποθήκευση παλιάς αξίας$v_{\text{παλαιός}}=v_{{{\rm E}\gamma ώ}_{\kappa }}$
   γ$v_{{{\rm E}\gamma ώ}_{\kappa }}=\nabla {\phi ά}_{{{\rm E}\gamma ώ}_{\kappa }}({{\rm X}}_{\kappa })$
   δ. Ενημέρωση${{\rm X}}_{\kappa +1}={{\rm X}}_{\kappa }-\gamma (v_{{{\rm E}\gamma ώ}_{\kappa }}-v_{\text{παλαιός}}+{\overline{\sigma o\lambda }}_{\kappa })$
   ε. Ενημέρωση εκτίμησης κλίσης${\overline{\sigma o\lambda }}_{\kappa }={\overline{\sigma o\lambda }}_{\kappa -1}+\frac{1}{n}(v_{{{\rm E}\gamma ώ}_{\kappa }}-v_{\text{παλαιός}})$
4. Παραγωγή:${{\rm X}}_{{\rm T}}$

Η μέθοδος SAGA έχει την ίδια πολυπλοκότητα επανάληψης με την SAG ${\rm O}(({\kappa }_{\text{Μέγιστη}}+n)\mathrm{\iota \delta oύ\sigma o\lambda }(1/ϵ))$, χρησιμοποιώντας το μέγεθος βήματος $\gamma ={\rm O}(1/{\mu \epsilon \gamma ά\lambda o}_{\text{Μέγιστη}})$ , αλλά η απόδειξη είναι πολύ πιο απλή.Ωστόσο, όπως το SAG, η μέθοδος SAGA απαιτεί αποθήκευση$n$ βοηθητικά διανύσματα$v_{{\rm E}\gamma ώ}\in {\mathbb{R}}^{\rho \epsilon }$ Για${\rm E}\gamma ώ=1,\dots ,n$, που σημαίνει την ανάγκη ${\rm O}(n\rho \epsilon )$ του αποθηκευτικού χώρου.πότε$\rho \epsilon$ και$n$ Όταν και τα δύο είναι μεγάλα, αυτό μπορεί να μην είναι εφικτό. Στην επόμενη ενότητα, περιγράφουμε λεπτομερώς τον τρόπο μείωσης αυτής της απαίτησης μνήμης για κοινά μοντέλα, όπως τα κανονικοποιημένα γραμμικά μοντέλα.

όταν μπορεί $n$ Όταν δύο βοηθητικά διανύσματα είναι αποθηκευμένα στη μνήμη, τα SAG και SAGA τείνουν να συμπεριφέρονται παρόμοια. Εάν αυτή η απαίτηση μνήμης είναι πολύ υψηλή, η μέθοδος SVRG, την οποία θα εξετάσουμε στην επόμενη ενότητα, είναι μια καλή εναλλακτική. Η μέθοδος SVRG επιτυγχάνει τον ίδιο ρυθμό σύγκλισης και συχνά είναι σχεδόν εξίσου γρήγορη στην πράξη, αλλά απαιτεί μόνο${\rm O}(\rho \epsilon )$ μνήμης, για γενικά θέματα.

2.3.Μέθοδος SVRG

Πριν από την εμφάνιση της μεθόδου SAGA, ορισμένες πρώτες εργασίες εισήγαγαν συμμεταβλητές για πρώτη φορά για να λύσουν το πρόβλημα υψηλής μνήμης που απαιτείται από τη μέθοδο SAG.Αυτές οι μελέτες βασίζονται σε ένα σταθερό σημείο αναφοράς$\overline{{\rm X}}\in {\mathbb{R}}^{\rho \epsilon }$ συμμεταβλητές, έχουμε υπολογίσει την πλήρη κλίση σε εκείνο το σημείο$\nabla \phi ά(\overline{{\rm X}})$ .με την αποθήκευση σημείων αναφοράς$\overline{{\rm X}}$ και την αντίστοιχη πλήρη κλίση$\nabla \phi ά(\overline{{\rm X}})$, μπορούμε να το κάνουμε αυτό χωρίς να αποθηκεύσουμε το καθένα $\nabla {\phi ά}_{\iota }(\overline{{\rm X}})$ Σε περίπτωση, χρησιμοποιήστε${\overline{{\rm X}}}_{\iota }=\overline{{\rm X}}$ σε όλους$\iota$ για την εφαρμογή της ενημέρωσης (24).Συγκεκριμένα, αντί να αποθηκεύουμε αυτά τα διανύσματα, χρησιμοποιούμε τα αποθηκευμένα σημεία αναφοράς σε κάθε επανάληψη$\overline{{\rm X}}$ να υπολογίσω$\nabla {\phi ά}_{{{\rm E}\gamma ώ}_{\kappa }}(\overline{{\rm X}})$ . Αυτή η μέθοδος προτάθηκε αρχικά από διαφορετικούς συγγραφείς με διαφορετικά ονόματα, αλλά αργότερα ενοποιήθηκε ως μέθοδος SVRG, ακολουθώντας την ονοματολογία των [28] και [84].

Επισημοποιούμε τη μέθοδο SVRG στον Αλγόριθμο 3.

Χρησιμοποιώντας το (23), μπορούμε να εξαγάγουμε την εκτίμηση της κλίσης ${\sigma o\lambda }_{\kappa }$ Η διακύμανση του οριοθετείται:
$$\mu \iota \left[\Vert {\sigma o\lambda }_{\kappa }-\nabla \phi ά({{\rm X}}_{\kappa }){\Vert }^2\right]\le \mu \iota \left[\Vert \nabla {\phi ά}_{{\rm E}\gamma ώ}({{\rm X}}_{\kappa })-\nabla {\phi ά}_{{\rm E}\gamma ώ}(\overline{{\rm X}}){\Vert }^2\right]\le {\mu \epsilon \gamma ά\lambda o}_{\text{Μέγιστη}}^2\Vert {{\rm X}}_{\kappa }-\overline{{\rm X}}{\Vert }^2$$
όπου η δεύτερη ανισότητα χρησιμοποιεί το καθένα${\phi ά}_{{\rm E}\gamma ώ}$ του${\mu \epsilon \gamma ά\lambda o}_{{\rm E}\gamma ώ}$-Ομαλότητα.

Αξίζει να σημειωθεί ότι το σημείο αναφοράς $\overline{{\rm X}}$ Όσο πιο κοντά στο σημερινό σημείο${{\rm X}}_{\kappa }$, τόσο μικρότερη είναι η διακύμανση της εκτίμησης της κλίσης.

Για να είναι αποτελεσματική η μέθοδος SVRG, πρέπει να ενημερώνουμε συχνά τα σημεία αναφοράς $\overline{{\rm X}}$ (που απαιτεί τον υπολογισμό της πλήρους διαβάθμισης) σταθμίζεται έναντι του οφέλους της μειωμένης διακύμανσης.Για το λόγο αυτό, ο καθένας μας$t$ Ενημερώνετε το σημείο αναφοράς μία φορά κάθε επανάληψη για να το πλησιάζετε${{\rm X}}_{\kappa }$ (Βλ. γραμμή 11 του Αλγορίθμου II-C).Δηλαδή, η μέθοδος SVRG περιέχει δύο βρόχους: έναν εξωτερικό βρόχο$\mu \iota \kappa \rho ό$, όπου υπολογίζεται η κλίση αναφοράς $\nabla \phi ά({\overline{{\rm X}}}_{\mu \iota \kappa \rho ό-1})$(γραμμή 4) και έναν εσωτερικό βρόχο όπου το σημείο αναφοράς είναι σταθερό και η εσωτερική επανάληψη ενημερώνεται με βάση το βήμα στοχαστικής κλίσης (22) ${{\rm X}}_{\kappa }$(Γραμμή 10).

Σε αντίθεση με το SAG και το SAGA, το SVRG απαιτεί μόνο ${\rm O}(\rho \epsilon )$ της μνήμης. Στα μειονεκτήματα του SVRG περιλαμβάνονται: 1) Έχουμε μια επιπλέον παράμετρο$t$, δηλαδή, το μήκος του εσωτερικού βρόχου, πρέπει να ρυθμιστεί.

Οι Johnson και Zhang [28] έδειξαν ότι το SVRG έχει επαναληπτική πολυπλοκότητα ${\rm O}(({\kappa }_{\text{Μέγιστη}}+n)\mathrm{\iota \delta oύ\sigma o\lambda }(1/ϵ))$ , παρόμοια με τα SAG και SAGA.Αυτός είναι ο αριθμός των βρόχων εντός της υπόθεσης$t$ από τη συλλογή { 1 , … , m } {1, ldots, m}{1,…,Μ} Λήφθηκε υπό την προϋπόθεση της ομοιόμορφης δειγματοληψίας, όπου${\mu \epsilon \gamma ά\lambda o}_{\text{Μέγιστη}}$，$\mu$, μέγεθος βήματος $\gamma$ και$t$ Ορισμένες εξαρτήσεις πρέπει να ικανοποιούνται μεταξύ τους.Στην πράξη, με τη χρήση$\gamma ={\rm O}(1/{\mu \epsilon \gamma ά\lambda o}_{\text{Μέγιστη}})$ και μήκος εσωτερικού βρόχου$t=n$, το SVRG τείνει να αποδίδει καλά, η οποία είναι ακριβώς η ρύθμιση που χρησιμοποιήσαμε στο Σχήμα 1.

Τώρα, υπάρχουν πολλές παραλλαγές της αρχικής μεθόδου SVRG.Για παράδειγμα, ορισμένες παραλλαγές χρησιμοποιούν$t$ εναλλακτική διανομή [32], ορισμένες παραλλαγές επιτρέπουν τη φόρμα${\rm O}(1/{\mu \epsilon \gamma ά\lambda o}_{\text{Μέγιστη}})$ Το μέγεθος βήματος [27], [33], [35].Υπάρχουν επίσης ορισμένες παραλλαγές χρησιμοποιώντας$\nabla \phi ά(\overline{{\rm X}})$ προσέγγιση μίνι-παρτίδας για τη μείωση του κόστους αυτών των αξιολογήσεων πλήρους κλίσης και την αύξηση του μεγέθους της μίνι παρτίδας για τη διατήρηση των ιδιοτήτων VR.Υπάρχουν επίσης ορισμένες παραλλαγές όπου οι ενημερώσεις επαναλαμβάνονται στον εσωτερικό βρόχο σύμφωνα με το [54]${\sigma o\lambda }_{\kappa }$：
[ g_k = nabla f_{i_k}(x_k) - nabla f_{i_k}(x_{k-1}) + g_{k-1} quad (25) ]
Αυτό παρέχει μια πιο τοπική προσέγγιση. Η χρήση αυτής της παραλλαγής συνεχούς ενημέρωσης (25) δείχνει μοναδικά πλεονεκτήματα στην ελαχιστοποίηση των μη κυρτών συναρτήσεων, όπως συζητάμε εν συντομία στην Ενότητα IV.Τέλος, σημειώστε ότι το SVRG μπορεί να εκμεταλλευτεί$\nabla \phi ά({\overline{{\rm X}}}_{\mu \iota \kappa \rho ό})$ τιμή για να αποφασίσετε πότε θα τερματιστεί ο αλγόριθμος.

Αλγόριθμος 3 Μέθοδος SVRG

1. Παράμετροι: μέγεθος βήματος $\gamma >0$
2. Αρχικοποίηση σημείου αναφοράς ${\overline{{\rm X}}}_0={{\rm X}}_0\in {\mathbb{R}}^{\rho \epsilon }$
3. Πραγματοποιήστε εξωτερική κυκλοφορία $\mu \iota \kappa \rho ό=1,2,\dots$：
   α. Υπολογίστε και αποθηκεύστε$\nabla \phi ά({\overline{{\rm X}}}_{\mu \iota \kappa \rho ό-1})$
   β. Υποθέστε${{\rm X}}_0={\overline{{\rm X}}}_{\mu \iota \kappa \rho ό-1}$
   c Επιλέξτε τον αριθμό των επαναλήψεων του εσωτερικού βρόχου$t$
   δ. Εκτελέστε εσωτερική κυκλοφορία$\kappa =0,1,\dots ,t-1$：
   i. Τυχαία επιλογή ik ∈ { 1 , … , n } i_k σε {1, ldots, n}Εγώκ​∈{1,…,n}
   ii. Υπολογισμός${\sigma o\lambda }_{\kappa }=\nabla {\phi ά}_{{{\rm E}\gamma ώ}_{\kappa }}({{\rm X}}_{\kappa })-\nabla {\phi ά}_{{{\rm E}\gamma ώ}_{\kappa }}({\overline{{\rm X}}}_{\mu \iota \kappa \rho ό-1})+\nabla \phi ά({\overline{{\rm X}}}_{\mu \iota \kappa \rho ό-1})$
   iii. Ενημέρωση${{\rm X}}_{\kappa +1}={{\rm X}}_{\kappa }-\gamma {\sigma o\lambda }_{\kappa }$
   ε. Ενημέρωση σημείου αναφοράς${\overline{{\rm X}}}_{\mu \iota \kappa \rho ό}={{\rm X}}_t$

2.4. SDCA και οι παραλλαγές του

Ένα μειονέκτημα των μεθόδων SAG και SVRG είναι ότι το μέγεθος του βήματος τους βασίζεται σε άγνωστες τιμές που μπορεί να είναι άγνωστες σε ορισμένα προβλήματα. ${\mu \epsilon \gamma ά\lambda o}_{\text{Μέγιστη}}$ . Πριν από το SVRG, η μέθοδος SDCA [70], ως μία από τις παλαιότερες μεθόδους VR, επέκτεινε την έρευνα για τις μεθόδους καθόδου συντεταγμένων σε προβλήματα πεπερασμένων αθροισμάτων. Η ιδέα πίσω από το SDCA και τις παραλλαγές του είναι ότι οι συντεταγμένες της κλίσης παρέχουν μια φυσική εκτίμηση της κλίσης που μειώνει τη διακύμανση.Συγκεκριμένα, ας υποθέσουμε j ∈ { 1 , … , d } j σε {1, ldots, d}ι∈{1,…,ρε}, και ορίστε ${\nabla }_{\iota }\phi ά({\rm X}):=\left(\frac{\partial \phi ά({\rm X})}{\partial {{\rm X}}_{\iota }}\right){\mu \iota }_{\iota }$ είναι το ου του (f(x))$\iota$ παράγωγα σε κατευθύνσεις συντεταγμένων, όπου${\mu \iota }_{\iota }\in {\mathbb{R}}^{\rho \epsilon }$ Είναι το πρώτο$\iota$ μονάδα διάνυσμα.Μια βασική ιδιότητα των παραγώγων συντεταγμένων είναι αυτή${\nabla }_{\iota }\phi ά({{\rm X}}^{\ast })=0$, γιατί ξέρουμε $\nabla \phi ά({{\rm X}}^{\ast })=0$ .Η παράγωγος αυτού με κάθε σημείο δεδομένων$\nabla {\phi ά}_{\iota }$ διαφορετικό, το τελευταίο είναι${{\rm X}}^{\ast }$ μπορεί να μην είναι μηδέν. Επομένως έχουμε:
$$\Vert \nabla \phi ά({\rm X})-{\nabla }_{\iota }\phi ά({\rm X}){\Vert }^2\to 0\text{πότε}{\rm X}\to {{\rm X}}^{\ast }(26)$$
Αυτό σημαίνει ότι η παράγωγος συντεταγμένων ικανοποιεί την ιδιότητα μείωσης της διακύμανσης (12).Επιπλέον, μπορούμε να χρησιμοποιήσουμε${\nabla }_{\iota }\phi ά({\rm X})$ χτίζω$\nabla \phi ά({\rm X})$ μια αμερόληπτη εκτίμηση του.Για παράδειγμα, ας υποθέσουμε$\iota$ είναι από τη συλλογή { 1 , … , d } {1, ldots, d}{1,…,ρε} Ένας ομοιόμορφα τυχαία επιλεγμένος δείκτης σε .Επομένως, για οποιαδήποτε i ∈ { 1 , … , d } i σε {1, ldots, d}Εγώ∈{1,…,ρε},Εχουμε $\Pi [\iota ={\rm E}\gamma ώ]=\frac{1}{\rho \epsilon }$ . επομένως,$\rho \epsilon \times {\nabla }_{\iota }\phi ά({\rm X})$ Ναί$\nabla \phi ά({\rm X})$ Μια αμερόληπτη εκτίμηση επειδή:
$$\mu \iota \left[\rho \epsilon {\nabla }_{\iota }\phi ά({\rm X})\right]=\rho \epsilon \sum _{{\rm E}\gamma ώ=1}^{\rho \epsilon }\Pi [\iota ={\rm E}\gamma ώ]\frac{\partial \phi ά({\rm X})}{\partial {{\rm X}}_{{\rm E}\gamma ώ}}{\mu \iota }_{{\rm E}\gamma ώ}=\sum _{{\rm E}\gamma ώ=1}^{\rho \epsilon }\frac{\partial \phi ά({\rm X})}{\partial {{\rm X}}_{{\rm E}\gamma ώ}}{\mu \iota }_{{\rm E}\gamma ώ}=\nabla \phi ά({\rm X})$$

επομένως,${\nabla }_{\iota }\phi ά({\rm X})$ Έχει όλες τις ιδανικές ιδιότητες που θα περιμέναμε για την εκτίμηση πλήρους διαβάθμισης VR, χωρίς την ανάγκη χρήσης συμμεταβλητών. Ένα μειονέκτημα της χρήσης αυτής της κλίσης συντεταγμένων είναι ότι είναι υπολογιστικά ακριβό για το πρόβλημα αθροίσματος (2).Αυτό συμβαίνει γιατί ο υπολογισμός${\nabla }_{\iota }\phi ά({\rm X})$ Πρέπει να διασχίσετε ολόκληρο το σύνολο δεδομένων γιατί${\nabla }_{\iota }\phi ά({\rm X})=\frac{1}{n}{\sum }_{{\rm E}\gamma ώ=1}^n{\nabla }_{\iota }{\phi ά}_{{\rm E}\gamma ώ}({\rm X})$ . Επομένως, η χρήση παραγώγων συντεταγμένων φαίνεται ασύμβατη με τη δομή του προβλήματος αθροίσματος μας. Ωστόσο, μπορούμε συχνά να ξαναγράψουμε το αρχικό πρόβλημα (2) σε μια λεγόμενη διπλή διατύπωση, όπου οι παράγωγοι συντεταγμένων μπορούν να εκμεταλλευτούν την εγγενή δομή.

Για παράδειγμα, ο διπλός τύπος του τακτοποιημένου γραμμικού μοντέλου L2 (15) είναι:
$$v^{\ast }\in \mathrm{\alpha \rho \sigma o\lambda }\underset{v\in {\mathbb{R}}^n}{\mathrm{{\rm M}έ\gamma \iota \sigma \tau \eta }}\frac{1}{n}\sum _{{\rm E}\gamma ώ=1}^n-{\ell }_{{\rm E}\gamma ώ}^{\ast }(-v_{{\rm E}\gamma ώ})-\frac{\lambda }{2}{\Vert \frac{1}{\lambda }\sum _{{\rm E}\gamma ώ=1}^n{v}_{{\rm E}\gamma ώ}{έ\nu \alpha }_{{\rm E}\gamma ώ}\Vert }^2(27)$$
σε${\ell }_{{\rm E}\gamma ώ}^{\ast }(v)$ Ναί${\ell }_{{\rm E}\gamma ώ}$ κυρτό συζυγές.Μπορούμε να χρησιμοποιήσουμε χαρτογράφηση${\rm X}=\frac{1}{\lambda }{\sum }_{{\rm E}\gamma ώ=1}^n{v}_{{\rm E}\gamma ώ}{έ\nu \alpha }_{{\rm E}\gamma ώ}$ για να επαναφέρετε το αρχικό πρόβλημα (15)${\rm X}$ μεταβλητός.θα λύσει$v^{\ast }$ Αντικαθιστώντας στη δεξιά πλευρά της παραπάνω χαρτογράφησης, μπορούμε να πάρουμε τη λύση του (15)${{\rm X}}^{\ast }$。

Σημειώστε ότι αυτό το διπλό πρόβλημα έχει $n$ πραγματικές μεταβλητές$v_{{\rm E}\gamma ώ}\in \mathbb{R}$ , που αντιστοιχεί σε ένα για κάθε δείγμα εκπαίδευσης.Επιπλέον, κάθε λειτουργία διπλής απώλειας${\ell }_{{\rm E}\gamma ώ}^{\ast }$ μόνο$v_{{\rm E}\gamma ώ}$ Η λειτουργία. Δηλαδή, ο πρώτος όρος στη συνάρτηση απώλειας είναι συντεταγμένος διαχωρισμός. Αυτή η δυνατότητα διαχωρισμού στις συντεταγμένες, σε συνδυασμό με την απλή μορφή του δεύτερου όρου, μας επιτρέπει να εφαρμόσουμε αποτελεσματικά τη μέθοδο συντεταγμένης ανάβασης.Πράγματι, οι Shalev-Shwartz και Zhang έδειξαν ότι η συντεταγμένη ανάβαση σε αυτό το πρόβλημα έχει παρόμοια επαναληπτική πολυπλοκότητα με τα SAG, SAGA και SVRG${\rm O}(({\kappa }_{\text{Μέγιστη}}+n)\mathrm{\iota \delta oύ\sigma o\lambda }(1/ϵ))$。

Το κόστος επανάληψης και η δομή του αλγορίθμου είναι επίσης πολύ παρόμοια: άθροιση με παρακολούθηση ${\sum }_{{\rm E}\gamma ώ=1}^n{v}_{{\rm E}\gamma ώ}{έ\nu \alpha }_{{\rm E}\gamma ώ}$ Για να χειριστείτε τον δεύτερο όρο στο (27), κάθε επανάληψη ανάβασης διπλής συντεταγμένης χρειάζεται μόνο να λάβετε υπόψη ένα δείγμα εκπαίδευσης και το κόστος κάθε επανάληψης είναι το ίδιο με$n$ Τίποτα να κάνω.Επιπλέον, μπορούμε να χρησιμοποιήσουμε μια αναζήτηση γραμμής 1D για να υπολογίσουμε αποτελεσματικά το μέγεθος του βήματος για μεγιστοποίηση$v_{{\rm E}\gamma ώ}$ Διπλός στόχος της συνάρτησης.Αυτό σημαίνει ότι ακόμη και χωρίς${\mu \epsilon \gamma ά\lambda o}_{\text{Μέγιστη}}$ Ή γνώση σχετικών ποσοτήτων, είναι επίσης δυνατό να επιτευχθούν γρήγοροι χρόνοι λειτουργίας στη χειρότερη περίπτωση για μεθόδους VR.

3. Πρακτικά θέματα μείωσης διασποράς

Προκειμένου να εφαρμοστεί η βασική μέθοδος μείωσης διασποράς (VR) και να επιτευχθούν λογικές επιδόσεις, πρέπει να αντιμετωπιστούν αρκετά ζητήματα υλοποίησης. Σε αυτή την ενότητα, συζητάμε διάφορα θέματα που δεν καλύπτονται παραπάνω.

3.1.Μέγεθος βήματος ρύθμισης SAG/SAGA/SVRG

Στον τομέα των αλγορίθμων βελτιστοποίησης, ειδικά σε μεθόδους μείωσης διακύμανσης όπως η στοχαστική μέση κλίση (SAG), ο στοχαστικός μέσος αλγόριθμος κλίσης (SAGA) και η στοχαστική κλίση (SVRG), η ρύθμιση του μεγέθους του βήματος είναι βασικό ζήτημα.Αν και για τη μέθοδο στοχαστικής ανάβασης διπλής συντεταγμένης (SDCA), μπορούμε να χρησιμοποιήσουμε τον διπλό στόχο για να καθορίσουμε το μέγεθος του βήματος, η θεωρητική βάση για τις αρχικές μεταβλητές μεθόδους των SAG, SAGA και SVRG είναι ότι το μέγεθος του βήματος πρέπει να είναι$\gamma ={\rm O}\left(\frac{1}{{\mu \epsilon \gamma ά\lambda o}_{\text{Μέγιστη}}}\right)$ μορφή.Ωστόσο, σε πρακτικές εφαρμογές, συχνά δεν γνωρίζουμε${\mu \epsilon \gamma ά\lambda o}_{\text{Μέγιστη}}$ Η ακριβής τιμή του και η χρήση άλλων μεγεθών βημάτων μπορεί να δώσει καλύτερη απόδοση.

Μια κλασική στρατηγική για τον ορισμό του μεγέθους βήματος στη μέθοδο πλήρους κλίσης κατάβασης (full-GD) είναι η αναζήτηση γραμμής Armijo.δεδομένο τρέχον σημείο${{\rm X}}_{\kappa }$ και κατεύθυνση αναζήτησης${\sigma o\lambda }_{\kappa }$, αναζήτηση γραμμής Armijo σε ${\gamma }_{\kappa }$ πραγματοποιείται στη γραμμή, η οποία ορίζεται ως γ k ∈ { γ : xk + γ gk } gamma_k σε {γάμα : x_k + γάμμα g_k}γκ​∈{γ:Χκ​+γσολκ​}, και η συνάρτηση απαιτείται να μειωθεί επαρκώς, δηλαδή:
$$\phi ά({{\rm X}}_{\kappa }+{\gamma }_{\kappa }{\sigma o\lambda }_{\kappa })<\phi ά({{\rm X}}_{\kappa })-\nu \tau o{\gamma }_{\kappa }\Vert \nabla \phi ά({{\rm X}}_{\kappa }){\Vert }^2$$
Ωστόσο, αυτή η προσέγγιση απαιτεί πολλαπλά βήματα υποψηφίου${\gamma }_{\kappa }$ Υπολογισμός$\phi ά({{\rm X}}_{\kappa }+{\gamma }_{\kappa }{\sigma o\lambda }_{\kappa })$, το οποίο αξιολογεί $\phi ά({\rm X})$ Απαγορευτικό κόστος όταν πρόκειται για τη διέλευση ολόκληρου του συνόλου δεδομένων.

Για να λυθεί αυτό το πρόβλημα, μπορεί να χρησιμοποιηθεί μια μέθοδος τυχαίας παραλλαγής για να βρεθούν εκείνα που πληρούν τις ακόλουθες προϋποθέσεις ${\gamma }_{\kappa }$：
$${\phi ά}_{ik}({{\rm X}}_{\kappa }+{\gamma }_{\kappa }{\sigma o\lambda }_{\kappa })<{\phi ά}_{ik}({{\rm X}}_{\kappa })-\nu \tau o{\gamma }_{\kappa }\Vert \nabla {\phi ά}_{ik}({{\rm X}}_{\kappa }){\Vert }^2$$
Αυτή η προσέγγιση συνήθως λειτουργεί καλά στην πράξη, ειδικά όταν$\Vert \nabla {\phi ά}_{ik}({{\rm X}}_{\kappa })\Vert$ όχι κοντά στο μηδέν, αν και δεν υπάρχει προς το παρόν καμία θεωρία που να υποστηρίζει αυτήν την προσέγγιση.

Επιπλέον, ο Mairal πρότεινε μια «τεχνική Bottou» για τον καθορισμό του μεγέθους του βήματος στην πράξη. Αυτή η μέθοδος εκτελεί μια δυαδική αναζήτηση λαμβάνοντας ένα μικρό μέρος του συνόλου δεδομένων (π.χ. 5%) για να προσπαθήσει να βρει το βέλτιστο μέγεθος βήματος σε ένα μόνο πέρασμα από αυτό το δείγμα. Παρόμοια με την αναζήτηση γραμμής Armijo, αυτή η μέθοδος συχνά αποδίδει καλά στην πράξη, αλλά και πάλι στερείται θεωρητικής βάσης.

Λάβετε υπόψη ότι το παραπάνω περιεχόμενο αποτελεί επαναδιατύπωση του αρχικού κειμένου, χρησιμοποιώντας τη μορφή Markdown για την αναπαράσταση μαθηματικών τύπων και μεταβλητών.

Ωστόσο, η μέθοδος SDCA έχει επίσης ορισμένα μειονεκτήματα.Πρώτον, απαιτεί τον υπολογισμό του κυρτού συζυγούς${\ell }_{{\rm E}\gamma ώ}^{\ast }$ παρά μια απλή κλίση. Δεν έχουμε αυτόματο διαφορικό ισοδύναμο για κυρτά συζεύγματα, επομένως αυτό μπορεί να αυξήσει την προσπάθεια υλοποίησης. Πρόσφατη εργασία έχει προτείνει μεθόδους SDCA "διπλής ελεύθερα" που δεν απαιτούν σύζευξη και αντίθετα χρησιμοποιούν απευθείας κλίσεις. Ωστόσο, σε αυτές τις μεθόδους δεν είναι πλέον δυνατή η παρακολούθηση του διπλού στόχου για να ορίσετε το μέγεθος του βήματος.Δεύτερον, αν και το SDCA απαιτεί μόνο${\rm O}(n+\rho \epsilon )$ μνήμη για την επίλυση του προβλήματος (15), αλλά για αυτήν την κατηγορία προβλημάτων, χρειάζεται μόνο το SAG/SAGA${\rm O}(n+\rho \epsilon )$ μνήμης (βλ. Ενότητα 3).Μια παραλλαγή του SDCA κατάλληλη για γενικότερα προβλήματα με SAG/SAGA${\rm O}(n\rho \epsilon )$ μνήμη γιατί$v_{{\rm E}\gamma ώ}$ γίνει έχοντας$\rho \epsilon$ διάνυσμα στοιχείων. Ένα τελευταίο λεπτό μειονέκτημα του SDCA είναι ότι υποθέτει έμμεσα μια ισχυρή σταθερά κυρτότητας$\mu$ ίσος$\lambda$ .Για$\mu$ περισσότερο από το$\lambda$ πρόβλημα, η αρχική μέθοδος VR ​​συνήθως ξεπερνά σημαντικά το SDCA.

3.2 Καθορισμός όρων τερματισμού

Στον τομέα της βελτιστοποίησης αλγορίθμων, βασιζόμαστε συχνά σε θεωρητικά αποτελέσματα επαναληπτικής πολυπλοκότητας για να προβλέψουμε τον αριθμό των επαναλήψεων στη χειρότερη περίπτωση που απαιτείται για να επιτύχει ένας αλγόριθμος μια συγκεκριμένη ακρίβεια. Ωστόσο, αυτά τα θεωρητικά όρια συχνά βασίζονται σε ορισμένες σταθερές που δεν μπορούμε να προβλέψουμε και σε πρακτικές εφαρμογές, ο αλγόριθμος μπορεί συχνά να επιτύχει την αναμενόμενη ακρίβεια σε λιγότερες επαναλήψεις. Επομένως, πρέπει να ορίσουμε κάποια κριτήρια δοκιμής για να καθορίσουμε πότε πρέπει να τερματιστεί ο αλγόριθμος.

Στην παραδοσιακή μέθοδο καθόδου πλήρους κλίσης (full-GD), συνήθως χρησιμοποιούμε τον κανόνα της κλίσης $\Vert \nabla \phi ά({{\rm X}}_{\kappa })\Vert$ Ή κάποια άλλη ποσότητα που σχετίζεται με αυτό για να αποφασίσετε πότε θα σταματήσετε την επανάληψη.Για τη μέθοδο SVRG μπορούμε να υιοθετήσουμε το ίδιο κριτήριο αλλά να χρησιμοποιήσουμε$\Vert \nabla \phi ά({\overline{{\rm X}}}_{\mu \iota \kappa \rho ό})\Vert$ ως βάση για κρίση.Για τη μέθοδο SAG/SAGA, αν και δεν υπολογίζουμε ρητά την πλήρη διαβάθμιση, η ποσότητα $ g_{bar{k}} $ θα προσεγγιστεί σταδιακά$\nabla \phi ά({{\rm X}}_{\kappa })$, επομένως, χρήση $\Vert {\sigma o\lambda }_{\bar{\kappa }}\Vert$ ως συνθήκη διακοπής είναι μια λογική ευρετική.

Στη μέθοδο SDCA, με κάποια πρόσθετη εργασία εγγραφής, μπορούμε να παρακολουθήσουμε την κλίση του διπλού στόχου χωρίς να προσθέσουμε επιπλέον ασυμπτωτικό κόστος.Επιπλέον, μια πιο συστηματική προσέγγιση θα ήταν η παρακολούθηση του διπλού χάσματος, αν και αυτό θα αύξανε το${\rm O}(n)$ κόστος, αλλά είναι σε θέση να παρέχει συνθήκες τερματισμού με αποδείξεις διπλού κενού. Επιπλέον, με βάση τη συνθήκη βελτιστοποίησης των έντονα κυρτών στόχων, η μέθοδος MISO υιοθετεί μια βασική μέθοδο βασισμένη στο τετραγωνικό κάτω όριο [41].

Οι παρακάτω είναι μαθηματικοί τύποι και μεταβλητές που εκφράζονται σε μορφή Markdown:

• Κανόνας κλίσης:$\Vert \nabla \phi ά({{\rm X}}_{\kappa })\Vert$
• Κανόνας κλίσης στη μέθοδο SVRG:$\Vert \nabla \phi ά({\overline{{\rm X}}}_{\mu \iota \kappa \rho ό})\Vert$
• Το ποσό της κλίσης προσέγγισης στη μέθοδο SAG/SAGA: $ g_{bar{k}} $
• Αυξημένο κόστος ανά επανάληψη:${\rm O}(n)$
• Μέθοδος MISO
• τετραγωνικό κάτω όριο

Λάβετε υπόψη ότι το παραπάνω περιεχόμενο αποτελεί επαναδιατύπωση του αρχικού κειμένου, χρησιμοποιώντας τη μορφή Markdown για την αναπαράσταση μαθηματικών τύπων και μεταβλητών.

3.3 Μειώστε τις απαιτήσεις μνήμης

Αν και ο αλγόριθμος Stochastic Variational Reduction of Gradient (SVRG) εξαλείφει τις απαιτήσεις μνήμης των προηγούμενων μεθόδων μείωσης παραλλαγής, σε πρακτικές εφαρμογές, οι αλγόριθμοι SAG (Stochastic Average Gradient Descent) και SAGA (Stochastic Average Gradient Descent with Gradient Accuulation) χρησιμοποιούνται σε πολλά προβλήματα. τείνουν να απαιτούν λιγότερες επαναλήψεις από τον αλγόριθμο SVRG.Αυτό πυροδότησε μια σκέψη: Υπάρχουν ορισμένα ζητήματα που επιτρέπουν στο SAG/SAGA${\rm O}(n\rho \epsilon )$ Οι απαιτήσεις μνήμης υλοποιούνται παρακάτω. Αυτή η ενότητα διερευνά μια κατηγορία γραμμικών μοντέλων για τα οποία οι απαιτήσεις μνήμης μπορούν να μειωθούν σημαντικά.

Εξετάστε ένα γραμμικό μοντέλο όπου κάθε συνάρτηση ${\phi ά}_{{\rm E}\gamma ώ}({\rm X})$ Μπορεί να εκφραστεί ως${\xi }_{{\rm E}\gamma ώ}({\mathbf{έ\nu \alpha }}_{{\rm E}\gamma ώ}^{\top }{\rm X})$ .σωστά${\rm X}$ Το παράγωγο δίνει τη μορφή κλίσης:
$$\nabla {\phi ά}_{{\rm E}\gamma ώ}({\rm X})={\xi }^{\prime }({\mathbf{έ\nu \alpha }}_{{\rm E}\gamma ώ}^{\top }{\rm X}){\mathbf{έ\nu \alpha }}_{{\rm E}\gamma ώ}$$
εδώ,${\xi }^{\prime }$ εξπρές$\xi$ το παράγωγο του.Υποθέτοντας ότι έχουμε άμεση πρόσβαση στα ιδιοδιανύσματα${\mathbf{έ\nu \alpha }}_{{\rm E}\gamma ώ}$, τότε για να εφαρμόσουμε τη μέθοδο SAG/SAGA, χρειάζεται μόνο να αποθηκεύσουμε το βαθμωτό $\xi ({\mathbf{έ\nu \alpha }}_{{\rm E}\gamma ώ}^{\top }{\rm X})$ .Με αυτόν τον τρόπο, οι απαιτήσεις μνήμης ποικίλλουν από${\rm O}(n\rho \epsilon )$ μειώθηκε σε${\rm O}(n)$ . Ο αλγόριθμος SVRG μπορεί επίσης να εκμεταλλευτεί αυτή τη δομή διαβαθμίσεων: αποθηκεύοντας αυτό$n$ κλιμακωτό, μπορούμε να μειώσουμε τον αριθμό των αξιολογήσεων κλίσης που απαιτούνται ανά "εσωτερική" επανάληψη SVRG σε 1 για αυτήν την κατηγορία προβλημάτων.

Υπάρχουν και άλλα είδη προβλημάτων, όπως πιθανοτικά γραφικά μοντέλα, τα οποία προσφέρουν επίσης τη δυνατότητα μείωσης των απαιτήσεων μνήμης [66]. Μέσω συγκεκριμένης δομής δεδομένων και βελτιστοποίησης αλγορίθμων, οι πόροι μνήμης που απαιτούνται από τον αλγόριθμο κατά το χρόνο εκτέλεσης μπορούν να μειωθούν περαιτέρω.

Οι παρακάτω είναι μαθηματικοί τύποι και μεταβλητές που εκφράζονται σε μορφή Markdown:

• Λειτουργία γραμμικού μοντέλου:${\phi ά}_{{\rm E}\gamma ώ}({\rm X})={\xi }_{{\rm E}\gamma ώ}({\mathbf{έ\nu \alpha }}_{{\rm E}\gamma ώ}^{\top }{\rm X})$
• Έκφραση κλίσης:$\nabla {\phi ά}_{{\rm E}\gamma ώ}({\rm X})={\xi }^{\prime }({\mathbf{έ\nu \alpha }}_{{\rm E}\gamma ώ}^{\top }{\rm X}){\mathbf{έ\nu \alpha }}_{{\rm E}\gamma ώ}$
• Διάνυσμα χαρακτηριστικών:${\mathbf{έ\nu \alpha }}_{{\rm E}\gamma ώ}$
• Οι απαιτήσεις μνήμης κυμαίνονται από ${\rm O}(n\rho \epsilon )$ Μειώστε σε${\rm O}(n)$。

3.4 Επεξεργασία αραιών κλίσεων

Σε ορισμένα προβλήματα, η κλίση $\nabla {\phi ά}_{{\rm E}\gamma ώ}({\rm X})$ Μπορεί να περιέχει μεγάλο αριθμό μηδενικών τιμών, όπως ένα γραμμικό μοντέλο με αραιά χαρακτηριστικά.Σε αυτήν την περίπτωση, ο παραδοσιακός αλγόριθμος στοχαστικής διαβάθμισης (SGD) μπορεί να εφαρμοστεί αποτελεσματικά, με υπολογιστική πολυπλοκότητα γραμμική ως προς τον αριθμό των μη μηδενικών στοιχείων στη διαβάθμιση, που είναι συνήθως πολύ μικρότερος από τη διάσταση του προβλήματος$\rho \epsilon$ . Ωστόσο, στις τυπικές μεθόδους μείωσης της μεταβολής (VR), αυτό το πλεονέκτημα δεν αξιοποιείται. Ευτυχώς, υπάρχουν δύο γνωστοί τρόποι για να βελτιωθεί αυτό.

Η πρώτη βελτίωση προτάθηκε από τους Schmidt et al., ο οποίος εκμεταλλεύεται την απλότητα της διαδικασίας ενημέρωσης και εφαρμόζει μια παραλλαγή του υπολογισμού "on-the-fly" έτσι ώστε το κόστος κάθε επανάληψης να είναι ανάλογο με τον αριθμό των μη μηδενικών στοιχεία.Λαμβάνοντας ως παράδειγμα το SAG (αλλά αυτή η προσέγγιση λειτουργεί για όλες τις παραλλαγές), αυτό γίνεται με το να μην αποθηκεύεται το πλήρες διάνυσμα μετά από κάθε επανάληψη$v_{ik}$, αλλά υπολογίζει μόνο εκείνα που αντιστοιχούν σε μη μηδενικά στοιχεία $v_{{\rm E}\gamma ώ{\kappa }_{\iota }}$, ενημερώνοντας κάθε μεταβλητή από την τελευταία φορά που αυτό το στοιχείο ήταν μη μηδενικό $v_{{\rm E}\gamma ώ{\kappa }_{\iota }}$。

Η δεύτερη μέθοδος βελτίωσης προτάθηκε από τους Leblond et al για το SAGA, η οποία ενημερώνει τον τύπο ${{\rm X}}_{\kappa +1}={{\rm X}}_{\kappa }-\gamma (\nabla {\phi ά}_{ik}({{\rm X}}_{\kappa })-\nabla {\phi ά}_{ik}({\overline{{\rm X}}}_{ik})+{\overline{\sigma o\lambda }}_{\kappa })$ Εισάγεται πρόσθετη τυχαιότητα. εδώ,$\nabla {\phi ά}_{ik}({{\rm X}}_{\kappa })$ και$\nabla {\phi ά}_{ik}({\overline{{\rm X}}}_{ik})$ είναι αραιή, και${\overline{\sigma o\lambda }}_{\kappa }$ είναι πυκνό.Σε αυτή τη μέθοδο, ο πυκνός όρος$({\overline{\sigma o\lambda }}_{\kappa }{)}_{\iota }$ Κάθε συστατικό του αντικαθίσταται από$w_{\iota }({\overline{\sigma o\lambda }}_{\kappa }{)}_{\iota }$,σε $w\in {\mathbb{R}}^{\rho \epsilon }$ είναι ένα τυχαίο αραιό διάνυσμα του οποίου το σύνολο υποστήριξης περιέχεται σε$\nabla {\phi ά}_{ik}({{\rm X}}_{\kappa })$ , και αναμένεται να είναι ένα σταθερό διάνυσμα με όλα τα στοιχεία ίσα με 1. Με αυτόν τον τρόπο, η διαδικασία ενημέρωσης παραμένει αμερόληπτη (αν και τώρα αραιή) και η αυξημένη διακύμανση δεν επηρεάζει τον ρυθμό σύγκλισης του αλγορίθμου. Περισσότερες λεπτομέρειες παρέχονται από τους Leblond et al.

Οι παρακάτω είναι μαθηματικοί τύποι και μεταβλητές που εκφράζονται σε μορφή Markdown:

• βαθμίδα:$\nabla {\phi ά}_{{\rm E}\gamma ώ}({\rm X})$
• Ενημέρωση SGD:${{\rm X}}_{\kappa +1}={{\rm X}}_{\kappa }-\gamma (\nabla {\phi ά}_{ik}({{\rm X}}_{\kappa })-\nabla {\phi ά}_{ik}({\overline{{\rm X}}}_{ik})+{\overline{\sigma o\lambda }}_{\kappa })$
• Αραιή κλίση:$\nabla {\phi ά}_{ik}({{\rm X}}_{\kappa })$ και$\nabla {\phi ά}_{ik}({\overline{{\rm X}}}_{ik})$
• Πυκνή κλίση:${\overline{\sigma o\lambda }}_{\kappa }$
• Τυχαία αραιά διανύσματα:$w$
• Αναμένει σταθερό διάνυσμα: ένα διάνυσμα με όλα τα στοιχεία ίσα με 1.