Improved SGD with line-search achieves fast convergence rates for various models.
problem Achieving fast convergence rates for stochastic gradient descent (SGD) in over-parameterized models.
method Proposes using line-search techniques to automatically set the step-size in SGD, proving convergence rates for convex, strongly-convex, and non-convex functions.
result SGD with Armijo line-search attains deterministic convergence rates for convex and strongly-convex functions, and linear convergence for non-convex functions.
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…
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.
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…
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.
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…
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.
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.
Stochastic quasi-Newton tackles noisy gradients in optimization.
problem Optimizing with noisy data in stochastic settings.
method Extends quasi-Newton methods to handle stochastic gradients through flexible Hessian modeling and line-search regularization.
result Demonstrates superior performance in maximum likelihood estimation for complex models.
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.
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.
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…
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.
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.
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.
Study examines line search approximations for neural networks using MBSS.
problem Reducing computational cost in training large-scale neural networks.
method Empirical study of quadratic line search approximations for dynamic MBSS loss functions, enforcing different types of function and derivative information.
result Selectively enforcing information in approximations reduces the variance of predicted step sizes.
New method finds optimal learning rates for neural nets.
problem Finding optimal learning rates in stochastic neural networks.
method Gradient-only line searches using Non-negative Associative Gradient Projection Points (NN-GPPs).
result Learning rates can be reliably resolved as step sizes along search directions.
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.
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.
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.
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,…
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.
A new line search rule improves support recovery in high-dimensional data.
problem Support recovery in high-dimensional data analysis with ℓ0 penalty. method Data-driven line search rule for adaptive step size determination.
result Proves ℓ2 error bound without restrictions on cost functional. 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 …
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…
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…
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.
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.
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.
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…
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.
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.
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.
Optimistic method adapted for faster convex-concave min-max problems.
problem Solving convex-concave min-max optimization problems efficiently.
method Adaptive, line search-free second-order methods combining optimistic updates and second-order information.
result Achieves optimal convergence rate without line search or backtracking.
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…
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.
New Q-Newton's method avoids saddle points and converges quadratically.
problem Optimizing functions with saddle points and ensuring convergence guarantees.
method Modified New Q-Newton's method with Backtracking line search.
result Theorem for Morse functions: quadratic convergence to local minima.
SPoC uses search to translate pseudocode into correct programs with error localization.
problem Mapping pseudocode to functionally correct long programs.
method Search-based approach guided by compilation errors for credit assignment.
result Search improves synthesis success rate from 25.6% to 44.7%.
In this paper we consider a general matrix factorization model which covers a large class of existing models with many applications in areas such as machine learning and imaging sciences. To solve this possibly nonconvex, nonsmooth and non-Lipschitz problem, we develop a non-monotone alternating updating method based o…
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.
Improved DANE algorithm for faster convergence in distributed machine learning.
problem Challenges in convergence of DANE algorithm for general convex functions.
method Introducing variants of DANE with backtracking line search and heavy-ball method.
result Proved global and local convergence rates for quadratic and non-quadratic strongly convex functions.
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 f(x), our algorithm introduces a simple line search step after each proximal gradient step in APG so that a biconvex function f(θx) is minimi…
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…
New methods solve MI problems with locally Lipschitz operators, improving solution efficiency.
problem Solving monotone inclusions with locally Lipschitz continuous operators.
method Primal-dual extrapolation methods using backtracking line search.
result Improved operation complexity for solving MI problems.