Daniela Genius
email: daniela.genius@lip6.fr

Scalability of TTool's AMS extensions: a case study

Embedded cyber-physical systems (CPS) are commonly built upon heterogeneous digital and analog integrated circuits, including sensors and actuators. Less common is their deployment on parallel, NoC based designs based on general purpose processor cores of a Multi-processor System-on-chip (MPSoC). Application code has to be run on the MPSoC for the digital part, and interact with the analog sensors. We recently proposed a major extension to the design and exploration tool named TTool, now allowing the design of CPS on a high level of abstraction and the generation of cycle-bit accurate simulations. We explore the scalability of our approach with an automotive case study.

I. INTRODUCTION

Many applications e.g. from robotics, automotive and autonomous systems require heterogeneous modeling -including modeling of analog/mixed signal (AMS) and radio frequency (RF) features. In very early design phases, rapid but less precise exploration of the design space is required. Co-simulation of heterogeneous embedded systems then requires a high-level representation that includes high-level models of AMS and RF components. In the approach we presented in [START_REF] Porto | Modeling and virtual prototyping for embedded systems on mixed-signal multicores[END_REF] software is run on the digital multiprocessor system on chip (MPSoC) platform, but has to communicate with the analog part. Whereas that work took as a starting point an analog application where only the controller was defined as a task running on a SoC, [START_REF] Genius | A tool for high-level modeling of analog/mixed signal embedded systems[END_REF] presented a full methodology on a toy example. The present paper explores a far more complex case study, where a lot more functionality resides in the software tasks.

The next section presents the ways in which the design problems problems are addressed in similar research work. Section III presents the bases. Some of the questions raised when modeling larger applications are listed in Section IV; Section V illustrates them by a larger case study, Section VI concludes the paper.

II. RELATED WORK

Well established tools in analog/mixed signal design, like Ptolemy II, [START_REF] Lee | Disciplined heterogeneous modeling[END_REF] [START_REF]System Design, Modeling, and Simulation using Ptolemy II[END_REF], based upon a data-flow model, address heterogeneous systems by defining several sub domains using hierarchical models. Instantiation of elements controlling the time synchronization between domains is left to the responsibility of designers.

Metropolis [START_REF] Balarin | Metropolis: An integrated electronic system design environment[END_REF] is based on a high level model and facilitates the separation of computation from communication concerns. Metro II [START_REF] Davare | A next-generation design framework for platform-based design[END_REF] introduces hierarchy and allows Adaptors for data synchronization as a bridge between the semantics of components belonging to different MoCs; the model designer still has to implement time synchronization. As a common simulation kernel handles all process execution, MoCs are not well separated.

Discrete Event System Specification (DEVS [START_REF] Concepcion | DEVS formalism: A framework for hierarchical model development[END_REF]), a modular and hierarchical formalism for modeling and analyzing general systems that can be discrete event or continuous state systems.

SystemC [START_REF]IEEE. SystemC. IEEE Standard[END_REF] is a C++ class library which makes it possible to model (digital) hardware on multiple levels of abstraction. Among the frameworks based on SystemC are HetSC [START_REF] Herrera | A framework for heterogeneous specification and design of electronic embedded systems in SystemC[END_REF], HetMoC [START_REF] Zhu | Hetmoc: Heterogeneous modelling in systemc[END_REF] and ForSyDe [START_REF] Niaki | Formal heterogeneous system modeling with systemc[END_REF], all having the disadvantage that instantiation of elements and controlling the synchronization have to be managed by the designer.

SystemC-AMS extensions [START_REF]Accellera Systems Initiative[END_REF] is a standard describing an extension of SystemC with AMS and RF features [START_REF] Vachoux | Analog and mixed signal modelling with SystemC-AMS[END_REF]. The usual approach for modeling the digital part of a heterogeneous system with SystemC is to rely on the Discrete Event (DE) part of SystemC AMS extensions. The Timed data Flow (TDF) part adds support for signals where data values are sampled with a constant time step.

In the scope of the project BeyondDreams [START_REF]Beyond Dreams (Design Refinement of Embedded Analogue and Mixed-Signal Systems)[END_REF], a mixed analog-digital systems proof-of-concept simulator has been developed, based on the SystemC AMS extension standard. Another simulator is proposed in the H-Inception project [START_REF]Heterogeneous Inception Project[END_REF]. All of these approaches rely on SystemC AMS code i.e. they don't provide a high-level interface for specifying the application. Integration with software code for general-purpose CPUs and with an operating system is however not yet addressed in these approaches.

III. CONTEXT

A. TTool

Our modeling framework is the free and opensource software called TTool [START_REF] Apvrille | TTool, an open-source toolkit for the modeling and verification of embedded systems[END_REF]. TTool relies on SysML to propose two abstract modeling levels: (i) HW/SW partitioning and (ii) software design and deployment [START_REF] Pedroza | AVATAR: A SysML environment for the formal verification of safety and security properties[END_REF]. Software tasks for the partitioning model are captured within the functional abstraction level, and software tasks used in deployments are captured in the software design abstraction level. In both levels, the computation part of tasks is then deployed to processors and hardware accelerators, and the communication and storage parts are deployed to buses and memories. In the software deployment level, so-called deployment diagrams are used to capture the allocation of software components onto a MPSoc platform. The tool chain which generates a cycle/bit accurate MPSoC virtual prototype built from SoCLib [START_REF]The SoCLib project: An integrated system-on-chip modelling and simulation platform[END_REF] components is explained in [START_REF] Genius | Virtual yet precise prototyping: An automotive case study[END_REF]. Figure 1, stemming from [START_REF] Genius | A tool for high-level modeling of analog/mixed signal embedded systems[END_REF], shows the overall design flow. TTool was recently extended with support for modeling CPS [START_REF] Genius | A tool for high-level modeling of analog/mixed signal embedded systems[END_REF], and validated for smaller examples but not yet whether the methodology scales to larger case studies.

B. SystemC Extensions for AMS

SystemC [START_REF]IEEE. SystemC. IEEE Standard[END_REF] relies on a Discrete Event (DE) simulation kernel. Timed Data Flow (TDF) is one of the (main) MoC of SystemC-AMS. It adds to SystemC support for signals where continuous data values are sampled with a constant time step. A TDF module is described by an attribute representing a time step and a so-called processing function. The time step is associated to a time period during which the processing function should be executed. The processing function corresponds to a mathematical function depending on both inputs and internal states. TDF modules interact with discrete parts using converter ports and have the following attributes:

1) Module Timestep (Tm) denotes the period during which the module is activated. A module will be activated only if there are enough samples available at its input ports. 2) Rate (R). Each module will read or write a fixed number of data samples each time it is activated, annotated to the port as port rate. 3) Port Timestep (Tp) denotes the period during which each port of a module will be activated. It also denotes the time interval between two samples being read or written. 4) Delay (D). A delay can be assigned to a port and will make the port handle a fixed number of samples at each activation, and read or write them in the following activation of the port.

C. MPSoC Virtual Prototype

In case software code is also deployed, an MPSoc platform containing processors / buses / memories must also be generated, as well as a description of mapping of tasks and other software objects provided. SoCLib offers a way to describe Multi-Processor System-on-Chip platforms with semantics based on the shared memory paradigm. Components can be initiators issuing requests (typically CPUs and hardware accelerators), or targets answering to requests (e.g. RAM).

In order to combine SoCLib specification with SystemC-AMS components, we have defined generic adaptor modules that can connect SystemC-AMS components to Virtual Component Interface (VCI) [START_REF]Virtual Component Interface Standard[END_REF] interfaces. The main idea for the integration of SystemC-AMS and SoCLib components into TTool is that analog components act as targets for the SoCLib initiator digital components (CPUs, DMA, . . . ).

An adapter is modeled as a general-purpose input/output (GPIO) target component, following the modeling rules for writing cycle-bit precise SystemC simulation models for SoCLib described below. GPIO components are visible in the deployment diagram, and, like the other VCI components, their interconnection to the central VCI interconnect is represented by an arc. The generated top cell is thus composed of SoCLib modules and interfaces to the SystemC-AMS clusters.

D. Simulation

Due to their different Model of Computation, AMS components require to execute their simulated behavior apart from the rest of the system, but regularly synchronize with the digital platform. The SystemC kernel is thus controlling the AMS kernel which runs continuously until it is interrupted by access to a converter port by a TDF cluster. Since model-driven approaches expect to ideally provide model validation before code generation (and thus simulation), we propose a way to statically identify synchronization problems [START_REF] Porto | Integration of SystemC-AMS simulation platforms into TTool[END_REF].

IV. QUESTIONS RAISED Until now, applications modeled with the recent extension of TTool ran basically on mono processors, even if, as mentioned in [START_REF] Porto | Modeling and virtual prototyping for embedded systems on mixed-signal multicores[END_REF], SoCLib is designed for MPSoC virtual prototypes. But does this also hold for multiple sensors connected by multiple GPIO and for a MPSoC with multiple processors? The rover application in [START_REF] Genius | A tool for high-level modeling of analog/mixed signal embedded systems[END_REF] contained only two sensors, each came with its GPIO with one input and one output port, and a single processor. Larger applications feature several GPIO, more ports, each accessing the central interconnect as a target, generating additional traffic. Secondly, in the presence of multiple TDF clusters, addressed by different parts of the software running on the SoCLib MPSoC, read and write operations between the digital and analog part must be handled carefully. Not only must causality between TDF and DE be respected as shown in [START_REF] Andrade | Pre-Simulation Formal Analysis of Synchronization Issues between Discrete Event and Timed Data Flow Models of Computation[END_REF], [START_REF] Porto | Modeling and virtual prototyping for embedded systems on mixed-signal multicores[END_REF], also the semantics of accesses by several analog blocks to the same digital block and vice versa must be preserved. Thirdly, the GPIO interface is to date limited to transmitting only one value at a time, of a basic type. In SystemC-AMS, it is quite complicated to pass structured data types as parameters of a module. While TTool already handles them issue when generating pure SystemC-AMS code, GPIO interfaces do not yet take them into account.

V. CASE STUDY

These problems and current attempts at their solution are illustrated by an automotive embedded system designed in the scope of a past European project [START_REF] Evita | E-safety Vehicle InTrusion protected Applications[END_REF] and the code generation for which was presented in [START_REF] Li | Virtual prototyping of automotive systems: Towards multi-level design space exploration[END_REF].

Recent on-board Intelligent Transport (IT) architectures comprise a very heterogeneous landscape of communication network technologies (e.g., LIN, CAN, MOST, and FlexRay) that interconnect incar Electronic Control Units (ECUs). One of these is automatic braking [START_REF] Kelling | Specification and evaluation of e-security relevant use cases[END_REF], which works essentially as follows: an obstacle is detected by another automotive system which broadcasts that information to neighboring cars. A car receiving that information has to decide whether or not it is concerned. This decision includes a plausibility check function that takes into account various parameters, such as the direction and speed of the car, and also information previously received from neighboring cars. Once the decision to brake has been taken, the braking order is forwarded to relevant ECUs. Also, the presence of this obstacle is forwarded to other neighboring cars in case they have not yet received this information.

The functional view comprises of a set of communicating tasks whose is described abstractly. Mapping then partitions the application into software and hardware. A task mapped onto a processor will be implemented in software, and a task mapped onto a hardware accelerator is implemented in hardware. Tasks destined to be in hardware are either digital or analog; each task is represented on a separate panel. In the example, all sensors obtaining information from the environment will be modeled as analog blocks.

A. Software design

Once the partitioning is done, the user designs the software, for which functional simulation and formal verification are performed. Figure 3 shows the block diagram from [START_REF] Li | Virtual prototyping of automotive systems: Towards multi-level design space exploration[END_REF] with on top the five sensors, modeled as software tasks. In the current version, the five sensors in the TestBench block are no longer modeled as software tasks. Remaining software components are grouped according to their destination ECU:

• Communication ECU manages communication with neighboring vehicles. To prototype the software components with the other elements of the destination platform (hardware components, operating system), we must map them to a model of the target system. Mapping can be performed using the deployment features introduced in [START_REF] Genius | Virtual yet precise prototyping: An automotive case study[END_REF]: such a deployment diagram is a SysML representation of hardware components, their interconnection, tasks and channels.

B. Modeling sensors

Modeling the sensors by blocks of code translated to Posix tasks running on the MPSoC, as was practice beforehand, oversimplified the problem. All five sensors are thus replaced by more realistic analog models: five independent TDF clusters (keeping in mind that TDF still is a strong abstraction of analog behavior).

Figure 4 shows an AMS panel with one of the sensor clusters, the CarPositionSimulator sensor. In further dialogues, not shown here, parameters like rate and delay can be entered. From these graphical information, TTool then infers, if possible, missing parameters, calculates a coherent schedule and generates SystemC-AMS code, comprising the ports, delays and interfaces [START_REF] Porto | Integration of SystemC-AMS simulation platforms into TTool[END_REF]. This cluster is read by the DSRSC_Management block and gives information on the car id and position. Often, data structures or more than one parameter are transmitted in the channels (here, id and position). Currently, they have to be transmitted one by one, basic type by basic type. Thus, id and position require two sequential write operations to the out port in the processing code and two corresponding read operations in the entry code.

We can easily model the randomized choice of an integer between 1 and 5 (id) and between 3 and 10 (position) stemming from the data type, on the left of Figure 3. The code of this simple processing function is shown on the right of the figure in a separate window. The write primitive sends one integer value to the out converter port.

C. Communication

A library named libsyscams has been provided to contain read and write primitives on the side of the MPSoC, the read_gpio2vci and write_gpio2vci functions. As shown above, CarPositionSimulator issues two random values from its output port, EmergencySimulator does the same.

On the side of the MPSoC platform, according to TTool's semantics, the DSRSC_Management block non-deterministically reads from either block, or read a broadcastEmergencyBrakingMessage from a third, the DangerAvoidanceStrategy block. In the current version, the first two blocks being replaced by sensors modeled in SystemC-AMS, this semantics should be preserved.

