6 papers
High-Probability Last-Iterate Guarantees for Two-Point Gaussian Zeroth-Order Stochastic Gradient Descent
Haishan Ye
We establish a direct high-probability last-iterate guarantee for the standard same-sample two-point Gaussian zeroth-order SGD method in smooth, strongly convex stochastic optimiza…
Logarithmic High-Probability Regret for Online Convex Optimization with Two-Point Bandit Feedback
Haishan Ye
We study online convex optimization (OCO) with two-point bandit feedback against a non-anticipating adaptive adversary. In this setting, a learner competes with an adversarial sequ…
High-Probability Guarantees for Random Zeroth-Order Gradient Descent on Smooth Functions
Haishan Ye
Randomized zeroth-order methods are classically analyzed in expectation, but a black-box Markov conversion can give misleading high-probability guarantees, in particular by forcing…
High-Probability Guarantees for Random Zeroth-Order (Stochastic) Gradient Descent
Haishan Ye
Zeroth-order optimization aims to minimize an objective function using only function evaluations, and is therefore fundamental in black-box optimization, hyperparameter tuning, ban…
Stochastic Non-Smooth Non-Convex Optimization with Decision-Dependent Distributions
Chengchang Liu, Zongqi Wan, Haishan Ye +1
We study stochastic zeroth-order optimization with decision-dependent distributions, where the sampling law depends on the current decision and only noisy function values are avail…
On the Complexity of Decentralized Smooth Nonconvex Finite-Sum Optimization
Luo Luo, Yunyan Bai, Lesi Chen +2
We study the decentralized optimization problem , where the local function on the -th a…