Value iteration is a fixed point iteration technique utilized to obtain the optimal value function and policy in a discounted reward Markov Decision Process (MDP). Here, a contraction operator is constructed and applied repeatedly to arrive at the optimal solution. Value iteration is a first order method and therefore …
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 “Iterative Optimization”
OptEx accelerates first-order optimization with parallelized iterations.
problem Inefficiencies in first-order optimization algorithms for complex tasks.
method Approximately parallelized iterations using kernelized gradient estimation.
result OptEx achieves substantial efficiency improvements with an effective acceleration rate of .
Developed an efficient iterative algorithm for SVI model.
problem SVI model's optimizer's strong dependence on input starting point.
method Fixed-point and least-square optimizer.
result Convergence results for fixed-point iterative algorithm in certain situations.
Adaptive optimal control of nonlinear dynamic systems with deterministic and known dynamics under a known undiscounted infinite-horizon cost function is investigated. Policy iteration scheme initiated using a stabilizing initial control is analyzed in solving the problem. The convergence of the iterations and the optim…
Establishes geometric convergence of iterative optimization algorithms.
problem Analyzes convergence of iterative optimization algorithms under general assumptions.
method General framework for iterative optimization algorithms, proving asymptotic geometric convergence and providing convergence rates.
result Asymptotic geometric convergence of iterative optimization algorithms with exact rate.
PACE optimizes training for averaged language models, improving performance.
problem How to optimize training for averaged language model iterates.
method Formulated as an optimal-control problem, solved for minimizing error of the average with a penalty on intervention size.
result PACE improves the limiting squared error of the iterate-average estimator by an arbitrarily large factor on some instances.
Paper proves suboptimal convergence rate of last iterate for SGDM.
problem Proves suboptimal convergence rate of last iterate for SGDM.
method Focuses on convergence rate of last iterate of SGDM, introduces Follow-The-Regularized-Leader-based algorithms.
result Shows optimal convergence rate of last iterate for unconstrained convex stochastic optimization problems.
Improving optimization for iterate-averaged language models
problem How to optimize the averaged model returned by Language Model pipelines
method Formulating optimizer design as an optimal-control problem
result Proven convergence rate and strict improvement in squared error
SCOPE iteratively optimizes sparsity-constrained problems without tuning hyperparameters.
problem Optimizing sparsity-constrained problems in signal processing, statistics, and machine learning.
method SCOPE (Sparsity-Constrained Optimization via sPlicing itEration) replaces gradient steps with a splicing operation guided by the objective value.
result SCOPE achieves linear convergence and superior support recovery performance.
A new method solves optimization problems on the generalized Stiefel manifold using random estimates of B.
problem Optimization over the generalized Stiefel manifold in applications like CCA, ICA, and GEVP.
method Cheap stochastic iterative method that converges to critical points on the manifold.
result The method achieves the same convergence rates as Riemannian optimization but with lower per-iteration cost.
Stability result for a popular algorithm in optimal transport.
problem Stability of the Iterative Proportional Fitting Procedure in time and metric.
method Uniform stability analysis in the 1-Wasserstein metric.
result Quantitative stability result for entropy-regularized Optimal Transport and Schrödinger bridges.
We propose and analyze a new parallel coordinate descent method---`NSync---in which at each iteration a random subset of coordinates is updated, in parallel, allowing for the subsets to be chosen non-uniformly. We derive convergence rates under a strong convexity assumption, and comment on how to assign probabilities t…
While classic work in convex-concave min-max optimization relies on average-iterate convergence results, the emergence of nonconvex applications such as training Generative Adversarial Networks has led to renewed interest in last-iterate convergence guarantees. Proving last-iterate convergence is challenging because ma…
A novel framework refines diffusion models iteratively for better downstream reward optimization.
problem Optimizing reward functions during inference of diffusion models.
method Iterative refinement process with noising and reward-guided denoising steps.
result Superior empirical performance in protein and DNA design.
Minimax optimal convergence rates for classes of stochastic convex optimization problems are well characterized, where the majority of results utilize iterate averaged stochastic gradient descent (SGD) with polynomially decaying step sizes. In contrast, SGD's final iterate behavior has received much less attention desp…
This work addresses the convergence of SGD's final iterate without restrictive assumptions.
problem Prove optimal convergence rate of SGD's final iterate without compact domains or bounded noise.
method Unified proof for general domains, composite objectives, non-Euclidean norms, etc.
result First unified convergence rates in expectation and high probability.
Last-Iterate Convergence of Saddle-Point Optimizers via High-Resolution Differential Equationsmath.OC
New ODE models show saddle-point optimization methods converge differently, with last-iterate convergence for OGDA.
problem Analyzing convergence properties of saddle-point optimization methods.
method High-Resolution Differential Equations (HRDEs) to design differential equation models for saddle-point optimization methods.
result HRDEs reveal last-iterate convergence for Optimistic Gradient Descent Ascent (OGDA) in bilinear games.
New analysis of stochastic approximation with non-expansive mappings.
problem Finite-time analysis of two-time-scale stochastic approximation with non-expansive mappings.
method Studied two-time-scale stochastic approximation algorithms with non-expansive mappings and projection steps.
result Last-iterate mean square residual error decays at a rate .
We propose a clustering-based iterative algorithm to solve certain optimization problems in machine learning, where we start the algorithm by aggregating the original data, solving the problem on aggregated data, and then in subsequent steps gradually disaggregate the aggregated data. We apply the algorithm to common m…
Improved iterative hard thresholding for faster, sparser solutions.
problem Finding sparser solutions without sacrificing runtime.
method Adaptive regularization framework applied to iterative hard thresholding.
result Returns solutions with sparsity , improving over existing methods.
Adaptive SAA solves large-scale stochastic linear programs efficiently.
problem Solving large-scale two-stage stochastic linear programs.
method Iterative algorithm with adaptive sample size and warm starts.
result The algorithm converges to the true solution set with a probabilistic guarantee.
This paper tightens the law of the iterated logarithm for empirical KL_inf, applicable to unbounded data.
problem Developing nonasymptotic concentration bounds for empirical KL_inf with optimal constants and rates.
method Presenting a tight law of the iterated logarithm for empirical KL_inf, applicable to unbounded data.
result A tight law of the iterated logarithm for empirical KL_inf, applicable to unbounded data.
Theoretical and Numerical Analysis of Approximate Dynamic Programming with Approximation Errorseess.SY
This study is aimed at answering the famous question of how the approximation errors at each iteration of Approximate Dynamic Programming (ADP) affect the quality of the final results considering the fact that errors at each iteration affect the next iteration. To this goal, convergence of Value Iteration scheme of ADP…
Entropy regularized algorithms such as Soft Q-learning and Soft Actor-Critic, recently showed state-of-the-art performance on a number of challenging reinforcement learning (RL) tasks. The regularized formulation modifies the standard RL objective and thus generally converges to a policy different from the optimal gree…
RL accelerates portfolio optimization and option pricing by dynamically adjusting preconditioner sizes.
problem Large linear systems in portfolio optimization and option pricing lead to slow convergence.
method Reinforcement Learning (RL) dynamically adjusts block-preconditioner sizes to accelerate convergence.
result RL-driven solver significantly reduces computational cost and accelerates convergence.
On the Benefits of Multiple Gossip Steps in Communication-Constrained Decentralized Optimizationcs.LG
Multiple gossip steps improve decentralized optimization convergence.
problem Efficiently optimizing large-scale machine learning models with limited communication.
method Integrates multiple gossip steps between gradient descent iterations in compressed decentralized optimization.
result Convergence to within ε of the optimal value for smooth non-convex objectives.
A technique identifies memoryless algorithms approximating memory-dependent optimization methods.
problem Understanding how memory in optimization algorithms affects loss and generalization.
method Introducing a general technique to replace past iterates with the current one and adding a correction term.
result Lion does not have the same implicit anti-regularization as AdamW, explaining its better generalization performance.
Study spectral learning for odeco tensors, addressing initialization bottlenecks.
problem Recovering orthogonally decomposable tensors under noise.
method Investigates perturbation bounds, non-convex optimization, and initialization strategies.
result Initialization is the main bottleneck for efficient algorithms.
Iterative Hessian sketch (IHS) is an effective sketching method for modeling large-scale data. It was originally proposed by Pilanci and Wainwright (2016; JMLR) based on randomized sketching matrices. However, it is computationally intensive due to the iterative sketch process. In this paper, we analyze the IHS algorit…
We present an optimizer which uses Bayesian optimization to tune the system parameters of distributed stochastic gradient descent (SGD). Given a specific context, our goal is to quickly find efficient configurations which appropriately balance the load between the available machines to minimize the average SGD iteratio…
In a recent series of papers it has been established that variants of Gradient Descent/Ascent and Mirror Descent exhibit last iterate convergence in convex-concave zero-sum games. Specifically, \cite{DISZ17, LiangS18} show last iterate convergence of the so called "Optimistic Gradient Descent/Ascent" for the case of \t…
This work studies the statistical performance of Sinkhorn iterations in estimating Schrödinger bridges.
problem Estimating Schrödinger bridges with limited samples.
method Intermediate Sinkhorn iterations applied to the time-dependent drifts of SDEs.
result Established a statistical bound on the squared total variation error of Sinkhorn bridge iterations.
Optimal ridge regularization computed iteratively from generative parameters.
problem Finding the optimal ridge regularization strength for linear regression.
method Iterative procedure to compute optimal regularization strength numerically.
result The proposed procedure attains near-optimal generalization across various conditions.
Iterative procedures for parameter estimation based on stochastic gradient descent allow the estimation to scale to massive data sets. However, in both theory and practice, they suffer from numerical instability. Moreover, they are statistically inefficient as estimators of the true parameter value. To address these tw…
HyperImpute improves iterative imputation by automatically selecting models and hyperparameters.
problem Imputing missing values in datasets with variable model specifications.
method Generalized iterative imputation framework that adapts and configures models and hyperparameters automatically.
result Demonstrates superior imputation accuracy compared to benchmarks.
Early stopping of iterative algorithms is an algorithmic regularization method to avoid over-fitting in estimation and classification. In this paper, we show that early stopping can also be applied to obtain the minimax optimal testing in a general non-parametric setup. Specifically, a Wald-type test statistic is obtai…
DSPI connects natural policy gradient to policy iteration, proving global convergence.
problem Optimizing policies in reinforcement learning.
method DSPI framework, combining smoothed policy iteration and natural policy gradient.
result DSPI achieves geometric convergence and optimal complexity for policy optimization.
Improved convergence rates for saddle-point optimization algorithms.
problem Understanding last-iterate convergence rates for saddle-point optimization algorithms in constrained settings.
method Expanding the understanding of last-iterate convergence for Optimistic Gradient Descent Ascent (OGDA) and Optimistic Multiplicative Weights Update (OMWU) in the constrained setting.
result Linear last-iterate convergence achieved with a universal constant learning rate for OMWU in bilinear games over the simplex.
Recently, deep neural networks (DNNs) have shown advantages in accelerating optimization algorithms. One approach is to unfold finite number of iterations of conventional optimization algorithms and to learn parameters in the algorithms. However, these are forward methods and are indeed neither iterative nor convergent…
New method solves constrained stochastic optimization problems efficiently.
problem Online statistical inference of constrained stochastic nonlinear optimization problems.
method Stochastic Sequential Quadratic Programming (StoSQP) with iterative sketching solver.
result The rescaled primal-dual sequence converges to a mean-zero Gaussian distribution.
This work's purpose is to understand the dynamics of some social systems whose properties can be captured by certain iterated function systems. To achieve this intension, we start from the theory of iterated function systems, and then we study two specific economic models on random utility function and optimal stochast…
Dynamic Programming (DP) provides standard algorithms to solve Markov Decision Processes. However, these algorithms generally do not optimize a scalar objective function. In this paper, we draw connections between DP and (constrained) convex optimization. Specifically, we show clear links in the algorithmic structure b…
Iterative shrinkage/thresholding algorithm (ISTA) is a well-studied method for finding sparse solutions to ill-posed inverse problems. In this letter, we present a data-driven scheme for learning optimal thresholding functions for ISTA. The proposed scheme is obtained by relating iterations of ISTA to layers of a simpl…
Stochastic Coordinate Minimization with Progressive Precision for Stochastic Convex Optimizationstat.ML
Optimizes CM for stochastic convex optimization with progressive precision.
problem Stochastic nature of objective function in convex optimization.
method Iterative coordinate minimization with optimal precision control.
result Order-optimal regret performance for strongly convex and nonsmooth functions.
Optimizes convergence rate of stochastic proximal algorithms for composite convex problems.
problem Solving composite convex optimization problems with composite regularizers.
method Analyzed proximal stochastic gradient method and randomized incremental proximal method under relaxed variance assumptions.
result Proves convergence rate for last iterate of both algorithms under componentwise convexity and smoothness.
New method averages SGD iterates to achieve adjustable regularization.
problem Overfitting in machine learning models.
method Averaging SGD iterates for regularized solutions.
result Obtain regularized solutions without tuning parameters.
In a discounted reward Markov Decision Process (MDP), the objective is to find the optimal value function, i.e., the value function corresponding to an optimal policy. This problem reduces to solving a functional equation known as the Bellman equation and a fixed point iteration scheme known as the value iteration is u…
On the Role of Normalization in Binary Iterative Hard Thresholding for 1-bit Compressed Sensingcs.IT
This paper resolves BIHT convergence, showing normalization is not necessary in noiseless settings but crucial for robustness.
problem Analyzing convergence and robustness of BIHT for 1-bit compressed sensing.
method Characterizes BIHT convergence and robustness, proving necessity of normalization for robustness under sign corruptions.
result Per-iteration normalization is not necessary for optimal recovery in noiseless settings but is crucial for robustness under sign corruptions.