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

Stochastic conditional gradient methods: From Convex Minimization to Submodular Maximization

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

作者： Mokhtari, Aryan Hassani, Hamed Karbasi, Amin Univ Texas Austin Dept Elect & Comp Engn Austin TX 78712 USA Univ Penn Dept Elect & Syst Engn Philadelphia PA 19104 USA Yale Univ Dept Elect Engn & Comp Sci New Haven CT 06520 USA

This paper considers stochastic optimization problems for a large class of objective functions, including convex and continuous submodular. Stochastic proximal gradient methods have been widely used to solve such problems;however, their applicability remains limited when the problem dimension is large and the projection onto a convex set is computationally costly. Instead, stochastic conditional gradient algorithms are proposed as an alternative solution which rely on (i) Approximating gradients via a simple averaging technique requiring a single stochastic gradient evaluation per iteration;(ii) Solving a linear program to compute the descent/ascent direction. The gradient averaging technique reduces the noise of gradient approximations as time progresses, and replacing projection step in proximal methods by a linear program lowers the computational complexity of each iteration. We show that under convexity and smoothness assumptions, our proposed stochastic conditional gradient method converges to the optimal objective function value at a sublinear rate of O(1/t(1/3)). Further, for a monotone and continuous DR-submodular function and subject to a general convex body constraint, we prove that our proposed method achieves a ((1-1/e)OPT-epsilon) guarantee (in expectation) with O(1/epsilon(3)) stochastic gradient computations. This guarantee matches the known hardness results and closes the gap between deterministic and stochastic continuous submodular maximization. Additionally, we achieve ((1/e)OPT-epsilon) guarantee after operating on O(1/epsilon(3)) stochastic gradients for the case that the objective function is continuous DR-submodular but non-monotone and the constraint set is a down-closed convex body. By using stochastic continuous optimization as an interface, we also provide the first (1-1/e) tight approximation guarantee for maximizing a monotone but stochastic submodular set function subject to a general matroid constraint and (1/e) approximation guarantee

关键词： Stochastic optimization conditional gradient methods convex minimization submodular maximization gradient averaging Frank-Wolfe algorithm greedy algorithm

来源：评论

学校读者我要写书评

暂无评论

Stochastic conditional gradient methods: from convex minimization to submodular maximization

The Journal of Machine Learning Research

引用

The Journal of Machine Learning Research 2020年第1期21卷 4232-4280页

作者： Aryan Mokhtari Hamed Hassani Amin Karbasi Department of Electrical and Computer Engineering The University of Texas at Austin Austin TX Department of Electrical and Systems Engineering University of Pennsylvania Philadelphia PA Department of Electrical Engineering and Computer Science Yale University New Haven CT

This paper considers stochastic optimization problems for a large class of objective functions, including convex and continuous submodular. Stochastic proximal gradient methods have been widely used to solve such problems; however, their applicability remains limited when the problem dimension is large and the projection onto a convex set is computationally costly. Instead, stochastic conditional gradient algorithms are proposed as an alternative solution which rely on (i) Approximating gradients via a simple averaging technique requiring a single stochastic gradient evaluation per iteration; (ii) Solving a linear program to compute the descent/ascent direction. The gradient averaging technique reduces the noise of gradient approximations as time progresses, and replacing projection step in proximal methods by a linear program lowers the computational complexity of each iteration. We show that under convexity and smoothness assumptions, our proposed stochastic conditional gradient method converges to the optimal objective function value at a sublinear rate of O(1/t1/3). Further, for a monotone and continuous DR-submodular function and subject to a general convex body constraint, we prove that our proposed method achieves a ((1 - 1/e)OPT - ε) guarantee (in expectation) with O(1/ε3) stochastic gradient computations. This guarantee matches the known hardness results and closes the gap between deterministic and stochastic continuous submodular maximization. Additionally, we achieve ((1/e)OPT - ε) guarantee after operating on O(1/ε3) stochastic gradients for the case that the objective function is continuous DR-submodular but nonmonotone and the constraint set is a down-closed convex body. By using stochastic continuous optimization as an interface, we also provide the first (1 - 1/e) tight approximation guarantee for maximizing a monotone but stochastic submodular set function subject to a general matroid constraint and (1/e) approximation guarantee for the non-monotone

关键词： stochastic optimization conditional gradient methods convex minimization submodular maximization gradient averaging Frank-Wolfe algorithm greedy algorithm

来源：评论

学校读者我要写书评

暂无评论

Extremal Points and Sparse Optimization for Generalized Kantorovich-Rubinstein Norms

引用