In the following, we give an example of how to use libsyscams to capture non-deterministic read operations. Consider the finite state machine (FSM) of the DSRSC_Management block (Figure 5). In [START_REF] Genius | A tool for high-level modeling of analog/mixed signal embedded systems[END_REF], we show how to use entry code that can be contained in a state to call libsyscams. This is the case of the WaitForEnvironmentInput state. Non-deterministically, either the input from Car-PositionSimulator or EmergencySimulator is read, whenever values are available on either. This nondeterminism, which was in the past expressed by the semantics of TTool's channels between software blocks, must now be reflected in the entry code of the software block's state machine. If there are several parameters (here id and position), they must currently be read sequentially. to CPUs, the latter to on-chip memory. For a better overview, the diagram contains sensors as gray boxes, each corresponding to a SystemC-AMS cluster connected via a GPIO. Clicking on the box opens the corresponding SystemC-AMS panel. A fifth CPU which the sensors beforehand is no longer in use. TTool first checks the coherency of the block and port parameters before calculating a valid TDF schedule for each TDF cluster, taking into account synchronization issues between the TDF and DE world [START_REF] Genius | A tool for high-level modeling of analog/mixed signal embedded systems[END_REF]. This is done in a so-called validation window (Figure 7). Once the cluster schedule is validated, one can initiate code generation by another mouse click. The number of targets connected to the central interconnect is now of 17 (five GPIO in addition to the original 12 target modules) and the number of initiators of 4 (one less CPU), potentially stretching the capacity of the VGMN to its limits, to be explored in future experiments.

VI. CONCLUSION AND FUTURE WORK

The paper presents a case study which explores current limitations of the AMS extensions of TTool on a larger industrial application. We succeeded in running larger-scale software on a MPSoC; exhaustive exploration and performance evaluation remains to be done.

Communication between the digital and the analog part is performed by C entry code inserted in the state blocks, relaxing the correct-by-construction hypothesis of TTool. Non-determinism of read and write operations should be handled more properly. Also, it should be possible to transmit structured data types and multiple parameters more conveniently. The TDF models are still oversimplified; in the EVITA industrial case study however, no more detail is available. Next, we will model an application stemming from the Open Source EchOpen project [START_REF] Community | Designing an open-source and low-cost echo-stethoscope[END_REF], where we will have access to full implementation detail. Finally, even if analog components tend to be unique, we plan to provide a library of parametrizable building blocks for typical components such as filters and analog/digital converters.

Figure 2

 2 Figure2shows a cluster, where the DE modules are represented as white blocks, TDF modules as gray blocks, TDF normal ports as black squares, TDF converter ports as black and white squares, DE ports as white squares and TDF signals as arrows.

Fig. 1 .

 1 Fig.1. Hardware/Software partitioning and Code generation for MPSoC platforms[START_REF] Genius | A tool for high-level modeling of analog/mixed signal embedded systems[END_REF]

  0 : int; ~in isObstacleAhead(int info) ~ out getInfoOnObstacle(int info) block PlausibilityCheck -id : int; -position : int; -speed : int; -obstacle : int; -list : NodeList; -currentPosition : int; -emergencyIgnored() -emergencyTakenIntoAccount() -getListOfNodes(int position, NodeList list) block VehiculeDynamicsManagement -speed : int; ~ in updateOnSpeed(int speed) ~ out getInfoOnSpeed(int speed) block BCU block DangerAvoidanceStrategy -speed : int; -position : int; -currentPosition : int; -carinfo : CarInfo; -value : int; ~ in brake(int speed, int currentPosition, int position) ~ out reducePower(int value) ~ out brakePower(int value) ~out forwardEmergency(int myID, int currentPosition) block BrakeManagement -value : int; -deltaBrake = 0 : int; -brakeMaxDuration : int; -applyBraking(int value) -brakingDone() ~ in brake(int value) block PTC block DrivingPowerReductionStrategy -value : int; -minReducePowerTime = 10 : int; -maxReducePowerTime = 20 : int; -applyReducePower(int value) -reducePowerDone() ~in getReducePowerOrder(int value) block Communication block DSRSC_Management -id : int; -position : int; -sendMessage(int id, int position) ~in obstacleDetected(int id, int position) ~ in carPosition(int id, int position) ~ out setCarPosition(int id, int position) ~ out forwardEmergencyBrakingMessage(int i... ~in broadcastEmergencyBrakingMessage(int i... block NeighbourhoodTableManagement -id : int; -position : int; -time_id : int; -listOfNodes : NodeList; -currentPosition : int; ~ in addANode(int id, int position) ~ in setPosition(int currentPosition) block CorrectnessChecking -id : int; -position : int; -canHaveInvalid = false : bool; -checkingMessage() -invalidMessage() -validMessage() ~ in getEmergencyBrakingMessage(... ~out toPlausibityCheckMessage(int... block TestBench block SpeedSensor -minSpeedUpdate = 150 : int; -maxSpeedUpdate = 150 : int; -speed : int; -carinfo : CarInfo; ~ out updateOnSpeed(int speed) block RadarSensor -minRadarUpdate = 100 : int; -maxRadarUpdate = 150 : int; -obstacleAhead : int; ~out obstacleAhead(int info) block GPSSensor -minGPSUpdate = 100 : int; -maxGPSUpdate = 100 : int; -position : int; -carinfo : CarInfo; ~ out setPosition(int currentPosition) block CarPositionSimulator -carid : CarInfo; -minCarPositionInterval = 200 : int; -maxCarPositionInterval = 250 : i... -id : int; -position : int; ~out carPosition(int id, int positio... block EmergencySimulator -minEmergencyInterval = 1000 :... -maxEmergencyInterval = 1000 ... -carid : CarInfo; -id : int; -position : int; ~out obstacleDetected(int id, int...

Fig. 3 .

 3 Fig. 3. Automotive case study: software design block diagram[START_REF] Li | Virtual prototyping of automotive systems: Towards multi-level design space exploration[END_REF]

Fig. 4 .

 4 Fig. 4. CarPositionSimulator sensor

Fig. 5 .Fig. 6 .

 56 Fig. 5. DSRSC_Management FSM containing entry code

Fig. 7 .

 7 Fig. 7. Validation and code generation window


Maxime

MINES Thomas

Le Pascal

Masson

Benoit

Weil

Modeling market to commercialize innovation: how the forgotten historical figure of salesman helps us learn on how firms design market models

Innovation commercialization phase appears more and more as an issue for both marketing and innovation management literatures. This paper studies a particular aspect of innovation commercialization, namely the market-model design activities occurring during this phase. The paper builds on an underlying paradox of the literature. On a one hand consistent market models are useful for company to commercialize innovation and on the other hand marketization literature claims that the relevant variables depicting a market are countless and unknown. To sort out how market-modeling activities support innovation commercialization we conducted seven longitudinal historical case studies on commercial travellers. We looked for how 19 th century companies employing commercial travellers structured their market models to foster commercialization excellence. Our results indicate that these companies used representations of the market that can be define as ad hoc market models. The representations are models as they are built only on few coherent variables but they are ad hoc as they differ from one case to another. Given these results we discuss the specificities of the design of ad hoc market models and define the innovation commercialization phase as the market-model design phase.

Context:

Marketing facilitates innovation commercialization. First by aligning product specifications with customer needs. Second by orchestrating product launches in known markets. However, radical innovations address unknown markets. Therefor the challenge is commercializing while learning. Before marketing science, nineteenth-century-firms employing commercial travellers confronted such challenge. Their history unveils market-modeling activities relevant for innovation commercialization. This paper is organized as follow. First we review the literature on innovation commercialization to depict the crucial role played by market models. The literature claiming also that market models are impossible to build due to the countless number of relevant variables, a research question is set to investigate this paradox. Then we detail a methodology based on the analysis of peer-reviewed business history papers that deal with commercial travellers. We then present our results that confirm the use of models, highlighting that firms hierarchized the variables to avoid the pitfalls described by the literature. We then conclude by a discussion toward a more strategic role played by salespeople.

firms operate in new marketing domain and face marketing discontinuity [START_REF] Mcnally | Product Innovativeness Dimensions and Their Relationships with Product Advantage, Product Financial Performance, and Project Protocol[END_REF]. This lead firms to engage in market-learning approach that are highly specific [START_REF] Lynn | Marketing and Discontinuous Innovation: The Probe and Learn Process[END_REF] as the market is not yet created at the beginning of the innovation commercialization process [START_REF] Storbacka | Learning with the market: Facilitating market innovation[END_REF]. Therefore actual conceptualization depict innovation commercialization as a dynamic process that include continuous feedbacks and changes in marketing strategy [START_REF] Aarikka-Stenroos | Commercializing a radical innovation : Probing the way to the market[END_REF][START_REF] Mattila | Coping with friction during technology commercialisation[END_REF]. This process aim at gaining support from the firm external network [START_REF] Aarikka-Stenroos | From new-product development to commercialization through networks[END_REF][START_REF] Chiesa | Commercializing Technological Innovation: Learning from Failures in High-Tech Markets[END_REF]. Therefore, commercialization is more and more conceptualized as a market-shaping activity [START_REF] Kjellberg | Market innovation processes: Balancing stability and change[END_REF] during which marketing and sales functions [START_REF] Geiger | Industrial sales people as market actors[END_REF] try to overcome the resistance of endusers and demonstrate the benefit of the commercialized innovation [START_REF] Aarikka-Stenroos | From new-product development to commercialization through networks[END_REF].

Therefore recent conceptualizations of commercialization depict this phase as the moment when companies have to overcome marketing discontinuity. To cope with it the literature identify that firm engage in market modeling activities.

Overcoming marketing discontinuity: Restoring coherent market models

When investigating the strategies that firm endorse to cope with marketing discontinuity, there is a growing interest in the literature towards market models. Two main key features of market models are discussed in the literature dealing with innovation commercialization.

First, market models are recognized as assets help firm to take strategic decision regarding commercialization [START_REF] Aarikka-Stenroos | Building up a firm ' s commercialisation competence : from product concept to the first reference[END_REF], 2014;[START_REF] Dmitriev | An exploration of business model development in the commercialization of technology innovations[END_REF][START_REF] Flammini | Business model configuration and dynamics for technology commercialization in mature markets[END_REF]. Therefore market visioning capabilities are key for innovation commercialization [START_REF] Colarelli | The nature of market visioning for technology-based radical innovation[END_REF] and market models should be developed and refined during the New Product Development process (O 'Connor, 1998;[START_REF] Tsai | Dynamic marketing capabilities and radical innovation commercialisation[END_REF].

Second, the literature highlight that market models are key assets in order to gain the support of the external network. Clear market models make firm take coherent actions regarding their network which is positively correlated with the commercialization success [START_REF] Chiesa | Commercializing Technological Innovation: Learning from Failures in High-Tech Markets[END_REF]. Thus market shaping literature considers modeling as an important phase of the market learning process [START_REF] Storbacka | Learning with the market: Facilitating market innovation[END_REF] that could help a market actor to drive he market. This literature defines market scripting as the conscious activities conducted by a market actor in order to alter the current market configuration in its favor. To do so a market actor should first be able to change its mental model before sending a signal to other players by changing its business model [START_REF] Storbacka | Scripting markets: From value propositions to market propositions[END_REF]. Therefore, in this literature, a new market is created once all the market actors changed their related market models [START_REF] Mason | Managing to make markets : Marketization and the conceptualization work of strategic nets in the life science sector[END_REF].

Therefore one of the key insights of the literature is that to cope with marketing discontinuity, firms should be able to develop new market models. Put differently, firm should be able to spot the critical variables that help build a viable commercial strategy.

The notion of model brings two important remarks. First, the number of variables in a model should remain low so that the model is still useful. Second the model is develop with a certain domain of validity. We conclude that having a coherent market model is a key asset to conduct innovation commercialization.

Difficulty of market modeling for innovation commercialization

However interesting, market models may be difficult to develop during innovation commercialization. Three main reasons account for the difficulties of market modeling during a commercialization process in the literature.

First the variables useful to describe a market are numerous and heterogeneous. The development of marketization literature [START_REF] Çalişkan | Economization, part 2: A research programme for the study of markets[END_REF] is an example of the multiplicity of the market descriptors that could be use. By considering markets as configurations (Storbacka & Nenonen, 2011a), marketization literature had multiply the relevant variables that can be used to describe markets.

Second the relevant variables of a market models are unknown at the beginning of the process and may be of very different nature. This is well documented in early work on innovation where the problems may come from both the technical side and the social side [START_REF] Akrich | Les utilisateurs , acteurs de l ' innovation Les utilisateurs[END_REF][START_REF] Akrich | the Key To Success in Innovation Part I: the Art of Interessement[END_REF][START_REF] Cochoy | L ' innovateur comme acheteur : Howard Head et l ' invention des skis composites ( 1947-1949 ) The Innovator as a Buyer : Howard Head and the Invention of Composite Skis[END_REF].

Third, relevant market variables are changing overtime. This is due to the efforts of others companies also trying to shape the market in directions that suit them more. As such, the multiplication of market shaping activities [START_REF] Azimont | Category reviews as market-shaping events[END_REF][START_REF] Geiger | Industrial sales people as market actors[END_REF][START_REF] Humphreys | Status Games: Market Driving through Social Influence in the US wine Industry[END_REF][START_REF] Kjellberg | Market innovation processes: Balancing stability and change[END_REF] contribute to make the variables even more changing.

Therefore we conclude with the literature that designing a market model is complex due to the fact that variables are countless, unknown and changing.

Literature gap and research question

According to innovation commercialization literature, firms uncover through commercialization a set of critical variables that ensure radical innovation success. However, marketization literature claims that prospective variables are countless and that critical variables are unforeseeable. Hence on the one hand: one should have a market model. Often the literature has tended to underestimate what this notion of model means; that is to say not only critical variables but also non-critical one, ie validity domain of the model. On the other hand it is unclear how this model could be designed since the candidates variables are countless, unknown and changing. Hence question: is this notion of "market model" really present in practice and more specifically, if there is such thing as a "market model", how can a firm organize to design this market model? In particular, guidance to separate useful learning from anecdotal evidence would be valuable for innovation commercialization literature. To provide such guidance, we investigate the link between market modeling and commercialization through the following research question: How do market-modeling activities conducted by a firm contribute to commercialization of radical innovation and the creation of the related market? More specifically we propose several interrelated sub-research questions:

1) How to account theoretically to the apparent paradox in the literature between the use of market-models for commercialization and the fact that relevant variables are countless? 2) What are the specificities of the design process to build a market model used to support commercialization? 3) In the case of innovation commercialization, what is the link between innovation commercialization phase and the design process of market model ?

Methodology

In order to study our exploratory research question, we decided to conduct a case studies analysis from a highly qualitative sample. Our aim is to build a sample of cases from which we can extract market models contributing to commercialization and analyze their common structures and discrepancies. In order to be relevant to our research question, each case should therefore comply with three conditions. First it should display an access to the market models of commercialization at stake. Second it should account for successful cases of commercialization to ensure that the studied market models supported commercialization. Third the richness of each case should be high in order to allow some longitudinal analysis and comparisons. Those three reasons drove us to build a sample of peered-review business history papers describing 19 th century firms employing traveling salesmen. The choice to study specifically traveling salesmen is rooted in the fact that 19 th century firm hired salesmen when they wanted specifically to stimulate and prime markets without modifying the product. Therefore our cases can be considered as pure commercialization cases. Furthermore, this sample complies with our three conditions. First salesmen and firms send numerous letters to each other, which spell out the market models prevailing during commercialization, enabling us to have access to the market model used by the firm. Second, the paper account for companies that succeeded on their market during a long period of time, therefore confirming that they were undertaking successful commercialization activities. Third, salesman activities are well documented over long time periods. Therefore this rich material is longitudinal in two senses: a) it cover time periods from product launch to product success; b) it covers, for a single company, several commercialization campaign, hence put light on the organizational process that is repeatedly used to design a market model.

To build our sample we follow the following approach. First we selected relevant business history peered-reviews journal, we selected Business History, Business History Review, Enterprise and Society, Entreprise et Histoire, Management and Organizational History.

Based on a review of the term used to designate traveling salesmen around the world [START_REF] Friedman | Salesmen in comparative perspective[END_REF], we looked for the terms "peddlers" ; "drummers" ; "commercial travellers" ; "manufacturers' reps" ; "commis voyageurs" and "traveling salesmen" in the databases of these journals. The abstract of the papers -and when more work was needed the content of the papers -helped to discriminate relevant papers. The choice of incorporating the papers in the sample was conducted separately by the authors. The main reason of reject was the quality of the description of the content of the letters that where send by companies to commercial travellers. The In the papers the market models are implicit in the papers, however, because of their richness our cases recount on the instructions the firms gave to salesman and the management tools used. For us, the dimensions on which the headquarters gave instructions and the management tools used spell out the market model mobilized by the firms. We selected all the instructions and management tools and the related quotes from our material. Then we agreed among the authors on a market model that encompasses all the orders. Then we compared the different models to see they common structures and discrepancies. Finally explain the discrepancies by the context of each specific case.

Results

Our results confirm that commercialization is a market-learning activity. The massive and continuous exchange of letters between salesman and the firm testifies the eager for market information. Our original results are two-folded. First, we show that firms endorse a proactive attitude toward market learning by setting market models. In each case, we have been able to identify a small number of market dimensions on which the firm focuses its instructions. Second, critical market dimensions differ from one case to the other. Table 2 for the detailed analysis of three cases [START_REF] Lyon-Jenness | Planting a Seed : The Nineteenth-Century Horticultural Boom in America[END_REF][START_REF] Rossfeld | Suchard and the emergence of traveling salesmen in Switzerland , 1860 -1920[END_REF][START_REF] Scott | Managing Door-to-Door Sales of Vacuum Cleaners in Interwar Britain[END_REF]. Each case is analyzed as follow : the market model is displayed, along with relevant quotes that illustrate it. Then to explain the discrepancies between market models, a "problem to be solved" is explained in each case, along with the relevant quotes.

To ease the understanding of our results we detailed them according to the three sub-research questions. Two French cases [START_REF] Bayard | Voyager plus pour vendre plus. Les commis voyageurs lyonnais au XVIII e siècle[END_REF][START_REF] Musset | L'expérimentation d'une nouvelle pratique commerciale : La maison Moët d'Epernay et ses commis voyageurs (1790-1815)[END_REF] are used to illustrate the results.

1) To solve the apparent paradox in the literature between the use of market-models for commercialization and the fact that relevant variables are countless, the 19 th century firm hierarchized the different variables. Thus the striking result of our study is that in each case, the number of dimensions on which indications are given to commercial salesmen is low. Headquarters concentrate on a restricted numbers of indications, leaving the other dimensions in the hands of the traveling salesmen. For example, logistics matters preoccupy silk manufacturers as they control carefully how, where and when their travelling salesmen are travelling. However, the traveling salesmen is in charge of setting the price (within a certain range), the time of the year the products will be delivered, the type of clients he meets… This results can be find in every case, see table two for more example. Thus headquarters deal with countless variables of the market by identifying critical ones on which they give instructions. The others dimensions are take care of by the traveling salesmen who adapt to sell more products. Therefore the notion of market-model is not usurped as headquarters identified not only critical variables but also identify noncritical one! Ie a market model (being a 'model') actually characterizes the variables that are not relevant to determine commercialization success.

