检索结果-内蒙古大学图书馆

Optimal Convergence for Distributed Learning with stochastic gradient methods and Spectral Algorithms

JOURNAL OF MACHINE LEARNING RESEARCH 2020年第1期21卷 1-63页

作者： Lin, Junhong Cevher, Volkan Zhejiang Univ Ctr Data Sci Hangzhou 310027 Peoples R China Ecole Polytech Fed Lausanne Lab Informat & Inference Syst CH-1015 Lausanne Switzerland

We study generalization properties of distributed algorithms in the setting of nonparametric regression over a reproducing kernel Hilbert space (RKHS). We first investigate distributed stochastic gradient methods (SGM), with mini-batches and multi-passes over the data. We show that optimal generalization error bounds (up to logarithmic factor) can be retained for distributed SGM provided that the partition level is not too large. We then extend our results to spectral algorithms (SA), including kernel ridge regression (KRR), kernel principal component regression, and gradient methods. Our results show that distributed SGM has a smaller theoretical computational complexity, compared with distributed KRR and classic SGM. Moreover, even for a general non-distributed SA, they provide optimal, capacity-dependent convergence rates, for the case that the regression function may not be in the RKHS in the well-conditioned regimes.

关键词： Kernel methods stochastic gradient methods Regularization Distributed Learning

来源：评论

学校读者我要写书评

暂无评论

Convergences of Regularized Algorithms and stochastic gradient methods with Random Projections

引用

JOURNAL OF MACHINE LEARNING RESEARCH 2020年第1期21卷 1-44页

作者： Lin, Junhong Cevher, Volkan Zhejiang Univ Ctr Data Sci Hangzhou 310027 Peoples R China Ecole Polytech Fed Lausanne Lab Informat & Inference Syst CH-1015 Lausanne Switzerland

We study the least-squares regression problem over a Hilbert space, covering nonparametric regression over a reproducing kernel Hilbert space as a special case. We first investigate regularized algorithms adapted to a projection operator on a closed subspace of the Hilbert space. We prove convergence results with respect to variants of norms, under a capacity assumption on the hypothesis space and a regularity condition on the target function. As a result, we obtain optimal rates for regularized algorithms with randomized sketches, provided that the sketch dimension is proportional to the effective dimension up to a logarithmic factor. As a byproduct, we obtain similar results for Nystrom regularized algorithms. Our results provide optimal, distribution-dependent rates that do not have any saturation effect for sketched/Nystrom regularized algorithms, considering both the attainable and non-attainable cases, in the well-conditioned regimes. We then study stochastic gradient methods with projection over the subspace, allowing multi-pass over the data and minibatches, and we derive similar optimal statistical convergence results.

关键词： kernel methods regularized algorithms stochastic gradient methods random projection sketching

来源：评论

学校读者我要写书评

暂无评论

Ritz-like values in steplength selections for stochastic gradient methods

引用

SOFT COMPUTING 2020年第23期24卷 17573-17588页

作者： Franchini, Giorgia Ruggiero, Valeria Zanni, Luca Univ Modena & Reggio Emilia Dept Phys Informat & Math Modena Italy Univ Ferrara Dept Math & Comp Sci Ferrara Italy

The steplength selection is a crucial issue for the effectiveness of the stochastic gradient methods for large-scale optimization problems arising in machine learning. In a recent paper, Bollapragada et al. (SIAM J Optim 28(4):3312-3343, 2018) propose to include an adaptive subsampling strategy into a stochastic gradient scheme, with the aim to assure the descent feature in expectation of the stochastic gradient directions. In this approach, theoretical convergence properties are preserved under the assumption that the positive steplength satisfies at any iteration a suitable bound depending on the inverse of the Lipschitz constant of the objective function gradient. In this paper, we propose to tailor for the stochastic gradient scheme the steplength selection adopted in the full-gradient method knows as limited memory steepest descent method. This strategy, based on the Ritz-like values of a suitable matrix, enables to give a local estimate of the inverse of the local Lipschitz parameter, without introducing line search techniques, while the possible increase in the size of the subsample used to compute the stochastic gradient enables to control the variance of this direction. An extensive numerical experimentation highlights that the new rule makes the tuning of the parameters less expensive than the trial procedure for the efficient selection of a constant step in standard and mini-batch stochastic gradient methods.

关键词： stochastic gradient methods Learning rate selection rule Ritz-like values Adaptive subsampling strategies Reduction variance techniques

来源：评论

学校读者我要写书评

暂无评论

Thresholding Procedure via Barzilai-Borwein Rules for the Steplength Selection in stochastic gradient methods 7th

Thresholding Procedure via Barzilai-Borwein Rules for the St...

引用

