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

Stochastic Gauss-Newton algorithm with STORM estimators for nonconvex composite optimization

JOURNAL OF APPLIED MATHEMATICS AND COMPUTING 2022年第6期68卷 4621-4643页

作者： Wang, Zhaoxin Wen, Bo Hebei Univ Technol Sch Sci Tianjin Peoples R China Hebei Univ Technol Inst Math Tianjin Peoples R China

In this paper, we propose a new variant of stochastic Gauss-Newton algorithm to solve a broad class of nonconvex composite optimization problems by using stochastic recursive momentum estimators. We first show that the mean-square error bounds on the estimators is bounded. Then, we prove that the oracle complexity of the proposed algorithm is O(epsilon(-2)) in the expectation setting. Moreover, the oracle complexity with high probability in the finite-sum setting is also established as O(epsilon(-2)). Finally, some numerical experiments have been conducted to verify the efficiency of the algorithm.

关键词： Momentum oracle complexity Nonconvex optimization Stochastic optimization

来源：评论

学校读者我要写书评

暂无评论

A Newton Frank-Wolfe method for constrained self-concordant minimization

引用

JOURNAL OF GLOBAL OPTIMIZATION 2022年第2期83卷 273-299页

作者： Liu, Deyi Cevher, Volkan Tran-Dinh, Quoc Univ N Carolina Dept Stat & Operat Res 318 Hanes Hall Chapel Hill NC 27599 USA Ecole Polytech Fed Lausanne Lab Informat & Inference Syst Lausanne Switzerland

We develop a new Newton Frank-Wolfe algorithm to solve a class of constrained self-concordant minimization problems using linear minimization oracles (LMO). Unlike L-smooth convex functions, where the Lipschitz continuity of the objective gradient holds globally, the class of self-concordant functions only has local bounds, making it difficult to estimate the number of linear minimization oracle (LMO) calls for the underlying optimization algorithm. Fortunately, we can still prove that the number of LMO calls of our method is nearly the same as that of the standard Frank-Wolfe method in the L-smooth case. Specifically, our method requires at most O(epsilon-(1+nu)) LMO's, where epsilon is the desired accuracy, and nu is an element of(0,0.139) is a given constant depending on the chosen initial point of the proposed algorithm. Our intensive numerical experiments on three applications: portfolio design with the competitive ratio, D-optimal experimental design, and logistic regression with elastic-net regularizer, show that the proposed Newton Frank-Wolfe method outperforms different state-of-the-art competitors.

关键词： Frank-Wolfe method Inexact projected Newton scheme Self-concordant function Constrained convex optimization oracle complexity

来源：评论

学校读者我要写书评

暂无评论

On the complexity of finding stationary points of smooth functions in one dimension 34

On the complexity of finding stationary points of smooth fun...

引用

34th International Conference on Algorithmic Learning Theory (ALT)

作者： Chewi, Sinho Bubeck, Sebastien Salim, Adil MIT Cambridge MA 02139 USA Microsoft Res Redmond WA USA

We characterize the query complexity of finding stationary points of one-dimensional non-convex but smooth functions. We consider four settings, based on whether the algorithms under consideration are deterministic or randomized, and whether the oracle outputs 1st-order or both 0th- and 1st-order information. Our results show that algorithms for this task provably benefit by incorporating either randomness or 0th-order information. Our results also show that, for every dimension d >= 1, gradient descent is optimal among deterministic algorithms using 1st-order queries only.

关键词： gradient descent non-convex optimization oracle complexity stationary point

来源：评论

学校读者我要写书评

暂无评论

Deterministic Nonsmooth Nonconvex Optimization 36

Deterministic Nonsmooth Nonconvex Optimization

引用

36th Annual Conference on Learning Theory (COLT)

作者： Jordan, Michael I. Kornowski, Guy Lin, Tianyi Shamir, Ohad Zampetakis, Manolis Univ Calif Berkeley Berkeley CA 94720 USA Weizmann Inst Sci Rehovot Israel

We study the complexity of optimizing nonsmooth nonconvex Lipschitz functions by producing (delta, epsilon)-Goldstein stationary points. Several recent works have presented randomized algorithms that produce such points using (O) over tilde(delta(-1)epsilon(-3)) first-order oracle calls, independent of the dimension d. It has been an open problem as to whether a similar result can be obtained via a deterministic algorithm. We resolve this open problem, showing that randomization is necessary to obtain a dimension-free rate. In particular, we prove a lower bound of Omega(d) for any deterministic algorithm. Moreover, we show that unlike smooth or convex optimization, access to function values is required for any deterministic algorithm to halt within any finite time horizon. On the other hand, we prove that if the function is even slightly smooth, then the dimension-free rate of (O) over tilde(delta(-1)epsilon(-3)) can be obtained by a deterministic algorithm with merely a logarithmic dependence on the smoothness parameter. Motivated by these findings, we turn to study the complexity of deterministically smoothing Lipschitz functions. Though there are well-known efficient black-box randomized smoothings, we start by showing that no such deterministic procedure can smooth functions in a meaningful manner (suitably defined), resolving an open question in the literature. We then bypass this impossibility result for the structured case of ReLU neural networks. To that end, in a practical "white-box" setting in which the optimizer is granted access to the network's architecture, we propose a simple, dimension-free, deterministic smoothing of ReLU networks that provably preserves (delta, epsilon)-Goldstein stationary points. Our method applies to a variety of architectures of arbitrary depth, including ResNets and ConvNets. Combined with our algorithm for slightly-smooth functions, this yields the first deterministic, dimension-free algorithm for optimizing ReLU networks, c

