Proximal online gradient minimizes dynamic regret in evolving environments.
problem Optimizing dynamic regret in online learning where the optimal solution changes over time.
method Proximal online gradient method, showing it is optimal for dynamic regret.
result Proximal online gradient matches the lower bound for dynamic regret, proving its optimality.
Gradient equilibrium improves online learning performance without requiring sublinear regret.
problem Achieving sublinear regret in online learning.
method Gradient equilibrium: average of gradients converges to zero.
result Gradient equilibrium can be achieved by standard online learning methods.
This paper improves an online learning algorithm using second-order information.
problem Online learning with limited feedback.
method Develops Online Newton Step with Expected Gradient (ONSEG) algorithm.
result Reduces expected regret from O(T^(5/6)) to O(T^(2/3)).
Proposes time-smoothed gradients for more stable online forecasting.
problem Stability and efficiency in online forecasting with SGD.
method Introduces time-smoothed gradients within SGD update rules.
result Time-smoothed gradients yield more stable results than existing methods.
We prove that the evolution of weight vectors in online gradient descent can encode arbitrary polynomial-space computations, even in very simple learning settings. Our results imply that, under weak complexity-theoretic assumptions, it is impossible to reason efficiently about the fine-grained behavior of online gradie…
New definition of regret for nonconvex online learning models.
problem Intractability of standard regret measures for nonconvex models.
method Introduced a local gradient based regret definition.
result Our definition provides more interpretable bounds for forecasting.
UORO reduces gradient variance in online RNN learning.
problem Improving gradient estimates in online RNN learning.
method Analyzes and proposes variance reduction techniques for UORO.
result Reduces gradient variance both theoretically and practically.
Paper proposes an ε ε ε -policy gradient for online pricing, reducing regret to O ( T ) \mathcal{O}(\sqrt{T}) O ( T ) .
problem Online pricing learning task
method Combines model-based and model-free reinforcement learning, using ε ε ε -greedy with gradient descent. result Achieves expected regret of order O ( T ) \mathcal{O}(\sqrt{T}) O ( T ) . A new method corrects staleness in online optimization by transporting past gradients.
problem Reducing staleness and variance in online optimization methods.
method Implicit gradient transport (IGT) to correct past gradients at the current iterate.
result IGT reduces variance and bias in updates over time and achieves state-of-the-art results.
Improved online gradient descent with fewer queries for dynamic environments.
problem Efficiently tracking changes in functions with varying gradients and smoothness.
method Developed a new theoretical framework to analyze online gradient descent in dynamic settings, reducing query complexity.
result Achieved state-of-the-art dynamic regret with significantly fewer gradient queries, independent of condition number.
New adaptive first-order methods improve on quasi-Newton variants.
problem Designing efficient gradient methods for practical applications.
method Online scaled gradient methods (OSGM) with new adaptive methods OSGM-Best.
result OSGM-Best matches quasi-Newton variants but requires less memory and cheaper iterations.
Improved complexity for smooth nonconvex optimization using quasi-Newton methods.
problem Finding ε-first-order stationary points of smooth functions with gradient information only.
method Two-level online learning approach involving quasi-Newton methods.
result Gradient complexity improved to O(d^(1/4)ε^(-13/8)) for d = O(ε^(-1/2)).
Optimal control methods achieve significantly smaller regret than previously thought.
problem Optimal control in linear dynamical systems with adversarial changes.
method Online gradient descent and online natural gradient methods.
result Achieves logarithmic regret scaling as O(poly(log T)) instead of O(sqrt(T)).
Two new methods reduce OCO problem complexity without projections.
problem Efficiently solving smooth Online Convex Optimization problems without projections.
method ORGFW and MORGFW methods using recursive gradient estimation.
result Achieve optimal regret bounds with low computational costs.
An online decision-making algorithm using stochastic gradient descent for big data.
problem Efficiently updating decision rules in online decision making with big data.
method Stochastic gradient descent for online updates, asymptotic normality of estimators.
result Asymptotic normality of parameter and value estimators, enabling statistical inference.
Improves SGD convergence by online linear regression of gradients in multiple directions.
problem SGD's rough approximations of gradients lead to suboptimal plateaus and saddle points.
method Online linear regression of noisy gradients using PCA to estimate second-order behavior, and gradient descent outside the subspace.
result Improves convergence by avoiding suboptimal plateaus and saddles, leading to better final values.
PGS uses neural networks to improve policies online without search trees.
problem Limited scalability of Monte Carlo Tree Search (MCTS) for high branching factor games.
method Adapts a neural network simulation policy via policy gradient updates, avoiding search trees.
result PGS achieves comparable performance to MCTS and defeats strong Hex agents.
New algorithm for online training of Spiking Neural Networks (SNNs).
problem Training Spiking Neural Networks (SNNs) online with BPTT-equivalent gradients.
method Clear separation of spatial and temporal gradient components, derived from biological insights.
result Online training of SNNs with BPTT-equivalent gradients and low time complexity.
New algorithms reduce regret in online convex optimization with heavy-tailed gradients.
problem Challenges in online convex optimization with heavy-tailed gradients.
method Examined and analyzed old algorithms for online convex optimization in the heavy-tailed setting.
result Established new regret bounds for classical methods without algorithmic modification.
BONG optimizes Bayesian inference online with natural gradient descent.
problem Sequential Bayesian inference in online settings.
method Bayesian online natural gradient (BONG) approach based on variational Bayes.
result BONG outperforms other online VB methods in non-conjugate settings.
New method for online statistical inference in contextual bandits using SGD.
problem Online decision-making in contextual bandits with statistical inference.
method Weighted stochastic gradient descent for adaptive data collection.
result Asymptotic normality of the parameter estimator with improved efficiency.
Paper analyzes regret bounds for unconstrained online optimization.
problem Minimizing regret in dynamic online learning for strongly convex and smooth functions.
method Preconditioned OGD, Online Optimistic Newton (OON), multiple gradient queries.
result Achieves O ( C 2 , T ∗ ) O(C^*_{2,T}) O ( C 2 , T ∗ ) regret bound with one gradient query per round. New algorithms adapt to both gradient norms and comparator norms in online learning.
problem Adapting to both gradient norms and comparator norms in online learning.
method Developed parameter-free and scale-free algorithms for unbounded online convex optimization.
result Improved regret bounds for scale-invariant online prediction with linear models.
Paper proposes an online estimator for covariance matrix of SGD iterates.
problem Quantifying variability and randomness of SGD-based estimates in online learning.
method Proposes a fully online estimator for covariance matrix of ASGD using SGD iterates.
result Establishes consistency of the online estimator and shows comparable convergence rate to offline methods.
Online optimization has been a successful framework for solving large-scale problems under computational constraints and partial information. Current methods for online convex optimization require either a projection or exact gradient computation at each step, both of which can be prohibitively expensive for large-scal…
GALA adapts learning rates online by aligning gradients, improving deep learning model performance.
problem Fine-tuning learning rates for deep learning models requires extensive grid search.
method GALA dynamically adjusts learning rates by tracking gradient alignment and local curvature.
result GALA produces a flexible, adaptive learning rate schedule that increases when gradients align.
OMGD algorithm optimizes online convex optimization with switching costs and delayed gradients.
problem Optimizing online convex optimization with switching costs and delayed gradients.
method Proposed an online multiple gradient descent (OMGD) algorithm for quadratic and linear switching costs.
result OMGD achieves optimal dynamic regret in the limited information setting.
Kernel-based online learning has often shown state-of-the-art performance for many online learning tasks. It, however, suffers from a major shortcoming, that is, the unbounded number of support vectors, making it non-scalable and unsuitable for applications with large-scale datasets. In this work, we study the problem …
Paper tackles online learning with interval regret, achieving adaptive bounds.
problem Non-stationary online learning over time intervals.
method Two-layer online ensemble structure with gradient variation.
result Achieves strong theoretical guarantees with adaptive bounds.
SGD noise has no bias advantage in online learning, contrary to offline learning.
problem The role of SGD noise in online learning.
method Extensive empirical analysis of image and language data.
result Small batch sizes do not confer any implicit bias advantages in online learning.
New method for online inference using SGD with random scaling.
problem Efficient online inference for SGD parameters.
method Asymptotic pivotal statistics via random scaling.
result Robust and efficient online inference without resampling.
ROIPCA and fROIPCA are online PCA algorithms using rank-one updates.
problem Memory-restricted online PCA for large or streaming data.
method ROIPCA and fROIPCA use rank-one updates for efficient computation.
result fROIPCA is faster with comparable accuracy; ROIPCA is more accurate.
New method improves online covariance estimation for SGD.
problem Improving online covariance estimation for SGD.
method Proposes a de-biased covariance estimator that eliminates second-order derivatives.
result Achieves a convergence rate of n ( α − 1 ) / 2 log n n^{(α-1)/2} \sqrt{\log n} n ( α − 1 ) /2 log n , outperforming existing methods. New method improves online nonparametric estimators with minimal extra computation.
problem Model selection and hyperparameter tuning for online nonparametric estimators.
method Weighted rolling validation procedure for online cross-validation.
result Improves base estimators to achieve better heuristic performance and adaptive convergence rate.
A new gradient estimator for online optimization with two function evaluations.
problem Online optimization of convex and Lipschitz functions with noisy data.
method L1-randomization approach for gradient estimation.
result Compared or better guarantees than previous methods for canceling noise.
New algorithms reduce online learning regret by tracking gradient variation.
problem Online learning with unconstrained losses and gradient variation.
method Parameter-free algorithms with adaptive updates for L L L -smooth convex losses. result Regret bounds of order O ~ ( ∥ u ∥ V T ( u ) + L ∥ u ∥ 2 + G 4 ) \widetilde{O}(\|u\|\sqrt{V_T(u)} + L\|u\|^2+G^4) O ( ∥ u ∥ V T ( u ) + L ∥ u ∥ 2 + G 4 ) achieved without prior knowledge of comparator norm or Lipschitz constant. Paper proposes an online learning method with multi-level adaptivity for diverse loss functions.
problem Online learning with unknown types and curvatures of functions.
method Multi-layer online ensemble approach with gradient variations.
result Achieves improved regret bounds for different types of loss functions.
This paper studies the complexity of the stochastic gradient algorithm for PCA when the data are observed in a streaming setting. We also propose an online approach for selecting the learning rate. Simulation experiments confirm the practical relevance of the plain stochastic gradient approach and that drastic improvem…
New approach improves convergence of online learning for ARIMA models.
problem Pitfalls in computational complexity and convergence of Online Newton Step optimization method.
method Proposes a new approach combining different Online Gradient Descent learners for iterative training of ARIMA models.
result The proposed approach outperforms existing methods resulting in lower prediction error.
A standard introduction to online learning might place Online Gradient Descent at its center and then proceed to develop generalizations and extensions like Online Mirror Descent and second-order methods. Here we explore the alternative approach of putting Exponential Weights (EW) first. We show that many standard meth…
Optimal algorithms for online convex optimization with missing sub-gradient observations.
problem Online convex optimization with noisy or missing sub-gradient observations.
method Adaptive algorithms using sub-gradient descent with minimax optimal regret guarantees.
result Achieves tight minimax optimal regret bounds with empirical property estimation.
OSGM uses online learning to adapt stepsize for faster convergence.
problem Improving convergence rates of first-order methods.
method OSGM combines online learning and feedback functions to adjust stepsize.
result OSGM achieves convergence rates asymptotically no worse than optimal.
Proves local convergence of various online and recurrent optimization algorithms.
problem Proves local convergence of online and recurrent optimization algorithms not covered by standard stochastic gradient descent theory.
method Uses a general set of assumptions for learning dynamical systems online, adopting an 'ergodic' viewpoint.
result Local convergence results for online and recurrent optimization algorithms, including RMSProp, NoBackTrack, UORO, Adam, and RTRL.
Meta-strategy learns tuning parameters for online learning methods.
problem Difficulty in setting tuning parameters for online learning methods.
method Meta-learning approach to learn parameters from past tasks.
result Meta-strategy improves on learning each task in isolation.
Paper develops online learning algorithms for quaternion ARMA models.
problem Adaptive learning for autoregressive moving average (ARMA) models in quaternion domain.
method Transformed learning problem into full information optimization task, solved using gradient descent and Newton's method.
result Online algorithms achieve asymptotic performance approaching best ARMA model.
Paper introduces P-FGD for online quantile regression models.
problem Training nonparametric additive quantile regression models in online settings.
method Projected functional gradient descent algorithm (P-FGD) for pinball loss.
result P-FGD achieves minimax optimal consistency rate O ( t − 2 s 2 s + 1 ) O(t^{-\frac{2s}{2s+1}}) O ( t − 2 s + 1 2 s ) . NeCPD improves online tensor decomposition using SGD with Hessian analysis and NAG.
problem Efficiently decompose multi-way tensors in online data processing.
method NeCPD solver based on SGD with Hessian analysis and NAG.
result NeCPD provides more accurate results than existing methods.
New method for distributed online learning with communication constraints reduces joint regret.
problem Joint regret minimization in a distributed online learning setting with communication constraints.
method Adaptive graph partitioning and comparator-adaptive online convex optimization with delayed gradient information.
result Optimal graph partition selection for adversarial activations and gradients reduces joint regret.