7th International Conference on Machine Learning, Optimization, and Data Science (LOD) / 1st Symposium on Artificial Intelligence and Neuroscience (ACAIN)

作者： Franchini, Giorgia Ruggiero, Valeria Trombini, Ilaria Univ Ferrara Dept Math & Comp Sci Ferrara Italy

ISBN: (纸本)9783030954703;9783030954697

A crucial aspect in designing a learning algorithm is the selection of the hyperparameters (parameters that are not trained during the learning process). In particular the effectiveness of the stochastic gradient methods strongly depends on the steplength selection. In recent papers [9,10], Franchini et al. propose to adopt an adaptive selection rule borrowed from the full-gradient scheme known as Limited Memory Steepest Descent method [8] and appropriately tailored to the stochastic framework. This strategy is based on the computation of the eigenvalues (Ritz-like values) of a suitable matrix obtained from the gradients of the most recent iterations, and it enables to give an estimation of the local Lipschitz constant of the current gradient of the objective function, without introducing line-search techniques. The possible increase of the size of the sub-sample used to compute the stochastic gradient is driven by means of an augmented inner product test approach [3]. The whole procedure makes the tuning of the parameters less expensive than the selection of a fixed steplength, although it remains dependent on the choice of threshold values bounding the variability of the steplength sequences. The contribution of this paper is to exploit a stochastic version of the Barzilai-Borwein formulas [1] to adaptively select the endpoints range for the Ritz-like values. A numerical experimentation for some convex loss functions highlights that the proposed procedure remains stable as well as the tuning of the hyperparameters appears less expensive.

关键词： stochastic gradient methods Learning rate selection rule Barzilai-Borwein rules Adaptive sub-sampling strategies Reduction variance techniques

来源：评论

学校读者我要写书评

暂无评论

On the Steplength Selection in stochastic gradient methods 3rd

On the Steplength Selection in Stochastic Gradient Methods

引用

3rd International Conference on Numerical Computations - Theory and Algorithms (NUMTA)

作者： Franchini, Giorgia Ruggiero, Valeria Zanni, Luca Univ Modena & Reggio Emilia Dept Phys Informat & Math Modena Italy Univ Ferrara Dept Math & Comp Sci Ferrara Italy INdAM Res Grp GNCS Rome Italy

ISBN: (纸本)9783030390815

This paper deals with the steplength selection in stochastic gradient methods for large scale optimization problems arising in machine learning. We introduce an adaptive steplength selection derived by tailoring a limited memory steplength rule, recently developed in the deterministic context, to the stochastic gradient approach. The proposed steplength rule provides values within an interval, whose bounds need to be prefixed by the user. A suitable choice of the interval bounds allows to perform similarly to the standard stochastic gradient method equipped with the best-tuned steplength. Since the setting of the bounds slightly affects the performance, the new rule makes the tuning of the parameters less expensive with respect to the choice of the optimal prefixed steplength in the standard stochastic gradient method. We evaluate the behaviour of the proposed steplength selection in training binary classifiers on well known data sets and by using different loss functions.

关键词： stochastic gradient methods Steplength selection rule Ritz-like values Machine learning

来源：评论

学校读者我要写书评

暂无评论

Optimization of complex simulation models with stochastic gradient methods 16

Optimization of complex simulation models with stochastic gr...

引用

International Conference on High Performance Computing & Simulation (HPCS)

作者： Gaivoronski, Alexei A. Norwegian Univ Sci & Technol Dept Ind Econ & Technol Management Trondheim Norway

ISBN: (纸本)9781538678794

We describe the structure of stochastic optimization solver SQG (stochastic Quasigradient), which implements stochastic gradient methods for optimization of complex stochastic simulation models. The solver finds the equilibrium solution when the simulation model describes the system with several actors. The solver is parallelizable and it performs several simulation threads in parallel. It is capable of solving stochastic optimization problems, finding stochastic Nash equilibria, stochastic bilevel problems where each level may require the solution of stochastic optimization problem or finding Nash equilibrium. We provide several complex examples with applications to water resources management, energy markets, pricing of services on social networks.

关键词： stochactic optimization stochastic equilibrium optimization of simulation models stochastic gradient methods

来源：评论

学校读者我要写书评

暂无评论

Stability and Differential Privacy of stochastic gradient methods

Stability and Differential Privacy of Stochastic Gradient Me...

引用

作者： Yang, Zhenhuan State University of New York at Albany

学位级别：Ph.D., Doctor of Philosophy

