We study online convex optimization in a setting where the learner seeks to minimize the sum of a per-round hitting cost and a movement cost which is incurred when changing decisions between rounds. We prove a new lower bound on the competitive ratio of any online algorithm in the setting where the costs are -strong…
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 “strongly convex costs”
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.
Almost all local minima in neural networks are strongly convex.
problem The prevalence of strongly convex neighborhoods around local minima in neural network optimization landscapes.
method Rigorous analysis of shallow neural networks with analytic activation functions, dividing parameter space into efficient and redundant domains.
result For shallow neural networks on the efficient domain, almost all local minima are strongly convex.
Convex optimization with sparsity-promoting convex regularization is a standard approach for estimating sparse signals in noise. In order to promote sparsity more strongly than convex regularization, it is also standard practice to employ non-convex optimization. In this paper, we take a third approach. We utilize a no…
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…
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.
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 study dual-based algorithms for distributed convex optimization problems over networks, where the objective is to minimize a sum of functions over in a network. We provide complexity bounds for four different cases, namely: each function is strongly convex and smooth, each function is ei…
In this paper, we study the optimal convergence rate for distributed convex optimization problems in networks. We model the communication restrictions imposed by the network as a set of affine constraints and provide optimal complexity bounds for four different setups, namely: the function $F(\xb) \triangleq \sum_{i=1}…
This paper addresses the problem of sparsity penalized least squares for applications in sparse signal processing, e.g. sparse deconvolution. This paper aims to induce sparsity more strongly than L1 norm regularization, while avoiding non-convex optimization. For this purpose, this paper describes the design and use of…
Strongly convex bodies can be approximated by smooth ones.
problem Approximating strongly convex bodies with smooth ones.
method Using locally strongly convex bodies.
result Smooth approximations of strongly convex bodies exist and can be controlled in terms of Hausdorff distance.
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…
We develop and analyze an asynchronous algorithm for distributed convex optimization when the objective writes a sum of smooth functions, local to each worker, and a non-smooth function. Unlike many existing methods, our distributed algorithm is adjustable to various levels of communication cost, delays, machines compu…
We consider Online Convex Optimization (OCO) in the setting where the costs are -strongly convex and the online learner pays a switching cost for changing decisions between rounds. We show that the recently proposed Online Balanced Descent (OBD) algorithm is constant competitive in this setting, with competitive rat…
Study large deviations rates for SGD with strongly convex functions.
problem High probability metrics with SGD.
method Large deviations theory, generic gradient noise, strongly convex functions.
result Upper large deviations bound for SGD with strongly convex functions.
Unified analysis of Federated Averaging and Nesterov FedAvg for linear speedup.
problem Understanding convergence of FL algorithms under non-i.i.d. data and partial participation.
method Systematic study of convergence guarantees for FedAvg and Nesterov FedAvg under different conditions.
result Unified analysis of linear speedup for FedAvg and Nesterov FedAvg in various settings.
OMGD algorithm optimizes online convex optimization with switching costs and delayed gradients.
problem Optimizing online convex optimization with switching costs and delayed gradients.
method Proposed an online multiple gradient descent (OMGD) algorithm for quadratic and linear switching costs.
result OMGD achieves optimal dynamic regret in the limited information setting.
New convergence bounds for online learning with heavy-tailed noise.
problem Learning on streaming data with heavy-tailed noise.
method Nonlinear stochastic gradient descent (SGD) for non-convex and strongly convex costs.
result Strong convergence rates for various nonlinearities and noise distributions.
The paper simplifies strongly convex problems to simplicial structures.
problem Strongly convex problems with smoothness.
method Generic linear perturbations and singularity theory.
result Strongly convex problems are simplicial.
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.
The paper analyzes the efficiency of unlearning methods and establishes bounds for minimax computation times.
problem Efficiency of removing specific data points from a trained model without full retraining.
method Analysis of unlearning methods and establishment of upper and lower bounds on computation times.
result A phase diagram for the unlearning complexity ratio, revealing three regimes of feasibility.
New methods optimize functions faster with less gradient accuracy needed.
problem Optimizing complex functions with limited gradient accuracy.
method Hessian averaging and adaptive gradient sampling methods.
result Improved convergence rates for various function types.
In this paper, we prove that a strongly convex complex Finsler metric on a domain is projectively flat (resp. dually flat) if and only if comes from a strongly convex complex Minkowski metric.
Sharp estimates for Finsler metrics in convex domains.
problem Estimating distances in Finsler metrics near convex points.
method Sharp estimates for intrinsic distances of Finsler metrics.
result Characterization of -quasi hyperbolic metric in convex geometry.
A distributed optimization method solves saddle point problems with strong concavity and convexity.
problem Solving saddle point problems with distributed and heterogeneous data.
method GT-GDA, a distributed first-order method using gradient tracking and consensus over coupling matrices.
result GT-GDA converges linearly to the unique saddle point solution under specific conditions.
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…
Accelerated Randomized Mirror Descent Algorithms For Composite Non-strongly Convex Optimizationmath.OC
We consider the problem of minimizing the sum of an average function of a large number of smooth convex components and a general, possibly non-differentiable, convex function. Although many methods have been proposed to solve this problem with the assumption that the sum is strongly convex, few methods support the non-…
We propose an optimization method for minimizing the finite sums of smooth convex functions. Our method incorporates an accelerated gradient descent (AGD) and a stochastic variance reduction gradient (SVRG) in a mini-batch setting. Unlike SVRG, our method can be directly applied to non-strongly and strongly convex prob…
DFFL tackles federated learning with heterogeneous objectives and constraints.
problem Federated learning with clients having different objectives and feasible regions.
method Derived heterogeneity bounds for cost-vector distances and support-function/shape-distance terms. Lifted pointwise bounds to local-versus-federated excess-risk comparison.
result Federation is beneficial when the statistical advantage of pooling exceeds a client-specific heterogeneity penalty.
ANIL adapts only a subset of parameters, reducing computational cost.
problem Efficiently adapt model parameters in meta-learning.
method Adapts only a small subset of parameters in the inner loop of ANIL.
result Theoretical convergence and computational complexity analysis for ANIL.
Conditional gradients constitute a class of projection-free first-order algorithms for smooth convex optimization. As such, they are frequently used in solving smooth convex optimization problems over polytopes, for which the computational cost of orthogonal projections would be prohibitive. However, they do not enjoy …
Unified analysis of federated learning with compression for various data distributions.
problem Communication overhead in federated learning with unreliable or limited communication.
method Periodic compressed communication and local gradient tracking schemes.
result Sharp convergence rates for various objective functions and data distributions.
New algorithm extends LMC to more complex potentials.
problem Addressing limitations of existing LMC methods.
method Inexact Proximal Langevin Algorithm (IPLA).
result Improved convergence rates and broader applicability.
Many classical algorithms are found until several years later to outlive the confines in which they were conceived, and continue to be relevant in unforeseen settings. In this paper, we show that SVRG is one such method: being originally designed for strongly convex objectives, it is also very robust in non-strongly co…
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…
Let and be domains of equipped with respective probability measures and . We consider the problem of optimal transport from to with respect to a cost function . To ensure that the solution to this problem is smooth, it is necessary to make several ass…
The paper proves properties of complex Finsler metrics on specific domains.
problem Investigating invariant complex Finsler metrics on complex domains.
method Analyzing holomorphic automorphism groups and constructing metrics.
result Explicitly constructed metrics on polydisks with properties similar to Bergman metric.
We develop recursive, data-driven, stochastic subgradient methods for optimizing a new, versatile, and application-driven class of convex risk measures, termed here as mean-semideviations, strictly generalizing the well-known and popular mean-upper-semideviation. We introduce the MESSAGEp algorithm, which is an efficie…
For -holomorphic mappings for a strongly pseudo-convex manifold, we prove elliptic regularity by the argument of boots-strapping.
Characterizes Anosov representations and strongly convex cocompact groups with eigenvalue gaps.
problem Understanding Anosov representations and their properties.
method Characterizations via equivariant limit maps, Cartan property, and uniform gap summation.
result Characterizations of Anosov representations and strongly convex cocompact subgroups.
The Adam algorithm has become extremely popular for large-scale machine learning. Under convexity condition, it has been proved to enjoy a data-dependant regret bound where is the time horizon. However, whether strong convexity can be utilized to further improve the performance remains an open problem…
The paper proves a Schwarz lemma for weakly Kähler-Finsler manifolds.
problem Estimating distance functions and proving Schwarz lemma for weakly Kähler-Finsler manifolds.
method Establishing theorems about distance functions and applying them to prove the Schwarz lemma.
result Holomorphic mappings from weakly Kähler-Finsler manifolds to pseudoconvex Finsler manifolds are constant under certain conditions.
Universal online optimization for dynamic environments using uniclass prediction.
problem Online optimization in changing environments with dynamic regret.
method Reduces dynamic online optimization to uniclass prediction problem, allowing control over dynamic regret bounds.
result First paper with state-of-the-art dynamic regret guarantees for general convex cost functions.
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.
Classification of the locally strongly convex centroaffine hypersurfaces with parallel cubic formmath.DG
In this paper, we study locally strongly convex centroaffine hypersurfaces with parallel cubic form with respect to the Levi-Civita connection of the centroaffine metric. As the main result, we obtain a complete classification of such centroaffine hypersurfaces. The result of this paper is a centroaffine version of the…
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.
In this paper, we establish a general inequality for locally strongly convex centroaffine hypersurfaces in involving the norm of the covariant derivatives of both the difference tensor and the Tchebychev vector field . Our result is optimal in that, applying our recent classification for local…
The paper examines hyperbolicity in bounded strongly minimally convex domains in R^d.
problem Investigating hyperbolicity in bounded strongly minimally convex domains.
method Analyzing the minimal metric and Hilbert metric in convex domains.
result Every bounded strongly minimally convex domain is Gromov hyperbolic.