The self-concordant-like property of a smooth convex function is a new analytical structure that generalizes the self-concordant notion. While a wide variety of important applications feature the self-concordant-like property, this concept has heretofore remained unexploited in convex optimization. To this end, we deve…
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 “self-concordant functions”
We study the smooth structure of convex functions by generalizing a powerful concept so-called self-concordance introduced by Nesterov and Nemirovskii in the early 1990s to a broader class of convex functions, which we call generalized self-concordant functions. This notion allows us to develop a unified framework for …
Improved Frank-Wolfe algorithm for generalized self-concordant functions converges quickly.
problem Efficiently solving learning problems with generalized self-concordant objectives.
method Simple Frank-Wolfe variant with open-loop step size strategy .
result Achieves convergence rate for primal and Frank-Wolfe gaps.
Improves statistical learning bounds with self-concordant losses.
problem Statistical prediction with nuisance components.
method Orthogonal statistical learning with self-concordant loss.
result Non-asymptotic bounds on excess risk improved by a dimension factor.
Many problems in statistical learning, imaging, and computer vision involve the optimization of a non-convex objective function with singularities at the boundary of the feasible set. For such challenging instances, we develop a new interior-point technique building on the Hessian-barrier algorithm recently introduced …
Paper improves learning rates for GSC loss functions using iterated Tikhonov regularization.
problem Improving learning rates for GSC loss functions.
method Iterated Tikhonov regularization using proximal point method.
result Achieves fast and optimal rates for GSC loss functions.
Unified analysis of online optimization with self-concordant barriers, improving regret bounds.
problem Online convex optimization with specific loss functions.
method Online mirror descent with self-concordant barriers and logarithmic loss.
result Improved regret bounds for online portfolio selection and quantum state learning.
We propose a variable metric framework for minimizing the sum of a self-concordant function and a possibly non-smooth convex function, endowed with an easily computable proximal operator. We theoretically establish the convergence of our framework without relying on the usual Lipschitz gradient assumption on the smooth…
Unified algorithm for linear bandits with improved regret bound.
problem Adversarial linear bandits with improved regret.
method Self-concordant perturbations in FTPL framework.
result Regret bound of for hypercube and ball.
We propose a randomized second-order method for optimization known as the Newton Sketch: it is based on performing an approximate Newton step using a randomly projected or sub-sampled Hessian. For self-concordant functions, we prove that the algorithm has super-linear convergence with exponentially high probability, wi…
We consider the class of convex minimization problems, composed of a self-concordant function, such as the metric, a convex data fidelity term and, a regularizing -- possibly non-smooth -- function . This type of problems have recently attracted a great deal of interest, mainly due to th…
New insights into natural exponential families improve regret bounds for bandit problems.
problem Improving regret bounds for bandit problems with subexponential tails.
method Proving self-concordance for natural exponential families and applying to bandits.
result Optimistic algorithms for generalized linear bandits have second-order regret bounds that are free of an exponential dependence on problem parameters.
Interior-point methods adapted for manifolds, achieving similar optimization results.
problem Optimizing on manifolds with self-concordant barriers.
method Generalization of self-concordance to Riemannian manifolds, path-following method analysis.
result Local quadratic convergence of Newton's method and standard complexity guarantees.
The paper improves confidence set construction for statistical inference.
problem Constructing reliable confidence sets in statistical inference.
method Establishes a finite-sample bound using effective dimension and generalized self-concordance.
result Developed a confidence set adapted to optimization landscapes.
New bounds on minimax regret for sequential probability assignment using logarithmic loss.
problem Minimizing regret in sequential probability assignment against arbitrary experts.
method Using self-concordance property of logarithmic loss to derive tight bounds.
result Tight bounds on minimax regret for various expert classes.
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…
RHMC improves sampling polytopes defined by inequalities with barriers.
problem Sampling polytopes defined by inequalities efficiently.
method Riemannian Hamiltonian Monte Carlo (RHMC) with a hybrid of Lewis weights and logarithmic barriers.
result RHMC achieves mixing rate of for polytopes defined by inequalities in .
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…
In this paper we consider the composite self-concordant (CSC) minimization problem, which minimizes the sum of a self-concordant function and a (possibly nonsmooth) proper closed convex function . The CSC minimization is the cornerstone of the path-following interior point methods for solving a broad class of co…
Improved prediction algorithm for 'easy' sequences with reduced regret.
problem Prediction with expert advice for 'easy' sequences.
method Variant of NormalHedge algorithm using second-order -quantile regret bound.
result Second-order -quantile regret bound of for .
New algorithm tackles heterogeneous curvature in online convex optimization.
problem Adversarial bandit convex optimization with varying curvature.
method Developed an adaptive algorithm that learns curvature on the fly.
result Achieves optimal regret bounds even with heterogeneous curvature.
New method improves HMC for sampling on manifolds.
problem Sampling from constrained manifolds with HMC.
method Self-Concordant Barrier Hamiltonian Monte Carlo (BHMC) with involution checking step.
result New algorithms generate unbiased Markov chains.
New sampling method improves accuracy for constrained spaces.
problem Sampling from constrained convex subsets of R^d.
method Metropolis-adjusted Preconditioned Langevin Algorithm.
result High-accuracy sampling with polylogarithmic error dependence.
The goal of this note is to construct, on many manifolds, non-trivial concordances from the identity to itself. This produces counterexamples to a recent conjecture by Botvinnik.
Unified meta-algorithm improves average performance across similar tasks in adversarial bandits.
problem Improving performance across multiple similar tasks in adversarial bandit settings.
method Unified meta-algorithm for multi-armed bandits and bandit linear optimization, tuning initialization, step-size, and entropy parameters.
result Unified meta-algorithm yields setting-specific guarantees for MAB and BLO, improving task-averaged regret.
New algorithm reduces prediction errors across various loss functions.
problem Online forecasting algorithms' inability to adapt to different loss functions.
method Design of a novel Follow-the-Perturbed-Leader (FTPL) algorithm with self-concordant noise.
result Simultaneously achieves regret for bounded proper losses and regret for bounded smooth proper losses.
The classical asymptotic theory for parametric -estimators guarantees that, in the limit of infinite sample size, the excess risk has a chi-square type distribution, even in the misspecified case. We demonstrate how self-concordance of the loss allows to characterize the critical sample size sufficient to guarantee …
Fast sampling from constrained spaces using the Metropolis-adjusted Mirror Langevin algorithmstat.CO
New algorithm improves sampling from constrained spaces.
problem Sampling from constrained spaces efficiently.
method Metropolis-adjusted Mirror Langevin algorithm.
result Unbiased sampling with improved mixing time.
We demonstrate how to scalably solve a class of constrained self-concordant minimization problems using linear minimization oracles (LMO) over the constraint set. We prove that the number of LMO calls of our method is nearly the same as that of the Frank-Wolfe method in the L-smooth case. Specifically, our Newton Frank…
We propose an algorithmic framework for convex minimization problems of a composite function with two terms: a self-concordant function and a possibly nonsmooth regularization term. Our method is a new proximal Newton algorithm that features a local quadratic convergence rate. As a specific instance of our framework, w…
Unified CS for GLMs improves bandit regret bounds.
problem Improving regret bounds for GLMs in bandit settings.
method Unified likelihood ratio-based CS with PAC-Bayesian bound.
result Unified CS attains poly(S)-free regret for Bernoulli.
Algorithm for online decision making with unknown dynamics and aggregate feedback.
problem Online decision making with unknown dynamics and aggregate bandit feedback.
method Developed an algorithm based on online mirror descent with a self-concordant barrier regularization and an increasing learning rate schedule.
result Achieved regret for the online Markov Decision Process with episodes.
The Riemannian Langevin Algorithm samples from manifolds efficiently.
problem Sampling from distributions on manifolds with log-Sobolev inequality.
method Riemannian Langevin Algorithm, log-Sobolev inequality, self-concordance extension, stochastic smoothness bounding.
result The Riemannian Langevin Algorithm converges rapidly to the target density.
Improved confidence bounds for linear logistic model with applications to bandits.
problem Improving confidence bounds for linear logistic model.
method Self-concordant analysis of the logistic loss to avoid dependence on worst-case variance.
result Significant improvement in confidence bounds, avoiding dependence on .
We compute the effect of concordance surgery, a generalization of knot surgery defined using a self-concordance of a knot, on the Ozsváth-Szabó 4-manifold invariant. The formula involves the graded Lefschetz number of the concordance map on knot Floer homology. The proof uses the sutured Floer TQFT, and a version of su…
New GLB algorithm handles non-stationary data with forgetting.
problem Non-stationary GLB with non-convex projection or burn-in phases.
method Self-concordant GLB with sliding window or exponential weights for forgetting.
result Novel confidence-based algorithm for maximum likelihood estimator.
This article introduces the concepts around Online Bandit Linear Optimization and explores an efficient setup called SCRiBLe (Self-Concordant Regularization in Bandit Learning) created by Abernethy et. al.\cite{abernethy}. The SCRiBLe setup and algorithm yield a regret bound and polynomial run time comple…
This work improves regret minimization for logistic bandits by reducing dependence on a large constant.
problem Minimizing regret in logistic bandits with reduced dependence on a large constant.
method Experimental design procedure and warmup sampling algorithm.
result Achieves a minimax regret of \(O(\sqrt{d \dotμT\log(|\mathcal{X}|)})\) in the fixed arm setting.
In this paper, we study large-scale convex optimization algorithms based on the Newton method applied to regularized generalized self-concordant losses, which include logistic regression and softmax regression. We first prove that our new simple scheme based on a sequence of problems with decreasing regularization para…
New approach for online learning with adaptive adversaries, simpler and more effective.
problem Online learning with adaptive adversaries, especially in bandits and MDPs.
method Uses standard unbiased estimators and a simple increasing learning rate schedule, aided by logarithmically homogeneous self-concordant barriers and strengthened Freedman's inequality.
result First high-probability regret bounds for adversarial bandits and MDPs, resolving open problems.
We consider stochastic second-order methods for minimizing smooth and strongly-convex functions under an interpolation condition satisfied by over-parameterized models. Under this condition, we show that the regularized subsampled Newton method (R-SSN) achieves global linear convergence with an adaptive step-size and a…
Study on using random subspaces for ERM with various loss functions.
problem Improving learning accuracy with computational savings from random subspaces.
method Random subspaces of a hypothesis space, considering data-dependent subspaces.
result Unified analysis showing computational efficiency can be improved without performance loss.
We propose a stochastic optimization method for minimizing loss functions, expressed as an expected value, that adaptively controls the batch size used in the computation of gradient approximations and the step size used to move along such directions, eliminating the need for the user to tune the learning rate. The pro…
We propose a new proximal, path-following framework for a class of constrained convex problems. We consider settings where the nonlinear---and possibly non-smooth---objective part is endowed with a proximity operator, and the constraint set is equipped with a self-concordant barrier. Our approach relies on the followin…
A Generalization of the Tristram-Levine Knot Signatures as a Singular Furuta-Ohta Invariant for Torimath.GT
Given a knot inside an integer homology sphere , the Casson-Lin-Herald invariant can be interpreted as a signed count of conjugacy classes of irreducible representations of the knot complement into which map the meridian of the knot to a fixed conjugacy class. It has the interesting feature that it deter…
We analyze the problem of sequential probability assignment for binary outcomes with side information and logarithmic loss, where regret---or, redundancy---is measured with respect to a (possibly infinite) class of experts. We provide upper and lower bounds for minimax regret in terms of sequential complexities of the …
Study shows fast rates for inverse reinforcement learning with linear rewards.
problem Entropy-regularized min-max inverse reinforcement learning in finite-horizon MDPs.
method Structural and statistical analysis of Min-Max-IRL with pseudo-self-concordance.
result Both trajectory-level KL divergence and parameter error decay at .
Popular machine learning estimators involve regularization parameters that can be challenging to tune, and standard strategies rely on grid search for this task. In this paper, we revisit the techniques of approximating the regularization path up to predefined tolerance in a unified framework and show that its comp…