New approach for distributed online optimization of non-convex losses with sublinear regret.
problem Regret evaluation and consensus in distributed, multi-agent systems with non-convex losses.
method Composite regret metric and consensus-based online normalized gradient (CONGD) approach for pseudo-convex losses; offline optimization oracle for general non-convex losses.
result First sublinear regret bound for general distributed online non-convex learning.
New method optimizes on curved manifolds without curvature dependence.
problem Curvature-dependent regret in online optimization on Hadamard manifolds.
method Riemannian online gradient descent for h-convex functions.
result Established O ( T ) O(\sqrt{T}) O ( T ) and O ( log ( T ) ) O(\log(T)) O ( log ( T )) regret guarantees, curvature-independent. Boosting improves online decision-making for large expert sets.
problem Online convex optimization with many experts is infeasible.
method Generalizes online boosting to online convex optimization and bandit linear optimization settings.
result Near-optimal regret guarantees for various feedback models.
Optimal algorithms for online convex optimization with random order.
problem Online convex optimization with random order and non-convex loss functions.
method Stochastic gradient descent and algorithmic stability analysis.
result Achieves optimal bounds and significantly outperforms previous methods.
New control methods for systems with adversarial perturbations.
problem Control systems with adversarial noise.
method Online convex optimization and convex relaxations.
result Low regret policies against adversarial perturbations.
New algorithms optimize non-smooth, non-convex objectives with improved complexity.
problem Optimizing non-smooth, non-convex stochastic objectives.
method Reduction to online learning, applying optimistic online learning techniques.
result Improved complexity for finding ( δ , ε ) (δ,ε) ( δ , ε ) -stationary points. Improved online learning for hidden-convex losses achieves optimal regret.
problem Adversarial online learning with nonconvex losses that become convex after reparameterization.
method Algorithmic equivalence between OGD and OMD on convex losses, with Hessian compatibility condition.
result OGD achieves O ( T ) \mathcal{O}(\sqrt{T}) O ( T ) regret for hidden-convex losses, matching optimal rate. New framework uses tempered optimism to handle imperfect experts in online learning.
problem Challenges of implicit optimism in practical online learning environments.
method Introduces tempered optimism as a framework for online non-convex learning, modifies existing algorithms.
result Demonstrates tempered optimism as a fruitful paradigm for online non-convex learning.
Optimal hidden-target learning for online inventory optimization on general convex sets.
problem Online inventory optimization (OIO) on arbitrary bounded convex capacity sets.
method Maintaining a hidden target and projecting it onto the feasible order-up-to set.
result The method improves the best known regret guarantee for OIO on general convex sets from inverse to inverse-square-root dependence on the common-demand probability.
Optimal control in changing systems without strong convexity assumptions.
problem Adversarial changes in convex costs for unknown linear systems.
method Non-convex lower confidence bounds and computationally-efficient regret minimization.
result Achieves T \smash{\sqrt{T}} T -regret rate, optimal compared to best stabilizing controller. Online optimization has been a successful framework for solving large-scale problems under computational constraints and partial information. Current methods for online convex optimization require either a projection or exact gradient computation at each step, both of which can be prohibitively expensive for large-scal…
We study online optimization in a setting where an online learner seeks to optimize a per-round hitting cost, which may be non-convex, while incurring a movement cost when changing actions between rounds. We ask: \textit{under what general conditions is it possible for an online learner to leverage predictions of futur…
Extends boosting to multiclass online agnostic classification.
problem Online multiclass classification with weak learners.
method Reduces multiclass online agnostic boosting to online convex optimization.
result First boosting algorithm for online agnostic multiclass classification.
Optimal bounds on regret and constraint violation in adversarial COCO.
problem Minimizing regret and cumulative constraint violation in adversarial COCO.
method New surrogate loss function and Follow-the-Regularized-Leader/Online Gradient Descent.
result Achieved optimal O ( T ) O(\sqrt{T}) O ( T ) bounds on both regret and cumulative constraint violation. Unified framework for analyzing online convex optimization across various settings.
problem Analyzing online convex optimization in different settings and feedback types.
method Unified framework allowing systematic proposal and analysis of meta-algorithms.
result Comparable regret bounds for various feedback types and adversary types.
New algorithm for online learning in episodic MDPs with convex objectives.
problem Online episodic convex reinforcement learning.
method Online mirror descent algorithm with varying constraint sets and exploration bonus.
result Near-optimal regret bounds for online CURL without prior knowledge of transition function.
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.
Study on collaborative vs. non-collaborative online and bandit convex optimization.
problem Minimizing average regret in distributed online and bandit convex optimization.
method Analyzes the impact of collaboration in adaptive and zeroth-order feedback settings.
result Collaboration is beneficial in high-dimensional federated online optimization with limited feedback.
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.
The paper develops methods for time-varying constrained online convex optimization.
problem Time-varying loss and constraint functions in online convex optimization.
method Model-based augmented Lagrangian methods (MALM) for time-varying and delayed feedback.
result Sublinear regret and constraint violation for both time-varying and delayed feedback scenarios.
Paper introduces a new G ⋆ G^\star G ⋆ regret measure for online convex optimization with smooth losses.
problem Online convex optimization with smooth losses.
method Introduces a new G ⋆ G^\star G ⋆ regret measure that depends on the cumulative squared gradient norm. result The G ⋆ G^\star G ⋆ regret can be arbitrarily sharper than existing measures when losses have vanishing curvature. Efficient algorithms for online convex optimization with limited switching decisions.
problem Online convex optimization with limited switching decisions.
method Presented computationally efficient algorithms for both general and strongly convex losses.
result Regret bounds of O ( T / S ) O(T/S) O ( T / S ) for general convex losses and O ~ ( T / S 2 ) \widetilde O(T/S^2) O ( T / S 2 ) for strongly convex losses. Online convex optimization is a sequential prediction framework with the goal to track and adapt to the environment through evaluating proper convex loss functions. We study efficient particle filtering methods from the perspective of such a framework. We formulate an efficient particle filtering methods for the non-st…
Fast algorithm for online optimization on transport polytopes.
problem Optimizing convex objectives on transport polytopes.
method Mirror Sinkhorn algorithm combining Sinkhorn scaling and mirror descent.
result Robust and efficient online optimization for convex objectives.
In this paper, we study adaptive online convex optimization, and aim to design a universal algorithm that achieves optimal regret bounds for multiple common types of loss functions. Existing universal methods are limited in the sense that they are optimal for only a subclass of loss functions. To address this limitatio…
Linear optimization is many times algorithmically simpler than non-linear convex optimization. Linear optimization over matroid polytopes, matching polytopes and path polytopes are example of problems for which we have simple and efficient combinatorial algorithms, but whose non-linear convex counterpart is harder and …
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.
Improved online convex optimization bounds between stochastic and adversarial settings.
problem Understanding optimization tasks that are neither i.i.d. nor fully adversarial.
method Establishing novel regret bounds exploiting smoothness of expected losses.
result Regret bounds improve on previous results by reducing dependence on maximum gradient length to variance of gradients.
New framework captures long-term decision dependence in online learning.
problem Long-term dependence on past decisions in online learning.
method Introduces Online Convex Optimization with Unbounded Memory (OCO-UMB) and p p p -effective memory capacity. result Proves O ( H p T ) O(\sqrt{H_p T}) O ( H p T ) upper bound on policy regret and matching lower bound. New method achieves both universality and adaptivity in online convex optimization.
problem Achieve optimal regret guarantees without prior knowledge of function curvature.
method Introduces UniGrad, a novel approach that achieves both universality and adaptivity.
result Achieves universal regret guarantees that adapt to gradient variation.
SA algorithms control dynamic regret in non-stationary settings with strong convexity or exp-concavity.
problem Non-stationary Online Convex Optimization with dynamic regret control.
method Strongly Adaptive (SA) algorithms view dynamic regret as path variation of the comparator sequence.
result SA algorithms achieve i l d e O ( T V T ∨ log T ) ilde O(\sqrt{TV_T} \vee \log T) i l d e O ( T V T ∨ log T ) and i l d e O ( d T V T ∨ d log T ) ilde O(\sqrt{dTV_T} \vee d\log T) i l d e O ( d T V T ∨ d log T ) dynamic regret for strongly convex and exp-concave losses, respectively. Optimal switching regret for all segmentations in online convex optimisation.
problem Non-stationary online convex optimisation problems.
method Developed an efficient algorithm to achieve optimal switching regret on every possible segmentation.
result Achieved asymptotically optimal switching regret on every possible segmentation simultaneously.
Paper tackles online learning on curved spaces without projections.
problem Online learning on Riemannian manifolds with computational constraints.
method Develops projection-free algorithms for geodesically convex optimization.
result Achieves sub-linear regret guarantees in online geodesically convex optimization.
Improved regret bounds for online convex optimization under stochastic and adversarial settings.
problem Interpolating between stochastic and adversarial online convex optimization.
method Optimistic online mirror descent (OMD) for the Stochastically Extended Adversarial (SEA) model.
result Established new regret bounds for various function classes.
We consider online learning in an adversarial, non-convex setting under the assumption that the learner has an access to an offline optimization oracle. In the general setting of prediction with expert advice, Hazan et al. (2016) established that in the optimization-oracle model, online learning requires exponentially …
New algorithms reduce regret in online convex optimization with heavy-tailed gradients.
problem Challenges in online convex optimization with heavy-tailed gradients.
method Examined and analyzed old algorithms for online convex optimization in the heavy-tailed setting.
result Established new regret bounds for classical methods without algorithmic modification.
Improved privacy and efficiency in online convex optimization.
problem Differentially private online convex optimization in high dimensions.
method Improves upon Agarwal et al. [2023] by reducing dimension factors and removing smoothness requirement.
result Best known rates for ( ε , δ ) (ε, δ) ( ε , δ ) -differentially private online convex optimization in the regime of ε not being very small. New private algorithms for online learning improve regret in high privacy regimes.
problem Private online learning from experts and convex optimization.
method Transformed lazy algorithms for differential privacy.
result Improved regret bounds for DP-OPE and DP-OCO.
Improved online convex optimization with delayed feedback using curvature.
problem Online convex optimization with curved losses and delayed feedback.
method Variant of follow-the-regularized-leader and Online Newton Step algorithm with adaptive learning rate.
result Regret bounds of order min { σ max ln T , d t o t } \min\{σ_{\max}\ln T, \sqrt{d_{\mathrm{tot}}}\} min { σ m a x ln T , d tot } for exp-concave losses. Paper proposes an online learning method with multi-level adaptivity for diverse loss functions.
problem Online learning with unknown types and curvatures of functions.
method Multi-layer online ensemble approach with gradient variations.
result Achieves improved regret bounds for different types of loss functions.
We consider Online Convex Optimization (OCO) in the setting where the costs are m m m -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…
New bounds for online convex optimization between stochastic and adversarial settings.
problem Understanding optimization tasks that are neither i.i.d. nor fully adversarial.
method Establishing novel regret bounds exploiting smoothness of expected losses.
result Regret bounds match expected rates in the fully i.i.d. case and gracefully deteriorate in the fully adversarial case.
New method tackles online DR-submodular maximization with improved regret guarantees.
problem Online maximization of non-monotone DR-submodular functions over down-closed convex sets.
method 1/e-linearization through exponential reparametrization, surrogate potential, and reduction to online linear optimization.
result Achieves O ( T 1 / 2 ) O(T^{1/2}) O ( T 1/2 ) static regret with single gradient query per round, improving state of the art. OSGM uses online learning to adapt stepsize for faster convergence.
problem Improving convergence rates of first-order methods.
method OSGM combines online learning and feedback functions to adjust stepsize.
result OSGM achieves convergence rates asymptotically no worse than optimal.
Boosting is a widely used machine learning approach based on the idea of aggregating weak learning rules. While in statistical learning numerous boosting methods exist both in the realizable and agnostic settings, in online learning they exist only in the realizable case. In this work we provide the first agnostic onli…
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…
New algorithm reduces regret in bandit optimization for high-dimensional data.
problem Optimizing decisions in uncertain environments with high-dimensional data.
method Inspired by online Newton step, proposes a simple and efficient BCO algorithm.
result Achieves optimal regret bounds for κ κ κ -convex functions. 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 O ( C 2 , T ∗ ) O(C^*_{2,T}) O ( C 2 , T ∗ ) regret bound with one gradient query per round.