2) Our research account also for the specificities of the design process to build a market model used to support commercialization. Even if we can only see the result of the design process (ie the market model) it is instructive. Even if it is a model, this is an 'ad hoc' model: the critical (and non critical) variables can be very different from one case to another. Therefore they have to be designed by taking into account contingent variables such as product to be sold, the commercialization company… The critical variables depend on the main problem to be solved by the headquarters. Fore example, for silk marchand, the main problem is to be the first to arrive in a city, therefore they concentrate their instructions on logistics matters. For champagne prodicers, the main issue is the quality of the wine once it reaches the client. Therefore instructions concentrated on carefully transport the delivery, of being always with a client when the first bottles are open and to manage caves in remote country so that the wine could be store more conveniently. For other matters such as publicity, logistics or type of clients, the instructions were much more flexible in coherence with results one. See table 2 for more example of specific problem to be solved and the specialized instructions given to solve it. Therefore our results is that, due to the specificities of the final model, the design of such market model have to be conducted during the commercialization phase. 1) "The enhancement of both advertising and catalogs served several functions for the horticultural industry" p398 "Customers could receive catalogs at no or minimal charge, often with the understanding that the cost of the catalog would be refunded with a purchase. Catalog producers also wanted to be sure that when a customer placed an order, he or she had appropriate cultural information in hand" p.399 2) "Agents, themselves lacking horticultural experience, sometimes failed to properly tend the plants in their care" p402 "These "official" agents usually received some horticultural training" p403 3) "Illustrations depicting fruit types or the ornamental potential of flowers and shrubs were critical to plant sales" p405 "Perhaps enchanted by the beauty of the illustrations, customers placed orders with virtual strangers and with little consideration for cultural details or regional hardiness.

Establishing trust for a product the client could not properly see as the main sells were seeds "The trade was dependent on customers' buying goods "sight unseen," both mechanisms were important vehicles for establishing familiarity and trust" p.398 "tree peddlers were everywhere and really did perpetrate fraud" p.407 "an unethical agent might boost prices, fail to provide adequate horticultural information to inexperienced customers, or perhaps inadvertently jumble horticultural varieties, so that eagerly awaited fruit trees or flowering roots were not "true to name"" p.402 (Ross feld, 2008) 1) Territories (to ensure intimacy with customer) 2) Coupled advertising and commercial traveller presence 3) Commission system (To ensure loyalty) 4) Commercial traveller manners (to ensure respectability) 1) "Initially, the traveling salesmen had no specifically defined territories and covered all of Switzerland […]; after 1880, clearly delineated "rayons" were assigned" p.743 "At the beginning of the 1880s, […] defined geographic regions, were assigned" p.741 2) "[Statistics] enabled the […] effectiveness of advertisements […] While this was "a complex, time-consuming task" it […] helped with the targeting of its advertising activities" p.747 "The traveling salesmen also participated in planning the use of advertising, distributing advertising materials, and improving their effectiveness" p.749 3) "Their remuneration comprised a fixed salary, travelling expenses and a commission that depended on sales, a feature […] introduced at the beginning of the 1890s" p.750 "Calculating the commissions was […] influenced by multiple factors, including the size of the territory, the traveling salesman's age, or the volume of goods sold" p.751 "at that time, most traveling salesmen were employed on a commission basis (without a fixed salary and expenses), which had disadvantages over [the firm's] system" p.751 4) "[The company] stated that politeness, patience, and "conversation suited" to the customer's character and education were important, as were a keen perception and carefully manicured hands for displaying the samples p.752

Fighting the bad reputation of commercial travellers of the time "It was difficult to draw a line between bona fide traveling salesmen and the uncontrollable peddlers and hawkers" p753

"The lack of differen-tiation between peddlers and hawkers, who sold their wares from door to door and were not employed by a company, and the profession of traveling salesman led to commercial travelers being considered as "ex-ponents of intermediate trade." Against the backdrop of an overcrowded retail market, which became noticeable after 1880, the traveling sales-man was anathema for many, viewed as the "embodiment of an imagi-nary parasitism.". p752 [START_REF] Scott | Managing Door-to-Door Sales of Vacuum Cleaners in Interwar Britain[END_REF] 1) Ensuring enough commercial travellers 2) Preparing the speech no to be drove back 1) "Chronic labor turnover entailed a constant stream of new salesmen, who were mainly recruited through small ads in local newspapers" p775 "Firms tended to apply only the most basic selectio in the knowledge that reliance on commission would soon weep out the poorer salesmen"p.775 2) "Recruits were typically sent to the firm's "schools" " p.776 "They were given a script to learn which they folloed almost to the letter" p777

The work of direct selling was deceptive hence with high turn over "High labor turnover was common in direct selling" p.772 "Hoover's British sales-force turnover was a staggering 500 percent"p.773 "The practicalities of selling vacuums door-to-door acted progressively to undermine morale, as the job entailed making calls that most often produced a curt "no thank you," p.778 Table 2 : Detailed cases of market models, problem to be solved and related quotes 3) More generally, it means that 'innovation commercialization' hence consists in identifying critical and non-critical variables; and consists in organizing the process to design the ad hoc market model. Therefore we propose to conceptualize the innovation commercialization phase as the phase during which the market model is designed.

Our results therefore show that each firm developed a specific market model for each commercialization process.

Discussion and contributions

Our results are aligned with precedent result on innovation commercialization. By focusing our analysis on market model, we highlight and concur with their crucial role in innovation commercialization [START_REF] Aarikka-Stenroos | Building up a firm ' s commercialisation competence : from product concept to the first reference[END_REF], 2014;[START_REF] Dmitriev | An exploration of business model development in the commercialization of technology innovations[END_REF][START_REF] Flammini | Business model configuration and dynamics for technology commercialization in mature markets[END_REF]. Second we set ground to explain more thoroughly why innovation commercialization is problematic: the market model is not establish yet [START_REF] Aarikka-Stenroos | Commercializing a radical innovation : Probing the way to the market[END_REF][START_REF] Connor | New Market Creation for Breakthrough Innovations : Enabling and Constraining Mechanisms[END_REF][START_REF] Lynn | Marketing and Discontinuous Innovation: The Probe and Learn Process[END_REF].

Our contribution extends current knowledge by building bridges between three literatures stream, namely marketization, innovation commercialization and sales roles. By showing that the headquarters rely on specific market models we solve a paradox that separated marketization literature and innovation commercialization literature. To deal with the countless variables described in marketization literature [START_REF] Azimont | Category reviews as market-shaping events[END_REF][START_REF] Kjellberg | Market innovation processes: Balancing stability and change[END_REF]Storbacka & Nenonen, 2011a) firms hierarchize them with a model enabling their action [START_REF] Mason | Managing to make markets : Marketization and the conceptualization work of strategic nets in the life science sector[END_REF]Storbacka & Nenonen, 2011a[START_REF] Tsai | Dynamic marketing capabilities and radical innovation commercialisation[END_REF]. Our second contribution is aligned with recent literature of sales agent that call for a more strategic-oriented role of sales [START_REF] Borg | Continuing the evolution of the selling process: A multi-level perspective[END_REF][START_REF] Fraenkel | Salesforce management factors for successful new product launch[END_REF][START_REF] Geiger | Industrial sales people as market actors[END_REF][START_REF] Goetz | The Role of Sales and Marketing in Market-Oriented Companies[END_REF][START_REF] Ulaga | The role of a solutions salesperson: Reducing uncertainty and fostering adaptiveness[END_REF]. Our results state that when commercializing an innovation, there is still a design activity to be conducted: to design a relevant market model. Therefore this call for a different perspective on sales, to move from an implementation role towards a more strategic role Of course, our research displays important limitations. First the research focuses only on commercial traveller due to our methodological choice. It could be interesting to see if others form of commercialization can also give access to market models and validate our results. Second we induce market models from our comprehension of the papers, an exchange among a wider community to validate that the model we choose are correct could be valuable.

We hope that this research could help further development in the three fields mentioned in particular to investigate the design activities related to salespeople.

  Table 1 describes the content of our sample.

	Reference	Journals	Type of product /	Period of study
			Industry
	(Berghoff, 2001)	Enterprise and	Harmonicas /	1857 -1930
		Society	Manufacturer Industry
	(Lyon-Jenness, 2004) The Business	Seeds / Horticulture	1800 -1900
		History Review
	(Rossfeld, 2008)	The Business	Chocolate / Food	1860 -1920
		History Review	Industry
	(Scott, 2008)	The Business	Vacuum Cleaner /	1918 -1945
		History Review	Manufacturing industry
	(Vabre, 2012)	Entreprise et	Roquefort / Food	1851 -1914
		Histoire	Transformation
	(Musset, 2012)	Entreprise et	Champagne / Food	1790 -1815
		Histoire	Industry
	(Bayard, 2012)	Entreprise et	Silk fabrics / Cloths	1700 -1800
		Histoire	Industry


Evgeniya Vorontsova

Alexander Gasnikov

Eduard Gorbunov

Pavel Dvurechenskii

Accelerated Gradient-Free Optimization Methods with a Non-Euclidean Proximal Operator

