Simple Complexity Analysis of Direct Search

Jakub Konecný, Peter RichtárikarXiv 2014 · arXiv · OpenReview

TL;DR

This paper introduces "Simplified Direct Search" (SDS), a new derivative-free optimization method that significantly reduces the number of tunable parameters compared to traditional direct search. The authors provide a unified and remarkably brief complexity analysis for SDS, establishing new, simpler, and often tighter bounds on the number of function evaluations required to find approximate solutions for nonconvex, convex, and strongly convex functions.

What Problem Does This Paper Address?

The paper tackles the challenge of unconstrained minimization of smooth functions when direct access to gradients is unavailable (derivative-free optimization). Traditional direct search methods, while effective, are notoriously complex to tune due to a large number of parameters. Furthermore, rigorous theoretical guarantees on their performance (complexity bounds) have only recently emerged, and these analyses are often intricate. The authors aim to simplify direct search, making it easier to understand, implement, and analyze, while also providing improved theoretical performance guarantees.

Methods

The core contribution is the Simplified Direct Search (SDS) algorithm. Unlike standard direct search, SDS relies on a single scalar parameter (either the forcing constant or initial stepsize, depending on initialization strategy) and a fixed set of search directions. The algorithm iteratively attempts to find a direction from the set that yields a "sufficient decrease" in the function value. If no such direction is found with the current stepsize, the stepsize is reduced.

Key methodological aspects include:

  • Parameter Simplification: SDS eliminates many parameters found in standard direct search (e.g., forcing constant exponent, stepsize decrease factors, stepsize increase factors), making it more user-friendly.
  • Unified Analysis: The authors present a single, remarkably brief analytical framework that covers nonconvex, convex, and strongly convex objective functions. This contrasts with previous work that often required separate analyses for each case.
  • Initialization Strategies: Three initialization strategies are proposed, two of which are novel and aim to automatically tune parameters, further simplifying the method's practical use.
  • Complexity Bounds: The paper derives new complexity bounds, expressed as the number of function evaluations needed to achieve a certain level of accuracy. These bounds are shown to be competitive with, and in some cases better than, existing results.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and algorithm design, not empirical evaluation on specific datasets.

Key Insights and Ideas

  • Parameter Reduction is Key: The paper demonstrates that much of the complexity in standard direct search is due to an overabundance of tunable parameters that don't significantly impact worst-case complexity. Simplifying these leads to a more elegant and theoretically tractable method.
  • Unified Analysis is Possible: The authors show that a single analytical approach can effectively bound the performance of direct search across different function classes (nonconvex, convex, strongly convex), simplifying the theoretical landscape.
  • "Unsuccessful" Steps Drive Progress: For nonconvex functions, the analysis reveals that the number of "unsuccessful" steps (where the stepsize is reduced) is the primary driver of the quality of the solution, while "successful" steps contribute to the overall cost.
  • Initialization Matters for Performance: While not strictly necessary for theoretical guarantees in the nonconvex case, effective initialization strategies can significantly improve the practical performance of SDS, especially in convex settings.

Key Results

The paper establishes complexity bounds for SDS, representing the number of function evaluations to find an $\epsilon$-solution:

  • Nonconvex Case: The bound is $O(n^2/\epsilon^2)$ for reducing the gradient norm below $\epsilon$.
  • Convex Case: The bound is $O(n^2/\epsilon)$ for reducing the function value to within $\epsilon$ of the minimum.
  • Strongly Convex Case: The bound is $O(n^2 \log(1/\epsilon))$ for reducing the function value to within $\epsilon$ of the minimum.

These bounds match existing results in their dependence on problem dimension ($n$) and error tolerance ($\epsilon$) but are presented in a simpler, more interpretable form. For specific choices of search directions (e.g., coordinate vectors and their negatives), the $n^2$ term is confirmed. The analysis is notably brief, with proofs for the main complexity theorems being only a few lines long.

Limitations and Future Work

  • L-smoothness Assumption: The analysis relies on the assumption that the objective function is L-smooth (its gradient is Lipschitz continuous). This is a common assumption in optimization but might not hold for all problems.
  • Knowledge of L: For optimal complexity bounds in the convex and strongly convex cases, the forcing constant $c$ should ideally be related to the Lipschitz constant $L$ of the gradient. However, in a derivative-free setting, $L$ is typically unknown, forcing the use of a constant $c$, which leads to a quadratic dependence on $L$ in the complexity.
  • Practical Performance: While theoretical bounds are provided, the paper focuses on worst-case complexity. The practical performance of SDS compared to other derivative-free methods on real-world problems is not extensively studied.
  • Future Work: The authors suggest exploring SDS for other function classes (e.g., nonsmooth), different optimization problems (stochastic, constrained), and variants of SDS (e.g., with randomization). They also mention that further improvements to the algorithm's practical performance can be achieved with additional stopping criteria, though these might be theoretical in nature due to unknown parameters.

Summary updated

Abstract

We consider the problem of unconstrained minimization of a smooth function in the derivative-free setting using. In particular, we propose and study a simplified variant of the direct search method (of direction type), which we call simplified direct search (SDS). Unlike standard direct search methods, which depend on a large number of parameters that need to be tuned, SDS depends on a single scalar parameter only. Despite relevant research activity in direct search methods spanning several decades, complexity guarantees---bounds on the number of function evaluations needed to find an approximate solution---were not established until very recently. In this paper we give a surprisingly brief and unified analysis of SDS for nonconvex, convex and strongly convex functions. We match the existing complexity results for direct search in their dependence on the problem dimension ($n$) and error tolerance ($\epsilon$), but the overall bounds are simpler, easier to interpret, and have better dependence on other problem parameters. In particular, we show that for the set of directions formed by the standard coordinate vectors and their negatives, the number of function evaluations needed to find an $\epsilon$-solution is $O(n^2 /\epsilon)$ (resp. $O(n^2 \log(1/\epsilon))$) for the problem of minimizing a convex (resp. strongly convex) smooth function. In the nonconvex smooth case, the bound is $O(n^2/\epsilon^2)$, with the goal being the reduction of the norm of the gradient below $\epsilon$.
BibTeX
@misc{konecny2014simple,
  author = {Jakub Konecný and Peter Richtárik},
  title = {{Simple Complexity Analysis of Direct Search}},
  year = {2014},
  eprint = {1410.0390},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1410.0390},
}
Figure