关键词： Nonsmooth nonconvex optimization oracle complexity smoothing ReLU networks

来源：评论

学校读者我要写书评

暂无评论

Improved complexities for stochastic conditional gradient methods under interpolation-like conditions

引用

OPERATIONS RESEARCH LETTERS 2022年第2期50卷 184-189页

作者： Xiao, Tesi Balasubramanian, Krishnakumar Ghadimi, Saeed Univ Calif Davis Dept Stat One Shields Ave Davis CA 95616 USA Univ Waterloo Dept Management Sci Waterloo ON Canada

We analyze stochastic conditional gradient methods for constrained optimization problems arising in over-parametrized machine learning. We show that one could leverage the interpolation-like conditions satisfied by such models to obtain improved oracle complexities. Specifically, when the objective function is convex, we show that the conditional gradient method requires O(epsilon(-2)) calls to the stochastic gradient oracle to find an epsilon-optimal solution. Furthermore, by including a gradient sliding step, we show that the number of calls reduces to O(epsilon(-1.5)). (C) 2022 Elsevier B.V. All rights reserved.

关键词： Stochastic conditional gradient oracle complexity Overparametrization Zeroth-order optimization

来源：评论

学校读者我要写书评

暂无评论

Mirror Descent Strikes Again: Optimal Stochastic Convex Optimization under Infinite Noise Variance 35

Mirror Descent Strikes Again: Optimal Stochastic Convex Opti...

引用

35th Conference on Learning Theory (COLT)

作者： Vural, Nuri Mert Yu, Lu Balasubramanian, Krishnakumar Volgushev, Stanislav Erdogdu, Murat A. Univ Toronto Dept Comp Sci Toronto ON Canada Vector Inst Toronto ON Canada Univ Toronto Dept Stat Sci Toronto ON Canada Univ Calif Davis Dept Stat Davis CA 95616 USA

We study stochastic convex optimization under infinite noise variance. Specifically, when the stochastic gradient is unbiased and has uniformly bounded (1+ k)-th moment, for some k is an element of (0;1], we quantify the convergence rate of the Stochastic Mirror Descent algorithm with a particular class of uniformly convex mirror maps, in terms of the number of iterations, dimensionality and related geometric parameters of the optimization problem. Interestingly this algorithm does not require any explicit gradient clipping or normalization, which have been extensively used in several recent empirical and theoretical works. We complement our convergence results with information-theoretic lower bounds showing that no other algorithm using only stochastic first-order oracles can achieve improved rates. Our results have several interesting consequences for devising online/streaming stochastic approximation algorithms for problems arising in robust statistics and machine learning.

关键词： Mirror descent algorithm uniformly convex functions heavy-tailed gradient noise oracle complexity information-theoretic lower bounds

来源：评论

学校读者我要写书评

暂无评论

Smooth Online Learning is as Easy as Statistical Learning 35

Smooth Online Learning is as Easy as Statistical Learning

引用

35th Conference on Learning Theory (COLT)

作者： Block, Adam Dagan, Yuval Golowich, Noah Rakhlin, Alexander MIT Cambridge MA 02139 USA

Much of modern learning theory has been split between two regimes: the classical offline setting, where data arrive independently, and the online setting, where data arrive adversarially. While the former model is often both computationally and statistically tractable, the latter requires no distributional assumptions. In an attempt to achieve the best of both worlds, previous work proposed the smooth online setting where each sample is drawn from an adversarially chosen distribution, which is smooth, i.e., it has a bounded density with respect to a fixed dominating measure. Existing results for the smooth setting were known only for binary-valued function classes and were computationally expensive in general;in this paper, we fill these lacunae. In particular, we provide tight bounds on the minimax regret of learning a nonparametric function class, with nearly optimal dependence on both the horizon and smoothness parameters. Furthermore, we provide the first oracle-efficient, no-regret algorithms in this setting. In particular, we propose an oracle-efficient improper algorithm whose regret achieves optimal dependence on the horizon and a proper algorithm requiring only a single oracle call per round whose regret has the optimal horizon dependence in the classification setting and is sublinear in general. Both algorithms have exponentially worse dependence on the smoothness parameter of the adversary than the minimax rate. We then prove a lower bound on the oracle complexity of any proper learning algorithm, which matches the oracle-efficient upper bounds up to a polynomial factor, thus demonstrating the existence of a statistical-computational gap in smooth online learning. Finally, we apply our results to the contextual bandit setting to show that if a function class is learnable in the classical setting, then there is an oracle-efficient, no-regret algorithm for contextual bandits in the case that contexts arrive in a smooth manner.