FOUNDATIONS OF COMPUTATIONAL MATHEMATICS 2025年第1期25卷 103-144页

作者： Carioni, Marcello Iglesias, Jose A. Walter, Daniel Univ Twente Dept Appl Math NL-7500AE Enschede Netherlands Humboldt Univ Inst Math D-10117 Berlin Germany

A precise characterization of the extremal points of sublevel sets of nonsmooth penalties provides both detailed information about minimizers, and optimality conditions in general classes of minimization problems involving them. Moreover, it enables the application of fully corrective generalized conditional gradient methods for their efficient solution. In this manuscript, this program is adapted to the minimization of a smooth convex fidelity term which is augmented with an unbalanced transport regularization term given in the form of a generalized Kantorovich-Rubinstein norm for Radon measures. More precisely, we show that the extremal points associated to the latter are given by all Dirac delta functionals supported in the spatial domain as well as certain dipoles, i.e., pairs of Diracs with the same mass but with different signs. Subsequently, this characterization is used to derive precise first-order optimality conditions as well as an efficient solution algorithm for which linear convergence is proved under natural assumptions. This behavior is also reflected in numerical examples for a model problem.

关键词： Extremal points Unbalanced optimal transport Sparse optimization conditional gradient methods Inverse problems Optimal design Kantorovich-Rubinstein duality

来源：评论

学校读者我要写书评

暂无评论

Decentralized Randomized Block-Coordinate Frank-Wolfe Algorithms for Submodular Maximization Over Networks

引用

IEEE TRANSACTIONS ON SYSTEMS MAN CYBERNETICS-SYSTEMS 2022年第8期52卷 5081-5091页

作者： Zhang, Mingchuan Zhou, Yangfan Ge, Quanbo Zheng, Ruijuan Wu, Qingtao Henan Univ Sci & Technol Sch Informat Engn Luoyang 471023 Peoples R China Tongji Univ Sch Elect & Informat Engn Shanghai 200092 Peoples R China

We consider decentralized large-scale continuous submodular constrained optimization problems over networks, where the goal is to maximize a sum of nonconvex functions with diminishing returns property. However, the computations of the projection step and the whole gradient can become prohibitive in high-dimensional constrained optimization problems. For this reason, a decentralized randomized block-coordinate Frank-Wolfe algorithm is proposed for submoduar maximization over networks by local communication and computation, which adopts the randomized block-coordinate descent and the Frank-Wolfe technique. We also show that the proposed algorithm converges to an approximation fact (1-e(-pmax)/(pmin)) of the global maximal points at a rate of O(1/T) by choosing a suitable stepsize, where T is the number of iterations. In addition, we confirm the theoretical results by experiments.

关键词： Optimization Approximation algorithms Heuristic algorithms Convergence Greedy algorithms Linear programming Germanium conditional gradient methods decentralized optimization randomized block-coordinate descent submodular maximization

来源：评论

学校读者我要写书评

暂无评论

Zeroth-Order Nonconvex Stochastic Optimization: Handling Constraints, High Dimensionality, and Saddle Points

引用

FOUNDATIONS OF COMPUTATIONAL MATHEMATICS 2022年第1期22卷 35-76页

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

In this paper, we propose and analyze zeroth-order stochastic approximation algorithms for nonconvex and convex optimization, with a focus on addressing constrained optimization, high-dimensional setting, and saddle point avoiding. To handle constrained optimization, we first propose generalizations of the conditional gradient algorithm achieving rates similar to the standard stochastic gradient algorithm using only zeroth-order information. To facilitate zeroth-order optimization in high dimensions, we explore the advantages of structural sparsity assumptions. Specifically, (i) we highlight an implicit regularization phenomenon where the standard stochastic gradient algorithm with zeroth-order information adapts to the sparsity of the problem at hand by just varying the step size and (ii) propose a truncated stochastic gradient algorithm with zeroth-order information, whose rate of convergence depends only poly-logarithmically on the dimensionality. We next focus on avoiding saddle points in nonconvex setting. Toward that, we interpret the Gaussian smoothing technique for estimating gradient based on zeroth-order information as an instantiation of first-order Stein's identity. Based on this, we provide a novel linear-(in dimension) time estimator of the Hessian matrix of a function using only zeroth-order information, which is based on second-order Stein's identity. We then provide a zeroth-order variant of cubic regularized Newton method for avoiding saddle points and discuss its rate of convergence to local minima.

关键词： Zeroth-order methods Nonconvex optimization Stochastic optimization Complexity bounds conditional gradient methods Newton method

来源：评论

学校读者我要写书评

暂无评论

Scalable Convex Optimization methods for Semidefinite Programming

