Distributed stochastic zeroth-order optimization(DSZO),in which the objective function is allocated over multiple agents and the derivative of cost functions is unavailable,arises frequently in large-scale machine lea...Distributed stochastic zeroth-order optimization(DSZO),in which the objective function is allocated over multiple agents and the derivative of cost functions is unavailable,arises frequently in large-scale machine learning and reinforcement learning.This paper introduces a distributed stochastic algorithm for DSZO in a projection-free and gradient-free manner via the Frank-Wolfe framework and the stochastic zeroth-order oracle(SZO).Such a scheme is particularly useful in large-scale constrained optimization problems where calculating gradients or projection operators is impractical,costly,or when the objective function is not differentiable everywhere.Specifically,the proposed algorithm,enhanced by recursive momentum and gradient tracking techniques,guarantees convergence with just a single batch per iteration.This significant improvement over existing algorithms substantially lowers the computational complexity.Under mild conditions,we prove that the complexity bounds on SZO of the proposed 1 algorithm are O(n/ϵ^(2))andO(n(21/ϵ))for convex and nonconvex cases,respectively.The efficacy of the algorithm is verified on black-box binary classification problems against several competing alternatives.展开更多
In this paper,we consider the distributed online optimization problem on a time-varying network,where each agent on the network has its own time-varying objective function and the goal is to minimize the overall loss ...In this paper,we consider the distributed online optimization problem on a time-varying network,where each agent on the network has its own time-varying objective function and the goal is to minimize the overall loss accumulated.Moreover,we focus on distributed algorithms which do not use gradient information and projection operators to improve the applicability and computational efficiency.By introducing the deterministic differences and the randomized differences to substitute the gradient information of the objective functions and removing the projection operator in the traditional algorithms,we design two kinds of gradient-free distributed online optimization algorithms without projection step,which can economize considerable computational resources as well as has less limitations on the applicability.We prove that both of two algorithms achieves consensus of the estimates and regrets of\(O\left(\log(T)\right)\)for local strongly convex objective,respectively.Finally,a simulation example is provided to verify the theoretical results.展开更多
基金supported by the National Natural Science Foundation of China under Grant Nos.62222303,62073035,and 62088101.
文摘Distributed stochastic zeroth-order optimization(DSZO),in which the objective function is allocated over multiple agents and the derivative of cost functions is unavailable,arises frequently in large-scale machine learning and reinforcement learning.This paper introduces a distributed stochastic algorithm for DSZO in a projection-free and gradient-free manner via the Frank-Wolfe framework and the stochastic zeroth-order oracle(SZO).Such a scheme is particularly useful in large-scale constrained optimization problems where calculating gradients or projection operators is impractical,costly,or when the objective function is not differentiable everywhere.Specifically,the proposed algorithm,enhanced by recursive momentum and gradient tracking techniques,guarantees convergence with just a single batch per iteration.This significant improvement over existing algorithms substantially lowers the computational complexity.Under mild conditions,we prove that the complexity bounds on SZO of the proposed 1 algorithm are O(n/ϵ^(2))andO(n(21/ϵ))for convex and nonconvex cases,respectively.The efficacy of the algorithm is verified on black-box binary classification problems against several competing alternatives.
文摘In this paper,we consider the distributed online optimization problem on a time-varying network,where each agent on the network has its own time-varying objective function and the goal is to minimize the overall loss accumulated.Moreover,we focus on distributed algorithms which do not use gradient information and projection operators to improve the applicability and computational efficiency.By introducing the deterministic differences and the randomized differences to substitute the gradient information of the objective functions and removing the projection operator in the traditional algorithms,we design two kinds of gradient-free distributed online optimization algorithms without projection step,which can economize considerable computational resources as well as has less limitations on the applicability.We prove that both of two algorithms achieves consensus of the estimates and regrets of\(O\left(\log(T)\right)\)for local strongly convex objective,respectively.Finally,a simulation example is provided to verify the theoretical results.
