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.
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.
169,291 papers · 148 categories
Trend · papers per month
48 results for “Self-Concordant Regularization”
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.
SCRiBLe optimizes online bandit linear optimization with a polynomial run time.
problem Efficiently solving online bandit linear optimization problems.
method SCRiBLe setup and algorithm with regret bound and polynomial run time complexity.
result Achieves regret bound and polynomial run time complexity.
New globally convergent Newton method tackles ill-conditioned generalized self-concordant losses.
problem Optimization of ill-conditioned generalized self-concordant losses in machine learning.
method Sequence of problems with decreasing regularization parameters, linear convergence with logarithmic condition number scaling.
result First large-scale algorithm with optimal generalization bounds for logistic and softmax regressions in non-parametric settings.
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…
Unified Newton-type methods for convex optimization using generalized self-concordant functions.
problem Designing efficient Newton-type methods for convex optimization.
method Introducing generalized self-concordant functions and developing Newton-type methods.
result Unified framework for global and local convergence of Newton-type methods.
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…
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…
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.
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.
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.
New method solves constrained self-concordant minimization problems efficiently.
problem Constrained self-concordant minimization problems.
method Newton Frank-Wolfe method using linear minimization oracles.
result The method uses nearly the same number of linear minimization calls as the Frank-Wolfe method.
Develops a new interior-point technique for non-convex optimization problems.
problem Optimization of non-convex functions with singularities.
method Generalized self-concordant Hessian-barrier algorithm.
result Global convergence to approximate stationary points with optimal iteration complexity.
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.
New bounds on sample size for M-estimators using self-concordance.
problem Characterizing the sample size needed for M-estimators to have chi-square type excess risk bounds.
method Using self-concordance of the loss function, we derive bounds on the critical sample size.
result Improved bounds on the critical sample size, showing it depends on effective dimension and parameter dimension.
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…
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.
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…
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.
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…
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 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 bounds for online portfolio selection without smoothness assumptions.
problem Online portfolio selection with non-Lipschitz, non-smooth losses.
method Data-dependent bounds using novel smoothness characterizations and FTRL with self-concordant regularizers.
result Achieves logarithmic regrets when data is 'easy' and sublinear worst-case regrets.
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 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 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 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.
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.
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.
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 .
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 .
The paper optimizes grid search for machine learning parameters with improved complexity.
problem Challenging tuning of machine learning regularization parameters.
method Unified framework for approximating regularization paths with refined complexity.
result Optimized grid search with improved complexity for various loss functions.
In this paper we propose a multi-armed bandit inspired, pool based active learning algorithm for the problem of binary classification. By carefully constructing an analogy between active learning and multi-armed bandits, we utilize ideas such as lower confidence bounds, and self-concordant regularization from the multi…
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…
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.
A Generalization of the Tristram-Levine Knot Signatures as a Singular Furuta-Ohta Invariant for Torimath.GT
The paper generalizes knot signatures to tori using representations and invariants.
problem Generalizing knot signatures to tori and defining new invariants.
method Defining a signed count of irreducible representations for tori complements and relating it to known invariants.
result Defines a new invariant for tori that recovers known invariants and connects to Floer homology.
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 .
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.
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.
Adaptive-SGD method optimizes machine learning training with dynamic batch and step sizes.
problem Optimizing machine learning training with adaptive batch and step sizes.
method Adaptive-SGD method that dynamically adjusts batch size and step size based on local curvature and probability of descent directions.
result Adaptive-SGD achieves global linear convergence on self-concordant functions and compares favorably to fine-tuned methods.
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.
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.
Stochastic second-order methods converge fast under interpolation conditions.
problem Minimizing smooth and strongly-convex functions efficiently.
method Regularized subsampled Newton method (R-SSN) and stochastic BFGS algorithms.
result R-SSN achieves global linear convergence and quadratic rate in a local neighbourhood.
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 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 how concordance surgery impacts a 4D knot invariant.
problem Understanding how concordance surgery affects a specific 4D knot invariant.
method Used sutured Floer TQFT and a perturbed version of sutured Floer homology.
result Formula involving the graded Lefschetz number of the concordance map on knot Floer homology.