Recently there are a considerable amount of work devoted to the study of the algorithmic stability as well as differential privacy (DP) for stochastic gradient methods (SGM). However, most of the existing work focus on the empirical risk minimization (ERM) and the population risk minimization problems. In this paper, we study two types of optimization problems that enjoy wide applications in modern machine learning, namely the minimax problem and the pairwise learning problem. For minimax problem, we establish a quantitative connection between stability and generalization for minimax learners in different forms including weak/strong primal-dual generalization, primal generalization and generalization with high probability. For the technical contributions, we introduce novel decompositions to handle the correlation between the primal model and dual model for connecting stability and generalization. We establish stability bounds of stochastic gradient descent ascent (SGDA) for convex-concave problems, from which we derive its optimal population risk bounds under an appropriate early-stopping strategy. We consider several measures of generalization and show that the optimal population risk bounds can be derived even in the nonsmooth case. To the best of our knowledge, our results are the first-ever known population risk bounds for minimax problems in the nonsmooth setting and the high-probability format. We further extend our analysis to the nonconvex-nonconcave setting and give the first generalization bounds for nonsmooth objective functions. Our analysis relaxes the range of step size for a controllable stability and implies meaningful primal population risk bounds under some regularity assumptions of objective functions, e.g., a decay of weak-convexity-weak-concavity parameter along the optimization process or a two-sided Polyak-Łojasiewicz (PL) condition. We analyze the privacy and utility of differentially private stochastic gradient descent ascent (DP-SGDA) unde

关键词： Algorithmic stability Differential privacy Minimax problems Pairwise learning stochastic gradient methods

来源：评论

学校读者我要写书评

暂无评论

Learning rate selection in stochastic gradient methods based on line search strategies

引用

APPLIED MATHEMATICS IN SCIENCE AND ENGINEERING 2023年第1期31卷

作者： Franchini, Giorgia Porta, Federica Ruggiero, Valeria Trombini, Ilaria Zanni, Luca Univ Modena & Reggio Emilia Dept Phys Informat & Math Via Campi 213-13 I-41125 Modena MO Italy Univ Ferrara Dept Math & Comp Sci Ferrara Italy Univ Parma Dept Math Phys & Comp Sci Parma Italy

Finite-sum problems appear as the sample average approximation of a stochastic optimization problem and often arise in machine learning applications with large scale data sets. A very popular approach to face finite-sum problems is the stochastic gradient method. It is well known that a proper strategy to select the hyperparameters of this method (i.e. the set of a-priori selected parameters) and, in particular, the learning rate, is needed to guarantee convergence properties and good practical performance. In this paper, we analyse standard and line search based updating rules to fix the learning rate sequence, also in relation to the size of the mini batch chosen to compute the current stochastic gradient. An extensive numerical experimentation is carried out in order to evaluate the effectiveness of the discussed strategies for convex and non-convex finite-sum test problems, highlighting that the line search based methods avoid expensive initial setting of the hyperparameters. The line search based approaches have also been applied to train a Convolutional Neural Network, providing very promising results.

关键词： stochastic gradient methods variance reduced methods learning rate selection mini batch size selection convolutional neural networks

来源：评论

学校读者我要写书评

暂无评论

Optimal convergence for distributed learning with stochastic gradient methods and spectral algorithms

The Journal of Machine Learning Research

引用

The Journal of Machine Learning Research 2020年第1期21卷 5852-5914页

作者： Junhong Lin Volkan Cevher Center for Data Science Zhejiang University Hang Zhou P. R. China. and Laboratory for Information and Inference Systems École Polytechnique Fédérale de Lausanne Lausanne Switzerland Laboratory for Information and Inference Systems École Polytechnique Fédérale de Lausanne Lausanne Switzerland

关键词： kernel methods stochastic gradient methods regularization distributed learning

来源：评论

学校读者我要写书评

暂无评论

Convergences of regularized algorithms and stochastic gradient methods with random projections

The Journal of Machine Learning Research

引用

The Journal of Machine Learning Research 2020年第1期21卷 690-733页

We study the least-squares regression problem over a Hilbert space, covering nonparametric regression over a reproducing kernel Hilbert space as a special case. We first investigate regularized algorithms adapted to a projection operator on a closed subspace of the Hilbert space. We prove convergence results with respect to variants of norms, under a capacity assumption on the hypothesis space and a regularity condition on the target function. As a result, we obtain optimal rates for regularized algorithms with randomized sketches, provided that the sketch dimension is proportional to the effective dimension up to a logarithmic factor. As a byproduct, we obtain similar results for Nyström regularized algorithms. Our results provide optimal, distribution-dependent rates that do not have any saturation effect for sketched/Nyström regularized algorithms, considering both the attainable and non-attainable cases, in the well-conditioned regimes. We then study stochastic gradient methods with projection over the subspace, allowing multi-pass over the data and minibatches, and we derive similar optimal statistical convergence results.

关键词： kernel methods regularized algorithms stochastic gradient methods random projection sketching

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：