关键词： Online Learning Smoothed Analysis oracle complexity

来源：评论

学校读者我要写书评

暂无评论

Stochastic Variance Reduction for Variational Inequality Methods 35

Stochastic Variance Reduction for Variational Inequality Met...

引用

35th Conference on Learning Theory (COLT)

作者： Alacaoglu, Ahmet Malitsky, Yura Univ Wisconsin Madison WI 53706 USA Linkoping Univ Linkoping Sweden

We propose stochastic variance reduced algorithms for solving convex-concave saddle point problems, monotone variational inequalities, and monotone inclusions. Our framework applies to extra-gradient, forward-backward-forward, and forward-reflected-backward methods both in Euclidean and Bregman setups. All proposed methods converge in the same setting as their deterministic counterparts and they either match or improve the best-known complexities for solving structured min-max problems. Our results reinforce the correspondence between variance reduction in variational inequalities and minimization. We also illustrate the improvements of our approach with numerical evaluations on matrix games.

关键词： Variational inequality extragradient stochastic methods variance reduction oracle complexity

来源：评论

学校读者我要写书评

暂无评论

Linear programming using limited-precision oracles

引用

MATHEMATICAL PROGRAMMING 2020年第1-2期183卷 525-554页

作者： Gleixner, Ambros Steffy, Daniel E. Konrad Zuse Zentrum Informat Tech Berlin Takustr 7 D-14195 Berlin Germany Oakland Univ Math & Stat Rochester MI 48309 USA

Since the elimination algorithm of Fourier and Motzkin, many different methods have been developed for solving linear programs. When analyzing the time complexity of LP algorithms, it is typically either assumed that calculations are performed exactly and bounds are derived on the number of elementary arithmetic operations necessary, or the cost of all arithmetic operations is considered through a bit-complexity analysis. Yet in practice, implementations typically use limited-precision arithmetic. In this paper we introduce the idea of a limited-precision LP oracle and study how such an oracle could be used within a larger framework to compute exact precision solutions to LPs. Under mild assumptions, it is shown that a polynomial number of calls to such an oracle and a polynomial number of bit operations, is sufficient to compute an exact solution to an LP. This work provides a foundation for understanding and analyzing the behavior of the methods that are currently most effective in practice for solving LPs exactly.

关键词： Linear programming oracle complexity Diophantine approximation Exact solutions Symbolic computation rational arithmetic Extended-precision arithmetic Iterative refinement

来源：评论

学校读者我要写书评

暂无评论

An Infeasible Stochastic Approximation and Projection Algorithm for Stochastic Variational Inequalities

引用

JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS 2019年第3期183卷 1053-1076页

作者： Zhang, Xiao-Juan Du, Xue-Wu Yang, Zhen-Ping Lin, Gui-Hua Chongqing Univ Posts & Telecommun Coll Mobile Telecommun Chongqing 400065 Peoples R China Chongqing Normal Univ Coll Math Sci Chongqing 401131 Peoples R China Shanghai Univ Sch Management Shanghai 200444 Peoples R China

In this paper, we consider a stochastic variational inequality, in which the mapping involved is an expectation of a given random function. Inspired by the work of He (Appl Math Optim 35:69-76, 1997) and the extragradient method proposed by Iusem et al. (SIAM J Optim 29:175-206, 2019), we propose an infeasible projection algorithm with line search scheme, which can be viewed as a modification of the above-mentioned method of Iusem et al. In particular, in the correction step, we replace the projection by computing search direction and stepsize, that is, we need only one projection at each iteration, while the method of Iusem et al. requires two projections at each iteration. Moreover, we use dynamic sampled scheme with line search to cope with the absence of Lipschitz constant and choose the stepsize to be bounded away from zero and the direction to be a descent direction. In the process of stochastic approximation, we iteratively reduce the variance of a stochastic error. Under appropriate assumptions, we derive some properties related to convergence, convergence rate, and oracle complexity. In particular, compared with the method of Iusem et al., our method uses less projections and has the same iteration complexity, which, however, has a higher oracle complexity for a given tolerance in a finite dimensional space. Finally, we report some numerical experiments to show its efficiency.

关键词： Stochastic variational inequality Infeasible projection algorithm Stochastic approximation Convergence rate oracle complexity

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：