Second-order Online Nonconvex Optimization
arXiv:2001.10114 · doi:10.1109/TAC.2020.3040372
Abstract
We present the online Newton's method, a single-step second-order method for online nonconvex optimization. We analyze its performance and obtain a dynamic regret bound that is linear in the cumulative variation between round optima. We show that if the variation between round optima is limited, the method leads to a constant regret bound. In the general case, the online Newton's method outperforms online convex optimization algorithms for convex functions and performs similarly to a specialized algorithm for strongly convex functions. We simulate the performance of the online Newton's method on a nonlinear, nonconvex moving target localization example and find that it outperforms a first-order approach.
References in corpus (15)
- An Online Convex Optimization Approach to Dynamic Network Resource Allocation
- Non-stationary Stochastic Optimization
- A Class of Prediction-Correction Methods for Time-Varying Convex Optimization
- Online Learning with Predictable Sequences
- Online Primal-Dual Methods with Measurement Feedback for Time-Varying Convex Optimization
- Online Learning with Inexact Proximal Online Gradient Descent Algorithms
- Online Optimization : Competing with Dynamic Comparators
- Online Convex Optimization with Time-Varying Constraints
- Improved Dynamic Regret for Non-degenerate Functions
- Online Optimization with Predictions and Switching Costs: Fast Algorithms and the Fundamental Limit
- Setpoint Tracking with Partially Observed Loads
- Efficient Regret Minimization in Non-Convex Games
- Predictive Online Convex Optimization
- Tracking Slowly Moving Clairvoyant: Optimal Dynamic Regret of Online Learning with True and Noisy Gradient
- Proximal Online Gradient is Optimum for Dynamic Regret
Cited by in corpus (6)
- Dynamic and Distributed Online Convex Optimization for Demand Response of Commercial Buildings
- Local Strong Convexity of Source Localization and Error Bound for Target Tracking under Time-of-Arrival Measurements
- Online Convex Optimization Using Coordinate Descent Algorithms
- An Online Newton's Method for Time-varying Linear Equality Constraints
- Unconstrained Online Optimization: Dynamic Regret Analysis of Strongly Convex and Smooth Problems
- A Logistic Regression Approach to Field Estimation Using Binary Measurements