published or not. The documents may come   L'archive ouverte pluridisciplinaire

структура.

Введение

В данной статье рассматриваются безградиентные методы выпуклой оптимизации, называемые также методами нулевого порядка [START_REF] Rosenbrock | An Automatic Method for Finding the Greatest or Least Value of a Function[END_REF][START_REF] Brent | Algorithms for Minimization Without Derivatives // Dover Books on Mathematics[END_REF][START_REF] Spall | Introduction to Stochastic Search and Optimization[END_REF]. Основной особенностью этих методов является предположение о доступности только значения целевой функции, но недоступности градиента или гессиана. Такая ситуация возникает, например, если значение функции вычисляется с помощью некоторой вспомогательной компьютерной программы и доработка этой программы для вычисления градиента стоит дороже, чем машинное время. Кроме того, в отличие от вычисления значения функции, вычисление градиента может быть вычислительно нестабильным, например, в глубинных нейронных сетях при использовании обратной прогонки (backpropagation) [START_REF] Rumelhart | Learning Representations by Back-Propagating errors[END_REF][START_REF] Schmidhuber | Deep Learning in Neural Networks: An Overview // Neural Networks[END_REF][START_REF] Goodfellow | Deep Learning[END_REF][START_REF] Николенко | Глубокое обучение. Погружение в мир нейронных[END_REF].

В [START_REF] Yu | Random Gradient-Free Minimization of Convex Functions // Université catholique de Louvain[END_REF][START_REF] Yu | Random Gradient-Free Minimization of Convex Functions // Found[END_REF] были предложены ускоренные методы нулевого порядка 2 (безградиентные методы) решения задач гладкой выпуклой безусловной оптимизации. В отличие от известных до [START_REF] Yu | Random Gradient-Free Minimization of Convex Functions // Université catholique de Louvain[END_REF][START_REF] Yu | Random Gradient-Free Minimization of Convex Functions // Found[END_REF] методов ускоренные методы обладают более высокой скоростью сходимости. В рассуждениях [START_REF] Yu | Random Gradient-Free Minimization of Convex Functions // Found[END_REF] существенным образом использовалось то, что был выбран именно евклидов проксимальный оператор (далее будем называть его проксструктурой, это выпуклая гладкая функция, порождающая расстояние, и 1-сильно выпуклая относительно какой-то нормы; строгое определение вводится в разделе 3).

