Parallel algorithm finds sparse solutions for nonconvex problems.
problem Nonconvex sparsity-regularized rank minimization.
method Parallel best-response algorithm with exact line search.
result Guaranteed convergence to a stationary point.
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.
169,181 papers · 148 categories
Trend · papers per month
48 results for “exact line search”
This research introduces a line search method for deep learning that uses parabolic approximations.
problem Finding optimal step sizes for deep learning optimization.
method Parabolic approximation line search approach.
result The batch loss over lines in negative gradient direction is mostly convex locally and suitable for parabolic approximations.
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.
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 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.
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.
Paper proposes algorithms for sparse signal estimation with nonconvex regularization.
problem Sparse signal estimation with nonconvex regularization.
method Successive convex approximation framework combining majorization-minimization and line search.
result Flexibility, fast convergence, low complexity, guaranteed convergence to stationary point.
New method solves constrained optimization problems efficiently.
problem Equality-constrained nonlinear, nonconvex optimization problems.
method Adaptive inexact Newton method with randomized iterative sketching.
result Global almost sure convergence and local linear/superlinear convergence.
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 …
Adaptive IHS improves sketching for large-scale data.
problem Efficiently modeling large-scale data with iterative Hessian sketch.
method Deterministic A-optimal subsampling for improved IHS.
result A-optimal IHS outperforms existing accelerated IHS methods.
New algorithm solves stochastic optimization problems with unknown gradients.
problem Solving nonlinear optimization problems with stochastic objectives and deterministic constraints.
method Adaptive SQP with differentiable exact augmented Lagrangian and stochastic line search.
result Global convergence established for both non-adaptive and adaptive SQP methods.
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.
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.
Introduces GOLS-I for automatically determining step sizes in neural networks without surrogates.
problem Determining step sizes in neural network training using predetermined rules or expensive global optimization strategies.
method Gradient-Only Line Searches (GOLS-I) that are Inexact.
result GOLS-I is a competitive strategy for reliably determining step sizes in stochastic loss functions.
Study on adversarial training dynamics in high dimensions using SGD.
problem Analyzing adversarial training of models in high-dimensional settings.
method Deriving deterministic equivalents for SGD iterates under Gaussian mixtures.
result No constant learning rate guarantees monotone descent in adversarial training.
A new method combines extrapolation and line search for solving nonconvex, nonsmooth optimization problems.
problem Nonconvex, nonsmooth optimization problems in machine learning and image processing.
method Proximal gradient method with extrapolation and line search (PGels).
result The method reduces to existing algorithms under proper parameter choices and converges to stationary points.
Empirical study towards understanding line search approximations for training neural networksstat.ML
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.
Paper improves full-text search engines for fast exact NNS in binary codes.
problem Efficient nearest neighbor search in Hamming space for full-text search engines.
method Revisits and combines three techniques from information retrieval: bit operation, subs-code filtering, and data preprocessing with permutation.
result Significant speed-ups for NNS in binary codes over state-of-the-art term match approach.
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…
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.
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.
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.
Exact LAD line fitting via PALB with linear scaling and speed.
problem Robust line fitting for data with outliers.
method Piecewise Affine Lower-Bounding (PALB) method using supporting lines and subdivision scheme.
result Empirical log-linear scaling and significantly faster than LP and IRLS methods.
EGN optimizes deep neural networks with exact Gauss-Newton for large-scale problems.
problem Training deep neural networks efficiently and accurately.
method Stochastic second-order optimization using low-rank linear algebra and matrix factorization.
result Converges to stationary points of the objective function under mild assumptions.
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.
The conjugate gradient (CG) method is an efficient iterative method for solving large-scale strongly convex quadratic programming (QP). In this paper we propose some generalized CG (GCG) methods for solving the -regularized (possibly not strongly) convex QP that terminate at an optimal solution in a finite numb…
Mapping Among Line Elementsmath.DG
Paper maps Hamiltonians and line elements in manifolds.
problem Mapping among generalized Hamiltonians and line elements.
method Constructing Calabi's Riemannian Line Elements and solving matrix Riccati equations.
result Analytical and exact solutions of mapping between manifolds.
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.
This is the second part of the proof of the exact traiangles in Seiberg-Witten Floer theory. We analyse the splitting and gluing of flow lines of the Chern-Simons-Dirac functional when the underlying three-manifold splits along a torus. (two corrections added)
A method for online tensor dictionary learning is proposed. With the assumption of separable dictionaries, tensor contraction is used to diminish a -way model of into a simple matrix equation of with a real-time capability. To avoid numerical instability d…
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.
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.
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.
Exact causal network discovery is polynomial for sparse networks.
problem Finding the optimal causal Bayesian network from data is computationally hard.
method Pruning the search space using network properties, combined with dynamic programming and shortest-path searches.
result Exact discovery is polynomial for sparse causal Bayesian networks.
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.
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 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.
New equations reveal how cylinder power in progressive lenses depends on geodesic curvature.
problem Current understanding of cylinder power in progressive lenses is incomplete.
method Derived complete compatibility equations for spatially-varying curvature surfaces.
result Cylinder power depends on geodesic curvature, not just principal curvature.
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.
Improved L-BFGS for large-scale ML with progressive batching.
problem Combining fast generalization with reliable line search in large-scale ML.
method Progressive batching, stochastic line search, stable quasi-Newton updating.
result Performs well on training logistic regression and deep neural networks.
HAMD optimizes cubic portfolios without quadratization, achieving better results.
problem Optimizing higher-order portfolio models with reduced distortion.
method Hybrid pipeline combining continuous Hamiltonian search, cardinality-preserving projection, and iterated local search.
result HAMD achieves significantly lower native cubic objective values than classical heuristics.
A new method clusters intersecting lines using hypergraphs.
problem Clustering intersecting lines in subspace clustering.
method Constructing a geometric hypergraph and using spectral algorithm.
result Achieves information-theoretic bounds for line clustering.
Novel SAAG variants reduce variance in large-scale learning.
problem Reduction of variance in noisy gradient approximations for large-scale machine learning.
method Proposed SAAG-III and IV variants with SBAS for step size determination.
result Proved linear convergence of SAAG-IV for all smoothness and strong-convexity combinations.