Stochastische Optimierung mit Importance Sampling

Die einheitliche Stichprobenentnahme von Trainingsdaten wurde in traditionellen stochastischen Optimierungsalgorithmen wie Proximal Stochastic Gradient Descent (prox-SGD) und Proximal Stochastic Dual Coordinate Ascent (prox-SDCA) häufig verwendet. Obwohl eine einheitliche Stichprobenentnahme garantieren kann, dass die stochastische Größe eine unverzerrte Schätzung der entsprechenden wahren Größe ist, kann der resultierende Schätzer eine ziemlich hohe Varianz aufweisen, was sich negativ auf die Konvergenz des zugrunde liegenden Optimierungsverfahrens auswirkt. In diesem Papier untersuchen wir die stochastische Optimierung mit Importance Sampling, das die Konvergenzrate verbessert, indem die stochastische Varianz reduziert wird. Insbesondere untersuchen wir prox-SGD (tatsächlich stochastische Spiegelabstieg) mit Importance Sampling und prox-SDCA mit Importance Sampling. Für prox-SGD verwendet der vorgeschlagene Algorithmus anstelle der einheitlichen Stichprobenentnahme während des Trainingsprozesses Importance Sampling, um die Varianz des stochastischen Gradienten zu minimieren. Für prox-SDCA zielt das vorgeschlagene Wichtigkeitsstichprobenverfahren darauf ab, einen höheren erwarteten dualen Wert bei jedem Schritt des dualen Koordinatenanstiegs zu erreichen. Wir bieten eine umfangreiche theoretische Analyse an, um zu zeigen, dass die Konvergenzraten mit den vorgeschlagenen Methoden des Importance Sampling unter geeigneten Bedingungen sowohl für prox-SGD als auch für prox-SDCA erheblich verbessert werden können. Experimente werden bereitgestellt, um die theoretische Analyse zu überprüfen.