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.
169,341 papers · 148 categories
Trend · papers per month
48 results for “composite self-concordant minimization”
Proposes a new method to solve large-scale CSC minimization problems.
problem Composite self-concordant minimization problems in machine learning.
method Randomized block proximal damped Newton (RBPDN) method.
result RBPDN method significantly reduces computational cost per iteration.
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 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.
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…
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.
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.
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.
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…
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.
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 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…
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.
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…
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.
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.
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 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.
A new optimization method for faster convergence.
problem Optimization problems, especially those involving self-concordant functions.
method Newton Sketch: approximate Newton step using randomly projected Hessian.
result Super-linear convergence with exponential probability for self-concordant functions.
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.
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.
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.
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.
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.
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 algorithm for minimizing composite functions with flexible design.
problem Minimizing composite functions with specific structural properties.
method Unified accelerated algorithm for complementary composite minimization.
result Near-optimal algorithms for various optimization problems.
Accelerates machine learning algorithms for sparse data.
problem Efficiently solving composite convex minimization problems.
method Accelerated dual-averaging primal-dual method for composite convex minimization.
result Demonstrates advantages in handling sparse data both theoretically and empirically.
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.
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 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.
New method reduces complexity for nonconvex optimization problems.
problem Minimizing composite functions with random or finite sum inner mappings.
method Stochastic composite gradient method with incremental variance reduction.
result Achieves complexity similar to best first-order methods for expected-value and finite-sum nonconvex functions.
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.
Paper studies how to combine regret minimizers for solving complex games.
problem Solving large-scale extensive-form games with constraints.
method Derives a calculus for constructing regret minimizers for composite convex sets.
result Local regret minimizers for simpler sets can be combined into an aggregate for composite sets.
A new method for faster optimization of machine learning problems.
problem Minimization of composition of expected value functions.
method C-SAG, a novel extension of SAG for FS-CEVF problems.
result C-SAG achieves lower oracle query complexity per iteration than C-SVRG and converges faster.
Extends geometric descent method for convex composite problems.
problem Nonsmooth and strongly convex composite problems.
method Geometric Proximal Gradient Method (GeoPG)
result Achieves optimal linear convergence rate of (1-1/\sqrtκ).
New analysis shows diverse classes in pre-training boost NLP performance.
problem Improving sample efficiency in downstream NLP tasks.
method Proved that diverse classes in pre-training lead to better performance, using a large last linear layer singular value.
result Transfer learning excess risk improves with large and $O\left(\frac{1}{ ildeν \sqrt{n}}
ight)$ rate.
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.
Develops consistent approximations for composite optimization problems.
problem Significant errors in solutions due to approximations in optimization problems.
method Specifies conditions for well-behaved approximations in minimizers, stationary points, and level-sets for a broad class of composite problems.
result Framework of consistent approximations for composite problems, including stochastic, neural-network, and multi-objective optimization.
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 .
Model estimates foreign exchange reserve compositions of undisclosed central banks.
problem Limited information on central bank reserve compositions hinders analysis.
method Hidden Markov Model relating portfolio valuation to exchange rates.
result China's reserve composition likely matches global average, while Singapore holds fewer US dollars.
New DP-CD method outperforms DP-SGD in solving composite DP-ERM problems.
problem Privacy-preserving machine learning with differential privacy.
method Differentially Private proximal Coordinate Descent (DP-CD) for composite Empirical Risk Minimization (ERM).
result DP-CD outperforms DP-SGD due to larger step sizes and better gradient exploitation.
A Geometric Analysis of PCAmath.ST
The paper analyzes the excess risk of PCA and provides a precise characterization.
problem Understanding the excess risk of principal component analysis (PCA).
method Established a central limit theorem for PCA error and derived the excess risk distribution.
result Obtained a non-asymptotic upper bound on the excess risk of PCA.
Study on crossing numbers of composite knots and graphs.
problem Understanding the minimal crossing number of composite knots and graphs.
method Relating the minimal crossing number of composite knots to the minimal crossing number of spatial graphs, specifically the 2n-theta curve.
result Proved that for large enough n, the crossing number of the 2n-theta curve is n times the sum of the crossing numbers of the prime knots.
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.
The paper generalizes offset Rademacher complexities to convex and non-convex problems.
problem Improper learning and convexity in statistical learning.
method Generalization of offset Rademacher complexities to convex and non-convex problems.
result The offset complexity provides versatile analytic tools for both convex and non-convex learning.
Classical stochastic gradient methods are well suited for minimizing expected-value objective functions. However, they do not apply to the minimization of a nonlinear function involving expected values or a composition of two expected-value functions, i.e., problems of the form $\min_x \mathbf{E}_v [f_v\big(\mathbf{E}_…