Такой выбор прокс-структуры для задач безусловной оптимизации является вполне естественным (см., например, [START_REF] Гасников | Стохастические градиентные методы с неточным оракулом // Тр[END_REF]). Однако в ряде задач имеется дополнительная информация, которая, например, позволяет рассчитывать на разреженность решения (когда в решении большая часть компонент нулевые). В частности, во многих задачах анализа данных существенным оказывается небольшое число признаков (потому и решения соответствующих задач обучения оказываются разреженными). Кроме

- 2𝛿 (𝑡 * ) 2 + 𝐿 2 = 0 ⇒ 𝑡 * = 2 √ 𝛿 𝐿 . Тогда (3) |𝛿 ∇ (𝑥, 𝑒, 𝑡 * )| 2 √ 𝐿𝛿 def = δ. Везде далее будем использовать параметр 𝑡 = 𝑡 * , поэтому можно писать 𝛿 ∇ (𝑥, 𝑒, 𝑡 * ) = 𝛿 ∇ (𝑥, 𝑒). Кроме того, для упрощения нотации будем использовать обозначение ̃ ∇𝑓 (𝑥)
вместо ̃ ∇ 𝛿, 𝑡 𝑓 (𝑥).

Ускоренный безградиентный метод

Введем дивергенцию Брэгмана 𝑉 𝑧 (𝑦), связанную с 𝑝-нормой:

𝑉 𝑧 (𝑦) def = 𝑑(𝑦) -𝑑(𝑧) -⟨∇𝑑(𝑧), 𝑦 -𝑧⟩,
где функция 𝑑(𝑥) является непрерывно дифференцируемой и сильно выпуклой с константой сильной выпуклости, равной единице (и называется прокс-функцией, или прокс-структурой, связанной с 𝑝-нормой). Например, для 𝑝 = 1 функцию 𝑑(𝑥) можно взять такой:

𝑑(𝑥) = 1 2(𝑎 -1) ||𝑥|| 2 𝑎 , где 𝑎 = 2 log 𝑛 2 log 𝑛-1 . Кроме того, пусть 𝑞 -такое число, что 1 𝑝 + 1 𝑞 = 1. Введем следующие объекты: Grad 𝑒 (𝑥) def = 𝑥 - 1 𝐿 ⟨ ̃ ∇𝑓 (𝑥) , 𝑒 ⟩ 𝑒, Mirr 𝑒 (𝑥, 𝑧, 𝛼) def = argmin 𝑦∈R 𝑛 { 𝛼 ⟨ 𝑛 ⟨ ̃ ∇𝑓 (𝑥) , 𝑒 ⟩ 𝑒, 𝑦 -𝑧 ⟩ + 𝑉 𝑧 (𝑦) } , где ⟨ ̃ ∇𝑓 (𝑥), 𝑒⟩ 𝑒 def = (⟨∇𝑓 (𝑥), 𝑒⟩ + 𝛿 ∇ (𝑥, 𝑒)) 𝑒.
Также обозначим (см. теорему 1 из [START_REF] Горбунов | О верхней оценке математического ожидания нормы равномерно распределенного на сфере вектора и явлении концентрации равномерной меры на[END_REF], формулировка приведена в Приложении) Выход: точка 𝑦 𝑁 .

(4) 𝐶 𝑛,𝑞 def = √ 3 min{2𝑞 -1,
1: 𝑦 0 ← 𝑥 0 , 𝑧 0 ← 𝑥 0 2: for 𝑘 = 0, . . . , 𝑁 -1

3:

𝛼 𝑘+1 ← 𝑘+2 4𝐿𝐶𝑛,𝑞 , 𝜏 𝑘 ← 1 2𝛼 𝑘+1 𝐿𝐶𝑛,𝑞 = 2 𝑘+2 4:
Генерируется 𝑒 𝑘+1 ∈ 𝑅𝑆 𝑛 2 (1), независимо от предыдущих итераций 5:

𝑥 𝑘+1 ← 𝜏 𝑘 𝑧 𝑘 + (1 -𝜏 𝑘 )𝑦 𝑘 6: 𝑦 𝑘+1 ← Grad 𝑒 𝑘+1 (𝑥 𝑘+1 ) 7: 𝑧 𝑘+1 ← Mirr 𝑒 𝑘+1 (𝑥 𝑘+1 , 𝑧 𝑘 , 𝛼 𝑘+1 )
8: end for Л е м м а 1. [START_REF] Bogolubsky | Learning Supervised PageRank with Gradient-Based and Gradient-Free Optimization Methods[END_REF] (формулировки приведены в Приложении), поэтому минимум достигается на втором 5 Если 𝑁 ∼ √ Θ𝐿𝐶𝑛,𝑞 𝜀 (оценивается порядок величины, числовые константы не учитываются), то

Если 𝜏 𝑘 = 1 2𝛼 𝑘+1 𝐿𝐶𝑛,𝑞 , то для всех 𝑢 ∈ R 𝑛 верны неравенства (5)
𝛼 𝑘+1 ⟨∇𝑓 (𝑥 𝑘+1 ), 𝑧 𝑘 -𝑢⟩ 2𝛼 2 𝑘+1 𝐿𝐶 𝑛,𝑞 (𝑓 (𝑥 𝑘+1 ) -E 𝑒 𝑘+1 [𝑓 (𝑦 𝑘+1 )]) + 𝑉 𝑧 𝑘 (𝑢) -E 𝑒 𝑘+1 [𝑉 𝑧 𝑘+1 (𝑢)]+ + 7 4 𝛼 2 𝑘+1 𝐶 𝑛,𝑞 δ2 + √ 𝑛 δ𝛼 𝑘+1 ||𝑢 -𝑧 𝑘 || 𝑝 , 𝑞 2, 𝑛 8. Л е м м а 2. Для всех 𝑢 ∈ R 𝑛 выполнено (6) 2𝛼 2 𝑘+1 𝐿𝐶 𝑛,𝑞 E 𝑒 𝑘+1 [𝑓 (𝑦 𝑘+1 ) | 𝑒 1 , . . . , 𝑒 𝑘 ]- -(2𝛼 2 𝑘+1 𝐿𝐶 𝑛,𝑞 -𝛼 𝑘+1 )𝑓 (𝑦 𝑘 ) + E 𝑒 𝑘+1 [𝑉 𝑧 𝑘+1 (𝑢)] -𝑉 𝑧 𝑘 (𝑢)- -7 4 𝛼 2 𝑘+1 𝐶 𝑛,𝑞 δ2 - √ 𝑛 δ𝛼 𝑘+1 ||𝑢 -𝑧 𝑘 || 𝑝 𝛼 𝑘+1 𝑓 (𝑢), 𝑞 2, 𝑛 8. Т е о р е м а. Пусть 𝑓 (𝑥) -выпуклая дифференцируемая функция на R 𝑛 с константой Липшица для градиента, равной 𝐿, 𝑑(𝑥) -1-сильно выпуклая в p-норме функция на R 𝑛 , 𝑁 ∈ N. Тогда ACDF на выходе даст точку 𝑦 𝑁 , удовлетворяющую неравенству (7) E[𝑓 (𝑦 𝑁 )] -𝑓 (𝑥 * ) 16Θ𝐿𝐶𝑛,𝑞 𝑁 2 + 35𝑁 𝛿 4 + 16 √ 2Θ𝑛𝐿𝛿 𝑁 2 + 8𝑛𝑁 2 𝛿 𝐶𝑛,𝑞 , где Θ def = 𝑉 𝑥 0 (𝑥 * ), 𝑞 2
𝛿 = 𝑂 ( min { 𝜀 3 2 √ Θ𝐿𝐶𝑛,𝑞 , 𝐶 2 𝑛,𝑞 Θ𝐿 𝑛 , 𝜀 2 𝑛Θ𝐿 }) = = 𝑂 ( min { 𝜀 3 2 √ Θ𝐿𝐶𝑛,𝑞 , 𝜀 2 𝑛Θ𝐿 }) . По определению (см. ( (8)
)) 𝐶 𝑛,𝑞 = √ 3 min{2𝑞 -1, 32 ln 𝑛 -8}𝑛 2 𝑞 +1 , а в случае 𝑝 = 2, 𝑞 = 2 можно взять 𝐶 𝑛,𝑞 = 𝑛 2 , что видно из теоремы 1 в [17] и леммы B.10 из 4
7(𝑁 +2)(2𝑁 +3)𝛿 6(𝑁 +1) ∼ 𝑁 𝛿 ∼ √ Θ𝐿𝐶𝑛,𝑞 𝜀 𝛿 ⇒ 𝛿 = 𝑂 ( 𝜀 3 2 √ Θ𝐿𝐶𝑛,𝑞 ) , 16 √ 2Θ𝑛𝐿𝛿 (𝑁 +1) 2 ∼ 𝜀 √ 𝑛𝛿 √ Θ𝐿𝐶𝑛,𝑞 ⇒ 𝛿 = 𝑂 ( Θ𝐿𝐶 2 𝑛,𝑞 𝑛 ) , 8𝑛𝑁 4 𝛿 𝐶𝑛,𝑞(𝑁 +1) 2 ∼ 𝑛𝑁 2 𝛿 𝐶𝑛,𝑞 ∼ 𝑛Θ𝐿𝛿 𝜀 ⇒ 𝛿 = 𝑂 ( 𝜀 2 𝑛Θ𝐿 ) . аргументе, т.е. если не учитывать еще и константы Θ и 𝐿, то 𝛿 = 𝑂 ( 𝜀 2 𝑛 ) и 𝑁 = 𝑂 ( √ Θ𝐿𝑛 2 𝜀 ) . Если же 𝑝 = 1, 𝑞 = ∞, то 𝐶 𝑛,𝑞 = 𝑛 √ 3 (32 ln 𝑛 -8) и 𝑁 = 𝑂 (√ Θ𝐿𝑛 ln 𝑛 𝜀 ) , 𝛿 = 𝑂 ( min { 𝜀 3 2 √ Θ𝐿𝑛 ln 𝑛 , 𝜀 2 𝑛Θ𝐿 }) .

Неускоренный безградиентный метод

Для сопоставления рассмотрим неускоренный метод

𝑥 𝑘+1 = argmin 𝑦∈R 𝑛 {𝛼⟨𝑛⟨ ̃ ∇𝑓 (𝑥 𝑘 ), 𝑒 𝑘+1 ⟩𝑒 𝑘+1 , 𝑦 -𝑥 𝑘 ⟩ + 𝑉 𝑥 𝑘 (𝑦)}.
Можно показать, что данный метод за 𝑁 итераций генерирует последовательность точек 𝑥 0 , 𝑥 1 , . . . , 𝑥 𝑁 , такую что

(9) E[𝑓 (x 𝑁 )] -𝑓 (𝑥 * ) 16Θ𝐿𝐶𝑛,𝑞 𝑛𝑁 + 8 √ 2𝑛Θ𝐿𝛿 𝑁 + 3𝑛𝛿 + 8𝑛 2 𝑁 𝛿 𝐶𝑛,𝑞 , где x𝑁 = 1 𝑁 ∑ 𝑁 -1 𝑘=0 𝑥 𝑘 . Оказывается, что нужно брать 𝛿 = 𝑂 ( 𝜀 2 𝑛
) (как и в ускоренном случае), чтобы получить 𝜀-решение по функции. Данная статья продолжает цикл работ, открытый публикацией [13] (см. также [START_REF] Гасников | Эффективные численные методы поиска равновесий в больших транспортных[END_REF]). Далее планируется распространить приведенные в настоящей статье результаты на задачи стохастической оптимизации и распространить все эти результаты на случай сильно выпуклой функции.

Численные эксперименты

П Р И Л О Ж Е Н И Е

Д о к а з а т е л ь с т в о л е м м ы 1. Во-первых, (П.1)

𝛼 𝑘+1 ⟨𝑛⟨ ̃ ∇𝑓 (𝑥 𝑘+1 ), 𝑒 𝑘+1 ⟩ 𝑒 𝑘+1 , 𝑧 𝑘 -𝑢⟩ = = ⟨𝛼 𝑘+1 𝑛⟨ ̃ ∇𝑓 (𝑥 𝑘+1 ), 𝑒 𝑘+1 ⟩ 𝑒 𝑘+1 , 𝑧 𝑘 -𝑧 𝑘+1 ⟩+ +⟨𝛼 𝑘+1 𝑛⟨ ̃ ∇𝑓 (𝑥 𝑘+1 ), 𝑒 𝑘+1 ⟩ 𝑒 𝑘+1 , 𝑧 𝑘+1 -𝑢⟩ x x ⟨𝛼 𝑘+1 𝑛⟨ ̃ ∇𝑓 (𝑥 𝑘+1 ), 𝑒 𝑘+1 ⟩ 𝑒 𝑘+1 , 𝑧 𝑘 -𝑧 𝑘+1 ⟩ + ⟨-∇𝑉 𝑧 𝑘 (𝑧 𝑘+1 ), 𝑧 𝑘+1 -𝑢⟩ y = y = ⟨𝛼 𝑘+1 𝑛⟨ ̃ ∇𝑓 (𝑥 𝑘+1 ), 𝑒 𝑘+1 ⟩ 𝑒 𝑘+1 , 𝑧 𝑘 -𝑧 𝑘+1 ⟩ + 𝑉 𝑧 𝑘 (𝑢) -𝑉 𝑧 𝑘+1 (𝑢) -𝑉 𝑧 𝑘 (𝑧 𝑘+1 ) z z ( ⟨𝛼 𝑘+1 𝑛⟨ ̃ ∇𝑓 (𝑥 𝑘+1 ), 𝑒 𝑘+1 ⟩ 𝑒 𝑘+1 , 𝑧 𝑘 -𝑧 𝑘+1 ⟩ -
⟨𝛼 𝑘+1 𝑛⟨ ̃ ∇𝑓 (𝑥 𝑘+1 ), 𝑒 𝑘+1 ⟩ 𝑒 𝑘+1 , 𝑧 𝑘 -𝑧 𝑘+1 ⟩ -1 2 ||𝑧 𝑘 -𝑧 𝑘+1 || 2 𝑝 𝛼 2 𝑘+1 𝑛 2 2 |⟨ ̃ ∇𝑓 (𝑥 𝑘+1 ), 𝑒 𝑘+1 ⟩| 2 ||𝑒|| 2 𝑞 = = 𝛼 2 𝑘+1 𝑛 2 2 (⟨∇𝑓 (𝑥 𝑘+1 ), 𝑒 𝑘+1 ⟩ + 𝛿 ∇ (𝑥 𝑘+1 , 𝑒 𝑘+1 )) 2 ||𝑒|| 2 𝑞 x x 𝛼 2 𝑘+1 𝑛 2 ⟨∇𝑓 (𝑥 𝑘+1 ), 𝑒 𝑘+1 ⟩ 2 ||𝑒 𝑘+1 || 2 𝑞 + 𝛼 2 𝑘+1 𝑛 2 𝛿 2 ∇ (𝑥 𝑘+1 , 𝑒 𝑘+1 )||𝑒 𝑘+1 || 2 𝑞 y y 𝛼 2 𝑘+1 𝑛 2 ⟨∇𝑓 (𝑥 𝑘+1 ), 𝑒 𝑘+1 ⟩ 2 ||𝑒 𝑘+1 || 2 𝑞 + 𝛼 2 𝑘+1 𝑛 2 δ2 ||𝑒 𝑘+1 || 2 𝑞 , где x следует из неравенства (𝑎 + 𝑏) 2 2𝑎 2 + 2𝑏
𝛼 𝑘+1 ⟨𝑛⟨ ̃ ∇𝑓 (𝑥 𝑘+1 ), 𝑒 𝑘+1 ⟩ 𝑒 𝑘+1 , 𝑧 𝑘 -𝑢⟩ 𝛼 2 𝑘+1 𝑛 2 ⟨∇𝑓 (𝑥 𝑘+1 ), 𝑒 𝑘+1 ⟩ 2 ||𝑒 𝑘+1 || 2 𝑞 + 𝛼 2 𝑘+1 𝑛 2 δ2 ||𝑒 𝑘+1 || 2 𝑞 + +𝑉 𝑧 𝑘 (𝑢) -𝑉 𝑧 𝑘+1 (𝑢), что можно записать в виде (П.4) 𝛼 𝑘+1 ⟨𝑛⟨∇𝑓 (𝑥 𝑘+1 ), 𝑒 𝑘+1 ⟩ 𝑒 𝑘+1 , 𝑧 𝑘 -𝑢⟩ 𝛼 2 𝑘+1 𝑛 2 ⟨∇𝑓 (𝑥 𝑘+1 ), 𝑒 𝑘+1 ⟩ 2 ||𝑒 𝑘+1 || 2 𝑞 + 𝛼 2 𝑘+1 𝑛 2 δ2 ||𝑒 𝑘+1 || 2 𝑞 + +𝑉 𝑧 𝑘 (𝑢) -𝑉 𝑧 𝑘+1 (𝑢) + 𝛼 𝑘+1 𝑛⟨𝛿 ∇ (𝑥 𝑘+1 , 𝑒 𝑘+1 )𝑒 𝑘+1 , 𝑢 -𝑧 𝑘 ⟩ 𝛼 2 𝑘+1 𝑛 2 ⟨∇𝑓 (𝑥 𝑘+1 ), 𝑒 𝑘+1 ⟩ 2 ||𝑒 𝑘+1 || 2 𝑞 + 𝑉 𝑧 𝑘 (𝑢) -𝑉 𝑧 𝑘+1 (𝑢)+ +𝛼 2 𝑘+1 𝑛 2 δ2 ||𝑒 𝑘+1 || 2 𝑞 + 𝛼 𝑘+1 𝑛|⟨𝛿 ∇ (𝑥 𝑘+1 , 𝑒 𝑘+1 )𝑒 𝑘+1 , 𝑢 -𝑧 𝑘 ⟩|.
В силу теоремы 1 из [START_REF] Горбунов | О верхней оценке математического ожидания нормы равномерно распределенного на сфере вектора и явлении концентрации равномерной меры на[END_REF] и того что 𝐶 𝑛,𝑞 равно √ 3 min{2𝑞-1, 32 ln 𝑛-8}𝑛 2 𝑞 +1 , получаем:

(П.5)

E 𝑒 𝑘+1 [𝛼 2 𝑘+1 𝑛 2 ⟨∇𝑓 (𝑥 𝑘+1 ), 𝑒 𝑘+1 ⟩ 2 ||𝑒 𝑘+1 || 2 𝑞 ] 𝛼 2 𝑘+1 𝐶𝑛,𝑞 𝑛 ||∇𝑓 (𝑥 𝑘+1 )|| 2 2 , E 𝑒 𝑘+1 [𝛼 2 𝑘+1 𝑛 2 δ2 ||𝑒 𝑘+1 || 2 𝑞 ] 3 4 𝛼 2 𝑘+1 𝐶 𝑛,𝑞 δ2 , E 𝑒 𝑘+1 [𝛼 𝑘+1 𝑛|⟨𝛿 ∇ (𝑥 𝑘+1 , 𝑒 𝑘+1 )𝑒 𝑘+1 , 𝑢 -𝑧 𝑘 ⟩|] = = E 𝑒 𝑘+1 [𝛼 𝑘+1 𝑛|𝛿 ∇ (𝑥 𝑘+1 , 𝑒 𝑘+1 )| • |⟨𝑒 𝑘+1 , 𝑢 -𝑧 𝑘 ⟩|] x x 𝛼 𝑘+1 𝑛 δE 𝑒 𝑘+1 [|⟨𝑒 𝑘+1 , 𝑢 -𝑧 𝑘 ⟩|] 𝛼 𝑘+1 𝑛 δ√ E 𝑒 𝑘+1 [|⟨𝑒 𝑘+1 , 𝑢 -𝑧 𝑘 ⟩| 2 ] y y 𝛼 𝑘+1 𝑛 δ√ ||𝑢-𝑧 𝑘 || 2 2 𝑛 = √ 𝑛 δ𝛼 𝑘+1 ||𝑢 -𝑧 𝑘 || 2 z √ 𝑛 δ𝛼 𝑘+1 ||𝑢 -𝑧 𝑘 || 𝑝 , где x следует из |𝛿 ∇ (𝑥 𝑘+1 , 𝑒 𝑘+1 )| δ,
𝛼 𝑘+1 ⟨∇𝑓 (𝑥 𝑘+1 ), 𝑧 𝑘 -𝑢⟩ 𝛼 2 𝑘+1 𝐶𝑛,𝑞 𝑛 ||∇𝑓 (𝑥 𝑘+1 )|| 2 2 + 𝑉 𝑧 𝑘 (𝑢) -E 𝑒 𝑘+1 [𝑉 𝑧 𝑘+1 (𝑢)]+ + 3 4 𝛼 2 𝑘+1 𝐶 𝑛,𝑞 δ2 + √ 𝑛 δ𝛼 𝑘+1 ||𝑢 -𝑧 𝑘 || 𝑝 .
Покажем теперь, что

(П.7) ||∇𝑓 (𝑥 𝑘+1 )|| 2 2 2𝑛𝐿(𝑓 (𝑥 𝑘+1 ) -E 𝑒 𝑘+1 [𝑓 (𝑦 𝑘+1 )]) + 𝑛 δ2 . 7 Пусть 𝑔 𝑥 (𝑝) def = ln ||𝑥|| 𝑝 = ln ( ∑ 𝑛 𝑘=1 |𝑥 𝑘 | 𝑝 ) 1 𝑝 = 1 𝑝 ln ( ∑ 𝑛 𝑘=1 |𝑥 𝑘 | 𝑝 ). Тогда 𝑑𝑔 𝑥 (𝑝) 𝑑𝑝 = - 1 𝑝 2 ln ( 𝑛 ∑ 𝑘=1 |𝑥 𝑘 | 𝑝 ) + 1 𝑝 • 𝑛 ∑ 𝑘=1 ln(|𝑥 𝑘 |) • |𝑥 𝑘 | 𝑝 𝑛 ∑ 𝑘=1 |𝑥 𝑘 | 𝑝 .
Так как ln 𝑦 -вогнутая по 𝑦 функция, то по неравенству Йенсена получаем, что

𝑑𝑔 𝑥 (𝑝) 𝑑𝑝 1 𝑝 ln ( 𝑛 ∑ 𝑘=1 |𝑥 𝑘 | 𝑝 ) -1 𝑝 + 1 𝑝 ln ⎛ ⎜ ⎜ ⎝ 𝑛 ∑ 𝑘=1 |𝑥 𝑘 | • |𝑥 𝑘 | 𝑝 𝑛 ∑ 𝑘=1 |𝑥 𝑘 | 𝑝 ⎞ ⎟ ⎟ ⎠ = 1 𝑝 ln ⎛ ⎜ ⎜ ⎜ ⎜ ⎝ 𝑛 ∑ 𝑘=1 |𝑥 𝑘 | 𝑝+1 ( 𝑛 ∑ 𝑘=1 |𝑥 𝑘 | 𝑝 ) 𝑝+1 𝑝 ⎞ ⎟ ⎟ ⎟ ⎟ ⎠ 1 𝑝 ln ⎛ ⎜ ⎜ ⎝ 𝑛 ∑ 𝑘=1 |𝑥 𝑘 | 𝑝+1 𝑛 ∑ 𝑘=1 (|𝑥 𝑘 | 𝑝 ) 𝑝+1 𝑝 ⎞ ⎟ ⎟ ⎠ = 0, т.е. функция 𝑔 𝑥 (𝑝) -невозрастающая функция на [1, +∞).
Во-первых, для всех 𝑥, 𝑦 ∈ R в силу ( 2)

𝑓 (𝑦) -𝑓 (𝑥) = 1 ∫ 0 ⟨∇𝑓 (𝑥 + 𝜏 (𝑦 -𝑥)), 𝑦 -𝑥⟩𝑑𝜏 = = ⟨∇𝑓 (𝑥), 𝑦 -𝑥⟩ + 1 ∫ 0 ⟨∇𝑓 (𝑥 + 𝜏 (𝑦 -𝑥)) -∇𝑓 (𝑥), 𝑦 -𝑥⟩𝑑𝜏 ⟨∇𝑓 (𝑥), 𝑦 -𝑥⟩ + 1 ∫ 0 ||∇𝑓 (𝑥 + 𝜏 (𝑦 -𝑥)) -∇𝑓 (𝑥)|| 2 • ||𝑦 -𝑥|| 2 𝑑𝜏 ⟨∇𝑓 (𝑥), 𝑦 -𝑥⟩ + 1 ∫ 0 𝜏 𝐿||𝑦 -𝑥|| 2 • ||𝑦 -𝑥|| 2 𝑑𝜏 = = ⟨∇𝑓 (𝑥), 𝑦 -𝑥⟩ + 𝐿 2 ||𝑦 -𝑥|| 2 2 , т.е. -⟨∇𝑓 (𝑥), 𝑦 -𝑥⟩ - 𝐿 2 ||𝑦 -𝑥|| 2 2 𝑓 (𝑥) -𝑓 (𝑦). Беря в последнем неравенстве 𝑥 = 𝑥 𝑘+1 , 𝑦 = Grad 𝑒 𝑘+1 (𝑥 𝑘+1 ) = 𝑥 𝑘+1 - 1 𝐿 ⟨ ̃ ∇𝑓 (𝑥 𝑘+1 ), 𝑒 𝑘+1 ⟩ 𝑒 𝑘+1 , получим, что 𝑓 (𝑥 𝑘+1 ) -𝑓 (𝑦 𝑘+1 ) 1 𝐿 ⟨ ̃ ∇𝑓 (𝑥 𝑘+1 ), 𝑒 𝑘+1 ⟩ • ⟨∇𝑓 (𝑥 𝑘+1 ), 𝑒 𝑘+1 ⟩- -1 2𝐿 ⟨ ̃ ∇𝑓 (𝑥 𝑘+1 ), 𝑒 𝑘+1 ⟩ 2 • ||𝑒 𝑘+1 || 2 2 = = 1 𝐿 ⟨∇𝑓 (𝑥 𝑘+1 ), 𝑒 𝑘+1 ⟩ 2 + 1 𝐿 ⟨∇𝑓 (𝑥 𝑘+1 ), 𝑒 𝑘+1 ⟩𝛿 ∇ (𝑥 𝑘+1 , 𝑒 𝑘+1 )- -1 2𝐿 ⟨∇𝑓 (𝑥 𝑘+1 ), 𝑒 𝑘+1 ⟩ 2 -1 𝐿 ⟨∇𝑓 (𝑥 𝑘+1 ), 𝑒 𝑘+1 ⟩𝛿 ∇ (𝑥 𝑘+1 , 𝑒 𝑘+1 )- -1 2𝐿 𝛿 2 ∇ (𝑥 𝑘+1 , 𝑒 𝑘+1 ) = 1 2𝐿 ⟨∇𝑓 (𝑥 𝑘+1 ), 𝑒 𝑘+1 ⟩ 2 -1 2𝐿 𝛿 2 ∇ (𝑥 𝑘+1 , 𝑒 𝑘+1 ), откуда получаем неравенство ⟨∇𝑓 (𝑥 𝑘+1 ), 𝑒 𝑘+1 ⟩ 2 2𝐿(𝑓 (𝑥 𝑘+1 ) -𝑓 (𝑦 𝑘+1 )) + 𝛿 2 ∇ (𝑥 𝑘+1 , 𝑒 𝑘+1 ) 2𝐿(𝑓 (𝑥 𝑘+1 ) -𝑓 (𝑦 𝑘+1 )) + δ2 , так как ∀𝑥, 𝑒 ∈ R 𝑛 ˓→ |𝛿 ∇ (𝑥, 𝑒)| δ. Возьмем от этого неравенства условное математическое ожидание E 𝑒 𝑘+1 [ • ]
, используя лемму B.10 из [START_REF] Bogolubsky | Learning Supervised PageRank with Gradient-Based and Gradient-Free Optimization Methods[END_REF], и получим (П.7).

Наконец, из (П.6) и (П.7) получим, что

𝛼 𝑘+1 ⟨∇𝑓 (𝑥 𝑘+1 ), 𝑧 𝑘 -𝑢⟩ 2𝛼 2 𝑘+1 𝐿𝐶 𝑛,𝑞 (𝑓 (𝑥 𝑘+1 ) -E 𝑒 𝑘+1 [𝑓 (𝑦 𝑘+1 )]) + 𝑉 𝑧 𝑘 (𝑢) -E 𝑒 𝑘+1 [𝑉 𝑧 𝑘+1 (𝑢)]+ + 7 4 𝛼 2 𝑘+1 𝐶 𝑛,𝑞 δ2 + √ 𝑛 δ𝛼 𝑘+1 ||𝑢 -𝑧 𝑘 || 𝑝 .
Лемма 1 доказана.

Д о к а з а т е л ь с т в о л е м м ы 2. Запишем цепочку неравенств:

𝛼 𝑘+1 (𝑓 (𝑥 𝑘+1 ) -𝑓 (𝑢)) 𝛼 𝑘+1 ⟨∇𝑓 (𝑥 𝑘+1 ), 𝑥 𝑘+1 -𝑢⟩ = = 𝛼 𝑘+1 ⟨∇𝑓 (𝑥 𝑘+1 ), 𝑥 𝑘+1 -𝑧 𝑘 ⟩ + 𝛼 𝑘+1 ⟨∇𝑓 (𝑥 𝑘+1 ), 𝑧 𝑘 -𝑢⟩ x = x = (1-𝜏 𝑘 )𝛼 𝑘+1 𝜏 𝑘 ⟨∇𝑓 (𝑥 𝑘+1 ), 𝑦 𝑘 -𝑥 𝑘+1 ⟩ + 𝛼 𝑘+1 ⟨∇𝑓 (𝑥 𝑘+1 ), 𝑧 𝑘 -𝑢⟩ y y (1-𝜏 𝑘 )𝛼 𝑘+1 𝜏 𝑘 (𝑓 (𝑦 𝑘 ) -𝑓 (𝑥 𝑘+1 )) + 𝛼 𝑘+1 ⟨∇𝑓 (𝑥 𝑘+1 ), 𝑧 𝑘 -𝑢⟩ z z (1-𝜏 𝑘 )𝛼 𝑘+1 𝜏 𝑘 (𝑓 (𝑦 𝑘 ) -𝑓 (𝑥 𝑘+1 ))+ +2𝛼 2 𝑘+1 𝐿𝐶 𝑛,𝑞 • (𝑓 (𝑥 𝑘+1 ) -E 𝑒 𝑘+1 [𝑓 (𝑦 𝑘+1 ) | 𝑒 1 , 𝑒 2 , . . . , 𝑒 𝑘 ])+ +𝑉 𝑧 𝑘 (𝑢) -E 𝑒 𝑘+1 [𝑉 𝑧 𝑘+1 (𝑢) | 𝑒 1 , 𝑒 2 , . . . , 𝑒 𝑘 ]+ + 7 4 𝛼 2 𝑘+1 𝐶 𝑛,𝑞 δ2 + √ 𝑛 δ𝛼 𝑘+1 ||𝑢 -𝑧 𝑘 || 𝑝 { = { = (2𝛼 2 𝑘+1 𝐿𝐶 𝑛,𝑞 -𝛼 𝑘+1 )𝑓 (𝑦 𝑘 ) -2𝛼 2 𝑘+1 𝐿𝐶 𝑛,𝑞 E 𝑒 𝑘+1 [𝑓 (𝑦 𝑘+1 ) | 𝑒 1 , 𝑒 2 , . . . , 𝑒 𝑘 ]+ +𝛼 𝑘+1 𝑓 (𝑥 𝑘+1 ) + 𝑉 𝑧 𝑘 (𝑢) -E 𝑒 𝑘+1 [𝑉 𝑧 𝑘+1 (𝑢) | 𝑒 1 , 𝑒 2 , . . . , 𝑒 𝑘 ]+ + 7 4 𝛼 2 𝑘+1 𝐶 𝑛,𝑞 δ2 + √ 𝑛 δ𝛼 𝑘+1 ||𝑢 -𝑧 𝑘 || 𝑝 . Действительно, x выполнено, так как 𝑥 𝑘+1 def = 𝜏 𝑘 𝑧 𝑘 + (1 -𝜏 𝑘 )𝑦 𝑘 ⇔ 𝜏 𝑘 (𝑥 𝑘+1 -𝑧 𝑘 ) = (1 - 𝜏 𝑘 )(𝑦 𝑘 -𝑥 𝑘+1 ), y следует из выпуклости 𝑓 (•) и неравенства 1 -𝜏 𝑘 0, z справедливо в силу леммы 1 и в { используется равенство 𝜏 𝑘 = 1 2𝛼
𝑘+1 𝐿𝐶𝑛,𝑞 . Лемма 2 доказана. Д о к а з а т е л ь с т в о т е о р е м ы. Заметим, что в силу выбора 𝛼 𝑘 = 𝑘+1 4𝐿𝐶𝑛,𝑝 выполняется равенство

(П.8) 2𝛼 2 𝑘 𝐿𝐶 𝑛,𝑞 = 2𝛼 2 𝑘+1 𝐿𝐶 𝑛,𝑞 -𝛼 𝑘+1 + 1 8𝐿𝐶𝑛,𝑞 .
Действительно,

2𝛼 2 𝑘 𝐿𝐶 𝑛,𝑞 = (𝑘+1) 2 8𝐿𝐶𝑛,𝑞 , 2𝛼 2 𝑘+1 𝐿𝐶 𝑛,𝑞 -𝛼 𝑘+1 + 1 8𝐿𝐶𝑛,𝑞 = (𝑘+2) 2 8𝐿𝐶𝑛,𝑞 -𝑘+2 4𝐿𝐶𝑛,𝑞 + 1 8𝐿𝐶𝑛,𝑞 = = (𝑘+1) 2 +2(𝑘+1)+1-2(𝑘+2)+1 8𝐿𝐶𝑛,𝑞 = (𝑘+1) 2 8𝐿𝐶𝑛,𝑞 = 2𝛼
0 (𝑁 +1) 2 8𝐿𝐶𝑛,𝑞 (E[𝑓 (𝑦 𝑁 )] -𝑓 (𝑥 * )) Θ -E[𝑉 𝑧 𝑁 (𝑥 * )] + 7 4 𝐶 𝑛,𝑞 δ2 𝑁 -1 ∑ 𝑘=0 𝛼 2 𝑘+1 + √ 𝑛 δ 𝑁 -1 ∑ 𝑘=0 𝛼 𝑘+1 E[𝑅 𝑘 ],
откуда следует еще одно полезное неравенство:

(П.12) E[𝑉 𝑧 𝑁 (𝑥 * )] Θ + 7 4 𝐶 𝑛,𝑞 δ2 𝑁 -1 ∑ 𝑘=0 𝛼 2 𝑘+1 + √ 𝑛 δ 𝑁 -1 ∑ 𝑘=0 𝛼 𝑘+1 E[𝑅 𝑘 ].
Докажем индукцией по 𝑁 неравенство (П.13)

Θ + 7 4 𝐶 𝑛,𝑞 δ2 𝑁 -1 ∑ 𝑘=0 𝛼 2 𝑘+1 + √ 𝑛 δ 𝑁 -1 ∑ 𝑘=0 𝛼 𝑘+1 E[𝑅 𝑘 ] (√ Θ + 7 4 𝐶 𝑛,𝑞 δ2 𝑁 -1 ∑ 𝑘=0 𝛼 2 𝑘+1 + √ 2Θ𝑛 δ 2𝐿𝐶𝑛,𝑞 + √ 2𝑛 𝑁 2 δ 4𝐿𝐶𝑛,𝑞 ) 2 .
Для 𝑁 = 1 неравенство (П.13) выполнено, так как

Θ + 7 4 𝐶 𝑛,𝑞 δ2 𝛼 2 1 + √ 𝑛 δ𝛼 1 E[𝑅 0 ] ⏟ ⏞ 𝑅 0 x x Θ + 7 4 𝐶 𝑛,𝑞 δ2 𝛼 2 1 + √ 2Θ𝑛 δ 2𝐿𝐶𝑛,𝑞 (√ Θ + 7 4 𝐶 𝑛,𝑞 δ2 𝛼 2 1 + √ 2Θ𝑛 δ 2𝐿𝐶𝑛,𝑞 + √ 2𝑛 δ 4𝐿𝐶𝑛,𝑞 ) 2 , где x следует из неравенства 𝑅 0 √ 2𝑉 𝑧 0 (𝑥 * ) = √ 2Θ (𝑉 𝑥 (𝑦) 1 2 ||𝑥 -𝑦|| 2 𝑝 в силу сильной выпуклости прокс-функции 𝑑(𝑥)) и равенства 𝛼 1 def = 2 4𝐿𝐶𝑛,𝑞 = 1
2𝐿𝐶𝑛,𝑞 . Таким образом, база индукции доказана. Докажем теперь шаг индукции: предположим, что (П.13) выполнено для некоторого натурального 𝑁 и докажем, что тогда оно выполнено и для 𝑁 + 1. Во-первых, из предположения индукции и (П.12) следует, что

1 2 (E[𝑅 𝑁 ]) 2 1 2 E[𝑅 2 𝑁 ] E[𝑉 𝑧 𝑁 (𝑥 * )] (П.12) (П.12) Θ + 7 4 𝐶 𝑛,𝑞 δ2 𝑁 -1 ∑ 𝑘=0 𝛼 2 𝑘+1 + √ 𝑛 δ 𝑁 -1 ∑ 𝑘=0 𝛼 𝑘+1 E[𝑅 𝑘 ] (П.13) (П.13) (√ Θ + 7 4 𝐶 𝑛,𝑞 δ2 𝑁 -1 ∑ 𝑘=0 𝛼 2 𝑘+1 + √ 2Θ𝑛 δ 2𝐿𝐶𝑛,𝑞 + √ 2𝑛 𝑁 2 δ 4𝐿𝐶𝑛,𝑞 ) 2 , откуда следует, что (П.14) E[𝑅 𝑁 ] √ 2 ⎛ ⎝ ⎯ ⎸ ⎸ ⎷ Θ + 7 4 𝐶 𝑛,𝑞 δ2 𝑁 -1 ∑ 𝑘=0 𝛼 2 𝑘+1 + √ 2Θ𝑛 δ 2𝐿𝐶 𝑛,𝑞 + √ 2𝑛 𝑁 2 δ 4𝐿𝐶 𝑛,𝑞 ⎞ ⎠ . Тогда получаем оценку Θ + 7 4 𝐶 𝑛,𝑞 δ2 𝑁 ∑ 𝑘=0 𝛼 2 𝑘+1 + √ 𝑛 δ 𝑁 ∑ 𝑘=0 𝛼 𝑘+1 E[𝑅 𝑘 ] (√ Θ + 7 4 𝐶 𝑛,𝑞 δ2 𝑁 -1 ∑ 𝑘=0 𝛼 2 𝑘+1 + √ 2Θ𝑛 δ 2𝐿𝐶𝑛,𝑞 + √ 2𝑛 𝑁 2 δ 4𝐿𝐶𝑛,𝑞 ) 2 + + 7 4 𝐶 𝑛,𝑞 δ𝛼 2 𝑁 +1 + √ 𝑛 δ𝛼 𝑁 +1 E[𝑅 𝑁 ] (П.14) (П.14) Θ + 7 4 𝐶 𝑛,𝑞 δ2 𝑁 ∑ 𝑘=0 𝛼 2 𝑘+1 + √ 2Θ𝑛 δ 2𝐿𝐶𝑛,𝑞 + +2 √ 2𝑛 𝑁 2 δ 4𝐿𝐶𝑛,𝑞 √ Θ + 7 4 𝐶 𝑛,𝑞 δ2 𝑁 -1 ∑ 𝑘=0 𝛼 2 𝑘+1 + √ 2Θ𝑛 δ 2𝐿𝐶𝑛,𝑞 + ( √ 2𝑛 𝑁 2 δ 4𝐿𝐶𝑛,𝑞 ) 2 + + √ 2𝑛 δ𝛼 𝑁 +1 (√ Θ + 7 4 𝐶 𝑛,𝑞 δ2 𝑁 -1 ∑ 𝑘=0 𝛼 2 𝑘+1 + √ 2Θ𝑛 δ 2𝐿𝐶𝑛,𝑞 + √ 2𝑛 𝑁 2 δ 4𝐿𝐶𝑛,𝑞 ) x x Θ + 7 4 𝐶 𝑛,𝑞 δ2 𝑁 ∑ 𝑘=0 𝛼 2 𝑘+1 + √ 2Θ𝑛 δ 2𝐿𝐶𝑛,𝑞 + +2 √ 2𝑛 (𝑁 +1) 2 δ 4𝐿𝐶𝑛,𝑞 √ Θ + 7 4 𝐶 𝑛,𝑞 δ2 𝑁 ∑ 𝑘=0 𝛼 2 𝑘+1 + √ 2Θ𝑛 δ 2𝐿𝐶𝑛,𝑞 + ( √ 2𝑛 (𝑁 +1) 2 δ 4𝐿𝐶𝑛,𝑞 ) 2 = = (√ Θ + 7 4 𝐶 𝑛,𝑞 δ2 𝑁 ∑ 𝑘=0 𝛼 2 𝑘+1 + √ 2Θ𝑛 δ 2𝐿𝐶𝑛,𝑞 + √ 2𝑛 (𝑁 +1) 2 δ 4𝐿𝐶𝑛,𝑞 ) 2 , где x следует из неравенств 2𝑁 2 4𝐿𝐶𝑛,𝑞 + 𝛼 𝑁 +1 = 2𝑁 2 4𝐿𝐶𝑛,𝑞 + 𝑁 +2 4𝐿𝐶𝑛,𝑞 2(𝑁 +1) 2 4𝐿𝐶𝑛,𝑞 , ( √ 2𝑛 𝑁 2 δ 4𝐿𝐶𝑛,𝑞 ) 2 + √ 2𝑛 δ𝛼 𝑁 +1 • √ 2𝑛 𝑁 2 δ 4𝐿𝐶𝑛,𝑞 = = ( √ 2𝑛 δ 4𝐿𝐶𝑛,𝑞 ) 2 (𝑁 4 + (𝑁 + 2)𝑁 2 ) ( √ 2𝑛 (𝑁 +1) 2 δ 4𝐿𝐶𝑛,𝑞 ) 2 , √ Θ + 7 4 𝐶 𝑛,𝑞 δ2 𝑁 -1 ∑ 𝑘=0 𝛼 2 𝑘+1 + √ 2Θ𝑛 δ 2𝐿𝐶𝑛,𝑞 √ Θ + 7 4 𝐶 𝑛,𝑞 δ2 𝑁 ∑ 𝑘=0 𝛼 2 𝑘+1 + √ 2Θ𝑛 δ 2𝐿𝐶𝑛,𝑞 .
Итак, неравенство (П.13) доказано.

Из (П.11), (П.13) и 𝑉 𝑧 𝑁 (𝑥 * ) 0 получаем неравенство (П.15)

0 (𝑁 +1) 2 8𝐿𝐶𝑛,𝑞 (E[𝑓 (𝑦 𝑁 )] -𝑓 (𝑥 * )) (√ Θ + 7 4 𝐶 𝑛,𝑞 δ2 𝑁 -1 ∑ 𝑘=0 𝛼 2 𝑘+1 + √ 2Θ𝑛 δ 2𝐿𝐶𝑛,𝑞 + √ 2𝑛 𝑁 2 δ 4𝐿𝐶𝑛,𝑞 ) 2 x x 2Θ + 7 2 𝐶 𝑛,𝑞 δ2

1

  Ключевые слова: ускоренные методы оптимизации, выпуклая оптимизация, безградиентные методы, неточный оракул, неевклидов проксимальный оператор, прокс-Исследование в разделе 3 выполнено за счет Российского научного фонда (проект № 17-11-01027). В остальных разделах работа А.В. Гасникова финансировалась в рамках Государственной поддержки ведущих университетов Российской Федерации "5-100" и была поддержана Российским фондом фундаментальных исследований (проект № 18-31-20005 мол-а-вед), работа Э.А. Горбунова была поддержана грантом Президента РФ МД-1320.2018.1, работа П.Е. Двуреченского и Е.А. Воронцовой была поддержана Российским фондом фундаментальных исследований (проект № 18-29-03071 мк).

9 :

 9 return 𝑦 𝑁 Схема доказательства оценки скорости сходимости ACDF близка к схеме доказательства теоремы в [13] и опирается на две следующие леммы, в которых δ определена в (3).

  Пусть про шум известно, что ∀ 𝑥 ∈ R 𝑛 ˓→ |𝛿(𝑥)| 𝛿. Оценим |𝛿 ∇ (𝑥, 𝑒, 𝑡)|:

	2 Здесь и далее термин "ускоренный" для безградиентных методов означает точно то же самое, что и для методов первого порядка (градиентных), см., в частности, описание основополагающего и очень популярного в последние годы ускоренного (быстрого, моментного) градиентного метода два условия: 1) нет возможности считать градиент, есть только возможность счи-тать зашумленное значение целевой функции (см., например, [12]); 2) при выборе параметрической модели часто сложно сразу правильно угадать параметрическое представление и часть параметров оказываются малозначимыми (лишними), что и обеспечивает разреженность. Кроме того, тот же эффект наблюдается, если выбирать точку старта так, чтобы разность между точкой старта и решением была разреженным вектором. Наконец, даже если вдруг это не выполняется, полученные прокс-структурой будет работать не хуже, чем в евклидовом случае. В [13] для решения задачи (1) вместо обычного градиента использовалась его стохастическая аппроксимация, построенная на базе производной по случайно выбранному направлению [15] где 𝑒 -случайный вектор, равномерно распределенный на 𝑆 𝑛 2 (1) -единичной сфере в 2-норме в пространстве R 𝑛 (𝑒 ∈ 𝑅𝑆 𝑛 2 (1) -под этой записью будем понимать, что случайный вектор 𝑒 имеет равномерное распределение на 𝑛-мерной единичной евклидовой сфере с центром в нуле), а угловые скобки ⟨•, •⟩ обозначают стандартное скалярное произведение векторов). В отличие от [13], будем использовать не ⟨∇𝑓 (𝑥), 𝑒⟩ 𝑒, а приближенный аналог 𝑓 (𝑥 + 𝑡𝑒) -𝑓 (𝑥) 𝑡 𝑒, 𝑡 > 0. точке, но с некоторым шумом 𝛿(𝑥), т.е. от оракула получаем значения f (𝑥) = 𝑓 (𝑥) + 𝛿(𝑥), поэтому на практике будем вынуждены использовать f (𝑥 + 𝑡𝑒) -f (𝑥) 𝑡 𝑒 вместо ⟨∇𝑓 (𝑥), 𝑒⟩ 𝑒. Итак в силу сделанных предположений теперь работаем не с истинной производ-ной по направлению, а с ее приближенным аналогом 4 ⟨ ̃ ∇ 𝛿, 𝑡 𝑓 (𝑥), 𝑒⟩ 𝑒 def = (⟨∇𝑓 (𝑥), 𝑒⟩ + 𝛿 ∇ (𝑥, 𝑡, 𝑒)) 𝑒, где 𝛿 ∇ (𝑥, 𝑡, 𝑒) -ошибка приближения значения ⟨∇𝑓 (𝑥), 𝑒⟩, связанная с вычисли-тельной ошибкой (значения функции известны с некоторым шумом) и с аппрокси-мационной ошибкой метода приближения, т.е. 𝛿 ∇ (𝑥, 𝑡, 𝑒) = 𝛿(𝑥 + 𝑡𝑒) -𝛿(𝑥) 𝑡 ⏟ ⏞ вычислительная ошибка + 𝑓 (𝑥 + 𝑡𝑒) -𝑓 (𝑥) 𝑡 -⟨∇𝑓 (𝑥), 𝑒⟩ ⏟ ⏞ ошибка метода . 3 Здесь и далее под оракулом понимается подпрограмма расчета значений целевой функции и/или градиента (его части), а оптимальность метода на классе задач понимается в смысле Бахвалова-Немировского [16] --как число обращений (по ходу работы метода) к оракулу для достижения заданной точности (по функции). 4 Строго говоря, вектор ̃ ∇ 𝛿, 𝑡 𝑓 (𝑥) определяется из приведенного выражения не единственным образом, однако данное обозначение крайне удобно использовать для записи метода и доказа-тельств. Кроме того, нигде в работе авторы не пользуются конкретным выбором ̃ ∇ 𝛿, 𝑡 𝑓 (𝑥), везде Ограничимся рассмотрением следующей концепции абсолютной неточности ора-кула. |𝛿 ∇ (𝑥, 𝑒, 𝑡)| |𝛿(𝑥+𝑡𝑒)|+|𝛿(𝑥)| 𝑡 + ⃒ ⃒ ⃒ 𝑓 (𝑥+𝑡𝑒)-𝑓 (𝑥) 𝑡 -⟨∇𝑓 (𝑥), 𝑒⟩ ⃒ ⃒ ⃒ 2𝛿 𝑡 + 𝐿𝑡 2 , где последнее слагаемое в правой части возникает в силу неравенства 𝑓 (𝑥 + 𝑡𝑒) -𝑓 (𝑥) -⟨∇𝑓 (𝑥), 𝑥 + 𝑡𝑒 -𝑥⟩ 𝐿 2 ||𝑥 + 𝑡𝑒 -𝑥|| 2 2 , которое следует из (2). Выберем параметр 𝑡 = 𝑡 * так, чтобы минимизировать Нестерова [10]. Ускоренный метод имеет скорость сходимости, пропорциональную 1/𝑘 того, во многих задачах обучения с подкреплением одновременно выполняются результаты свидетельствуют о том, что предложенный в статье метод с неевклидовой Более того, предположим, что оракул 3 может выдавать значение функции в любой значение верхней оценки на 𝛿 ∇ (𝑥, 𝑒, 𝑡). Параметр 𝑡 * находится из условия
	существенную роль играет выражение ⟨ ̃ ∇ 𝛿, 𝑡 𝑓 (𝑥), 𝑒⟩𝑒, которое определяется однозначно.
	𝑔 (𝑥, 𝑒) = 𝑛 ⟨∇𝑓 (𝑥) , 𝑒⟩ 𝑒,

2

, где 𝑘номер итерации. В отличие от него неускоренный метод имеет скорость сходимости по значению целевой функции, пропорциональную 1/𝑘. В [13] был предложен ускоренный спуск (опирающийся на метод из

[START_REF] Allen-Zhu | Linear Сoupling: An Ultimate Unification of Gradient and Mirror Descent[END_REF]

) по случайному направлению и получена оценка скорости сходимости. В [13] метод использовал проекцию градиента на случайное направление. В данной статье используется не сама проекция градиента на случайное направление, а ее аппроксимация конечной разностью, т.е. приближение, которое не использует градиент. Кроме того, рассматривается случай, когда значения функции известны с некоторым ограниченным по абсолютной величине шумом.

2. Постановка задачи

Рассматривается разрешимая задача гладкой выпуклой оптимизации

(1) 𝑓 (𝑥) → min 𝑥∈R 𝑛 , где функция 𝑓 (𝑥), заданная на R 𝑛 , имеет липшицев градиент с константой 𝐿 в 2норме (2) ‖∇𝑓 (𝑦) -∇𝑓 (𝑥)‖ 2 𝐿 ‖𝑦 -𝑥‖ 2 ∀ 𝑥, 𝑦 ∈ R 𝑛 .

При этом в точке минимума 𝑥 * выполнено равенство ∇𝑓 (𝑥 * ) = 0.

  Опишем ускоренный безградиентный метод (Accelerated by Coupling Derivative-Free Method -ACDF) (см. алгоритм 1). Обращение к оракулу целевой функции происходит на шагах вычисления значений Grad 𝑒 𝑘+1 (𝑥 𝑘+1 ) и Mirr 𝑒 𝑘+1 (𝑥 𝑘+1 , 𝑧 𝑘 , 𝛼 𝑘+1 ).

32 ln 𝑛 -8}𝑛 2 𝑞 +1 . Алгоритм 1. 1 ACDF Вход: оракул, выдающий значение функции 𝑓 (выпуклой дифференцируемой функции на R 𝑛 с липшицевым градиентом с константой 𝐿 по отношению к 2-норме) в любой точке 𝑥 с некоторым шумом 𝛿(𝑥); 𝑥 0 -некоторая стартовая точка; 𝑁количество итераций.

  = (1, 0, 0, . . . , 0) ⊤ . Решение этой задачи известно и равно 𝑥 * , 𝑓 (𝑥 * ) = 0. Начальная точка 𝑥 0 для всех экспериментов выбиралась как 𝛿 ′ , где 𝛿 ′ ∈ [-𝛿, 𝛿]. Для различных 𝑛, заданной точности 𝜀 и заданной границы максимального шума 𝛿 были рассчитаны теоретически требуемые значения числа итераций по теореме и проведена проверка сходимости на практике. Для данной задачи во всех случаях практическая скорость сходимости по функции была выше. Так,

	Необходимо минимизировать функцию 6. Заключение
	(10) В статье предложен ускоренный безградиентный метод и рассмотрен неускорен-𝑓 (𝑥) = 1 2 ный безградиентный метод. Безградиентные методы рассматриваются в условиях наличия малого шума, возникающего при вычислении значения функции. Получен-ные оценки скорости сходимости ускоренного безградиентного метода в условиях ⟨𝑥 -𝑥 Константа Липшица градиента целевой функции 𝐿 = 1. малого шума подтверждены результатами вычислительных экспериментов.
	В отличие от известных вариантов безградиентных методов (см., например,
	[9]) в данной статье рассматриваются безградиентные методы с неевклидовым
	проксимальным оператором. В случае, когда 1-норма решения близка к 2-норме
	решения (это имеет место, например, если решение задачи разрежено -имеет много
	нулевых компонент), предлагаемый подход улучшает оценку на необходимое число
	итераций, полученную оптимальным методом из [9], приблизительно в	√ 𝑛 раз, где
	𝑛 -размерность пространства, в котором происходит оптимизация.
	ренный безградиентный метод с неевклидовой прокс-структурой работает быстрее
	ускоренного безградиентного метода с евклидовой прокс-структурой. Сравнение
	этого эксперимента для ускоренного безградиентного метода (с неточным оракулом)
	по (8). Код метода и демонстрация вычислительных свойств метода с построением с таким же, но для ускоренного спуска по случайному направлению (с точным
	графиков сходимости доступны как Jupyter Notebook и выложены в свободном оракулом) из [13] (см. рис. 2, б ), показывает, что принципиальный результат тот
	доступе на Github [19]. же, но скорость сходимости оказывается хуже, что вполне естественно для метода
	нулевого порядка с неточным оракулом.
	Рассмотрим следующую з а д а ч у. Пусть 𝐴 -матрица размеров 𝑛 × 𝑛 со
	случайными независимыми элементами, равномерно распределенными на [0, 1], а В целом, численные эксперименты с ускоренным безградиентным методом под-
	матрица 𝐵 = тверждают теоретические результаты.

Для практического применения предложенный ускоренный безградиентный метод ACDF был реализован на языке программирования Python. Также была реализована концепция неточно заданного оракула. Был рассмотрен случай, когда неточность порождается только неточностью вычисления целевой функции. Зашумления производились на каждой итерации, независимо от предыдущих, случайным образом из отрезка [-𝛿, 𝛿], где максимально возможная для шума граница 𝛿 вычислялась 𝐴 ⊤ 𝐴 𝜆max(𝐴 ⊤ 𝐴) , где 𝜆 max (𝐴 ⊤ 𝐴) -максимальное собственное значение матрицы 𝐴 ⊤ 𝐴. * , 𝐵(𝑥 -𝑥 * )⟩ , 𝑥 ∈ R 𝑛 , где 𝑥 * например, для 𝑛 = 10, 𝜀 = 10 -4 , 𝛿 = 2, 1715 • 10 -10 заданная точность была достигнута за 1106 итераций (см. рис. 1), а теоретическая оценка числа итераций Рис. 1 дает 17215 итераций. Далее, для 𝑛 = 10 3 , 𝜀 = 10 -4 теоретическая оценка числа итераций дает не более чем 527756 итераций. По факту алгоритм завершил работу за 141476 итераций (см. рис. 2). Рис. 2 При проведении численных экспериментов также были подтверждены результаты зкспериментов в [13]: и для ускоренного безградиентного метода преимущество выбора проксимального оператора, связанного с 1-нормой, возникает только для задач средней и большой размерности (от 𝑛 = 1000). Будет ли иметь преимущество предложенный метод, можно определить, сравнив теоретические оценки числа итераций из теоремы для разных 𝑝. На рис. 2 показаны случаи, когда уско-

  1 2 ||𝑧 𝑘 -𝑧 𝑘+1 || 2 𝑛 , y выполнено в силу равенства треугольника для дивергенции Брэгмана 6 , z выполнено, так как 𝑉 𝑥 (𝑦)

	𝑝 𝑝 в силу сильной выпуклости прокс-) + 2 ||𝑥 -𝑦|| 2 Аналогично доказательству (П.3) из [13] можно показать, что функции 𝑑(𝑥). +𝑉 𝑧 1 (П.2)

𝑘 (𝑢) -𝑉 𝑧 𝑘+1 (𝑢), где x выполнено в силу того, что 𝑧 𝑘+1 = argmin 𝑧∈R 𝑛 { 𝑉 𝑧 𝑘 (𝑧) + 𝛼 𝑘+1 ⟨𝑛⟨ ̃ ∇𝑓 (𝑥 𝑘+1 ), 𝑒 𝑘+1 ⟩ 𝑒 𝑘+1 , 𝑧⟩ } , откуда следует, что ⟨∇𝑉 𝑧 𝑘 (𝑧 𝑘+1 ) + 𝛼 𝑘+1 𝑛⟨ ̃ ∇𝑓 (𝑥 𝑘+1 ), 𝑒 𝑘+1 ⟩ 𝑒 𝑘+1 , 𝑢 -𝑧 𝑘+1 ⟩ 0 для всех 𝑢 ∈ R

  y выполнено в силу леммы B.10 из[START_REF] Bogolubsky | Learning Supervised PageRank with Gradient-Based and Gradient-Free Optimization Methods[END_REF], z получено при помощи следующего факта:∀ 𝑥 ∈ R 𝑛 ∀ 1 𝑝 𝑞 ∞ ˓→ ||𝑥|| 𝑝 ||𝑥|| 𝑞(данное неравенство доказывается, например, при помощи рассмотрения 𝑝-нормы для фиксированного 𝑥 как функции, зависящей от 𝑝, а точнее логарифма 𝑝-нормы 7 ).

	Беря от (П.4) математическое ожидание по 𝑒 𝑘+1 и пользуясь неравенствами (П.5),
	получим, что
	(П.6)

  2 𝑘 𝐿𝐶 𝑛,𝑞 . для любого 𝑢 ∈ R 𝑛 , здесь также δ определена в (3). Положим 𝑢 = 𝑥 * . Так как ∑ 𝑁 𝑘=1 𝛼 𝑘 = 𝑁 (𝑁 +3) 8𝐿𝐶𝑛,𝑞 , E[𝑓 (𝑦 𝑘 )] 𝑓 (𝑥 * ) и 𝑉 𝑧 0 (𝑥 * ) = 𝑉 𝑥 0 (𝑥 * ) = Θ, то из (П.9) следует, что

			(𝑁 +1) 2 8𝐿𝐶𝑛,𝑞 E[𝑓 (𝑦 𝑁 )] -	(	𝑁 (𝑁 +3) 8𝐿𝐶𝑛,𝑞 -𝑁 -1 8𝐿𝐶𝑛,𝑞	)	𝑓 (𝑥 * )
	(П.10)	Θ -E[𝑉 𝑧 𝑁 (𝑥 * )] + 7 4 𝐶 𝑛,𝑞	δ2	𝑘=0 𝑁 -1 ∑		𝛼 2 𝑘+1 +	√	𝑛	𝑘=0 δ 𝑁 -1 ∑	𝛼 𝑘+1 E[𝑅 𝑘 ],
	где 𝑅 𝑘	def = ||𝑥 * -𝑧 𝑘 || 𝑝 . После простых преобразований неравенство (П.10) запишется в
	виде
	(П.11)
	Возьмем для 𝑘 = 0, 1, . . . , 𝑁 -1 математическое ожидание по 𝑒 1 , 𝑒 2 , . . . , 𝑒 𝑁 от
	неравенств (6) и сложим получившиеся неравенства, учитывая (П.8):
	(П.9)	-7 4 𝐶 𝑛,𝑞	2𝛼 2 𝑁 𝐿𝐶 𝑛,𝑞 E[𝑓 (𝑦 𝑁 )] + 𝑘=0 δ2 𝑁 -1 ∑ 𝛼 2 𝑘+1 -√ 𝑛 δ 𝑁 -1 ∑	𝑁 -1 ∑ 𝑘=1	E[𝑓 (𝑦 𝑘 )] 8𝐿𝐶𝑛,𝑞 + E[𝑉 𝑧 𝑁 (𝑢)] -𝑉 𝑧 0 (𝑢)-𝑘=0 𝑁 -1 ∑ 𝛼 𝑘+1 𝑓 (𝑢)

𝑘=0 𝛼 𝑘+1 E[||𝑢 -𝑧 𝑘 || 𝑝 ]

  где x следует из неравенства (𝑎 + 𝑏) 22𝑎 2 + 2𝑏 2 ∀ 𝑎, 𝑏 ∈ R, y получается из неравенства Поделим неравенство (П.15) на (𝑁 +1) 2 8𝐿𝐶𝑛,𝑞 и получим окончательно, чтоE[𝑓 (𝑦 𝑁 )] -𝑓 (𝑥 * ) 16Θ𝐿𝐶𝑛,𝑞 (𝑁 +1) 2 + 7(𝑁 +2)(2𝑁 +3)𝛿 + 8𝑛𝑁4 𝛿 𝐶𝑛,𝑞(𝑁 +1) 2 . где под знаком || • || 𝑞 понимается векторная 𝑞-норма. Кроме того, приводим формулировку леммы B.10 из [18]. Отметим, что в доказательстве нигде не использовалось, что второй вектор в скалярном произведении (помимо 𝑒) есть градиент функции 𝑓 (𝑥) (поэтому утверждение леммы остается верным для произвольного вектора 𝑠 ∈ R 𝑛 вместо ∇𝑓 (𝑥)). Рис. 1. Сходимость метода ACDF для функции (10), размерность 𝑛 = 10. Показана практическая зависимость точности нахождения минимума 𝑓 (𝑦 𝑁 ) -𝑓 (𝑥 * ) от числа итераций N алгоритма -темный график и теоретическая оценка Сходимость метода ACDF для функции (10), размерность 𝑛 = 10 3 , точность 𝜀 = 10 -4 . Показана практическая зависимость точности нахождения минимума 𝑓 (𝑦 𝑁 ) -𝑓 (𝑥 * ) от числа итераций 𝑁 алгоритма (а), график 1). Также для сравнения на рис. 2, а приведены результаты работы метода при других 𝑝 (евклидова норма -график 2; 𝑝 = 1, 8 -график 3; 𝑝 = 1, 9 -график 4) при одних и тех же генерируемых 𝑒 𝑘 и точке старта 𝑥 0 . На рис. 2, б приведены результаты сравнения на той же задаче работы метода ACDF (пунктирная линия) и ускоренного неевклидового спуска ACDS [13] (сплошная линия, график 1), предназначенного для работы с точным оракулом первого порядка.

						Список подрисуночных подписей
	Рис. 2.	𝑂	(	16Θ𝐿𝐶𝑛,𝑞 𝑁 2	)	𝑁 -1 ∑ 𝑘=0 2Θ + 7 δ2 (𝑁 +1)(𝑁 +2)(2𝑁 +3) 𝛼 2 𝑘+1 + -светлый график. y 192𝐿 2 𝐶𝑛,𝑞 + z = 2Θ + 7(𝑁 +1)(𝑁 +2)(2𝑁 +3)𝛿 48𝐿𝐶𝑛,𝑞	√ 𝐿𝐶𝑛,𝑞 + 𝑛𝑁 4 δ2 2Θ𝑛 δ 4𝐿 2 𝐶 2 𝑛,𝑞 √ 2Θ𝑛 δ 𝐿𝐶𝑛,𝑞 + 𝑛𝑁 4 δ2 4𝐿 2 𝐶 2 𝑛,𝑞 + 2 2Θ𝑛𝛿 √ 𝐿𝐶 2 𝑛,𝑞 y z = , 𝐿𝐶𝑛,𝑞 + 𝑛𝑁 4 𝛿 √
								𝑁 -1 ∑ 𝑘=0	𝛼 2 𝑘+1 =	𝑁 -1 ∑ 𝑘=0	(𝑘+2) 2 16𝐿 2 𝐶 2 𝑛,𝑞	=	1 16𝐿 2 𝐶 2 𝑛,𝑞	𝑁 +1 𝑘=2 ∑	𝑘 2 =
					=	1 16𝐿 2 𝐶 2 𝑛,𝑞	•	(	(𝑁 +1)(𝑁 +2)(2𝑁 +3) 6	) -1	(𝑁 +1)(𝑁 +2)(2𝑁 +3) 96𝐿 2 𝐶 2 𝑛,𝑞
	6(𝑁 +1) (𝑁 +1) 2 Теорема доказана. √ 2Θ𝑛𝐿𝛿 + 16
	Приводим формулировку теоремы 1 из [17].
	(П.17)		E[⟨𝑠, 𝑒⟩ 2 ||𝑒|| 2 𝑞 ]			√ 3||𝑠|| 2 2 min{2𝑞 -1, 32 ln 𝑛 -8}𝑛
									||𝑠|| 2 2 𝑛	.

