Efficient algorithm for unknown linear systems with convex costs.
problem Controlling an unknown linear system with stochastic convex costs.
method Optimism in the Face of Uncertainty paradigm.
result Achieves optimal regret-rate.
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,742 papers · 148 categories
Trend · papers per month
48 results for “stochastic convex costs”
New algorithm controls linear systems with bandit feedback, achieving optimal regret.
problem Controlling linear systems with bandit feedback under adversarial costs.
method Developed a new algorithm for linear control with memory optimization technique.
result Achieved optimal regret growth proportional to square root of time horizon.
Exact second-order optimization for deep learning reduces computational cost and improves performance.
problem Inadequate use of second-order optimization methods in deep learning due to high computational cost and non-convexity.
method Developed an exact stochastic second-order Newton method that addresses the non-convexity issue and provides an expression for the stochastic Hessian.
result Exact second-order Newton direction formula and its application in deep learning datasets.
In this paper, the online variants of the classical Frank-Wolfe algorithm are considered. We consider minimizing the regret with a stochastic cost. The online algorithms only require simple iterative updates and a non-adaptive step size rule, in contrast to the hybrid schemes commonly considered in the literature. Seve…
This study optimizes trading and arbitrage in decentralized finance's CPMs, revealing convexity costs and developing efficient strategies.
problem Optimizing trading and arbitrage in decentralized finance's constant product markets (CPMs).
method Developed models for CPMs in competing centralised exchanges, CPMs, and both venues. Derived computationally efficient strategies.
result Accurately estimated convexity costs in CPMs, which are linear in trade size and nonlinear in liquidity depth and exchange rate.
A new method reduces the complexity of decentralized optimization.
problem Decentralized stochastic non-convex optimization over a network.
method GT-HSGD, a hybrid variance-reduced method.
result Achieves an oracle complexity of O(n^(-1)ε^(-3)) for small ε.
We propose a projected semi-stochastic gradient descent method with mini-batch for improving both the theoretical complexity and practical performance of the general stochastic gradient descent method (SGD). We are able to prove linear convergence under weak strong convexity assumption. This requires no strong convexit…
A new parallel algorithm for learning optimal policies in MDPs with low communication costs.
problem Learning optimal policies for infinite-horizon MDPs.
method Primal-Dual Stochastic Mirror Descent for convex programming problems with inexact constraints.
result First parallel algorithm for average-reward MDPs with generative model and low communication costs.
The dueling bandit is a learning framework wherein the feedback information in the learning process is restricted to a noisy comparison between a pair of actions. In this research, we address a dueling bandit problem based on a cost function over a continuous space. We propose a stochastic mirror descent algorithm and …
SCaLE tackles dynamic regret in noisy bandit feedback with switching costs.
problem Unbounded metric movement costs in bandit online convex optimization.
method SCaLE algorithm for high-dimensional dynamic quadratic hitting costs and -norm switching costs, with spectral regret analysis.
result First algorithm achieving sub-linear dynamic regret without hitting cost knowledge.
New algorithm tackles risk-aware learning problems efficiently.
problem Risk-aware learning with mean-semideviation objective.
method Zeroth-order compositional stochastic optimization algorithm.
result Algorithm converges to optimal solutions with explicit rates.
Paper tackles online control of linear systems with unbounded noise.
problem Online control of linear systems under unbounded noise with unknown convex cost functions.
method Developed an algorithm achieving high-probability regret under unbounded noise, and established regret bound for strongly convex costs and sub-Gaussian noise.
result Achieved high-probability regret under unbounded noise, and regret bound for specific noise and cost conditions.
SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimatormath.OC
In this paper, we propose a new technique named \textit{Stochastic Path-Integrated Differential EstimatoR} (SPIDER), which can be used to track many deterministic quantities of interest with significantly reduced computational cost. We apply SPIDER to two tasks, namely the stochastic first-order and zeroth-order method…
We present a generic framework for trading off fidelity and cost in computing stochastic gradients when the costs of acquiring stochastic gradients of different quality are not known a priori. We consider a mini-batch oracle that distributes a limited query budget over a number of stochastic gradients and aggregates th…
Stochastic gradient algorithms estimate the gradient based on only one or a few samples and enjoy low computational cost per iteration. They have been widely used in large-scale optimization problems. However, stochastic gradient algorithms are usually slow to converge and achieve sub-linear convergence rates, due to t…
This paper presents a stochastic model for discrete-time trading in financial markets where trading costs are given by convex cost functions and portfolios are constrained by convex sets. The model does not assume the existence of a cash account/numeraire. In addition to classical frictionless markets and markets with …
New bounds on adaptivity cost in stochastic optimization.
problem Understanding the cost of changing strategies in stochastic optimization.
method Proving impossibility results for adaptivity in non-smooth stochastic convex optimization.
result Lower bounds on the price of adaptivity for different levels of uncertainty.
We consider the problem of minimizing the sum of two convex functions: one is the average of a large number of smooth component functions, and the other is a general convex function that admits a simple proximal mapping. We assume the whole objective function is strongly convex. Such problems often arise in machine lea…
This work proposes ACTC for adaptive distributed learning under communication constraints.
problem Adaptive distributed learning in networks with communication constraints.
method ACTC (Adapt-Compress-Then-Combine) strategy with diffusion exchange of compressed updates.
result ACTC iterates converge to the optimizer with significant bit savings.
In this paper, we study the problem of distributed multi-agent optimization over a network, where each agent possesses a local cost function that is smooth and strongly convex. The global objective is to find a common solution that minimizes the average of all cost functions. Assuming agents only have access to unbiase…
New algorithms protect user-level privacy in learning tasks.
problem Protecting user-level privacy in learning tasks with stringent constraints.
method Proposes algorithms for learning tasks under user-level differential privacy constraints.
result Privacy cost decreases as users provide more samples or as the number of users increases.
Large sectors of the recent optimization literature focused in the last decade on the development of optimal stochastic first order schemes for constrained convex models under progressively relaxed assumptions. Stochastic proximal point is an iterative scheme born from the adaptation of proximal point algorithm to nois…
Optimizes distributions robustly with Sinkhorn distance.
problem Distributionally robust optimization with Wasserstein distance.
method Convex programming dual reformulation, stochastic mirror descent algorithm.
result Demonstrates superior performance in synthetic and real data.
Paper improves a method for fast global and local convergence in optimization.
problem Slow global convergence in optimization methods with noisy Hessian estimates.
method Stochastic Newton Proximal Extragradient method using HPE framework.
result Faster global linear rate and superlinear convergence in fewer iterations.
Deep Hedging learns risk-neutral vol dynamics for option pricing.
problem Statistical arbitrage in market dynamics without transaction costs.
method Numerical approach to train market simulator and find risk-neutral density.
result Risk-neutral model for stochastic implied volatility can be used for pricing or Deep Hedging.
This paper examines a Markovian model for the optimal irreversible investment problem of a firm aiming at minimizing total expected costs of production. We model market uncertainty and the cost of investment per unit of production capacity as two independent one-dimensional regular diffusions, and we consider a general…
Standard results in stochastic convex optimization bound the number of samples that an algorithm needs to generate a point with small function value in expectation. More nuanced high probability guarantees are rare, and typically either rely on "light-tail" noise assumptions or exhibit worse sample complexity. In this …
Study on collaborative vs. non-collaborative online and bandit convex optimization.
problem Minimizing average regret in distributed online and bandit convex optimization.
method Analyzes the impact of collaboration in adaptive and zeroth-order feedback settings.
result Collaboration is beneficial in high-dimensional federated online optimization with limited feedback.
This paper focuses on projection-free methods for solving smooth Online Convex Optimization (OCO) problems. Existing projection-free methods either achieve suboptimal regret bounds or have high per-iteration computational costs. To fill this gap, two efficient projection-free online methods called ORGFW and MORGFW are …
New algorithm reduces decision switching in dynamic environments.
problem Online learning with memory and non-stationary environments.
method Dynamic policy regret, novel ensemble approach, meta-base decomposition.
result Proves optimal dynamic policy regret for memory length, non-stationarity, and time horizon.
Learning representation from relative similarity comparisons, often called ordinal embedding, gains rising attention in recent years. Most of the existing methods are batch methods designed mainly based on the convex optimization, say, the projected gradient descent method. However, they are generally time-consuming du…
Sharp asymptotic lower bounds of the expected quadratic variation of discretization error in stochastic integration are given. The theory relies on inequalities for the kurtosis and skewness of a general random variable which are themselves seemingly new. Asymptotically efficient schemes which attain the lower bounds a…
We consider a multi-objective risk-averse two-stage stochastic programming problem with a multivariate convex risk measure. We suggest a convex vector optimization formulation with set-valued constraints and propose an extended version of Benson's algorithm to solve this problem. Using Lagrangian duality, we develop sc…
We consider a stochastic inventory control problem under censored demands, lost sales, and positive lead times. This is a fundamental problem in inventory management, with significant literature establishing near-optimality of a simple class of policies called ``base-stock policies'' for the underlying Markov Decision …
Stochastic Gradient Langevin Dynamics (SGLD) is a popular variant of Stochastic Gradient Descent, where properly scaled isotropic Gaussian noise is added to an unbiased estimate of the gradient at each iteration. This modest change allows SGLD to escape local minima and suffices to guarantee asymptotic convergence to g…
AOT aligns LLMs on distributional preferences via optimal transport.
problem Current LLM alignment techniques lack distributional level alignment.
method Alignment via Optimal Transport (AOT) aligns LLMs on unpaired preference data.
result AOT enables alignment by penalizing reward distribution violations.
New algorithm reduces dimensionality in stochastic optimization.
problem Stochastic optimization in high-dimensional problems.
method Proposes a sparsity-inducing stochastic gradient-free (SI-SGF) algorithm.
result Proves dimension-free query complexity in convex and strongly convex cases.
We study a robust stochastic optimization problem in the quasi-sure setting in discrete-time. We show that under a lineality-type condition the problem admits a maximizer. This condition is implied by the no-arbitrage condition in models of financial markets. As a corollary, we obtain existence of an utility maximizer …
In this paper, we study distributed stochastic optimization to minimize a sum of smooth and strongly-convex local cost functions over a network of agents, communicating over a strongly-connected graph. Assuming that each agent has access to a stochastic first-order oracle (), we propose a novel distribut…
We consider stochastic strongly convex optimization with a complex inequality constraint. This complex inequality constraint may lead to computationally expensive projections in algorithmic iterations of the stochastic gradient descent~(SGD) methods. To reduce the computation costs pertaining to the projections, we pro…
In recent literature, a general two step procedure has been formulated for solving the problem of phase retrieval. First, a spectral technique is used to obtain a constant-error initial estimate, following which, the estimate is refined to arbitrary precision by first-order optimization of a non-convex loss function. N…
A new algorithm for decentralized optimization over directed graphs.
problem Decentralized stochastic optimization over directed networks.
method Gradient tracking and S-ADDOPT algorithm with constant and decaying step-sizes.
result S-ADDOPT converges linearly with constant step-size and sublinearly with decaying step-size.
This paper studies convex duality in optimal investment and contingent claim valuation in markets where traded assets may be subject to nonlinear trading costs and portfolio constraints. Under fairly general conditions, the dual expressions decompose into tree terms, corresponding to the agent's risk preferences, tradi…
New algorithm achieves optimal regret in non-stochastic control, showing stochasticity is not beneficial.
problem Achieving optimal control in non-stochastic systems with adversarial noise.
method Novel online Newton step algorithm adapted to adversarial disturbances, using policy regret bounds.
result Optimal regret achieved in unknown dynamics, regret in known dynamics.
Distributed stochastic gradient descent~(DSGD) has been widely used for optimizing large-scale machine learning models, including both convex and non-convex models. With the rapid growth of model size, huge communication cost has been the bottleneck of traditional DSGD. Recently, many communication compression methods …
Algorithm reduces control regret for unknown systems.
problem Minimizing control regret for unknown linear systems.
method Novel geometric exploration strategy and polynomial-time algorithms.
result First polynomial-time algorithms with optimal regret bounds.
Superhedging in illiquid marketsq-fin.PR
We study contingent claims in a discrete-time market model where trading costs are given by convex functions and portfolios are constrained by convex sets. In addition to classical frictionless markets and markets with transaction costs or bid-ask spreads, our framework covers markets with nonlinear illiquidity effects…
RES, a regularized stochastic version of the Broyden-Fletcher-Goldfarb-Shanno (BFGS) quasi-Newton method is proposed to solve convex optimization problems with stochastic objectives. The use of stochastic gradient descent algorithms is widespread, but the number of iterations required to approximate optimal arguments c…