Primal-Dual Rates and Certificates

By Celestine Mendler-Dünner, Simone Forte, Martin Takác, Martin Jaggi. 2016

60 citations recorded by the source corpus.

We propose an algorithm-independent framework to equip existing optimization methods with primal-dual certificates. Such certificates and corresponding rate of convergence guarantees are important for practitioners to diagnose progress, in particular in machine learning applications. We obtain new primal-dual convergence rates, e.g., for the Lasso as well as many L1, Elastic Net, group Lasso and TV-regularized problems. The theory applies to any norm-regularized generalized linear model. Our approach provides efficiently computable duality gaps which are globally defined, without modifying the original problems in the region of interest.

Subfields: Artificial Intelligence, Computational Mechanics, Mathematical Physics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Mathematical Physics

Citations in the corpus

COLA: Decentralized Linear Learning (2018, methodology): “Then after T iterations where We have that the expected duality gap satisﬁes ⇤ , and v 0 k := =1 W kl v l and ¯ v k := and ¯ w k := 1 P P Note that the assumption of bounded support for the g i functions is not restrictive in the general convex case, as discussed e.g. in [Dünner et al., 2016].”
CoCoA: A General Framework for Communication-Efficient Distributed Optimization (2016, background): “Lipschitz continuity of ḡ∗i follows directly, or alternatively also from the general result that g∗i is L-Lipschitz if and only if gi has L-bounded support (Rockafellar, 1997, Corollary 13.3.3) or (Dünner et al., 2016, Lemma 5).”
Distributed optimization with arbitrary local solvers (2015, background): “We always explicitly state when we require each assumption.”
Stochastic, Distributed and Federated Optimization for Machine Learning (2017, background): “It is well known [143, 172, 164, 55] that the first-order optimality conditions give rise to a natural mapping that relates pairs of primal and dual variables.”
Hessian-CoCoA : a general parallel and distributed framework for non-strongly convex regularizers (2017, methodology): “Already with [2], the already existing CoCoA+ framework, described in [7], was extended to problems with non-strongly convex regularizers.”
Efficient Use of Limited-Memory Accelerators for Linear Learning on Heterogeneous Systems (2017, methodology): “This was shown before in [13, 4] for the special case of exact coordinate updates.”
Adaptive balancing of gradient and update computation times using global geometry and approximate subproblems (2018, unknown): “For more details about the setting and applications, we refer to the discussion in [9].”
A Dual Approach for Optimal Algorithms in Distributed Optimization over Networks (2018, background): “Sometimes this function are also called admissible [29, 71], or Fenchel tractable [23].”
Faster Coordinate Descent via Adaptive Importance Sampling (2017, methodology): “A function f : R n → R ∪ { + ∞} has B -bounded support if its domain is bounded by B : Lemma 2.2 (Duality between Lipschitzness and L-Bounded Support, [D¨unner et al., 2016]) .”
L1-Regularized Distributed Optimization: A Communication-Efficient Primal-Dual Framework (2015, background): “Lemma 3 (Duality between Lipschitzness and L-Bounded Support, [24, Corollary 13.3.3]).”