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 g…
On-device research index
arXiv research
A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
168,742 papers · 148 categories
Trend · papers per month
48 results for “zeroth-order algorithms”
New method for zeroth-order stochastic gradient algorithms provides confidence intervals.
problem Lack of inferential capabilities for zeroth-order stochastic gradient algorithms.
method Established central limit theorem and provided online estimators for asymptotic covariance matrix.
result Asymptotically valid confidence sets for parameter estimation and prediction.
Zeroth-order optimization methods lack inherent privacy guarantees.
problem Ensuring differential privacy in zeroth-order optimization methods.
method Analyzing ZO-GD with and without random initialization for convex and strongly convex objectives.
result ZO-GD is not differentially private for strongly convex objectives and can have superlinear privacy loss.
Zeroth-order optimization is an important research topic in machine learning. In recent years, it has become a key tool in black-box adversarial attack to neural network based image classifiers. However, existing zeroth-order optimization algorithms rarely extract second-order information of the model function. In this…
Two algorithms solve nonconvex minimax problems with linear constraints, achieving complexity guarantees.
problem Nonconvex minimax problems with coupled linear constraints.
method Zeroth-order primal-dual alternating projected gradient (ZO-PDAPG) and zeroth-order regularized momentum primal-dual projected gradient (ZO-RMPDPG) algorithms.
result Iteration complexity guarantees for solving nonconvex-(strongly) concave minimax problems with coupled linear constraints.
Improved zeroth-order algorithms for nonconvex optimization with reduced complexity and improved performance.
problem Designing efficient zeroth-order algorithms for nonconvex optimization with reduced function query complexities and improved convergence rates.
method Proposed new algorithms ZO-SVRG-Coord-Rand and ZO-SPIDER-Coord, developed new analyses, and addressed issues of function query complexities and stepsize generation.
result New algorithms outperform existing methods in terms of function query complexities and convergence rates.
Improved zeroth-order algorithms tackle nonconvex minimax problems with reduced complexity.
problem Nonconvex minimax optimization problems in machine learning.
method Design and analysis of Zeroth-Order Gradient Descent Ascent ( exttt{ZO-GDA}) and Zeroth-Order Gradient Descent Multi-Step Ascent ( exttt{ZO-GDMSA}) algorithms.
result Oracle complexity improvements for minimax optimization problems.
We consider the problem of optimizing a high-dimensional convex function using stochastic zeroth-order queries. Under sparsity assumptions on the gradients or function values, we present two algorithms: a successive component/feature selection algorithm and a noisy mirror descent algorithm using Lasso gradient estimate…
Improves zeroth-order optimization for private machine learning with public data.
problem High computation and memory cost of first-order DP methods.
method PAZO (Public Data Assisted Zeroth-order Optimization) framework.
result Achieves superior privacy/utility tradeoffs across tasks.
New algorithm tackles risk-aware learning problems efficiently.
problem Risk-aware learning with mean-semideviation objective.
method Zeroth-order compositional stochastic optimization algorithm.
result Algorithm converges to optimal solutions with explicit rates.
Proximal gradient method has been playing an important role to solve many machine learning tasks, especially for the nonsmooth problems. However, in some machine learning problems such as the bandit model and the black-box learning problem, proximal gradient method could fail because the explicit gradients of these pro…
Derivative-free Alternating Projection Algorithms for General Nonconvex-Concave Minimax Problemsmath.OC
New algorithms solve complex minimax problems without needing derivatives.
problem Solving nonconvex-concave minimax problems efficiently.
method Zeroth-order alternating and proximal gradient algorithms.
result Iteration complexity and function value estimation bounds established.
Paper proposes algorithms for solving nonconvex-nonconcave problems with complexity guarantees.
problem Nonconvex-nonconcave minimax problems with PL condition.
method Zeroth-order AGDA and VRAGDA algorithms.
result Iteration complexities for obtaining ε-stationary points.
New optimization method improves generalization across various tasks.
problem Improving zeroth-order optimization for better generalization.
method Exponential tilting objective to connect zeroth-order optimization with sharpness-aware minimization.
result Achieves better generalization compared to vanilla zeroth-order baselines.
Discretizations of Langevin diffusions provide a powerful method for sampling and Bayesian inference. However, such discretizations require evaluation of the gradient of the potential function. In several real-world scenarios, obtaining gradient evaluations might either be computationally expensive, or simply impossibl…
Optimal algorithms for Riemannian optimization with reduced complexity.
problem Stochastic optimization on Riemannian manifolds with limited data.
method Zeroth-order Riemannian Averaging Stochastic Approximation algorithms using Riemannian moving-average estimators and novel geometric conditions.
result Achieves optimal sample complexities for generating approximate first-order stationary solutions.
Simplifies noisy convex optimization with a new algorithm.
problem Finding minimum of noisy, convex functions without gradient information.
method Adapts center of gravity method for noisy, zeroth order optimisation.
result Achieves a faster convergence rate than existing methods.
Bandit Convex Optimisationmath.OC
Book covers tools for zeroth-order convex optimisation.
problem Zeroth-order convex optimisation.
method Cutting plane methods, interior point methods, continuous exponential weights, gradient descent, online Newton step.
result Improved existing bounds and algorithms.
In this paper, we focus on solving an important class of nonconvex optimization problems which includes many problems for example signal processing over a networked multi-agent system and distributed learning over networks. Motivated by many applications in which the local objective function is the sum of smooth but po…
New algorithm reduces regret in stochastic bandit convex optimization.
problem Optimizing decisions in uncertain environments with convex losses.
method Introduces a second-order method for zeroth-order stochastic convex bandits.
result Regret bound of .
This paper analyzes and guarantees convergence of prior-guided ZO algorithms.
problem Understanding convergence properties of prior-guided zeroth-order optimization algorithms.
method Analysis of convergence under a greedy descent framework with various gradient estimators, and development of ARS algorithm.
result Convergence guarantee for prior-guided random gradient-free (PRGF) algorithms and accelerated random search (ARS) algorithm.
Certified algorithms optimize functions with varying costs, providing error bounds.
problem Optimizing functions with varying evaluation costs and error bounds.
method Formalized as a min-max game, proposed certified MFDOO algorithm with cost complexity bound.
result Proposed certified MFDOO algorithm has near-optimal cost complexity for Lipschitz functions.
ZOSPI improves RL policies with global value function exploitation.
problem Limited sample efficiency of PG algorithms in RL.
method Zeroth-order supervised policy improvement, leveraging global value function estimation.
result ZOSPI achieves competitive results with remarkable sample efficiency.
A new method for MARL with partial observations reduces communication overhead.
problem Inefficient MARL algorithms in large-scale problems due to state and action information sharing.
method Distributed zeroth-order policy optimization with local policy gradient estimation using consensus.
result The method converges to a policy that is a stationary point of the global objective function.
New method improves zeroth-order stochastic optimization with adaptive sampling.
problem Optimization problems without gradient information.
method Adaptive sampling quasi-Newton method using finite differences.
result Significant improvement in performance with adaptive sample sizes.
We consider the problem of global optimization of an unknown non-convex smooth function with zeroth-order feedback. In this setup, an algorithm is allowed to adaptively query the underlying function at different locations and receives noisy evaluations of function values at the queried points (i.e. the algorithm has ac…
In this paper, we design and analyze a new zeroth-order online algorithm, namely, the zeroth-order online alternating direction method of multipliers (ZOO-ADMM), which enjoys dual advantages of being gradient-free operation and employing the ADMM to accommodate complex structured regularizers. Compared to the first-ord…
Zeroth-order (a.k.a, derivative-free) methods are a class of effective optimization methods for solving complex machine learning problems, where gradients of the objective functions are not available or computationally prohibitive. Recently, although many zeroth-order methods have been developed, these approaches still…
New algorithm reduces dimensionality in stochastic optimization.
problem Stochastic optimization in high-dimensional problems.
method Proposes a sparsity-inducing stochastic gradient-free (SI-SGF) algorithm.
result Proves dimension-free query complexity in convex and strongly convex cases.
New method uses zeroth-order queries to approximate proximal sampling efficiently.
problem Approximating proximal sampling with zeroth-order information.
method Direct simulation of heat flow dynamics, treating intermediate distribution as Gaussian mixture.
result Inherits exponential convergence under isoperimetric conditions, avoids rejection sampling.
Alternating direction method of multipliers (ADMM) is a popular optimization tool for the composite and constrained problems in machine learning. However, in many machine learning problems such as black-box attacks and bandit feedback, ADMM could fail because the explicit gradients of these problems are difficult or in…
A new algorithm for optimizing huge-scale black-box problems with reduced memory usage.
problem Optimizing huge-scale black-box problems with limited vector operations.
method ZO-BCD algorithm for zeroth-order optimization with reduced memory footprint.
result ZO-BCD achieves state-of-the-art adversarial attack success rate of 97.9%.
Zeroth-order methods favor flat minima in machine learning.
problem Finding solutions with small Hessian trace in optimization.
method Zeroth-order optimization with two-point estimator.
result Zeroth-order optimization converges to flat minima.
Escaping Saddle Points for Zeroth-order Nonconvex Optimization using Estimated Gradient Descentmath.OC
Paper proposes estimating gradients for zeroth-order nonconvex optimization.
problem Oracle access of gradients is limited in many applications.
method Develops a gradient descent method using estimated gradients.
result Algorithm finds second-order stationary points efficiently.
Paper tackles gradient-free minimax optimization with variance reduction for faster convergence.
problem Gradient-free minimax optimization problems in machine learning.
method Variance reduction technique to design a novel zeroth-order gradient descent ascent algorithm.
result Achieves the best known query complexity of O(κ(d₁ + d₂)ε⁻³), outperforming previous methods.
Two new algorithms solve high-dimensional optimization problems without gradients.
problem Optimizing complex, high-dimensional functions without gradient information.
method GradientLess Descent (GLD) algorithms that use evaluations at adaptively chosen inputs.
result Converges within an ε-ball of the optimum with a number of evaluations that is poly-logarithmic in dimensionality.
New adaptive methods solve weakly convex stochastic optimization problems.
problem Solving weakly convex stochastic optimization problems.
method Adaptive first and zeroth-order methods using exponential moving averages.
result Established non-asymptotic convergence rates for nonsmooth and nonconvex problems.
Paper learns to optimize without gradients for better performance.
problem Optimization without gradient information.
method Learned optimizer using RNNs and Gaussian sampling.
result Learned optimizer outperforms hand-designed algorithms.
Efficient algorithm for zeroth-order bandit convex optimization with bounds on regret.
problem Optimizing in unknown, noisy environments with limited information.
method Online Newton Method for bandit convex optimization, proving regret bounds.
result Regret bounds for both adversarial and stochastic settings.
ConMeZO: Adaptive Descent-Direction Sampling for Gradient-Free Finetuning of Large Language Modelscs.LG
ConMeZO speeds up zeroth-order optimization for large language models.
problem Slow convergence in high-dimensional parameter spaces of large language models.
method Adaptive directional sampling in a cone centered around a momentum estimate.
result Achieves the same convergence rate as MeZO but up to 2X faster.
We propose a method for zeroth order stochastic convex optimization that attains the suboptimality rate of after queries for a convex bounded function . The method is based on a random walk (the \emph{Ball Walk}) on the epigraph of the function. Th…
In this paper, we consider distributed optimization problems over a multi-agent network, where each agent can only partially evaluate the objective function, and it is allowed to exchange messages with its immediate neighbors. Differently from all existing works on distributed optimization, our focus is given to optimi…
As application demands for zeroth-order (gradient-free) optimization accelerate, the need for variance reduced and faster converging approaches is also intensifying. This paper addresses these challenges by presenting: a) a comprehensive theoretical analysis of variance reduced zeroth-order (ZO) optimization, b) a nove…
DPZero fine-tunes large models privately without backpropagation.
problem Memory and privacy challenges in fine-tuning large language models.
method DPZero uses zeroth-order methods for private fine-tuning, avoiding backpropagation.
result DPZero achieves private fine-tuning of RoBERTa and OPT on various tasks.
In this paper, we introduce a new stochastic approximation (SA) type algorithm, namely the randomized stochastic gradient (RSG) method, for solving an important class of nonlinear (possibly nonconvex) stochastic programming (SP) problems. We establish the complexity of this method for computing an approximate stationar…
Paper proposes ZO-SMD for MERO, achieving optimal convergence rates.
problem Minimizing excess risk across all test distributions.
method Zeroth-order stochastic mirror descent algorithm for both smooth and non-smooth MERO.
result Converges at optimal rates of for estimates and optimization errors.
This paper reviews zeroth-order optimization in signal processing and machine learning.
problem Optimization problems without gradient information.
method Iterative steps: gradient estimation, descent direction computation, solution update.
result Demonstrates applications in robustness evaluation and black-box model explanations.
New analysis for black-box learning without gradients, improving generalization bounds.
problem Generalization error analysis for derivative-free optimization.
method Zeroth-order Stochastic Search (ZoSS) algorithm for Lipschitz and smooth losses.
result Generalization bounds independent of model dimension, batch size, and number of perturbed evaluations.