NIPS'96 Postconference Workshop

[Marco Maggini]

=================================================================  
                         CALL FOR PAPERS
           
                NIPS'96 Postconference Workshop 
-----------------------------------------------------------------
              ANNs and Continuous Optimization:
Local Minima, Sub-optimal Solutions, and Computational Complexity
-----------------------------------------------------------------
        
              Snowmass (Aspen), Colorado USA
                   Fri Dec 6th, 1996

M. Gori                                  M. Protasi
Universita' di Siena                     Universita' Tor Vergata (Roma)
Universita' di Firenze                   protasi at utovrm.it
marco at mcculloch.ing.unifi.it
http://www-dsi.ing.unifi.it/neural

Most ANNs used for  either learning or problem solving (e.g. Backprop 
nets and analog  Hopfield nets) rely on continuous optimization.  The 
elegance  and  generality of  this  approach, however, seems  also to 
represent  the  main  source of  troubles  that typically arise  when 
approaching  complex problems. Most of the times this gives rise to a 
sort of  suspiciousness concerning  the  actual chance to discover an 
optimal solution under reasonable computational constraints. 
The computational complexity of  the problem at  hand seems to appear 
in  terms  of  local  minima  and  numerical problems  of  the chosen 
optimization algorithm. 

While  most practitioners use to  accept without reluctance the flavor 
of suspiciousness and  use to be proud of their  eventual experimental 
achievements, most theoreticians are instead quite skeptical. 
Obviously, the success of ANNs for either learning and problem solving 
is often related to the problem at hand and, therefore, one can expect 
an excellent behavior for a class of problems, while can raise serious 
suspects about the  solution of others. To the  best of our knowledge, 
however, so far,  this intuitive  idea has no satisfactory theoretical
explanation. Basically,  there is neither theory  to support naturally 
the  intuitive  concept of  suspiciousness,  nor theory to relate this 
concept to computational complexity.

The  study  of  the  complexity  of  algorithms  has  been essentially 
performed on discrete  structures  and an impressive  theory  has been 
developed  in  the  last  two  decades. On the other hand optimization 
theory  has  a  twofold face:  discrete  optimization  and  continuous 
optimization.  Actually  there  are some  important  approaches of the 
computational complexity theory that  were proposed for the continuous 
cases, for instance, the information based-complexity (Traub) and real 
Turing Machines (Blum-Shub-Smale).  These approaches can be fruitfully 
applied to problems arising in continuous optimization  but, generally 
speaking,  the  formal  study  of  the  efficiency  of  algorithms and 
problems has received much more attention in the discrete environment, 
where the theory can be easily used and error  and precision  problems 
are not present. 

===========================================
DISCUSSION POINTS FOR WORKSHOP PARTICIPANTS
===========================================
Taking  into  account  this  framework,  a  fascinating  area, that we 
believe deserves a careful study,  concerns  the  relationship between 
the emergence of  sub-optimal solutions in continuous optimization and 
the  corresponding  computational  complexity  of  the problem at hand. 
More specifically,there are a number of very intriguing open questions:  

 - Is there a relationship between the complexity of algorithms in 
   the continuous and discrete settings for solving the same problem? 

 - Can we deduce bounds on the complexity of discrete algorithms from 
   the study of the properties of continuous ones and vice-versa? 

 - Some loading problems are intuitively easily solvable, while others 
   are considered hard. Are there links between the presence  of local 
   minima and the computational complexity of the problem at hand?

 - What is the impact of approximate solutions on the complexity?
   (e.g. learning is inherently an approximate process whose complexity
   is often studied in the framework of theories like PAC)  

==========
OBJECTIVES
==========
The  aim  of  the workshop is  not to reach some definite points, but to 
stimulate  a  starting  discussion,  and to put on the table some of the 
most important themes that we hope could be extensively  explored in the 
future. 
We  also  expect that  the study of the interplay between continuous and 
discrete  versions  of  a  problem  can  be  very  fruitful for both the 
approaches. Since, until now,  this interplay has been rarely  explored, 
the workshop  is  likely  to stimulate  different  point of view; people 
working  on discrete optimization are in fact likely not to be expert on 
the continuous side and vice-versa. 

=========================================
SUBMISSION OF WORKSHOP EXTENDED ABSTRACTS
=========================================
If you would like to contribute, please send an abstract or extended 
summary to: 

    Marco Gori
    Facolta' di Ingegneria
    Universita' di Siena
    Via Roma, 56
    53100 Siena (Italy)
    Fax: +39 577 26.36.02

    Electronic submission:
    Send manuscripts in postscript format at
    marco at mcculloch.ing.unifi.it


Important Dates:

Submission of abstract deadline:         30 September, 1996 
Notification of acceptance:              21 October,   1996 
Final paper to be sent by:                4 November,  1996

For the format of papers, the usual NIPS style file should be used with 
up to 16 pages allowed. Workshop notes will be produced.

NIPS style files are available at
  http://www.cs.cmu.edu/afs/cs/project/cnbc/nips/formatting/nips.sty
  http://www.cs.cmu.edu/afs/cs/project/cnbc/nips/formatting/nips.tex
  http://www.cs.cmu.edu/afs/cs/project/cnbc/nips/formatting/nips.ps

Please contact the workshop organizers for further information, or consult 
the NIPS WWW home page:

http://www.cs.cmu.edu/afs/cs.cmu.edu/Web/Groups/NIPS/