, а z верно в силу

[START_REF] Spall | Introduction to Stochastic Search and Optimization[END_REF]

.

Т е о р е м а П.1. Пусть 𝑒 ∈ 𝑅𝑆 𝑛 2 (1), 𝑛 8, 𝑠 ∈ R 𝑛 , тогда (П.16) E[||𝑒|| 2 𝑞 ] min{𝑞 -1, 16 ln 𝑛 -8}𝑛 2 𝑞 -1 , 2 𝑞 ∞, 2 𝑞 -2 , 2 𝑞 ∞, Л е м м а П.1. Пусть 𝑒 ∈ 𝑅𝑆 𝑛 2 (1) и вектор 𝑠 ∈ R 𝑛 -некоторый вектор. Тогда E 𝑒 [⟨𝑠, 𝑒⟩ 2 ] =

Также на рис. 2, б приведены результаты работы указанных методов при 𝑝 = 2

(график 2, штрихпунктирная линия -ACDF, сплошная линия -ACDS).

Рис. 1.

а б

Рис. 2.

Действительно, ∀𝑥, 𝑦 ∈ R 𝑛 ⟨-∇𝑉 𝑥 (𝑦), 𝑦 -𝑢⟩ = ⟨∇𝑑(𝑥) -∇𝑑(𝑦), 𝑦 -𝑢⟩ = (𝑑(𝑢) -𝑑(𝑥) -⟨∇𝑑(𝑥), 𝑢 -𝑥⟩)--(𝑑(𝑢) -𝑑(𝑦) -⟨∇𝑑(𝑦), 𝑢 -𝑦⟩) -(𝑑(𝑦) -𝑑(𝑥) -⟨∇𝑑(𝑥), 𝑦 -𝑥⟩) = 𝑉 𝑥 (𝑢) -𝑉 𝑦 (𝑢) -𝑉 𝑥 (𝑦).