A major challenge in current optimization research for deep learning is to automatically find optimal step sizes for each update step. The optimal step size is closely related to the shape of the loss in the update step direction. However, this shape has not yet been examined in detail. This work shows empirically that…
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,695 papers · 148 categories
Trend · papers per month
48 results for “Line search”
Step sizes in neural network training are largely determined using predetermined rules such as fixed learning rates and learning rate schedules. These require user input or expensive global optimization strategies to determine their functional form and associated hyperparameters. Line searches are capable of adaptively…
Recent works have shown that stochastic gradient descent (SGD) achieves the fast convergence rates of full-batch gradient descent for over-parameterized models satisfying certain interpolation conditions. However, the step-size used in these works depends on unknown quantities and SGD's practical performance heavily re…
In deterministic optimization, line searches are a standard tool ensuring stability and efficiency. Where only stochastic gradients are available, no direct equivalent has so far been formulated, because uncertain gradients do not allow for a strict sequence of decisions collapsing the search space. We construct a prob…
In deterministic optimization, line searches are a standard tool ensuring stability and efficiency. Where only stochastic gradients are available, no direct equivalent has so far been formulated, because uncertain gradients do not allow for a strict sequence of decisions collapsing the search space. We construct a prob…
In this paper, we consider a class of possibly nonconvex, nonsmooth and non-Lipschitz optimization problems arising in many contemporary applications such as machine learning, variable selection and image processing. To solve this class of problems, we propose a proximal gradient method with extrapolation and line sear…
Adaptive gradient methods converge faster with over-parameterization and line-search.
problem Training over-parameterized models using adaptive gradient methods.
method Simplified setting of smooth, convex losses with over-parameterized models, proving convergence rates and demonstrating improvements with line-search techniques.
result Adaptive gradient methods, particularly AMSGrad, converge faster with line-search techniques.
Adaptive SGD with Line-Search and Polyak Stepsizes: Nonconvex Convergence and Accelerated Ratesmath.OC
Improved SGD methods converge faster for nonconvex optimization.
problem Nonconvex optimization challenges in machine learning.
method Adaptive SGD with line-search and Polyak stepsizes.
result Unified convergence rates for various nonconvex functions.
GOLS-I automatically determines learning rates for various neural network training algorithms.
problem Adapting learning rates in stochastic training algorithms for neural networks.
method Gradient-Only Line Search (GOLS-I) for automatically setting learning rates.
result GOLS-I learning rate schedules are competitive with manually tuned rates across multiple algorithms, architectures, datasets, and loss functions.
In this paper, we propose a convergent parallel best-response algorithm with the exact line search for the nondifferentiable nonconvex sparsity-regularized rank minimization problem. On the one hand, it exhibits a faster convergence than subgradient algorithms and block coordinate descent algorithms. On the other hand,…
Armijo line-search speeds up gradient descent for various functions.
problem Improving convergence rate of gradient descent.
method Applying Armijo line-search to adjust step-size in gradient descent.
result GD with Armijo line-search converges faster than GD with a fixed step-size.
A new line search rule improves support recovery in high-dimensional data.
problem Support recovery in high-dimensional data analysis with penalty.
method Data-driven line search rule for adaptive step size determination.
result Proves error bound without restrictions on cost functional.
New algorithm optimizes AUC in binary classification and changepoint detection.
problem Difficult to optimize AUC in binary classification and changepoint detection.
method Proposes efficient path-following algorithms for choosing optimal learning rate.
result Proposed line search algorithm computes complete AUM/AUC representation.
The group lasso is a penalized regression method, used in regression problems where the covariates are partitioned into groups to promote sparsity at the group level. Existing methods for finding the group lasso estimator either use gradient projection methods to update the entire coefficient vector simultaneously at e…
Auto-conditioned primal-dual hybrid gradient method and alternating direction method of multipliersmath.OC
New methods solve saddle point problems without line search.
problem Solving saddle point problems efficiently and adaptively.
method Auto-conditioned primal-dual hybrid gradient (AC-PDHG) and auto-conditioned ADMM (AC-ADMM) methods.
result Methods achieve optimal complexity and convergence guarantees.
GOALS improves learning rate selection for dynamic MBSS in deep learning.
problem Challenges in selecting learning rates for dynamic MBSS in deep learning.
method Gradient-only approximation line search (GOALS) for dynamic MBSS loss functions.
result GOALS reduces model errors in multimodal cases.
Online boosting method improves weak to strong learner.
problem Online learning of weak to strong learner.
method Extends batch GentleAdaBoost to online approach with line search.
result Online boosting performs better than other methods.
Simple DP algorithms find approximate solutions for nonconvex ERM.
problem Finding approximate solutions to nonconvex ERM problems with privacy.
method Differential privacy, descent directions, line search, mini-batching, two-phase strategy.
result Effective algorithms for nonconvex ERM with privacy guarantees.
Paper introduces a privacy-preserving line search method for optimization.
problem Optimization performance depends on step size tuning, which is difficult and privacy-sensitive.
method Introduces a stochastic adaptive line search algorithm that satisfies differential privacy.
result The algorithm efficiently uses privacy budget and outperforms existing private optimizers.
Empirical study towards understanding line search approximations for training neural networksstat.ML
Choosing appropriate step sizes is critical for reducing the computational cost of training large-scale neural network models. Mini-batch sub-sampling (MBSS) is often employed for computational tractability. However, MBSS introduces a sampling error, that can manifest as a bias or variance in a line search. This is bec…
Paper introduces FoMoH for optimization without backpropagation.
problem Optimizing machine learning models without backpropagation.
method Second-order hyperplane search, forward-mode stochastic gradient method, hyper-dual numbers, FoMoH.
result Developed a novel optimization algorithm that avoids backpropagation.
A new method approximates expected empirical loss for stochastic deep learning tasks.
problem Determining optimal step sizes for stochastic gradient descent in deep learning.
method Applying one-dimensional function fitting to noisy losses of vertical cross sections to approximate expected empirical loss.
result The method leads to a robust and straightforward optimization method that performs well across datasets and architectures.
A new L-BFGS method tackles large-scale optimization with fewer evaluations.
problem Efficiently solving large-scale unconstrained optimization problems.
method Proposes a regularized L-BFGS method with line search techniques.
result Shows global convergence and robust performance in numerical tests.
SALSA automatically adjusts learning rates in stochastic gradient methods.
problem Automatic adjustment of learning rates in stochastic gradient methods.
method SALSA uses a line-search procedure to gradually increase the learning rate, then a statistical test to decrease it.
result SALSA matches the performance of best hand-tuned learning rate schedules in deep learning tasks.
Learning rates in stochastic neural network training are currently determined a priori to training, using expensive manual or automated iterative tuning. This study proposes gradient-only line searches to resolve the learning rate for neural network training algorithms. Stochastic sub-sampling during training decreases…
The High Line: Exact Risk and Learning Rate Curves of Stochastic Adaptive Learning Rate Algorithmsmath.OC
Exact risk and learning rate curves derived for adaptive SGD on high-dimensional problems.
problem Analyzing risk and learning rate dynamics in high-dimensional optimization problems.
method Developed a framework to give exact expressions for risk and learning rate curves using ODEs.
result Exact expressions for risk and learning rate curves, with detailed analysis of two adaptive learning rates.
Stochastic gradient descent on manifolds improves low-rank approximation.
problem Efficiently approximate large matrices with lower rank.
method Stochastic gradient descent on a manifold.
result Algorithm outperforms Euclidean space methods on Netflix Prize data.
Monte Carlo Tree Search (MCTS) algorithms perform simulation-based search to improve policies online. During search, the simulation policy is adapted to explore the most promising lines of play. MCTS has been used by state-of-the-art programs for many problems, however a disadvantage to MCTS is that it estimates the va…
In this paper we present a novel quasi-Newton algorithm for use in stochastic optimisation. Quasi-Newton methods have had an enormous impact on deterministic optimisation problems because they afford rapid convergence and computationally attractive algorithms. In essence, this is achieved by learning the second-order (…
Novel approach simplifies VI problems with faster performance.
problem Black-box VI optimization problems.
method Sample Average Approximation (SAA) combined with quasi-Newton methods and line search.
result Achieves faster performance than existing methods.
Investigating the interaction between gradient-only line searches and different activation functionsstat.ML
GOLS finds activation functions affect training robustness, especially ReLU.
problem Investigate how different activation functions impact GOLS in neural network training.
method Identify SNN-GPPs for GOLS, analyze activation function effects on gradient continuity.
result GOLS robust for most activation functions but sensitive to ReLU.
We extend the well-known BFGS quasi-Newton method and its memory-limited variant LBFGS to the optimization of nonsmooth convex objectives. This is done in a rigorous fashion by generalizing three components of BFGS to subdifferentials: the local quadratic model, the identification of a descent direction, and the Wolfe …
In this paper, we propose a successive convex approximation framework for sparse optimization where the nonsmooth regularization function in the objective function is nonconvex and it can be written as the difference of two convex functions. The proposed framework is based on a nontrivial combination of the majorizatio…
The standard L-BFGS method relies on gradient approximations that are not dominated by noise, so that search directions are descent directions, the line search is reliable, and quasi-Newton updating yields useful quadratic models of the objective function. All of this appears to call for a full batch approach, but sinc…
Unified framework for sparse logistic regression with nonconvex regularization.
problem Sparse logistic regression with nonconvex regularization.
method Unified framework, line search criteria for nonconvex terms.
result Effective classification and feature selection at lower computational cost.
Stochastic approximation is one of the effective approach to deal with the large-scale machine learning problems and the recent research has focused on reduction of variance, caused by the noisy approximations of the gradients. In this paper, we have proposed novel variants of SAAG-I and II (Stochastic Average Adjusted…
Extends NAS to learn both intra-cell and inter-cell architectures for language modeling.
problem Limited NAS systems restrict search to recurrent or convolutional cells.
method Designs a joint learning method to perform intra-cell and inter-cell NAS simultaneously.
result Significantly outperforms a strong baseline on PTB and WikiText data.
Attention-based encoder decoder network uses a left-to-right beam search algorithm in the inference step. The current beam search expands hypotheses and traverses the expanded hypotheses at the next time step. This traversal is implemented using a for-loop program in general, and it leads to speed down of the recogniti…
Improved causal discovery methods for large graphs without strict assumptions.
problem Sub-optimal solutions due to faithfulness assumption violations.
method Super-structure estimation and local search strategies.
result The proposed method scales to hundreds of nodes with high accuracy.
Yau's Affine Normal Descent optimizes smooth unconstrained problems with geometrically adapted directions.
problem Optimizing smooth unconstrained problems with geometrically adapted directions.
method Yau's Affine Normal Descent (YAND) uses the equi-affine normal of level-set hypersurfaces as search directions.
result YAND converges globally under standard smoothness assumptions and locally quadratically near nondegenerate minimizers.
Negative step sizes improve second-order methods for neural networks.
problem Second-order methods discard negative curvature, limiting their effectiveness.
method Introduce negative step sizes in second-order methods combined with Wolfe line search.
result Negative step sizes lead to global convergence and improved performance.
We consider the task of mapping pseudocode to long programs that are functionally correct. Given test cases as a mechanism to validate programs, we search over the space of possible translations of the pseudocode to find a program that passes the validation. However, without proper credit assignment to localize the sou…
The digital traces of bubbles: feedback cycles between socio-economic signals in the Bitcoin economyphysics.soc-ph
What is the role of social interactions in the creation of price bubbles? Answering this question requires obtaining collective behavioural traces generated by the activity of a large number of actors. Digital currencies offer a unique possibility to measure socio-economic signals from such digital traces. Here, we foc…
New method selects critical DER scenarios for distribution grid investment planning.
problem Determining critical DER adoption scenarios for risk assessment in distribution grids.
method Bayesian Optimization framework using Gaussian Process surrogates and Pareto-critical acquisition function.
result Statistical guarantee and significant speed-up over exhaustive search in selecting critical DER scenarios.
New algorithms improve SGD convergence and reduce variance for over-parameterized models.
problem Slower convergence in non-interpolation settings for SGD variants.
method Proposed AdaSPS and AdaSLS with variance reduction for robust convergence.
result Achieves faster convergence rates and robustness in non-interpolation settings.
Mini-batch sub-sampling in neural network training is unavoidable, due to growing data demands, memory-limited computational resources such as graphical processing units (GPUs), and the dynamics of on-line learning. In this study we specifically distinguish between static mini-batch sub-sampled loss functions, where mi…
New Frank-Wolfe algorithm speeds up SVM-type multi-category learning.
problem Improving pattern recognition performance in multi-category SVM learning.
method Developed a new optimization algorithm based on Frank-Wolfe framework for MC-SVM variants.
result Closed-form solutions for direction finding and line search in the Frank-Wolfe framework for MC-SVM.
In this paper, we propose a new algorithm to speed-up the convergence of accelerated proximal gradient (APG) methods. In order to minimize a convex function , our algorithm introduces a simple line search step after each proximal gradient step in APG so that a biconvex function is minimi…