We propose an online convex optimization algorithm (RescaledExp) that achieves optimal regret in the unconstrained setting without prior knowledge of any bounds on the loss functions. We prove a lower bound showing an exponential separation between the regret of existing algorithms that require a known bound on the los…
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,695 papers · 148 categories
Trend · papers per month
48 results for “Unconstrained convex optimization”
Study optimal portfolio management with periodic evaluations in stochastic models, considering convex constraints.
problem Optimal portfolio management under ratio-type periodic evaluations in stochastic factor models with convex trading constraints.
method Transformed infinite horizon optimal control problem into an auxiliary terminal wealth optimization problem. Introduced an auxiliary unconstrained optimization problem in a modified market model. Used martingale duality approach to establish dual minimizer and optimal unconstrained wealth process.
result Derived and verified the optimal constrained portfolio process for the original problem over an infinite horizon.
A new optimization algorithm improves convergence in unconstrained problems.
problem Unconstrained optimization problems.
method Element-wise relaxed scalar auxiliary variable (E-RSAV) algorithm.
result Improved convergence and alignment of modified and original energy.
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.
Unconstrained Online Optimization: Dynamic Regret Analysis of Strongly Convex and Smooth Problemscs.LG
Paper analyzes regret bounds for unconstrained online optimization.
problem Minimizing regret in dynamic online learning for strongly convex and smooth functions.
method Preconditioned OGD, Online Optimistic Newton (OON), multiple gradient queries.
result Achieves regret bound with one gradient query per round.
OMWU shows last iterate convergence in convex-concave games.
problem Optimizing in constrained min-max optimization landscapes.
method OMWU (Optimistic Multiplicative-Weights Update) in the no-regret online learning framework.
result OMWU exhibits last iterate convergence for convex-concave games, generalizing previous results.
New algorithm reduces regret in stochastic bandit convex optimization.
problem Optimizing decisions in uncertain environments with convex losses.
method Introduces a second-order method for zeroth-order stochastic convex bandits.
result Regret bound of .
In this paper, we study two classes of optimal reinsurance models from perspectives of both insurers and reinsurers by minimizing their convex combination where the risk is measured by a distortion risk measure and the premium is given by a distortion premium principle. Firstly, we show that how optimal reinsurance mod…
Accelerated first-order methods for convex optimization with locally Lipschitz continuous gradientmath.OC
New methods for convex optimization with locally Lipschitz gradient, achieving faster convergence.
problem Optimization problems with locally Lipschitz continuous gradient.
method Accelerated proximal gradient (APG) methods and proximal augmented Lagrangian method.
result Achieved faster convergence rates for convex optimization problems with locally Lipschitz gradient.
Adam converges with high probability under unconstrained non-convex smooth stochastic optimizations.
problem Theoretical limitations of Adam's convergence under unconstrained non-convex smooth stochastic optimizations.
method Deep analysis of Adam's convergence rate under affine variance noise, without bounded gradient assumptions.
result Adam converges to the stationary point with a high probability rate of $\mathcal{O}\left({
m poly}(\log T)/\sqrt{T}
ight)$.
We address the problem of solving convex optimization problems with many convex constraints in a distributed setting. Our approach is based on an extension of the alternating direction method of multipliers (ADMM) that recently gained a lot of attention in the Big Data context. Although it has been invented decades ago…
New algorithm improves convergence for non-convex problems with boundaries.
problem Optimizing non-convex problems with constraints.
method Reflected Gradient Langevin Dynamics with probabilistic representation.
result Promising convergence rates, faster than existing methods.
DP-GD achieves dimension-independent convergence for unconstrained private GLMs.
problem Differentially private empirical risk minimization for unconstrained GLMs.
method Differentially private gradient descent (DP-GD).
result DP-GD achieves an excess empirical risk of $ ilde O\left(\sqrt{ exttt{rank}}/εn
ight)$ for unconstrained GLMs.
Adaptive algorithm AMSGrad converges for weakly convex constrained optimization problems.
problem Solving constrained stochastic optimization problems with weakly convex objectives.
method Analysis of AMSGrad algorithm for a specific class of problems.
result AMSGrad achieves a convergence rate of for the norm of the gradient of the Moreau envelope.
We consider a variant of online convex optimization in which both the instances (input vectors) and the comparator (weight vector) are unconstrained. We exploit a natural scale invariance symmetry in our unconstrained setting: the predictions of the optimal comparator are invariant under any linear transformation of th…
SurvLIME explains survival models by approximating them with Cox models.
problem Explaining complex survival models in machine learning.
method Applies Cox proportional hazards model to approximate survival model locally.
result Demonstrates efficiency through numerical experiments.
New adaptive methods for constrained convex optimization and variational inequalities.
problem Optimization of constrained convex problems and variational inequalities.
method AdaACSA and AdaAGD+ are accelerated methods that achieve nearly-optimal convergence rates for smooth and non-smooth functions.
result Achieve nearly-optimal convergence rates for both smooth and non-smooth functions, even with stochastic gradients.
Algorithm achieves optimal regret for unknown Lipschitz convex losses.
problem Online learning with unknown Lipschitz constant and target vector norm.
method Develops an online learning algorithm without knowledge of or .
result Matches optimal regret bound up to logarithmic factors.
We consider the problem of unconstrained online convex optimization (OCO) with sub-exponential noise, a strictly more general problem than the standard OCO. In this setting, the learner receives a subgradient of the loss functions corrupted by sub-exponential noise and strives to achieve optimal regret guarantee, witho…
Neural networks have been used prominently in several machine learning and statistics applications. In general, the underlying optimization of neural networks is non-convex which makes their performance analysis challenging. In this paper, we take a novel approach to this problem by asking whether one can constrain neu…
Structured regularizers enable faster optimization on SPD manifolds with constraints.
problem Optimizing SPD matrices with additional constraints.
method Structured regularizers based on symmetric gauge functions.
result Structured regularizers can preserve or induce desirable structure like convexity.
Second-order methods improve differential privacy in convex optimization.
problem Improving differential privacy in convex optimization.
method Developed a private variant of the regularized cubic Newton method for strongly convex loss functions.
result Achieves quadratic convergence and optimal excess loss for strongly convex loss functions.
This paper analyzes the landscape of supervised contrastive loss in over-parameterized networks.
problem Understanding the structure of solutions in over-parameterized networks under supervised contrastive loss.
method Analytical approach using unconstrained features model (UFM) to study the solutions of SC loss minimization.
result All local minima of SC loss are global minima in over-parameterized networks, and the minimizer is unique (up to rotation).
The (constrained) minimization of a ratio of set functions is a problem frequently occurring in clustering and community detection. As these optimization problems are typically NP-hard, one uses convex or spectral relaxations in practice. While these relaxations can be solved globally optimally, they are often too loos…
In this letter, we address sparse signal recovery using spike and slab priors. In particular, we focus on a Bayesian framework where sparsity is enforced on reconstruction coefficients via probabilistic priors. The optimization resulting from spike and slab prior maximization is known to be a hard non-convex problem, a…
Paper revisits DP-SCO in Euclidean and spaces, focusing on constrained and bounded sets.
problem Differentially private stochastic convex optimization in constrained and bounded sets in Euclidean and spaces.
method Proposes methods achieving excess population risks dependent on Gaussian width of the constraint set, and novel algorithms for unconstrained and heavy-tailed data.
result Theoretical results for DP-SCO in spaces, including optimal bounds for strongly convex functions.
New approach reduces unconstrained linear bandits to simpler optimization problems.
problem Unconstrained linear bandits problem.
method Perturbation-based approach combined with comparator-adaptive OLO algorithms.
result First high-probability guarantees for both static and dynamic regret in unconstrained linear bandits.
How can we efficiently mitigate the overhead of gradient communications in distributed optimization? This problem is at the heart of training scalable machine learning models and has been mainly studied in the unconstrained setting. In this paper, we propose Quantized-Frank-Wolfe (QFW), the first projection-free and co…
Higher-order methods for convex-concave min-max optimization and monotone variational inequalitiesmath.OC
Improved algorithms for convex-concave min-max optimization and monotone variational inequalities.
problem Efficiently solving constrained convex-concave min-max problems and monotone variational inequalities.
method Higher-order methods achieving iteration complexities of O(1/T^{ rac{p+1}{2}}) for p-th order derivatives.
result Achieved improved convergence rates for min-max and monotone variational inequalities.
Paper solves inverse optimal transport problem with convex optimization and neural network.
problem Learning the cost function for optimal transport from observed data.
method Unconstrained convex optimization, Sinkhorn-Knopp algorithm, and deep neural network parameterization.
result Novel framework avoids repeated OT solving, demonstrating efficiency and accuracy.
We address structured covariance estimation in elliptical distributions by assuming that the covariance is a priori known to belong to a given convex set, e.g., the set of Toeplitz or banded matrices. We consider the General Method of Moments (GMM) optimization applied to robust Tyler's scatter M-estimator subject to t…
Develops parameter-free online mirror descent for optimal dynamic regret.
problem Optimal online linear optimization in unbounded domains.
method Modified online mirror descent framework for parameter-free algorithms.
result First unconstrained online linear optimization achieving optimal dynamic regret.
The move from hand-designed to learned optimizers in machine learning has been quite successful for gradient-based and -free optimizers. When facing a constrained problem, however, maintaining feasibility typically requires a projection step, which might be computationally expensive and not differentiable. We show how …
Paper improves differential privacy analysis for machine learning.
problem Quantifying privacy leakage in noisy gradient descent.
method Shifted interpolation in -differential privacy.
result First exact privacy analysis for strongly convex optimization.
SUSTAIN algorithm tackles stochastic bilevel optimization with near-optimal complexity.
problem Stochastic bilevel optimization problems with specific convexity and smoothness properties.
method SUSTAIN algorithm using single-timescale double-momentum stochastic approximation.
result SUSTAIN achieves near-optimal complexity for finding ε-stationary solutions.
The paper explores optimal insurance contracts using various deviation measures.
problem Optimal insurance contracts with mean-deviation measures.
method Study of convex signed Choquet integrals and standard deviation as deviation measures, analyzing premium principles like expected value, Value-at-Risk, and Expected Shortfall.
result Characterization of optimal indemnities and deductibles under different premium principles.
New algorithms for constrained online optimization with memory and predictions.
problem Control of constrained dynamical systems and scheduling with reconfiguration budgets.
method Proposed algorithms achieving sublinear regret and constraint violation under time-varying constraints, both with and without predictions.
result First algorithms achieving sublinear regret and constraint violation in constrained online optimization with memory.
Paper tackles bilevel optimization problems using penalty methods.
problem Unconstrained and constrained bilevel optimization problems with nonsmooth lower levels.
method Introduces first-order penalty methods and and operation complexities.
result Establishes operation complexities for finding -KKT solutions.
We study optimal solutions to an abstract optimization problem for measures, which is a generalization of classical variational problems in information theory and statistical physics. In the classical problems, information and relative entropy are defined using the Kullback-Leibler divergence, and for this reason optim…
New method solves convex optimization faster than NAG.
problem Unconstrained smooth convex optimization problems.
method Accelerated quasi-Newton proximal extragradient (A-QPNE) method.
result Achieves a faster convergence rate of .
ROOT-SGD solves convex optimization problems with optimal nonasymptotic and near-optimal asymptotic performance.
problem Solving strongly convex and smooth unconstrained optimization problems using stochastic first-order algorithms.
method ROOT-SGD: Recursive One-Over-T SGD, averaging past stochastic gradients.
result Achieves state-of-the-art performance in both nonasymptotic and asymptotic senses.
Inference problems in graphical models are often approximated by casting them as constrained optimization problems. Message passing algorithms, such as belief propagation, have previously been suggested as methods for solving these optimization problems. However, there are few convergence guarantees for such algorithms…
New algorithms reduce online learning regret by tracking gradient variation.
problem Online learning with unconstrained losses and gradient variation.
method Parameter-free algorithms with adaptive updates for -smooth convex losses.
result Regret bounds of order achieved without prior knowledge of comparator norm or Lipschitz constant.
Double Duality: Variational Primal-Dual Policy Optimization for Constrained Reinforcement Learningcs.LG
Algorithm optimizes constrained reinforcement learning with dual variables.
problem Minimizing convex functional subject to convex constraint in large state spaces.
method VPDPO algorithm using Lagrangian and Fenchel duality.
result Achieves sublinear regret and constraint violation, globally optimal policy.
Submodular function minimization is well studied, and existing algorithms solve it exactly or up to arbitrary accuracy. However, in many applications, such as structured sparse learning or batch Bayesian optimization, the objective function is not exactly submodular, but close. In this case, no theoretical guarantees e…
Study optimizes zero-order strongly convex function minimization with higher order smoothness.
problem Optimizing a strongly convex function with noisy evaluations.
method Randomized approximation of projected gradient descent with smoothing kernel.
result Upper bounds and minimax lower bounds for the algorithm, showing near-optimality.
Paper tackles efficient SGD methods for constrained bilevel optimization.
problem Stochastic bilevel optimization with equality constraints.
method Alternating implicit projected SGD and its variants.
result Achieves sample complexity matching state-of-the-art for unconstrained problems.
Submodularity is one of the most well-studied properties of problem classes in combinatorial optimization and many applications of machine learning and data mining, with strong implications for guaranteed optimization. In this thesis, we investigate the role of submodularity in provable non-convex optimization and vali…