In machine learning research, the proximal gradient methods are popular for solving various optimization problems with non-smooth regularization. Inexact proximal gradient methods are extremely important when exactly solving the proximal operator is time-consuming, or the proximal operator does not have an analytic sol…
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 “inexact algorithms”
Convergence and Complexity Guarantee for Inexact First-order Riemannian Optimization Algorithmsmath.OC
Inexact Riemannian optimization converges to stationary points efficiently.
problem Analyzing convergence and complexity of inexact Riemannian optimization.
method Tangential Block Majorization-Minimization (tBMM) framework.
result tBMM converges to an ε-stationary point within O(ε⁻²) iterations.
New characterization limits sampling with inexact scores.
problem Limiting sampling with inexact scores for unbiased results.
method Characterized types of inexact score oracle access.
result Weaker error assumptions rule out tractability of unbiased sampling.
A New Inexact Proximal Linear Algorithm with Adaptive Stopping Criteria for Robust Phase Retrievalmath.OC
New algorithm solves phase retrieval with adaptive stopping criteria.
problem Robust phase retrieval problem as nonsmooth, nonconvex optimization.
method Inexact proximal linear algorithm with adaptive stopping criteria.
result Proposed methods are more efficient than existing methods.
Inexact acquisition solutions in BO lead to sublinear cumulative regret.
problem Inexact maximization of acquisition functions in Bayesian optimization.
method Define inaccuracy measure, establish cumulative regret bounds for GP-UCB and GP-TS.
result Inexact BO algorithms can achieve sublinear cumulative regret under appropriate inaccuracy conditions.
We propose novel first-order stochastic approximation algorithms for canonical correlation analysis (CCA). Algorithms presented are instances of inexact matrix stochastic gradient (MSG) and inexact matrix exponentiated gradient (MEG), and achieve -suboptimality in the population objective in $\operatorname{poly}(\fr…
In this paper, we consider the convergence of an abstract inexact nonconvex and nonsmooth algorithm. We promise a pseudo sufficient descent condition and a pseudo relative error condition, which are both related to an auxiliary sequence, for the algorithm; and a continuity condition is assumed to hold. In fact, a lot o…
Inexact and Stochastic Generalized Conditional Gradient with Augmented Lagrangian and Proximal Stepmath.OC
New algorithm tackles complex optimization problems with inexact and stochastic methods.
problem Solving complex optimization problems with inexact and stochastic methods.
method Developed ICGALP algorithm for composite minimization problems with inexact computations.
result Convergence of Lagrangian to an optimum and asymptotic feasibility of the affine constraint.
We propose a supervised anomaly detection method for data with inexact anomaly labels, where each label, which is assigned to a set of instances, indicates that at least one instance in the set is anomalous. Although many anomaly detection methods have been proposed, they cannot handle inexact anomaly labels. To measur…
This paper analyzes the bias of inexact MCMC methods in high dimensions.
problem Understanding the bias of inexact MCMC methods in high-dimensional spaces.
method Establishing bounds on Wasserstein distances between inexact MCMC methods and target distributions.
result The asymptotic bias of ULA and uHMC depends on key quantities related to the target distribution or the stationary probability measure of the scheme.
In this paper we present a convergence rate analysis of inexact variants of several randomized iterative methods. Among the methods studied are: stochastic gradient descent, stochastic Newton, stochastic proximal point and stochastic subspace ascent. A common feature of these methods is that in their update rule a cert…
New algorithm extends LMC to more complex potentials.
problem Addressing limitations of existing LMC methods.
method Inexact Proximal Langevin Algorithm (IPLA).
result Improved convergence rates and broader applicability.
Paper shows how gradient concentration helps in learning from inexact data.
problem Learning from inexact and stochastic training data.
method Combines probabilistic gradient concentration with inexact optimization techniques.
result Derives sharp test error guarantees for learning.
In kernel methods, the kernels are often required to be positive definite, which restricts the use of many indefinite kernels. To consider those non-positive definite kernels, in this paper, we aim to build an indefinite kernel learning framework for kernel logistic regression. The proposed indefinite kernel logistic r…
Contextual Strongly Convex Simulation Optimization: Optimize then Predict with Inexact Solutionsstat.ML
Study optimizes decisions in real-time using inexact simulation solutions.
problem Real-time decision-making in simulation optimization with inexact solutions.
method Optimize then predict (OTP) approach, analyzing bias and variance in simulation-optimization algorithms.
result Unified analysis framework for OTP, establishing convergence rates and optimal allocation of computational budget.
We propose an inexact variable-metric proximal point algorithm to accelerate gradient-based optimization algorithms. The proposed scheme, called QNing can be notably applied to incremental first-order methods such as the stochastic variance-reduced gradient descent algorithm (SVRG) and other randomized incremental opti…
Optimizes solving complex min-max problems with stochastic and nonconvex elements.
problem Min-max problems with stochastic and nonconvex elements.
method Combines conic nonexpansiveness, refined inexact Halpern iteration, and multilevel Monte Carlo estimator.
result Optimal or best-known complexity guarantees for $ρ< rac{1}{L}$, improving previous results.
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.
A Class of Accelerated Fixed-Point-Based Methods with Delayed Inexact Oracles and Its Applicationsmath.OC
Develops accelerated fixed-point methods with delayed oracles for scientific computing.
problem Approximating fixed points of nonexpansive operators.
method Combines Nesterov's acceleration and KM iteration with delayed inexact oracles.
result Establishes improved convergence rates for fixed-point approximation.
In this paper we consider the problem of minimizing a convex function using a randomized block coordinate descent method. One of the key steps at each iteration of the algorithm is determining the update to a block of variables. Existing algorithms assume that in order to compute the update, a particular subproblem is …
Improved analysis for fair federated learning reduces dependence on noise floor.
problem Asymptotic stationarity in group fair federated learning with reduced noise floor dependence.
method DS FedProxGrad framework with inexact local proximal solutions and fairness regularization.
result Algorithm converges asymptotically to stationarity without dependence on a noise floor.
Inexact subgradient methods work well for semialgebraic functions with additive errors.
problem Approximate gradients in machine learning and optimization.
method Inexact subgradient methods with persistent additive errors in semialgebraic functions.
result Iterates eventually fluctuate near the critical set with a proximity of , where is the magnitude of subgradient evaluation errors.
Evolutionary forms, as well as exterior forms, are skew-symmetric differential forms. But in contrast to the exterior forms, the basis of evolutionary forms is deforming manifolds (with unclosed metric forms). Such forms possess a peculiarity, namely, the closed inexact exterior forms are obtained from that. The closur…
Inexact bilevel stochastic gradient methods for constrained and unconstrained lower-level problemsmath.OC
New methods solve complex optimization problems in machine learning.
problem Challenges in stochastic bilevel optimization with constraints and high variables.
method Inexact bilevel stochastic gradient methods for constrained and unconstrained lower-level problems.
result Comprehensive convergence theory for both unconstrained and constrained cases.
In [19], a general, inexact, efficient proximal quasi-Newton algorithm for composite optimization problems has been proposed and a sublinear global convergence rate has been established. In this paper, we analyze the convergence properties of this method, both in the exact and inexact setting, in the case when the obje…
In this two-part work, we propose an algorithmic framework for solving non-convex problems whose objective function is the sum of a number of smooth component functions plus a convex (possibly non-smooth) or/and smooth (possibly non-convex) regularization function. The proposed algorithm incorporates ideas from several…
Optimal Guarantees for Algorithmic Reproducibility and Gradient Complexity in Convex Optimizationcs.LG
New algorithms ensure reproducibility and optimal convergence in convex optimization.
problem Trade-off between reproducibility and convergence rate in convex optimization.
method Regularization-based algorithms for smooth convex minimization and minimax optimization.
result Achieves optimal reproducibility and near-optimal gradient complexity for various oracle settings.
We consider distributed convex optimization problems originated from sample average approximation of stochastic optimization, or empirical risk minimization in machine learning. We assume that each machine in the distributed computing system has access to a local empirical loss function, constructed with i.i.d. data sa…
New algorithms optimize convex functions with high-order derivatives.
problem Optimizing convex functions with high-order derivatives under various norms.
method Developed a non-Euclidean inexact accelerated proximal point method using an inexact uniformly convex regularizer.
result Showed nearly optimal algorithms for high dimensions in the black-box oracle model for -settings and all .
Paper tackles BNSL with IP, improving quality of solutions.
problem Bayesian Network Structure Learning (BNSL) with IP formulations.
method Inexact column generation using difference-of-submodular optimization.
result Improved solutions quality compared to state-of-the-art approaches.
An inexact LPA for DC composite optimization and application to matrix completions with outliersmath.OC
Paper proposes iLPA for solving DC composite optimization problems, with applications to matrix completion with outliers.
problem Solving nonconvex and nonsmooth DC composite optimization problems.
method Inexact linearized proximal algorithm (iLPA) for DC composite optimization problems.
result The iLPA achieves local R-linear convergence rate under the Kurdyka-Łöjasiewicz property.
We analyze the performance of alternating minimization for loss functions optimized over two variables, where each variable may be restricted to lie in some potentially nonconvex constraint set. This type of setting arises naturally in high-dimensional statistics and signal processing, where the variables often reflect…
New method tackles inexact bilevel optimization for faster parameter learning.
problem Nested optimization problems in bilevel learning with computationally difficult exact solutions.
method Inexact derivative-free optimization algorithms for approximate lower-level solutions.
result Global convergence and worst-case complexity for the proposed approach.
Unbiased method for Bayesian posterior means using kinetic Langevin dynamics.
problem Estimating Bayesian posterior means efficiently and accurately.
method Combines advanced splitting methods with enhanced gradient approximations in a multilevel Monte Carlo approach.
result The method achieves unbiased estimates with finite variance and central limit theorem properties.
Many scientific and engineering applications feature nonsmooth convex minimization problems over convex sets. In this paper, we address an important instance of this broad class where we assume that the nonsmooth objective is equipped with a tractable proximity operator and that the convex constraint set affords a self…
Second order Sobolev metrics are a useful tool in the shape analysis of curves. In this paper we combine these metrics with varifold-based inexact matching to explore a new strategy of computing geodesics between unparametrized curves. We describe the numerical method used for solving the inexact matching problem, appl…
Interpreting gradient methods as fixed-point iterations, we provide a detailed analysis of those methods for minimizing convex objective functions. Due to their conceptual and algorithmic simplicity, gradient methods are widely used in machine learning for massive data sets (big data). In particular, stochastic gradien…
This paper analyzes how errors accumulate in PCA's deflation method.
problem Error accumulation in PCA's deflation method.
method Mathematical analysis of inexact Hotelling's deflation method in two scenarios.
result Characterization of error propagation in PCA's deflation method.
The paper studies the solution of stochastic optimization problems in which approximations to the gradient and Hessian are obtained through subsampling. We first consider Newton-like methods that employ these approximations and discuss how to coordinate the accuracy in the gradient and Hessian to yield a superlinear ra…
Improved sampling algorithm with state-of-the-art complexity bounds.
problem Efficient sampling from various probability distributions.
method Proximal sampler with inexact restricted Gaussian oracle.
result State-of-the-art complexity bounds in almost all settings.
New method controls gradient error for sparse MRFs.
problem Efficient learning for sparse discrete MRFs with NP-hard inference.
method Stochastic proximal gradient (SPG) with controlled gradient approximation error.
result Novel bounds control gradient approximation quality.
Stochastic Second-order Methods for Non-convex Optimization with Inexact Hessian and Gradientmath.OC
Trust region and cubic regularization methods have demonstrated good performance in small scale non-convex optimization, showing the ability to escape from saddle points. Each iteration of these methods involves computation of gradient, Hessian and function value in order to obtain the search direction and adjust the r…
Proposes a stochastic method for solving trilevel optimization problems.
problem Efficient and theoretically sound methods for trilevel optimization.
method Stochastic gradient descent method for unconstrained trilevel optimization.
result First convergence theory for stochastic methods in trilevel optimization.
Exact minibatch MH method improves scalability for large datasets.
problem Inexactness in minibatch MH methods causes inference errors.
method TunaMH proposes an exact minibatch MH method with a tunable batch size.
result TunaMH is asymptotically optimal in terms of batch size.
Enforcing Fair Predicted Scores on Intervals of Percentiles by Difference-of-Convex Constraintscs.LG
Proposes a framework for partially fair machine learning models.
problem Achieving full fairness across all score ranges compromises predictive performance.
method Formulates model training as constrained optimization with difference-of-convex constraints, solvable by IDCA.
result Demonstrates high predictive performance while enforcing partial fairness in specific percentile intervals.
Study on reproducibility in optimization with bounds on limits.
problem Limits of reproducibility in noisy or error-prone optimization procedures.
method Defined a quantitative measure of reproducibility and analyzed convex optimization settings.
result Revealed a fundamental trade-off between computation and reproducibility.
Distributed algorithms are often beset by the straggler effect, where the slowest compute nodes in the system dictate the overall running time. Coding-theoretic techniques have been recently proposed to mitigate stragglers via algorithmic redundancy. Prior work in coded computation and gradient coding has mainly focuse…
Recently several methods were proposed for sparse optimization which make careful use of second-order information [10, 28, 16, 3] to improve local convergence rates. These methods construct a composite quadratic approximation using Hessian information, optimize this approximation using a first-order method, such as coo…