Publication
Adaptive Stochastic Variance Reduction for Non-convex Finite-Sum Minimization
Volkan Cevher, Kimon Antonakopoulos, Efstratios Panteleimon Skoulakis, Leello Tadesse Dadi, Ali Kavis
2022
Article de conférence
2022
Article de conférence
Résumé
We propose an adaptive variance-reduction method, called AdaSpider, for minimization of L-smooth, non-convex functions with a finite-sum structure. In essence, AdaSpider combines an AdaGrad-inspired [Duchi et al., 2011, McMahan & Streeter, 2010], but a fairly distinct, adaptive step-size schedule with the recursive stochastic path integrated estimator proposed in [Fang et al., 2018]. To our knowledge, Adaspider is the first parameter-free non-convex variance-reduction method in the sense that it does not require the knowledge of problem-dependent parameters, such as smoothness constant L, target accuracy ϵ or any bound on gradient norms. In doing so, we are able to compute an ϵ-stationary point with Õ (n+n‾√/ϵ2) oracle-calls, which matches the respective lower bound up to logarithmic factors.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.
Proximité ontologique
Concepts associés (32)
Algorithme du gradient stochastique
L'algorithme du gradient stochastique est une méthode de descente de gradient (itérative) utilisée pour la minimisation d'une fonction objectif qui est écrite comme une somme de fonctions différentiables. À la fois l'estimation statistique et l'apprentissage automatique s'intéressent au problème de la minimisation d'une fonction objectif qui a la forme d'une somme : où le paramètre qui minimise doit être estimé. Chacune des fonctions est généralement associée avec la -ème observation de l'ensemble des données (utilisées pour l'apprentissage).
Fonction convexe
vignette|upright=1.5|droite|Fonction convexe. En mathématiques, une fonction réelle d'une variable réelle est dite convexe : si quels que soient deux points et du graphe de la fonction, le segment est entièrement situé au-dessus du graphe, c’est-à-dire que la courbe représentative de la fonction se situe toujours en dessous de ses cordes ; ou si l'épigraphe de la fonction (l'ensemble des points qui sont au-dessus de son graphe) est un ensemble convexe ; ou si vu d'en dessous, le graphe de la fonction est en bosse.
Nonlinear dimensionality reduction
Nonlinear dimensionality reduction, also known as manifold learning, refers to various related techniques that aim to project high-dimensional data onto lower-dimensional latent manifolds, with the goal of either visualizing the data in the low-dimensional space, or learning the mapping (either from the high-dimensional space to the low-dimensional embedding or vice versa) itself. The techniques described below can be understood as generalizations of linear decomposition methods used for dimensionality reduction, such as singular value decomposition and principal component analysis.
Publications associées (32)
Universal and adaptive methods for robust stochastic optimization
Within the context of contemporary machine learning problems, efficiency of optimization process depends on the properties of the model and the nature of the data available, which poses a significant problem as the complexity of either increases ad infinit ...
EPFL2023Augmented Lagrangian Methods for Provable and Scalable Machine Learning
Non-convex constrained optimization problems have become a powerful framework for modeling a wide range of machine learning problems, with applications in k-means clustering, large- scale semidefinite programs (SDPs), and various other tasks. As the perfor ...
EPFL2023The statistical complexity of early-stopped mirror descent
Tomas Vaskevicius, Varun Kanade
Recently there has been a surge of interest in understanding implicit regularization properties of iterative gradient-based optimization algorithms. In this paper, we study the statistical guarantees on the excess risk achieved by early-stopped unconstrain ...
Oxford2023MOOCs associés (1)
Introduction to optimization on smooth manifolds: first order methods
Learn to optimize on smooth, nonlinear spaces: Join us to build your foundations (starting at "what is a manifold?") and confidently implement your first algorithm (Riemannian gradient descent).