Scalable Convex Optimization Methods for Semidefinite Progra...

引用

作者： Alp YURTSEVER ECOLE POLYTECHNIQUE FEDERALE DE LAUSNNE

学位级别：博士

With the ever-growing data sizes along with the increasing complexity of the modern problem formulations, contemporary applications in science and engineering impose heavy compu- tational and storage burdens on the optimization algorithms. As a result, there is a recent trend where heuristic approaches with unverifiable assumptions are overtaking more rigorous, conventional methods at the expense of robustness and reproducibility. My recent research results show that this trend can be overturned when we jointly exploit dimensionality reduction and adaptivity in optimization at its core. I contend that even the classical convex optimization did not reach yet its limits of scalability. Many applications in signal processing and machine learning cast a fitting problem from limited data, introducing spatial priors to be able to solve these otherwise ill-posed problems. Data is small, the solution is compact, but the search space is high in dimensions. These problems clearly suffer from the wasteful use of storage resources by the classical optimization algorithms. This problem is prevalent. Storage is a critical bottleneck that prevents us from solving many important large-scale optimization problems. For example, semidefinite programs (SDP) often have low-rank solutions. However, SDP algorithms require us to store a matrix decision variable in the ambient dimensions. This dissertation presents a convex optimization paradigm which makes it possible to solve trillion dimensional SDP relaxations to combinatorial decision problems on a regular personal computer. The key idea is to use an optimization procedure that performs compact updates, and to maintain only a small sketch of the decision variable. Once the iterations terminate, we can recover an approximate solution from the information stored in this sketch. We start by formalizing this idea for a model problem with low-rank solutions. Based on the classical conditional gradient method, we propose the first convex opt

关键词： Convex optimization semidefinite programming low-rank matrix optimization primal-dual methods conditional gradient methods low-rank matrix sketching

来源：评论

学校读者我要写书评

暂无评论

A LINEARLY CONVERGENT VARIANT OF THE conditional gradient ALGORITHM UNDER STRONG CONVEXITY, WITH APPLICATIONS TO ONLINE AND STOCHASTIC OPTIMIZATION

引用

SIAM JOURNAL ON OPTIMIZATION 2016年第3期26卷 1493-1528页

作者： Garber, Dan Hazan, Elad Toyota Technol Inst Chicago 6045 S Kenwood Ave Chicago IL 60637 USA Princeton Univ Dept Comp Sci Princeton NJ 08540 USA

Linear optimization is many times algorithmically simpler than nonlinear convex optimization. Linear optimization over matroid polytopes, matching polytopes, and path polytopes are examples of problems for which we have simple and efficient combinatorial algorithms but whose nonlinear convex counterpart is harder and admits significantly less efficient algorithms. This motivates the computational model of convex optimization, including the offline, online, and stochastic settings, using a linear optimization oracle. In this computational model we give several new results that improve on the previous state of the art. Our main result is a novel conditional gradient algorithm for smooth and strongly convex optimization over polyhedral sets that performs only a single linear optimization step over the domain on each iteration and enjoys a linear convergence rate. This gives an exponential improvement in convergence rate over previous results. Based on this new conditional gradient algorithm we give the first algorithms for online convex optimization over polyhedral sets that perform only a single linear optimization step over the domain while having optimal regret guarantees, answering an open question of Kalai and Vempala and of Hazan and Kale. Our online algorithms also imply conditional gradient algorithms for nonsmooth and stochastic convex optimization with the same convergence rates as projected (sub)gradient methods.

关键词： Frank-Wolfe algorithm conditional gradient methods linear programming first-order methods online convex optimization online learning stochastic optimization

来源：评论

学校读者我要写书评

暂无评论

A FEASIBLE DIRECTIONS ALGORITHM FOR TIME-LAG OPTIMAL-CONTROL PROBLEMS WITH CONTROL AND TERMINAL INEQUALITY CONSTRAINTS

引用

JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS 1985年第3期46卷 295-317页

作者： TEO, KL WONG, KH CLEMENTS, DJ UNIV WITWATERSRAND DEPT APPL MATHJOHANNESBURG 2001SOUTH AFRICA UNIV NEW S WALES SCH ELECT ENGN & COMP SCIKENSINGTONNSW 2033AUSTRALIA

A computational algorithm for a class of time-lag optimal control problems involving control and terminal inequality constraints is presented. The convergence properties of the algorithm is also investigated. To test ... 详细信息

关键词： Nonlinear time-lag systems linear control constraints nonlinear terminal inequality constraints conditional gradient methods feasible direction methods control parametrization initial feasible control computational schemes finite convergence

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：