How Free is Parameter-Free Stochastic Optimization?
We study the problem of parameter-free stochastic optimization, inquiring whether, and under what conditions, do fully parameter-free methods exist: these are methods that achieve convergence rates competitive with optimally tuned methods, without requiring significant knowledge of the true problem parameters. Existing parameter-free methods can only be considered ``partially'' parameter-free, as they require some non-trivial knowledge of the true problem parameters, such as a bound on the stochastic gradient norms, a bound on the distance to a minimizer, etc. In the non-convex setting, we demonstrate that a simple hyperparameter search technique results in a fully parameter-free method that outperforms more sophisticated state-of-the-art algorithms. We also provide a similar result in the convex setting with access to noisy function values under mild noise assumptions. Finally, assuming only access to stochastic gradients, we establish a lower bound that renders fully parameter-free stochastic convex optimization infeasible, and provide a method which is (partially) parameter-free up to the limit indicated by our lower bound.
Code (0)
등록된 구현이 없습니다.
Tasks
Stochastic OptimizationSimilar Papers 제목 키워드 기반
Better Parameter-free Stochastic Optimization with ODE Updates for Coin-Betting
Parameter-free stochastic gradient descent (PFSGD) algorithms do not require setting learning rates while achieving optimal theoretical performance. In practical applications, however, there remains an empirical gap betw…
Stochastic OptimizationTowards Fully Parameter-Free Stochastic Optimization: Grid Search with Self-Bounding Analysis
Parameter-free stochastic optimization aims to design algorithms that are agnostic to the underlying problem parameters while still achieving convergence rates competitive with optimally tuned methods. While some paramet…
Stochastic OptimizationASOC: An Adaptive Parameter-free Stochastic Optimization Techinique for Continuous Variables
Stochastic optimization is an important task in many optimization problems where the tasks are not expressible as convex optimization problems. In the case of non-convex optimization problems, various different stochasti…
Evolutionary AlgorithmsStochastic OptimizationWSBD: Freezing-Based Optimizer for Quantum Neural Networks
The training of Quantum Neural Networks (QNNs) is hindered by the high computational cost of gradient estimation and the barren plateau problem, where optimization landscapes become intractably flat. To address these cha…
Tuning-Free Stochastic Optimization
Large-scale machine learning problems make the cost of hyperparameter tuning ever more prohibitive. This creates a need for algorithms that can tune themselves on-the-fly. We formalize the notion of "tuning-free" algorit…
Stochastic Optimization