The second order method as Newton Step is a suitable technique in Online Learning to guarantee regret bound. The large data is a challenge in Newton method to store second order matrices as hessian. In this paper, we have proposed an modified online Newton step that store first and second order matrices of dimension m …
On-device research index
arXiv research
A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
168,657 papers · 148 categories
Trend · papers per month
48 results for “online Newton step”
Paper proposes an online covariance estimator for sketched Newton methods.
problem Estimating the limiting covariance matrix of sketched Newton methods.
method Proposes a fully online covariance matrix estimator from Newton iterates.
result Establishes the consistency and convergence rate of the proposed estimator.
Online learning with limited information feedback (bandit) tries to solve the problem where an online learner receives partial feedback information from the environment in the course of learning. Under this setting, Flaxman et al.[8] extended Zinkevich's classical Online Gradient Descent (OGD) algorithm [29] by proposi…
Paper proposes an efficient online Newton method with Nesterov's acceleration for streaming data.
problem Efficient inference of online Newton methods with robustness to noise and ill-conditioning.
method Online Newton method with Hessian averaging and Nesterov's accelerated sketch-and-project solver.
result Global almost-sure convergence and asymptotic normality of the last iterate with non-asymptotic convergence guarantees.
An online learning framework for survival analysis with real-time adaptation.
problem Real-time adaptation to dynamic environments and censored data in survival analysis.
method Online Newton Step (ONS) for optimal second order online convex optimization.
result Logarithmic stochastic regret for ONS with adaptive aggregation method.
New quasi-Newton method guarantees global superlinear convergence.
problem Global convergence and superlinear convergence of quasi-Newton methods.
method Hybrid proximal extragradient method with online learning for Hessian approximation.
result First globally convergent quasi-Newton method with explicit superlinear convergence rate.
We describe a framework for deriving and analyzing online optimization algorithms that incorporate adaptive, data-dependent regularization, also termed preconditioning. Such algorithms have been proven useful in stochastic optimization by reshaping the gradients according to the geometry of the data. Our framework capt…
New algorithm achieves optimal regret in non-stochastic control, showing stochasticity is not beneficial.
problem Achieving optimal control in non-stochastic systems with adversarial noise.
method Novel online Newton step algorithm adapted to adversarial disturbances, using policy regret bounds.
result Optimal regret achieved in unknown dynamics, regret in known dynamics.
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 multiclass logistic regression with lower computational complexity.
problem High computational complexity in existing methods for multiclass logistic regression.
method Developed a new algorithm that achieves a lower computational complexity.
result Achieved a regret of with computational complexity .
Muon with Newton-Schulz converges to the same stationary point as SVD-polar, up to a constant factor.
problem Improving the convergence rate of Muon optimizer.
method Using Newton-Schulz steps for momentum orthogonalization, proving convergence rate and constant factor.
result Muon with Newton-Schulz converges to the same stationary point as SVD-polar, up to a constant factor.
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)).
Paper proposes a quasi-Newton method for nonlinear equations with global convergence guarantees.
problem Solving smooth and monotone nonlinear equations efficiently and globally.
method Hybrid proximal extragradient framework combined with online learning for Jacobian approximation.
result First global convergence results showing quasi-Newton method's advantage over extragradient method.
This paper introduces online algorithms to estimate robust geometric median in large data streams.
problem Detecting outliers in large data sets using robust statistical measures.
method Online stochastic Newton methods for estimating the geometric median.
result Rates of convergence for online estimation of the geometric median.
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.
In this work, we present a globalized stochastic semismooth Newton method for solving stochastic optimization problems involving smooth nonconvex and nonsmooth convex terms in the objective function. We assume that only noisy gradient and Hessian information of the smooth part of the objective function is available via…
We consider prediction with expert advice under the log-loss with the goal of deriving efficient and robust algorithms. We argue that existing algorithms such as exponentiated gradient, online gradient descent and online Newton step do not adequately satisfy both requirements. Our main contribution is an analysis of th…
RONM method reduces regret in stochastic convex bandits with decreasing noise.
problem Stochastic convex bandit problem with decreasing noise.
method Regularized Online Newton Method (RONM) based on Online Newton Method (ONM).
result RONM achieves polylogarithmic regret in time horizon n.
A new algorithm reduces online exp-concave optimization runtime.
problem Minimizing regret in online learning with exponentially concave losses.
method LightONS, a variant of Online Newton Step (ONS), reduces runtime to .
result Optimal regret with reduced runtime to .
Bandit Convex Optimisationmath.OC
Book covers tools for zeroth-order convex optimisation.
problem Zeroth-order convex optimisation.
method Cutting plane methods, interior point methods, continuous exponential weights, gradient descent, online Newton step.
result Improved existing bounds and algorithms.
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…
In this paper, a novel stochastic extra-step quasi-Newton method is developed to solve a class of nonsmooth nonconvex composite optimization problems. We assume that the gradient of the smooth part of the objective function can only be approximated by stochastic oracles. The proposed method combines general stochastic …
Global convergence of an online (stochastic) limited memory version of the Broyden-Fletcher- Goldfarb-Shanno (BFGS) quasi-Newton method for solving optimization problems with stochastic objectives that arise in large scale machine learning is established. Lower and upper bounds on the Hessian eigenvalues of the sample …
In stochastic gradient descent, especially for neural network training, there are currently dominating first order methods: not modeling local distance to minimum. This information required for optimal step size is provided by second order methods, however, they have many difficulties, starting with full Hessian having…
New method solves convex optimization faster than NAG.
problem Unconstrained smooth convex optimization problems.
method Accelerated quasi-Newton proximal extragradient (A-QPNE) method.
result Achieves a faster convergence rate of .
Regularized nonlinear acceleration (RNA) estimates the minimum of a function by post-processing iterates from an algorithm such as the gradient method. It can be seen as a regularized version of Anderson acceleration, a classical acceleration scheme from numerical analysis. The new scheme provably improves the rate of …
Newton-LESS sparsifies Gaussian sketching for faster optimization.
problem Computing the Hessian matrix in optimization is computationally expensive.
method Uses a sparsified version of a dense Gaussian sketching matrix.
result Achieves nearly the same convergence rate as dense Gaussian embeddings without the computational cost.
Unconstrained Online Optimization: Dynamic Regret Analysis of Strongly Convex and Smooth Problemscs.LG
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 regret bound with one gradient query per round.
Efficient algorithm for zeroth-order bandit convex optimization with bounds on regret.
problem Optimizing in unknown, noisy environments with limited information.
method Online Newton Method for bandit convex optimization, proving regret bounds.
result Regret bounds for both adversarial and stochastic settings.
We study the smooth structure of convex functions by generalizing a powerful concept so-called self-concordance introduced by Nesterov and Nemirovskii in the early 1990s to a broader class of convex functions, which we call generalized self-concordant functions. This notion allows us to develop a unified framework for …
A new method for machine learning updates reduces complexity and improves robustness.
problem Stochastic gradient updates are inefficient and sensitive to feature scaling.
method Incremental Gauss-Newton Descent (IGND) reduces the need for matrix operations and improves robustness.
result IGND improves robustness to sensitivity scaling and can be competitive with common stochastic optimizers.
Develops a new SPP algorithm with variance reduction for weakly convex optimization.
problem Weakly convex, composite optimization problems.
method Inexact semismooth Newton framework with variance reduction for stochastic proximal point updates.
result Establishes convergence results for the proposed algorithm.
Paper develops efficient methods for estimating Hessian inverses in stochastic optimization.
problem Estimating the inverse Hessian for convex function minimization.
method Robbins-Monro procedure for recursive estimation of the inverse Hessian.
result Develops universal stochastic Newton methods with improved efficiency.
New method for online inference of constrained optimization problems.
problem Online inference of constrained stochastic optimization problems.
method Random scaling of Sketched Stochastic Sequential Quadratic Programming (SSQP).
result Asymptotically valid confidence intervals and matrix-free computation.
New approach removes data influence in high dimensions with single step.
problem Efficiently removing data influence in high-dimensional settings with strong convexity and smoothness assumptions.
method Introduces ε-Gaussian certifiability and analyzes Newton method performance.
result Single Newton step followed by Gaussian noise achieves privacy and accuracy.
An EM Gradient Algorithm for Mixture Models with Components Derived from the Manly Transformationstat.ML
A new EM gradient algorithm for mixture models with skewed components.
problem Fitting mixture models with skewed components derived from the Manly transformation.
method Proposes an alternative EM gradient algorithm using Newton's method for better parameter updates.
result Shows improved convergence and parameter estimation compared to the Nelder-Mead optimization.
Improved online convex optimization with delayed feedback using curvature.
problem Online convex optimization with curved losses and delayed feedback.
method Variant of follow-the-regularized-leader and Online Newton Step algorithm with adaptive learning rate.
result Regret bounds of order for exp-concave losses.
Generalized Linear Bandits (GLBs), a natural extension of the stochastic linear bandits, has been popular and successful in recent years. However, existing GLBs scale poorly with the number of rounds and the number of arms, limiting their utility in practice. This paper proposes new, scalable solutions to the GLB probl…
Proposes a new method for optimizing large-scale models using Nyström approximation of the Hessian.
problem Optimizing non-convex functions like deep learning models using second-order methods.
method Nyström-approximated curvature for stochastic optimization of large-scale empirical risk minimization.
result The proposed method achieves performance competitive with state-of-the-art first-order and stochastic quasi-Newton methods.
We propose a trust region method for policy optimization that employs Quasi-Newton approximation for the Hessian, called Quasi-Newton Trust Region Policy Optimization QNTRPO. Gradient descent is the de facto algorithm for reinforcement learning tasks with continuous controls. The algorithm has achieved state-of-the-art…
New algorithm improves convergence of gradient boosting trees.
problem Global convergence of Newton boosting in tabular machine learning.
method Introduces Gradient Regularized Newton Descent for GBDTs, proving linear convergence for smooth, strongly convex losses and rate for general convex losses.
result Achieves globally convergent second-order GBDT algorithm with rate matching first-order boosting.
In distributed optimization and distributed numerical linear algebra, we often encounter an inversion bias: if we want to compute a quantity that depends on the inverse of a sum of distributed matrices, then the sum of the inverses does not equal the inverse of the sum. An example of this occurs in distributed Newton's…
Bayesian approach improves AdaLoRA's performance and efficiency.
problem Improving the efficiency and performance of adaptive low-rank adaptation.
method Utilized Bayesian metrics and the Improved Variational Online Newton (IVON) optimizer for adaptive parameter budget allocation.
result Bayesian counterpart outperforms sensitivity-based importance metric and is faster than AdaLoRA.
A new sequential method estimates Poisson means in streaming data, achieving optimality and efficiency.
problem Estimating Poisson means in a streaming, or online, framework.
method A quasi-Bayesian approach based on Newton's algorithm for a sequential estimate.
result Established frequentist guarantees including consistency and asymptotic optimality.
Algorithm removes specific training data from models efficiently in high-dimensional settings.
problem Efficiently removing specific training data from high-dimensional models without full retraining.
method Starts from original model parameters, performs Newton steps, adds isotropic Laplacian noise.
result Two Newton steps are sufficient for effective unlearning in high-dimensional problems.
In this paper, we address the problem of adaptive learning for autoregressive moving average (ARMA) model in the quaternion domain. By transforming the original learning problem into a full information optimization task without explicit noise terms, and then solving the optimization problem using the gradient descent a…
SVRN accelerates Newton methods by reducing variance and improving performance.
problem Improving the efficiency of Newton methods for large-scale optimization problems.
method Stochastic Variance-Reduced Newton (SVRN) algorithm that accelerates Subsampled Newton and Iterative Hessian Sketch algorithms.
result SVRN accelerates Newton methods by reducing the number of passes over the data, achieving a significant improvement in performance.
A new distributed method for convex optimization over networks with fast convergence.
problem Large-scale convex optimization over networks with limited communication.
method Distributed cubic-regularized Newton method.
result Convergence rate of for convex functions with Lipschitz gradient and Hessian.