1,721,108 research outputs found
Minimisation of Polyak-\L{}ojasewicz Functions Using Random Zeroth-Order Oracles
Get PDFThe application of a zeroth-order scheme for minimising Polyak-\L{}ojasewicz
(PL) functions is considered. The framework is based on exploiting a random
oracle to estimate the function gradient. The convergence of the algorithm to a
global minimum in the unconstrained case and to a neighbourhood of the global
minimum in the constrained case along with their corresponding complexity
bounds are presented. The theoretical results are demonstrated via numerical
examples
Global Convergence of Arbitrary-Block Gradient Methods for Generalized Polyak-{\L} ojasiewicz Functions
No full textIn this paper we introduce two novel generalizations of the theory for gradient descent type methods in the proximal setting. First, we introduce the proportion function, which we further use to analyze all known (and many new) block-selection rules for block coordinate descent methods under a single framework. This framework includes randomized methods with uniform, non-uniform or even adaptive sampling strategies, as well as deterministic methods with batch, greedy or cyclic selection rules. Second, the theory of strongly-convex optimization was recently generalized to a specific class of non-convex functions satisfying the so-called Polyak-{\L}ojasiewicz condition. To mirror this generalization in the weakly convex case, we introduce the Weak Polyak-{\L}ojasiewicz condition, using which we give global convergence guarantees for a class of non-convex functions previously not considered in theory. Additionally, we establish (necessarily somewhat weaker) convergence guarantees for an even larger class of non-convex functions satisfying a certain smoothness assumption only. By combining the two abovementioned generalizations we recover the state-of-the-art convergence guarantees for a large class of previously known methods and setups as special cases of our general framework. Moreover, our frameworks allows for the derivation of new guarantees for many new combinations of methods and setups, as well as a large class of novel non-convex objectives. The flexibility of our approach offers a lot of potential for future research, as a new block selection procedure will have a convergence guarantee for all objectives considered in our framework, while a new objective analyzed under our approach will have a whole fleet of block selection rules with convergence guarantees readily available
On the Lower Bound of Minimizing Polyak-{\L}ojasiewicz Functions
Get PDFPolyak-{\L}ojasiewicz (PL) [Polyak, 1963] condition is a weaker condition
than the strong convexity but suffices to ensure a global convergence for the
Gradient Descent algorithm. In this paper, we study the lower bound of
algorithms using first-order oracles to find an approximate optimal solution.
We show that any first-order algorithm requires at least
gradient costs to
find an -approximate optimal solution for a general -smooth
function that has an -PL constant. This result demonstrates the optimality
of the Gradient Descent algorithm to minimize smooth PL functions in the sense
that there exists a ``hard'' PL function such that no first-order algorithm can
be faster than Gradient Descent when ignoring a numerical constant. In
contrast, it is well-known that the momentum technique, e.g. [Nesterov, 2003,
chap. 2] can provably accelerate Gradient Descent to
gradient
costs for functions that are -smooth and -strongly convex.
Therefore, our result distinguishes the hardness of minimizing a smooth PL
function and a smooth strongly convex function as the complexity of the former
cannot be improved by any polynomial order in general
Gradient-Type Methods For Decentralized Optimization Problems With Polyak-{\L}ojasiewicz Condition Over Time-Varying Networks
Get PDFThis paper focuses on the decentralized optimization (minimization and saddle
point) problems with objective functions that satisfy Polyak-{\L}ojasiewicz
condition (PL-condition). The first part of the paper is devoted to the
minimization problem of the sum-type cost functions. In order to solve a such
class of problems, we propose a gradient descent type method with a consensus
projection procedure and the inexact gradient of the objectives. Next, in the
second part, we study the saddle-point problem (SPP) with a structure of the
sum, with objectives satisfying the two-sided PL-condition. To solve such SPP,
we propose a generalization of the Multi-step Gradient Descent Ascent method
with a consensus procedure, and inexact gradients of the objective function
with respect to both variables. Finally, we present some of the numerical
experiments, to show the efficiency of the proposed algorithm for the robust
least squares problem
A Generalized Alternating Method for Bilevel Learning under the Polyak-{\L}ojasiewicz Condition
Get PDFBilevel optimization has recently regained interest owing to its applications
in emerging machine learning fields such as hyperparameter optimization,
meta-learning, and reinforcement learning. Recent results have shown that
simple alternating (implicit) gradient-based algorithms can match the
convergence rate of single-level gradient descent (GD) when addressing bilevel
problems with a strongly convex lower-level objective. However, it remains
unclear whether this result can be generalized to bilevel problems beyond this
basic setting. In this paper, we first introduce a stationary metric for the
considered bilevel problems, which generalizes the existing metric, for a
nonconvex lower-level objective that satisfies the Polyak-{\L}ojasiewicz (PL)
condition. We then propose a Generalized ALternating mEthod for bilevel
opTimization (GALET) tailored to BLO with convex PL LL problem and establish
that GALET achieves an -stationary point for the considered problem
within iterations, which matches the iteration
complexity of GD for single-level smooth nonconvex problems.Comment: Camera ready versio
Quantized Distributed Nonconvex Optimization Algorithms with Linear Convergence under the Polyak--{\L}ojasiewicz Condition
Get PDFThis paper considers distributed optimization for minimizing the average of
local nonconvex cost functions, by using local information exchange over
undirected communication networks. To reduce the required communication
capacity, we introduce an encoder--decoder scheme. By integrating them with
distributed gradient tracking and proportional integral algorithms,
respectively, we then propose two quantized distributed nonconvex optimization
algorithms. Assuming the global cost function satisfies the
Polyak--{\L}ojasiewicz condition, which does not require the global cost
function to be convex and the global minimizer is not necessarily unique, we
show that our proposed algorithms linearly converge to a global optimal point
and that larger quantization level leads to faster convergence speed. Moreover,
we show that a low data rate is sufficient to guarantee linear convergence when
the algorithm parameters are properly chosen. The theoretical results are
illustrated by numerical examples
Going Beyond Counting First Authors in Author Co-citation Analysis
Get PDFThe present study examines one of the fundamental aspects of author co-citation analysis (ACA) - the way co-citation
counts are defined. Co-citation counting provides the data on which all subsequent statistical analyses and mappings
are based, and we compare ACA results based on two different types of co-citation counting - the traditional type that
only counts the first one among a cited work's authors on the one hand and a non-traditional type that takes into
account the first 5 authors of a cited work on the other hand. Results indicate that the picture produced through this non-traditional author co-citation counting contains more coherent author groups and is therefore considerably clearer. However, this picture represents fewer specialties in the research field being studied than that produced through the traditional first-author co-citation counting when the same number of top-ranked authors is selected and analyzed. Reasons for these effects are discussed
Distributionally Time-Varying Online Stochastic Optimization under Polyak-{\L}ojasiewicz Condition with Application in Conditional Value-at-Risk Statistical Learning
Get PDFIn this work, we consider a sequence of stochastic optimization problems
following a time-varying distribution via the lens of online optimization.
Assuming that the loss function satisfies the Polyak-{\L}ojasiewicz condition,
we apply online stochastic gradient descent and establish its dynamic regret
bound that is composed of cumulative distribution drifts and cumulative
gradient biases caused by stochasticity. The distribution metric we adopt here
is Wasserstein distance, which is well-defined without the absolute continuity
assumption or with a time-varying support set. We also establish a regret bound
of online stochastic proximal gradient descent when the objective function is
regularized. Moreover, we show that the above framework can be applied to the
Conditional Value-at-Risk (CVaR) learning problem. Particularly, we improve an
existing proof on the discovery of the PL condition of the CVaR problem,
resulting in a regret bound of online stochastic gradient descent
Variations on the Author
Get PDF“Variations on the Author” discusses two of Eduardo Coutinho’s recent films (Um Dia na Vida, from 2010, and Últimas Conversas, posthumously released in 2015) and their contribution to the general question of documentary authorship. The director’s filmography is characterized by a consistent yet self-effacing form of authorial self-inscription: Coutinho often features as an interviewer that rather than express opinions propels discourses; an interviewer that is good at listening. This mode of self-inscription characterizes him as an author who is not expressive but who is nonetheless markedly present on the screen. In Um Dia na Vida, however, Coutinho is completely absent form the image, while Últimas Conversas, on the contrary, includes a confessional prologue that moves the director from the margins to the center of his films. This article examines the ways in which these works stand out in the filmography of a director who offers new insights into the notion of cinematic authorship
- …
