instruction:
In this task, you are given a part of an article. Your task is to generate headline (title) for this text. Preferred headlines are under fifteen words.
question:
Traditional algorithms for stochastic optimization require projecting the solution at each iteration into a given domain to ensure its feasibility. When facing complex domains, such as positive semi-definite cones, the projection operation can be expensive, leading to a high computational cost per iteration. In this paper, we present a novel algorithm that aims to reduce the number of projections for stochastic optimization. The proposed algorithm combines the strength of several recent developments in stochastic optimization, including mini-batch, extra-gradient, and epoch gradient descent, in order to effectively explore the smoothness and strong convexity. We show, both in expectation and with a high probability, that when the objective function is both smooth and strongly convex, the proposed algorithm achieves the optimal O(1/T ) rate of convergence with only O(log T ) projections. Our empirical study verifies the theoretical result.
answer:
O(logT ) Projections for Stochastic Optimization of Smooth and Strongly Convex Functions


question:
Existing methods for dealing with knowledge updates differ greatly depending on the underlying knowledge representation formalism. When Classical Logic is used, updates are typically performed by manipulating the knowledge base on the model-theoretic level. On the opposite side of the spectrum stand the semantics for updating Answer-Set Programs that need to rely on rule syntax. Yet, a unifying perspective that could embrace both these branches of research is of great importance as it enables a deeper understanding of all involved methods and principles and creates room for their cross-fertilisation, ripening and further development. Furthermore, from a more pragmatic viewpoint, such a unification is a necessary step in addressing updates of hybrid knowledge bases consisting of both a classical and a rule component. This paper bridges the seemingly irreconcilable approaches to updates. It introduces a novel monotonic characterisation of rules, dubbed RE-models, and shows it to be a more suitable semantic foundation for rule updates than SE-models. Then it proposes a generic scheme for specifying semantic rule update operators, based on the idea of viewing a program as the set of sets of RE-models of its rules; updates are performed by introducing additional interpretations – exceptions – to the sets of RE-models of rules in the original program. The introduced scheme is then used to define particular rule update operators that are closely related to both classical update principles and traditional approaches to rules updates, enjoying a range of plausible syntactic as well as semantic properties. In addition, these operators serve as a basis for a solution to the long-standing problem of state condensing for two of the foundational rule update semantics, showing how they can be equivalently defined as binary operators on some class of logic programs. Finally, the essence of these ideas is extracted to define an abstract framework for exception-based update operators, viewing a knowledge base as the set of sets of models of its elements. It is shown that the framework can capture a wide range of both modeland formula-based classical update operators, and thus serves as the first firm formal ground connecting classical and rule updates.
answer:
Exception-Based Knowledge Updates


question:
We define a logic of propositional formula schemata adding to the syntax of propositional logic indexed propositions (e.g., pi) and iterated connectives ∨ or ∧ ranging over intervals parameterized by arithmetic variables (e.g., ∧n i=1 pi, where n is a parameter). The satisfiability problem is shown to be undecidable for this new logic, but we introduce a very general class of schemata, called bound-linear, for which this problem becomes decidable. This result is obtained by reduction to a particular class of schemata called regular, for which we provide a sound and complete terminating proof procedure. This schemata calculus (called stab) allows one to capture proof patterns corresponding to a large class of problems specified in propositional logic. We also show that the satisfiability problem becomes again undecidable for slight extensions of this class, thus demonstrating that bound-linear schemata represent a good compromise between expressivity and decidability.
answer:

Decidability and Undecidability Results for Propositional Schemata