Adaptive scale-invariant online algorithms for learning linear models
We consider online learning with linear models, where the algorithm predicts on sequentially revealed instances (feature vectors), and is compared against the best linear function (comparator) in hindsight. Popular algorithms in this framework, such as Online Gradient Descent (OGD), have parameters (learning rates), which ideally should be tuned based on the scales of the features and the optimal comparator, but these quantities only become available at the end of the learning process. In this paper, we resolve the tuning problem by proposing online algorithms making predictions which are invariant under arbitrary rescaling of the features. The algorithms have no parameters to tune, do not require any prior knowledge on the scale of the instances or the comparator, and achieve regret bounds matching (up to a logarithmic factor) that of OGD with optimally tuned separate learning rates per dimension, while retaining comparable runtime performance.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
An efficient implementation of graph-based invariant set algorithm for constrained nonlinear dynamical systems
The graph-based invariant set (GIS) algorithm is a promising set-based technique for computing the largest (with respect to inclusion) control invariant set of general discrete-time nonlinear dynamical systems. However, …
graph constructionScale-Free Algorithms for Online Linear Optimization
We design algorithms for online linear optimization that have optimal regret and at the same time do not need to know any upper or lower bounds on the norm of the loss vectors. We achieve adaptiveness to norms of loss ve…
Scale-invariant unconstrained online learning
We consider a variant of online convex optimization in which both the instances (input vectors) and the comparator (weight vector) are unconstrained. We exploit a natural scale invariance symmetry in our unconstrained se…
Self-Normalized Martingales and Uniform Regret Bounds for Linear Regression
Self-normalized martingale inequalities lie at the heart of confidence ellipsoids for online least squares and, more broadly, many bandit and reinforcement-learning results. Yet existing vector and scalar results typical…
Scale-free Unconstrained Online Learning for Curved Losses
A sequence of works in unconstrained online convex optimisation have investigated the possibility of adapting simultaneously to the norm $U$ of the comparator and the maximum norm $G$ of the gradients. In full generality…
Computational Efficiencyregression